Solutions to Interview Questions 2

This post provides the solutions/approaches to the problems provided by me in the Interview Problems 2.

If you have better approaches do share as comments.

Question 1: You are given 2 arrays of size ‘n’ each. You need to stable-merge these arrays such that in the new array sum of product of consecutive elements is maximized and the relative ordering of elements of A and B in C is not reversed.
eg
A= { 2, 1, 3}
B= { 3, 7, 9}
Stable merging A and B will give an array C with ’2n’ elements say C={c1, c2, c3, c4, c5, c6}
You need to find a new array C by merging (stable) A and B such that sum= c1*c2 + c3*c4 + c5* c6….. n terms is maximum.

Solution 1: A simple DP problem with the following recurrence
Condition : S[i+j-1] + max ( A[i] * A[i+1], A[i] * B[j], B[j]*B[j+1])
If in the above condition, the max is due to A[i]*A[i+1], then the merged array will have A[i] in (i+j)th place and A[i+1] at (i+j+1)th place and i will be i+=2, similarly if max is due to A[i]*B[j], then merged array will have A[i] in (i+j)th place and B[j] in (i+j+1)th place and same for the third one.
i is the index of the elements in A array and j in B array and S[i+j-1] is the max sum upto the current state.

A code is worth a million explanations, so here is it.

const int Max = 1000;
vector<int> a,b;
int n;

int memo[Max][Max];


int solve(int i,int j) {

   if(i == n) {
      int ret = 0;
      for (int k=j;k<n;k++) {
	 ret += b[k] * b[k+1];
	 ++k;
      }
      return ret;
   }
   if(j == n) {
      int ret = 0;
      for (int k = i; k < n; k++) {
	 ret += a[k] * a[k+1];
	 ++k;
      }
      return ret;
   }

   int&ret = memo[i][j];
   if(ret != -1) return ret;

   ret = -INF;
   // Three possibilities.
   // (i,i+1) ; (j,j+1) ; [(i,j) == (j,i)]
   if(i + 1 < n) {
      ret = max(ret, a[i] * a[i+1] + solve(i+2,j));
   }
   if(j + 1 < n) {
      ret = max(ret, b[j] * b[j+1] + solve(i,j+2));
   }
   ret = max(ret, a[i]*b[j] + solve(i+1,j+1));
   return ret;
}
int main() {


   scanf("%d",&n);
   a.resize(n); b.resize(n);

   for (int i=0;i<n;i++) scanf("%d",&a[i]);
   for (int i=0;i<n;i++) scanf("%d",&b[i]);

   memset(memo, -1, sizeof memo);
   printf("%d\n",solve(0,0));
   return 0;

}

Question 2: Write code for aligned malloc and free.
Solution 2: See The C programming Language by Brian Kernighan and Dennis Ritchie. It has the implementation of malloc and free. But for this question you will need to make an additional structure and record the actual starting address returned by the malloc call and you will return the aligned pointer. When the call to aligned_free is made, you only pass the recorded address as argument to the actual free function. [I’ll code this only on request :lazy]

Question 3: Our cell phones have T9 dictionary embedded for message writing…How this dictionary is implemented? State any other way to optimize complexity.Mechanism of Addition of new words in that dictionary.
Solution 3: See T9 Dictionary and the tutorial on the DS used is here, here and this is a tutorial on the best DS (optimized for better performance) used for this type of situation. [Tries and Compressed Tries]

Question 4: Given an array of integers(both positive and negative) divide the array into two parts(sub-arrays) such that the difference between the sum of elements in each array is minimum?
Solution 4: A simple interview problem on O(n) space and O(n) time 🙂

Question 5: Write a program to shuffle an pack of cards in the most efficient way.
Solution 5: Knuth Shuffle is the best.

Question 6: Sort an array of 0s, 1s and 2s in O(n) time and O(1) space.
Solution 6: Here is my code for the problem and this is a link shared by spsneo in the comments.

#include<stdio.h>

int main()
{
	int n, i;
	scanf("%d",&n);
	int arr[n];
	for (i=0;i<n;i++)
		scanf("%d",&arr[i]);
	int p_0 = 0, p_2 = n-1, p_1 = -1;
	while (p_1 < p_2 )
	{
		while (p_0 < p_2 && arr[p_0] == 0)
			p_0++;
		while (p_0 < p_2 && arr[p_2] == 2)
			p_2--;
		if (arr[p_0] == 2 || arr[p_2] == 0)
		{
			arr[p_0]^=arr[p_2]^=arr[p_0]^=arr[p_2];
			continue;
		}
		if (p_1 == -1 )
			p_1 = p_0 + 1;
		while (p_1 <= p_2 && arr[p_1] == 1 )  p_1++;
		if (p_1 > p_2)
			break;
		if ( arr[p_1] == 0 )
		{
			arr[p_1]^=arr[p_0]^=arr[p_1]^=arr[p_0];
			p_0++;
		}
		else if ( arr[p_1] == 2 )
		{
			arr[p_1]^=arr[p_2]^=arr[p_1]^=arr[p_2];
			p_2--;
		}
	}
	for (i=0;i<n;i++)
		printf("%d ",arr[i]);
	return 0;
}

Another trivial solution can be to just count the number of 0s,1s and 2s and create the array again.

Solutions to Interview Questions 1

Sorry guys for posting too late here … I have been in a dream world since I got accepted at Google, Bangalore. I have left my college campus and now am at home and will be updating the blog more than before :). Now I shall start posting solutions to the problems here ( some of them even I don’t know so will have to think over them 😛 ) and also will be looking and creating new problems.

This post provides the solution/approaches to solve the problems listed by me in Interview Questions 1.
The solutions here are derived through the comments section and by me. So please post any corrections or improvements.

Question 1 : Consider a binary tree, and listing of its nodes in the inorder traversal. Now write a function such that given any node in the tree it returns the next node that is visited by in the inorder traversal program.
E.g. if the is tree is like root – 1 has children 2, 3. 2 has children 4, 5. Then given 4, it should return 2 and given 5 it should return 1 etc.

Solution 1 [ given by spsneo in the comments] : If each node has a pointer to its parent, then it is easy-
1) The node is a leaf-node and it is the left child of its parent – its parent is the inorder successor
2) The node is a leaf-node and it is the right child of its parent – keep on going up till there is a node which is a left child of its parent, this parent is the inorder successor
3)The node has a right child – leftmost leaf of the subtree rooted at its right child.

Question 2 : Given an array of n numbers in which all the members are less than or equal to k (k<n). device an algorithm of order O(k) to find the first repeating element.

Solution 2: The order will be O(k) because the (k+1)th number will have to be a repeated one and it will be the solution in the worst case. So, the method is simply to remember the numbers ( < k) seen and mark the index corresponding to them as -ve. So, whenever you see a number, say i, it will be < k, and you mark the number at arr[i] as -arr[i]. If it is already a -ve number then it is the solution. Do this from arr[0] up till the solution condition is not met. In this case, the array can be acquired back, just negate the negative numbers, but still the array has to be modified. If it is not the case, then O(k) space will be needed.

Question 3: You r given a large string of characters lets call it Sbig. Then there is a small set of characters lets call it Ssmall. You have to find smallest substring of Sbig which contains all characters in Ssmall.
For example you are given Sbig = “hello what are you doing”
Ssmall= “eo”
answer is “ello”
Solution 3: The detailed solution to this problem is discussed in my post Programming Problem Solution 2.

Question 4: Given a positive integer having all unique digits. Find the immediate next greater number having the same digits.
Solution 4: Start from the one’s digit and move towards the left till the digits are in increasing order. When you find the nth digit (from left) is smaller than (n-1)th digit (from left), you stop here. The digits you have encountered till now, including the nth digit from left, will be sufficient for you to construct the next immediate largest number. If there is no (n+1)th digit, i.e. the number is like 875, then there is no solution, obviously :). Else, you can easily see that you only have to construct the next largest number by carefully rearranging the digits you selected in the previous step. So, replace the nth digit with the immediate larger of the (n-1) digits from left and then sort the remaining digits in ascending order and append it to the already constructed number. (It’s complex to explain here :P)
eg. 23471
nth = 4
n-1th = 7
the larger digit among 7 and 1 which is immediately larger than 4 is 7. So append 7 to 23.
The number till now is 237.
The digits remain 1,4. Sort them .. 14
Append it to 237
Resulting number 23714
Another Eg. 83496521
nth = 4
n-1th = 9
the larger digit among 9,6,5,2,1 which is immediately larger than 4 is 5. So append 5 to 83.
The number till now is 835
The digits remain 9,6,2,1,4. Sort them : 12469
Append it to existing number 83512469

Please post if any test case does not satisfy this.

Programming Problems 12

A few more questions which I dug up from my laptop :). I feel that people are taking interest in problems now so I’ll try to solve more problems and put them here or I’ll re-post the older problems. Enjoy 🙂

1. Given an integer array of length n, find 2 numbers which has maximum XOR.

2. Given a string and a array of smaller strings. Design a method to find out every occurence of smaller implementation in larger string.

3. A semi-connected graph is a graph that for each pair of vertices u,v, there is either a path from u to v or a path from v to u. Give an algorithm to test if a graph is semi-connected.

4. Suppose you have a tree. A binary tree (for something like simplicity :P). You are traversing it (using infix, postfix or prefix) to search for a node. You find your required node. You just realized that you need to know the path from this node back to the root node (and/or vice versa). Given the following description of the structure of the tree node that you “cant” change:

struct node
{
         Data data;
         node *right,*left;
};

To make it more intresting (or maybe just the application of the above problem) suppose you find the node A and a node B in consecutive searches. Now what will your strategy be to show a path from A to B. (not neccesarily from the root of the whole tree, but possibly).

5. Print a 2D Youngs Tableau (rows and columns sorted ) in sorted order in less than O(n^3).

6. Input : You have been given a sequence of integers.
Now without actually constructing BST from the given sequence of integers (assuming the sequence is pre-order) determine if each node of BST has single child (either left or right but not both).
Output : YES if given integer sequence corresponds to such a BST. otherwise say NO.

Ex. Say NO for 16,10,8,9,29,27,22.
Say YES for 10,19,17,14,15,16

%d bloggers like this: