Balance partition Input: give you a integer set {A[0]…A[n-1]}, 0 < A[i] < k, partition to two subsets S1 and S2, minimize |sum(S1)-sum(S2)|

Balance partition
Input: give you a integer set {A[0]…A[n-1]}, 0 < A[i] < k, partition to two subsets S1 and S2, minimize |sum(S1)-sum(S2)|
p(i,j)=1 means there is at least one subset in set i{A[0]…A[i-1]} has sum of j. i is from 0~n-1, j is from 0~(n-1)k
p(i,j)=0 means there is no subset in set i{A[0]…A[i-1]} has sum of j
so
p(i,j) =max{p(i-1,j),p(i-1,j-A[i])}
and define s=sum{A[0]…A[n-1]}/2
so minimize |sum(S1)-sum(S2)|= minimize |s-i:p(i,j)=1|

Longest increasing subsequence in array A[n]

Longest increasing subsequence in array A[n]
L(j)=max{L(i)}+1, where i < j and A[i] < A[j]
max_g=max{L(j)}
O(n^2)

int foo(int A[], int len)
{
int max_g=0;
int L[len];
for(int j=0;j < len;j++)
{
for(i=0; i < j; i++)
{
if(A[i] < A[j])
L[j]=max(L[j],L[i]+1);
}
max_g=max(max_g,L[j]);
}
return max_g;
}

Given 2 sorted arrays of n elements A,B. Find the k-th smallest element in the union of A and B in O(logk) time. You can assume that there are no dupl

Take each k elements from A and B, the kth smallest element is the median of the union of A and B. use binary search to find out median element.

int foo(int* a, int* b, int min_a, int max_a, int min_b, int max_b)//max_a=k, max_b=k
{
if(min_a+1==max_a&&min_b+1==max_b) //last 4 elements, return median of them
return median of a[],a[],b[],b[];
int mid_a=(min_a+max_a)/2;
int mid_b=ceil((min_b+max_b)/2);
if(a[mid_a]==b[mid_b]) return a[mid_a];//find median
if(a[mid_a]>b[mid_b])
return foo(a,b,min_a,mid_a,mid_b,max_b);//cut half
if(a[mid_a] < b[mid_b])
return foo(a,b,mid_a,max_a,min_b,mid_b);//cut half
}

let T be a heap sorting n keys. Give an efficient algorithm for reporting all the keys in T that are smaller than or equal to a given query key x (whi

let T be a heap sorting n keys. Give an efficient algorithm for reporting all the keys in T that are smaller than or equal to a given query key x (which is not necessarily in T). Keys do not need to be reported in sorted order. The algorithm should run in O(k) time where k is the number of keys reported.
p1 point to head, p2 points to tail

while(p1 < p2)
{
if(*p1 < =x&&*p2>=x) {p1++;p2--;}
if(*p1>x&&*p2 < x) {swap(*p1,*p2);p1++;p2--;}
if(*p1 < x&&*p2 < x) {p1++;}
if(*p1>x&&*p2>x) {p2--;}
}

Lets assume we have a rat maze as represented by the following NxM matrix where S is the start location and F is the end location. S 0 0 0

Lets assume we have a rat maze as represented by the following NxM matrix where S is the start location and F is the end location.
S 0 0 0 0 0
1 1 0 0 0 0
1 0 1 0 0 0
1 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
0 1 1 1 1 F
The idea (as with any rat maze) is to traverse from S to F. The matrix can have only 0 and 1 as values. 1 represents a path that can be taken and 0 represents a blocked path.
We can make the following assumption:
S will always be (0,0) and F will always be (N,M).
As seen from above, there can be many paths from S to F.
How do we find the shortest (or longest) path from S to F without actually traversing all the possible paths.
Please provide an optimized algo.....

Use A* search to find f(x)=g(x)+h(x)
Shortest path: iteratively get min(f(x))
Longest path: iteratively get max(f(x))

Given three sorted arrays, A, B, C, each of length n (assume odd), with all 3n elements distinct, find the median of the 3n elements.

Given three sorted arrays, A, B, C, each of length n (assume odd), with all 3n elements distinct, find the median of the 3n elements.

Iteratively find arrays having max median and min median of three arrays, then discard the max-end part of the max median array, and discard the min-end part of the min median array, the lengths of max/min end part are equal to half length of shorter one of max/min median arrays

You have a very large document, for an instance the document containing 1 million words. You are given a huge file, which contains list of 1 million w

You have a very large document, for an instance the document containing 1 million words. You are given a huge file, which contains list of 1 million words (includes multi-word strings). Give an algorithm/datastructure which returns the positions of the words/multiwords occurring in document which exist in the list given.

Example:
given document (which can be upto 1 million words):

I am xyz who did my bachelors from Aab Bbc Ccd Dde university. I like solving puzzles like Albert Einstein used to.

given list:

Albert Einstein
Abdul Kalam
Aab Bbc Ccd Dde
Massachusetts Institute of Technology
xyz
so no...upto million words

Result:
Word position:

3 (xyz)
9-12 (Aab Bbc Ccd Dde)
19-20 (Albert Einstein)
The basic idea is suffix tree, if the memory is not big enough, build the suffix array which is sorted, then sort the word list if it is unsorted, do the merge to two lists to find matching words
O(nlongn)

There are two sentences. Find the common words in the two sentences.

There are two sentences. Find the common words in the two sentences.

using suffix trees or suffix array based on words (find common sub-sentences )
use hash table
sort two sentences and merge

You have a billion urls, where each has a huge page. How do you detect the duplicate documents?

You have a billion urls, where each has a huge page. How do you detect the duplicate documents?

Suggest a cryptographic hash function, SHA1 or MD5. They are expensive but very good hash function.

KD tree search

Given a set of points (x,y) on a 2D coord system, identify list of 2D coords that are of distance less than x units long.
Eg.
Let x = 1;
Given (0,0), (0,1), (1, 2), (4,6);
Return 1 -> (0,0), (0,1)
Build the kd tree, use the range where the radius is unit long originated from anyone point to search on the kd tree, get a subset of points. Do the iteratively search on the subset…

matrix string match

Given a puzzle of letters/ characters e.g.
a e r o p s
b h a r l s
w r i s l o
a s n k t q
Write a function to which this puzzle and a word will be passed to test whether that word exists in the puzzle or not.
e.g. rain and slow will return true. rain is present in the second column and slow in the third row wrapped around.
Find the signature (sorting by alphabet) for each row and each column, put them on the hashtable where the key is signature and the value is corresponding row or column O(n*n)
Get signature of input string and look up the hashtable O(1)
After we locate the row or column, we can do the string match on the row/column with input string O(n)

convert a fully paranthesized, arithmetic expression to a binary tree

convert a fully paranthesized, arithmetic expression to a binary tree
1) Convert the infix expression to postfix expression
e.g. (a+b)*c = ab+c* ( you can get the standard infix to postfix algos )
2) Then use a stack to build the tree
Algo:
1)check the current char
i)if its a operand make a tree node with data as the char and put it in the stack
ii) if its an operator make a node with data as the operator. pop 2 elements from the stack(these has to be operand as we use postfix expr). make them the children of the current node. Push the current node back on the stack
2) if the input is over pop the content of the stack .... it is the root of the binary expression tree

partition the array

let T be a heap sorting n keys. Give an efficient algorithm for reporting all the keys in T that are smaller than or equal to a given quary key x (which is not necessarily in T). Keys do not need to be reported in sorted order. The algorithm should run in O(k) time where k is the number of keys reported.
p1 point to head, p2 points to tail
while(p1< p2)
{
if(*p1< k&&*p2>k) {p1++;p2--;}
if(*p1>k&&*p2< k) {swap(*p1,*p2);p1++;p2--;}
if(*p1< k&&*p2< k) {p1++;}
if(*p1>k&&*p2>k) {p2--;}
}

How to determine if there is a cycle in the graph

How to determine if there is a cycle in the graph
If the graph is undirected Bfs + hashtable (bitvector)
If the graph is directed, dfs the tree and each node has a visited value, where 0 is unvisited, 1 is visiting or 2 is finished, you can see clrs p458

Given a m*n array only containing 0s and 1s, some blocks in the array are occupied by all 1s, find the maximum square which does not cross these block

Given a m*n array only containing 0s and 1s, some blocks in the array are occupied by all 1s, find the maximum square which does not cross these blocks
row[i][j] counts the contiguous 0s from array[i][j] to left boundary
col[i][j] counts the contiguous 0s from array[i][j] to up boundary
sqr[i][j] counts the length of maximum all 0s square which takes array[i][j] as right-down corner
for(int i=0;i < m;i++)
for(int j=0;j < n;j++)
sqr[i][j]=min{sqr[i-1][j-1]+1,row[i][j],col[i][j]}
sqr[0][j]=1-array[0][j], j=1…N
sqr[i][0]=1-array[i][0],i=1…M

Given n pairs of parentheses. Write a program to print out all valid configrations. For example n=2, ()(), (()) are valid, but ))((, ())( are not.

Given n pairs of parentheses. Write a program to print out all valid configrations.
For example n=2, ()(), (()) are valid, but ))((, ())( are not.
foo(stack s, int count, int len)
{
if(count<0)
return ;
if(len==0)
{
if(count==0)
print s;
else return;
}
foo(s.push('('),count+1,len-1);
foo(s.push(')'),count-1.len-1);
}

mouse and maze

give you a maze. and drop a mouse in the maze randomly, and place a piece of cheese randomly. the mouse can move 4 directions
up down left right
There are some walls on the way to block certain directions for certain position.
design an algorithm for the mouse to find the cheese.
note, the mouse does not know where he is, and where the cheese is. he cannot find x,y for the position he is right now.
for instance
X X B
D X D
A X X
D is the block with walls on 4 sides.
If the mouse reaches the end of row or column, it gets the dead end.
Mouse is A, cheese is B. how to find the cheese.
Use dfs, and one stack and one hash table
Dfs traverse the maze, use stack to record the path, and hash table to record visited nodes

I have a 32 bit unsigned int and I have to check the lowest set bit in that. I can check linearly i.e. staring from lowest bit to highest, but I was w

I have a 32 bit unsigned int and I have to check the lowest set bit in that. I can check linearly i.e. staring from lowest bit to highest, but I was wondering whether there is any better way.
Why do not we adopt a binary search kind of option? Mask the lower half of the bit pattern with a mask like 0XFF if it is non-zero then do binary search repeatedly else look at the other half.

Two reverse sorted arrays A and B have been given. such that size of A is m and size of B is n You need to find the k th largest sum (a+b) where a is

Two reverse sorted arrays A and B have been given.
such that size of A is m and size of B is n
You need to find the k th largest sum (a+b) where a is taken from A and b is taken from B. such that k < m*n
It can be done in O(n*n) but it can also be done in really optimal way.
a[m]+b[n]>a[m-1]+b[n]>a[m-1]+b[n-1]
a[m]+b[n]>a[m]+b[n-1]>a[m-1]+b[n-1]
so a[m]+b[n] has two children a[m-1]+b[n] and a[m]+b[n-1]
typedef struct node
{
int val;
int idx1;
int idx2;
}N;
void foo(int* a, int* b, int lena, int lenb, int k)
{
int c=1;
priority_queue pq;
pq.push(a[m]+b[n],m,n);
while(!q.empty())
{
N t=pq.pop();
c++;
if(c==k)
print(t.m,t.n);
pq.push(a[t.m-1]+b[t.n],t.m-1,t.n);
pq.push(a[t.m]+b[t.n-1],t.m,t.n-1);
}
}

Sort the array representation of a complete binary search tree in O(n) time complexity and by using constant space.

Sort the array representation of a complete binary search tree in O(n) time complexity and by using constant space.
The array is partially sorted by the length of 2^n(n>=0), so a merge sort can do this in O(n) time and O(n) space