[Algorithm] Basic Calculator

Basic Calculator:

Problem Statement

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Solution 1: Iterative Approach

Let's first examine the iterative way of solving this problem. Typically, we need to involve a scope stack which is quite a common technique in iterative approach. The rule is simple, we define scope as sub-expression surrounded by "(" and ")". Whenever we meet a "(" we push the scope, whenever we meet a ")" we pop the scope.

And inside each sub-expression we follow the post operation rule, meaning that we can view the expression as post polish notation, namely "x + y" is "x y +". We don't need to literally change it to post notation, we can evaluate expression in that fashion. What do I mean by saying this, this means:

1) If we are looking at an operator: Calculate the previous pending operation and save the current operator as pending operator, the left operand is the previous operation's result.

2) If we are at the end of sub-expression: Calculate the previous pending operation and we have the final result.

The pending operation is modeled as left operand and operator, and we keep right operand on the side as we go along the expression.

When we meet a ")" we are done with this scope, we compute the pending operation and save the current result as right operand, pop the scope and move on.

Keep in mind:

1) We use a scope stack to manage sub-expression defined by "(" and ")".

2) We keep the left operand and operator only, we always calculate to maintain this.

3) Right operand can be number we read from string or number carried from i+1 scope to i scope

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

class Solution { struct Node { Node() : value(0), op('+') {}; inline void calculate(long long v) { value = (op == '+') ? value + v : value - v; } long long value; char op; }; public: int calculate(string s) { vector<Node> stack; if (s.empty()) return 0; stack.push_back(Node()); long long rightOperand = 0; bool hasNum = false; for (int i=0; i<s.size(); i++) { if (s[i] == ' ') continue; if (s[i] == '(') { stack.push_back(Node()); continue; } if (s[i] == ')') { if (hasNum) stack.back().calculate(rightOperand); rightOperand = stack.back().value; hasNum = true; stack.pop_back(); continue; } /* when meeting an operator compute the previous value */ if (s[i] == '+' || s[i] == '-') { stack.back().calculate(rightOperand); stack.back().op = s[i]; rightOperand = 0; hasNum = false; continue; } hasNum = true; rightOperand *= 10; rightOperand += (s[i] - '0'); } if (hasNum) { stack.back().calculate(rightOperand); } return stack.back().value; } };

Solution 2: Recursive Approach

Recursive approach is kind of similar except that it uses program stack as its scope stack. When we meet a "(" we call recursion, evaluate the sub-expression and return back when we have met an ")".

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

class Solution { public: int calculate(string s) { int next = 1; return helper(s, 0, s.size(), next); } inline int helper(const string& str, int s, int n, int& next) { int sum = 0; int op = 1; for (int i=s; i<n; i++) { if (str[i] == ' ') { continue; } if (str[i] == '+' || str[i] == '-') { op = (str[i] == '+') ? 1 : -1; continue; } if (str[i] == '(') { sum += op * helper(str, i+1, n, i); continue; } if (str[i] == ')') { next = i; return sum; } int j = 0; int num = 0; while(isdigit(str[i+j])) { num *= 10; num += str[i+j] - '0'; j++; } i = i+j-1; sum += op * num; } return sum; } };

[Algorithm] Largest Divisible Subset

Largest Divisible Subset

Problem Statment

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj% Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

nums: [1,2,3]

Result: [1,2] (of course, [1,3] will also be ok)

Example 2:

nums: [1,2,4,8]

Result: [1,2,4,8]

Solution: Dynamic Programming & Sorting

Let's first look at the following equations:

Given that nums[i] > nums[j] > nums[k], if:

nums[i] % nums[j] == 0 and nums[j] % nums[k] == 0, then

nums[i] % nums[k] == 0 must also be true.

So let the state dp[j] of nums[j] be the count of divisible numbers less or equal to nums[j], and given nums[j] > nums[i] and nums[j] % nums[i] == 0, we can have dp[i] = dp[j] + 1. And we can keep track of the longest length of divisible subset.

The problem wants us to find out the full sequence, so when never we update dp[i] we shall keep track of the index j which leads to this index i. And when we are worst-casing the length, we need to keep track of the ending index i.

To get the full sequence, we simply backtrace from ending index back to the beginning of this sequence.

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

class Solution { public: vector<int> largestDivisibleSubset(vector<int>& nums) { if (nums.size() < 2) return nums; sort(nums.begin(), nums.end()); int n = nums.size(); vector<int> dp(n, 1); vector<int> backtrace(n, -1); int endIdx = 0; for (int i=0; i<n; i++) { for (int j=0; j<i; j++) { if (nums[i] % nums[j] != 0) continue; if (dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; backtrace[i] = j; if (dp[i] > dp[endIdx]) { endIdx = i; } } } } vector<int> result; while (endIdx != -1) { result.push_back(nums[endIdx]); endIdx = backtrace[endIdx]; } return result; } };

[Algorithm] Longest Valid Parentheses

Longest Valid Parentheses

Problem Statement:

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Solution: Dynamic Programming

This problem can be solved with DP. We will have 1D array as our bookkeeping for the maximum length of valid parentheses so far.

We keep the maximum length of valid parentheses ending with ")" at ")".  If the character right before this ")" is a "(" we let dp[i] = dp[i-1] + 2. If the character right before this ")" is a "(" we need to trace back dp[i-1] number of characters (let prev = i - dp[i-1] - 1) to see if it is a unmatched "(" so we let dp[i] = (i - prev + 1) + dp[prev]

To keep this equation valid, for "(", we keep either 1) the previous sequence length prior to this "(" if there's a ")" right before it or 2) 0 if there's a ")" right before it. This is important because we need to stitch two valid sequences together to make a longer valid sequence if there's a ")(" sequence encountered.

To better explain why we are keeping the length this way let's consider these cases:


Case 1: "()()"

Our DP algorithm will have:

1 2 3

char: | ( | ) | ( | ) | index: | 0 | 1 | 2 | 3 | subLen: | 0 | 2 | 2 | 4 |

The two valid subsequences will be stitched together by dp[i] = dp[i-1] + 2, since we keep the previous subsequence length at "(" if there's a ")" right before that "(".


Case 2: "()((()))"

We have:

1 2 3

char: | ( | ) | ( | ( | ( | ) | ) | ) | index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | subLen: | 0 | 2 | 2 | 0 | 0 | 2 | 4 | 8 |

When we are looking at the 7th character ")", we notice this time we have a ")" at index 6, so we need to trace back to character at index 2 (7 - dp[6] - 1 = 7 - 4 - 1 = 2). We have a "(" at index 2 which is unmatched and can be matched with ")" at index 7, so dp[7] = 7 - 2 + 1 + dp[2] = 8.

Case 3: "())((()))"

We have:

1 2 3

char: | ( | ) | ) | ( | ( | ( | ) | ) | ) | index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | subLen: | 0 | 2 | 0 | 0 | 0 | 0 | 2 | 4 | 6 |

The ")" at index 2 does not match any open "(" so dp[2] = 0. "(" at index 3 will have the previous sequence length which is dp[3] = dp[2] = 0. So when we traceback to index 3 and we make dp[8] = 8 - 3 + 1 = 6.

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

class Solution { public: int longestValidParentheses(string s) { vector<int> board(s.size(), 0); int maxLen = 0; for (int i=1; i<s.size(); i++) { if (s[i] == '(' && s[i-1] == ')') { // case 1, "()()" board[i] = board[i-1]; } if (s[i] == ')') { if (s[i-1] == ')') { // case 2, "((()))" int prev = i - board[i-1] - 1; if (prev >= 0 && s[prev] == '(') { board[i] = (i - prev + 1) + board[prev]; } } else { // case 2, inner "()" only board[i] = board[i-1] + 2; } maxLen = max(maxLen, board[i]); } } return maxLen; } };

[Algorithm] Find Minimum in Rotated Sorted Array

[Algorithm]Find Minimum in Rotated Sorted Array

Problem statement

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Solution 

There is only one pivot point in this array. So for each subarray [lhs, rhs], consider following situation -

1. nums[lhs] < nums[rhs] - the pivot point must be outside of this subarray, the minimum value should be nums[lhs].

2. If nums[lhs] > nums[rhs] - the pivot point must be inside this array. Then take the middle element ( mid = lhs + (rhs-lhs)/2 ). The minimum should be the pivot point number.

• nums[mid] >= nums[lhs] - pivot point must be in the second half, then we shift the scope to be [mid+1, rhs]
• Num[mid] < nums[lhs] - pivot point must be in the first half, then we shift the scope to be [lhs, mid] 

Code Implementation

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: int findMin(vector<int>& nums) { int lhs = 0; int rhs = nums.size()-1; while (lhs < rhs) { if (lhs == rhs-1) return std::min(nums[lhs], nums[rhs]); int mid = (lhs + rhs) / 2; if (nums[mid] < nums[rhs]) { rhs = mid; } else { lhs = mid+1; } } return nums[lhs]; } };

[DevNote] Morphia Example with Spring Framework

full code example is available on GitHub

This is part of my note on Morphia with Spring MVC. I will try to demonstrate in this blog how to setup Morphia with Spring MVC Framework.

There are multiple flavors when it comes to ODM (object document mapper) for MongoDB, there's Jongo, Morphia, Spring Data, Hibernate OGM and etc,. Different applications may have different needs. I've tried with some personally and I feel like Morphia and Spring Data are more mature and relatively easy to use.

Particularly we are looking at Morphia in this blog. We are going to use Spring as our application framework, Morphia as our ODM and DB access layer, JUnit as our testing tool to verify configuration and test our DB access layer, and we are going to use a little bit of Spring Data also to perform drop_collection actions.

1. Setting up your project.

We are using Maven as our project management tool and to use Morphia and Spring MVC you will need some dependencies added for them.

Spring property:

1 2 3 4 5 6 7 8 9

<parent> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-parent</artifactId> <version>1.3.5.RELEASE</version> </parent> <properties> <java.version>1.8</java.version> </properties>

Dependency for Morphia:

1 2 3 4 5

<dependency> <groupId>org.mongodb.morphia</groupId> <artifactId>morphia</artifactId> <version>1.0.0-rc0</version> </dependency>

Dependency for JUnit:

1 2 3 4 5

<dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-test</artifactId> <scope>test</scope> </dependency>

Dependency for Spring Data:

1 2 3 4

<dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-data-mongodb</artifactId> </dependency>

These dependencies are required for our example application and there's nothing special to explain really.

2. Configuration

There are two ways of configuring a Spring application. One is via XML property file, while the other is through Java annotation.

I prefer Java annotation as the configuration since it's more type-safe, typo-safe compared to XML property file. One can capture any typo occurred or any unsuitable types immediately.

Here's the configuration of our application.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

@Configuration public class DatabaseConfiguration { private static final String host = "127.0.0.1"; private static final String port = "27017"; private static final String dbname = "morphiaTest"; public @Bean MongoClient mongoClient() throws UnknownHostException { return (new MongoClient(host+":"+port)); } @Bean public Datastore datastore() throws UnknownHostException { Morphia morphia = new Morphia(); morphia.mapPackage("com.hackinghorse.morphiamongoexample.model"); Datastore datastore = morphia.createDatastore(mongoClient(), dbname); datastore.ensureIndexes(); return datastore; } public @Bean MongoDbFactory mongoDbFactory() throws UnknownHostException { return new SimpleMongoDbFactory(mongoClient(), dbname); } public @Bean MongoTemplate mongoTemplate() throws UnknownHostException { MongoTemplate mongoTemplate = new MongoTemplate(mongoDbFactory()); return mongoTemplate; } }

@Configuration annotation is provided by Spring and this tells Spring to process this class since it will contain multiple @Bean methods which will be added to the Spring container. This is not necessary for this project since we can specify our configuration in JUnit test class, this I will demonstrate later.

This configuration class defines multiple beans we are going to use. @Bean annotation tells Spring that a method annotated with @Bean will produce a bean which needs to be managed by Spring container.

A Spring bean is actually an Singleton object managed by spring container. We can retrieve the bean through ApplicationContext interface or through @Autowired annotation which will search and match the bean according to their name and type.

Note that inside this function a @Bean method is calling another @Bean method within the same class, for example we are calling mongoClient() method inside datastore() method. Spring ensures that references between beans are strongly typed and navigable and when a @Bean method is being called/referenced the @Bean method being called/referenced is guaranteed to return the same bean as it would for other places.

Also note that if we are intended to reference @Bean methods among each other within the same class, the @Configuration class and its factory methods should not be final or private.

The datastore() bean method is going to create a Morphia Datastore object. The Datastore object will provide all the interfaces we need to access, manipulate the MongoDB.

mongoTemplate() bean method is required for Spring Data. The reason to add this is that there seems to be no API in Morphia that can drop the whole collection, so I used this MongoTemplate as a shortcut of cleaning up our datastore after each run of our application. MongoTemplate provides remove() interface which will provide drop collection capability.

3. Model

Data model is usually POJO classes with annotation provided by the ODM vendor. In our case we are using Morphia annotations for data model.

Java code for data model of Customer.java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

@Entity(value="customers") public class Customer { @Id private ObjectId id; private String firstName; private String lastName; private String created; @Reference private Group group; //--------getter/setter--------- }

The setters and getters are not shown, they are just boilerplate code.

@Entity annotation is going to tell Morphia that this class is a model for a Mongo document. The value specified in the annotation defines the name of the collection.

@Id annotation specifies the id member field in the model, this will be automatically populated by Morphia once saved into database. By default it is using the default mongo _id format.

@Reference here models a one-to-one relationship between another model Group. In stead of going with embedded, we choose to use normalized data which uses reference. (There's no specific reason for using this to model them, just what to demonstrate @Reference)

We have another data model Group.java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

@Entity(value = "groups") public class Group { @Id private ObjectId id; @Indexed(value = IndexDirection.ASC, unique = true, dropDups = true) private String groupId; private String groupName; @Reference List<Customer> customers; //------- setters/getters ------ }

In Group.java, we have a one-to-many relationship with @Reference annotated. There's also an @Indexed annotation which models a indexed field. By default MongoDB indexes on _id field and user can opt to use any field as the index. Here we are using groupId as our index field and we order them by ascending order with "value=IndexDirection.ASC" and make sure they are unique with "unique=true". We also opt to drop duplicates, so keep in mind that when we do save() with Datastore API we can get an DuplicateKeysException.

4. Test

(Will post later...)