Coding Dragon

Coding, puppies, places and food

[codingdragon]

Longest 2 character substring

Given a string find the longest substring that has only 2 characters.

Solution: This problem is extension of the problem where given a string we have to find the longest substring that has only one character. For finding the longest single character substring, we keep 2 variables one to keep track of longest substring so far and other to count the frequency of current longest substring candidate. Similarly to find the longest 2 character substring we keep 3 variables, two to keep track of longest substring so far and current candidate like the single character problem, the third variable is used to track the frequency of last character. Following c++ implementation is self explanatory:

https://gist.github.com/nirvana-attained/7433191

Analysis: Worst case time complexity is O(n) when n is the length of string. Space complexity is O(1).

[codingdragon]

Balanced partition

You have a set of n integers each in the range 0 ... K. Partition these integers into two subsets such that you minimize |S1 - S2|, where S1 and S2 denote the sums of the elements in each of the two subsets.

Solution: Let's say S denotes the sum of all the numbers in the set of n integers. The lowest possible value of |S1-S2| is zero, which is obtained when S1 is equal to S/2. Thus this problem reduces to a problem where we have to find a subset of numbers whose sum is closest to S/2. Let's say the sorted input array/set is denotes by V[1].......V[n] and M[i][j] is true when it's possible to obtain a sum of j using array elements from V[1] to V[i]. M[i][j] = True when  => i equals j because we have a subset {V[i]} that can produce a sum of j. => M[i][j-V[i]] is true, because in this case we can obtain a sum of j simply by adding V[i] to the subset that produces a sum of j-V[i]. => M[i-1][j] is true, because in this case it's possible to get a sum of j by using elements to the left of V[i] so we don't have to add anything to the subset from the left. Otherwise, M[i][j] = False where j varies from 1 to S/2. After we have populated the matrix M, we need to explore it to find the highest value of j for which M[i][j] is true, that value of j is the value of S1. S2= S-S1. C++ implementation follows

https://gist.github.com/nirvana-attained/bac6b1c756402ceb595f

Analysis: Worst case time complexity is O(n*S) where n is the number of elements in the set and S sum of all elements. This is deduced as: O(n*logn) for sorting + O(n*S/2) for populating the matrix + O(n*S/2) for exploring the matrix = O(n*S). Space complexity is also O(n*S).

[codingdragon]

Optimal Strategy for a Game

Consider a row of n coins of values V1 . . . Vn, where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first. Solution: Let's say at some stage of the game, the sequence of coins is Vi,Vi+1.....Vj-1,Vj and it's player A's turn. Now player A can either pick Vi or Vj. Also assume M[i][j] is the maximum sum that a player can obtain for this sequence of coins.

Case 1: He picks Vi. Now Player B will either pick Vi+1 or Vj. Since player Bd is equally smart he'll choose the coin that will lead to minimum sum for player A. So M[i][j] = Vi+Minimum(M[i+2][j], M[i+1][j-1]) Case 2: He picks Vj. Now Player B will either pick Vi or Vj-1. Similar to case 1 M[i][j] = Vj+Minimum(M[i+1][j-1], M[i][j-2]) But hey! Player is very smart, he'll choose the value of M[i][j] that yields maximum amount. So M[i][j] = Maximum( Vi+Minimum(M[i+2][j], M[i+1][j-1]),  Vj+Minimum(M[i+1][j-1], M[i][j-2]) ) This is a recurrence relation that could be used to obtain the maximum amount money. I use dynamic programming to get the result optimally. C++ implementation follows:

https://gist.github.com/nirvana-attained/7280435

Analysis: Worst case time complexity is O(n^2) and space complexity is also O(n^2) where n is the number of coins.

Observation: For even number of coins, if both the players play optimally the player who'll make the first move is guaranteed to not loose. Proof: Assume the following arrangement of coins, notice the positions marked 0 and positions marked 1: V1 V2 V3 V4...V2n-1 V2n 0    1  0   1 ...  0        1 If I make the first move I can easily force the second player to pick all the coins at 0 positions or all the coins at 1 positions. If Summation of all the coins at position 0 is greater than those at position 1, I'd force the second player to pick all the coins at position 1 and vice versa. This is one strategy that guarantees a Win or Draw (draw occurs when sum of 0 coins is same as sum of 1 coins) outcome for me. Now this strategy is an ad-hoc strategy and not better than the dynamic programming strategy discussed above. This means the dynamic programming strategy is at least as good as this ad-hoc strategy. Hence dynamic programming strategy will ensure no loss for the player who makes the first move with even number of coins.

[codingdragon]

Set of Stack data structure with threshold

Problem:

Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks push() and SetOfStacks pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack). 

Solution:

I use a vector of stacks for implementing this data structure. During push I make sure size of individual stacks doesn't exceed the threshold and during pop I make sure empty stacks are erased from the vector. C++ implementation follows:

https://gist.github.com/nirvana-attained/7197052

[codingdragon]

Rotate matrix by 90 degrees

Given a N X N matrix, rotate it by 90 degrees clockwise (or counter-clockwise). For example:

Input = [1, 2, 3] [4, 5, 6] [7, 8, 9]

output (clockwise rotation) = [7, 4, 1] [8, 5, 2] [9 ,6, 3]

Solution: If we look closely at the output matrix, we could notice that all the rows in input matrix have become a column in the output matrix and vice versa. That means taking the transpose matrix of input matrix might help. Transpose for sample input = [1, 4, 7] [2, 5, 8] [5, 6, 9]

Now, if we look closely at the transpose matrix and compare it with the output matrix very carefully, we could notice that 90 degree clockwise rotation could be obtained simply by reversing all the rows of the transpose matrix and similarly counter clockwise rotation could be obtained by reversing all the columns. This works for any N X M matrix.

C++ implementation (tailored for N X N matrix) follows:

https://gist.github.com/nirvana-attained/7157733

Above code could be easily generalized for N X M matrix, by passing an input matrix that has dimensions Max(N, M) X Max(N, M) and, N and M as parameters to the Rotate function.

Worst case time complexity is O(n*n) whereas the space complexity is O(1).

[codingdragon]

Find a key in circularly shifted sorted array

Given an integer array sorted in ascending order and circularly shifted left an arbitrary number of times, find the position of a given key in the array. e.g. find position of 1 in {9,12,-5,0,1,4}; (Note: this array has been left shifted 4 times)

Following solution is a modified version of binary search algorithm:

https://gist.github.com/7143339

To understand this algorithm, let's assume the input array is circularly shifted 0 times and first element in this array is denoted by F. Now if the array is circularly shifted left arbitrary number of times, let's assume M denotes the new middle element and L denotes the new last element. Now only two cases arise:

F is to the left of M (current middle element) which implies everything to the right of M is sorted and based on the value of key we can accurately predict if the key is present in the right half in constant time. Thus we can reject either the left half or the right half.

F is to the right of M which implies that everything to the left of M is sorted and similar to case 1, we can reject a half of the array.

You might be wondering how do I determine whether F is to the left of M or not (because you don't know the position of F in shifter array)? The answer is, if M is smaller than L that means F is to the left otherwise F is to the right of M.  

Needless to say the worst case time complexity is O(logn) where n is the number of elements in the array because we are rejecting a half of the array in every step. Space complexity is O(1).

[codingdragon]

Longest common prefix for n strings

A very common coding interview question, the problem here is to find the longest common prefix string for a given set of strings. For example, for input = "slow", "sloppy", "sloth", output is 3 or "slo".

Solution: Match characters at ith index in all the strings of the input set where i varies from 0 to the length of smallest string minus 1. Whenever there is a mismatch terminate the function. C++ code follows:

https://gist.github.com/7134968

Analysis: This code runs in O(|S|*n) worst case time where |S| is the average string length and n is the number of strings. Space complexity is O(1).

Alternatively, create a trie of all the strings and find the first node from the root that has zero or more than 1 children. The number of nodes between root and this node is the length of LCP.