## Interview Questions 8

Some more nice problems collected from Antonio Gulli’s Coding Playground

1. Find the longest common subsequence of given N strings each having length between 0 to M.

2. Partition a set of numbers into two sets such that the difference between their sum is mininum and they have equal num of elements.

3. Given a bst of n nodes, find two nodes whose sum is equal to a number k in O(n) time and constant space

4. We have N element array with k distinct keys. sort this array without using any extra memory.

5. You buy a newspaper and notice that page 8 and 21 are on the same sheet. Can you infer the total number of pages in the newspaper?

6. Given two sorted postive integer arrays A(n) and B(n) (let’s say they are decreasingly sorted), we define a set S = {(a,b) | a \in A and b \in B}. Obviously there are n^2 elements in S. The value of such a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs from S with largest values. in O(n).

## 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”
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.

## Funny SMS 1 – ADULT :P

All of us (guys) get a shit-load of funny SMSs everyday … me too … I just now start to accumulate them and post them here ..

• Light chale jaane pe logon ka reaction : U.K. – Oh No!, U.S.A. – What is this !, Pakistan – Batti Chali gayi & U.P. – Lo fir maiyya chudwa li is Mayawati ne .. !
• Garmi aa chuki hai, kripya apni girlfrnd k bra me barf k tukde rakhiye, kyuki garmi me doodh fat sakta hai. Purush kalyan samiti ki taraf se janhit mein jaari
• [TRUE ONE] 1 bacha paida hote hi nurse se poochta hai – LIGHT hai kya ?? ; Nurse: No ; Bacha: Oh Shit!!  fir se M.P. mein paida ho gaya .. 😦
• Mickey Mouse comes home and says to Minnie Mouse ” I want a divorce!”, Minnie Mouse: “Are u fucking crazy??!”; Mickey Mouse: ” No, these days I’m fucking Daisy !!”
• Call girl to old man- “Uncle lund sidha chut mein daalo, neeche slip hoke gand mein jaa rha hai” ; Old man: “Jane de.. madarchod ki kismat mein hi goo khana likha hai”
• “I luv walking in the rain bcoz nobdy knows I’m crying” is OLD now !!!, Now latest is ” I luv walking in the FOG bcoz no1 can find I’m SMOKING!!”
• “Main India chhod ke jaa rha hun, Kyuki Katrina pregnant hai or log mujhpe shak kar rhe hain.. Tu bhi nikal le .. suna hai uski kaamwaali bhi pregnant hai .. airport pe milte hain ” 😛
• Arz kiya hai .. Mohabbat k naam pe saza maine payi hai…Gaur farmaiye.. Mohabbat k naam pe saza maine payi hai … baaki ka sher baad mein padhunga .. abhi zor se potty aayi hai 😛
• Sholay ki team ne IPL mein part liya.. Gabbar k bowlers ne 20 overs mein 250 run de diye jinme 200 extra run the … btao kyu ???????? ……………… Qki wicket keeper Thakur tha 😀
• Zindagi aapko muh se lekar gand tak sukh samriddhi de, Koi bhosdika aapki jhant ka baal na ukhad sake. Aap safalta ki aisi maa chodo ki khushiyo se aapki gand fat jaye ..
• Dost mere ..marne k baad mera janaaza uski gali mein ghuma dena … Agar vo dikh jaye to ek baar mera nikaal k HILA DENA ..
• “1 scientist BRA banana chahta tha jisme running krte hue girls ke boobs na hile aur bheegne par nipple na dikhe … .. Tension mat le bhai .. mar diya madarchod ko ”  .. 😛

Disclaimer: Copy, paste and distribute … Everything Open Source 😛