Solutions to Google Top Interview Puzzles

To start with,we are posting solutions to some of the questions.In due course of time ,all the questions shall be solved.


1.There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].

Solve it without division operator and in O(n).


Solution:At each position i,we need to assign A[i], the product of all the elements in the array except A[i].This amounts to same as putting A[i]=a*b,where a=cumulative product of all those elements to the left of A[i] and b=cumulative product of all those elements to the right of A[i].

We can put this simply by storing the result in a separate array and by traversing the input array twice.

In the first iteration, we traverse the input array left to right and assign Output[i]=a (where a is the product of all the numbers preceding A[i]).

Now we traverse the input array again ,but in reverse direction and this time we find
b(here b is the product of all the numbers following A[i]) and Assign

Output[i]=Output[i]*b; which amounts to putting Output[i]=a*b

Hence Each Output[i] contains the product of all the elements in A except A[i].

Below is a C function to do the same.


int* function(int input[],int size,int output[])
{
long int result=1;
for(int i=0;i<size;i++)
{
output[i]=result;
result*=input[i];
}
result=1;
for(int i=size-1;i>=0;i--)
{
output[i]*=result;
result*=input[i];
}
return output;
}


Click here for the questions

2.There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.

Hint:

1. Use random function rand() (returns a number between 0 and 1) and irand()
(return either 0 or 1)
2. It should be done in O(n).


Solution:Traverse the list, generating a new random number for each entry. Keep a ‘top k’ chart of the highest random numbers, and their associated entries. When we hit the end of the list, the numbers in the chart are the required random numbers.

This random number generated for each element can be defined as a function f=absolute(irand()-rand()),which is random enough.

Click here for the questions

3 Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M >> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm

Solution:This problem can be solved using bitmaps.bitmap will be an array (say b_array) where we have one bit per M possible number. If we use a character array to store bitmaps, b_array size will be M/8, since 1 char can store 8 bits. Bitmap array will be initialized to zero first. Now for each of the N numbers its corresponding bit should be turned on(1). Corresponding bit for 'n' can be found as follows:

base = n/8; (base is the char whose certain bit needs to be set)

offset = 1 << (n mod 8); (offset is the bit to be set)

b_array[base] |= offset; (I set the particular bit)

Once this is done of all N numbers, given a number m,
we can first find corresponding bit offset and check whether it is one.

base = m/8; (base is the char whose certain bit needs to be set)

offset = 1 << (m mod 8); (offset is the bit to be set)

if (b_array[base] & offset)
// found the number
else
//number could not be found

*Any other solutions will be appreciated.

5)You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*...*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed.

Solution:Please refer to Question1.This question is identical to the first one,except that it is made to look much harder.

Click here for the questions


6 How do you put a Binary Search Tree in an array in a efficient manner.


Hint :: If the node is stored at the ith position and its children are at
2i and 2i+1(I mean level order wise)Its not the most efficient way.



Solution:The method of construction given in Hint though looks good at a mere glance,it has too many shortcomings.Exponential memory is required at the worst case.

The solution is maintain inorder and one of the other 2 traversals of the tree.These 2 are sufficient to construct back the tree.So the space requirement now is 2N i.e O(N)

Click here for the questions

7. How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.
Note :: You should not use use any extra space. i.e sorting Binary Search Tree
and storing the results in an array and listing out the fifth element.


Solution:

int num=0;
void max(tree*t)
{
if(t==NULL)
return;
max(t->right);
num++;
if(num==5)
printf("%d\n",t->no);
max(t->left);
}


Click here for the questions

8.Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 ... iN c1 c2 c3 ... cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 ... in cn


Solution:we divide the array in four sections:[X,Y|A,B]
It is easy to see that with swaps we can modify it to the form [X,A|Y,B].
Now do recursion to solve [X|A] and [Y|B] separately,essentially using divide and conquer.[as given in comments section]

Click here for the questions

9.Given two sequences of items, find the items whose
absolute number increases or decreases the most when comparing
one sequence with the other by reading the sequence only once.

Solution:Well, this question requires some reading and understanding
of data streams.The stress is upon the algorithmic challenges in web search engines.It wouldn't be appropriate to quote a short piece of text
as the answer.So please go through the paperFinding Frequent Items in Data Streams to have a thorough understanding of the problem
as well as its applications.
Click here for the questions



11.How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points ?

Solution:The three non-collinear points form a triangle. There will be 3 lines which are equidistant from all the three points.
Draw altitudes from each point to the line joining the other two points.We get 3 altitudes.Now draw a line passing through the mid point of the altitude line and parallel to line onto which the altitude is drawn.This line is equidistant from all the 3 points.Thus we get 3 lines.

Click here for the questions

13.Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ?


Solution:This solution has been framed on the assumption that all the occurances of a string in the large string of length N are to be reported.
So one can just sort the M strings in O(l*Mlog(M)).An additional l figures because comparison function of strings of length l is of complexity O(l).
Once these M strings are sorted,we can simply do a binary search on them for each of the N-l+1 continuous substrings of big string.The complexity of this search for each such substring is O(l*logM).
So the complexity of this procedure is O(l*MlogM)+O((N-l+1)*(l*logM)).
For N>>l this reduces to O(l*MlogM)+O(N*l*log(M).
This can be reduced to O((M+N)*l*log(M)).

If you find a better solution than this,please post it in the comments section.
Click here for the questions


14.Given a Binary Tree, Programmatically you need to Prove it is a Binary Search Tree
Hint: Some kind of pointer handling with In Order Traversal - anybody in for
writing some code.

Solution:If the given binary tree is a Binary search tree,then the inorder traversal should output the elements in increasing order.We make use of this property of inorder traversal to check whether the given binary tree is a BST or not.We make note of the latest element that could have been printed and compare it with the current element.Given below is a C function to check it.



bool flag=true;
void inorder(tree T,int *lastprinted)
{
if(T==NULL)
{
printf("the tree is empty .Hence, it is a BST\n");
}
else
{
if(T->left!=NULL)
{
inorder(T->left,lastprinted);
}
if(T->data > *lastprinted)
{
*lastprinted=T->data;
}
else
{
printf("the given binary tree is not a BST\n");
flag=false;
exit(0);
}
inorder(T->right,lastprinted);
}
}


Now check the value of flag to say whether it is a BST or not.If it is not then it is already taken care by the code.
Click here for the questions


15.You are given a small sorted list of numbers, and a very very long sorted list of numbers - so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?

Solution:For each chunk of sorted list which occupies a block,make a note of the first and last elements.Thus we have lookup table giving the first and last elements of each of the blocks.Now associate an empty list with each of the blocks.
Now try to find the block which might contain the first entry A[1]of the small sorted list(say)A given.Since we knew the first and last elements of all the blocks,we can identify the block Bi ,which only can contain the desired number.Now add A[1] to the empty list associated with Bi.Now we need to identify the candidate block for A[2].As A is also sorted,A[2] should lie either in Bi or its successors.So we simultaneously traverse
A as well as lookup table.When we are done with finding the probable blocks of all the numbers in A,we have also finished the look up table. We also have in the lists associated with each block,all those entries of A to search for, in that particular block.Now for each block Bi,search for all the entries in its list using binary search.This way we have minimized the number of disk block accesses,which is the bottleneck .

Click here for the questions



16.Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?


Solution:Different solutions exist for this problem,depending on how once perceives the question.
If all the companies are assumed to be unique things,then the solution goes like this.Initially we need to merge 2 companies.These 2 can be chosen in Nc2 ways.Now in the second iteration we can merge 2 companies among the remaining N-1 in N-1c2.
We go on merging like this until we have a single union of all the companies.
Hence the number of ways of doing this is (Nc2)*(N-1c2)*(N-2c2)*........*(2c2)=(N!*(N-1)!)/2^(N-1) .

One more way of looking at this problem is the structural aspect of merging.In the above solution suppose there are 4 companies say,to be merged.

We could have merged companies 1&2 in the first iteration and 3&4 in the 2nd iteration.Likewise we could have also merged 3&4 in the first iteration and then 1&2 in the 2nd iteration.After these 2 merges,both of them are identical,though we put them as different ways in solution1,depending on which 2 were merged before the other 2.If we were interested only in the structural aspects,then the above solution doesn't even consider that.
If we are interested in the number of structurally different ways to merge these, then we can confront this problem on the assumption that all the given companies are identical .Then this problem reduces to parenthesis problem,i.e number of ways of putting N pairs of parenthesis.The answer then would be N-1 th Catalan Number,
i.e (2N-2)!/N!(N-1)!.

If the companies aren't identical ,with some permutations also getting into the picture, then the solution isn't straightforward and we couldn't figure it out.

So if anyone has a solution to this,please post it in the comments section.

Click here for the questions


17.Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?


Solution:The maximum size of int is 2,147,483,647 in case of 32-bit integers. Thus we need declare an array of long long int.
Then we can do a merge sort and in doing so we can find the integers which appear atleast twice in the merge step.Thus we can solve the problem in
nlogn time.
If you have any better solution then please comment.

Click here for the questions

18 Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.

Solution:This question is similar to question 9 in the context which it appears and
answer lies in the same paper Finding Frequent Items in Data Streams.
Click here for the questions




19.Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.

Solution:Use 2 stacks S1 in to which the elements are pushed and S2 in to which only the current minimum is pushed.
When one needs to insert an element E ,we first push E on to S1 and then access the top element T of S2 which is the minimum before E has been inserted.If only E is less than T , we push E on to S2 .
When one needs to pop an element ,pop the top element of S1 and if this element is also equal to the one on top of S2, then pop it off S2 as well.

Hence the current minimum will always be on top of S2 .Hence along with other normal stack operations, access of minimum element is also possible in O(1).

Click here for the questions

20.Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.


Solution:This is a flavour of coin change problem ,for which sufficient material is available at Coin Change Problem.
If you have gone through the above link,please refer below to the minor changes we make to the pseudo code of one given in the above link.

Let p[n][m] denote the minimum no of coins of various denomination required to give change for n cents from coins of m different denominations.

P[n][m]=min((1+p[n-S[m]][m]),p[n][m-1])// these notations will be clear only if you go through the above link thoroughly.

Then it isn't much difficult to write the conditions for base cases as well.
This is only a suggested solution to this problem and we have clues here and there as to how to proceed.

Click here for the questions

21.Given an array,

i) find the longest continuous increasing subsequence.

ii) find the longest increasing subsequence.


Solution:a)Given a sequence,we can find the longest continuous increasing subsequence in O(n) time.We traverse the sequence one and keep track of the points where the number decreases.

b)This problem can be solved in O(n^2).This can be solved in 3 methods.One method is to find the longest path in a directed acyclic graph.The other method is to sort the given sequence and make it copy and find the longest common subsequence on the 2 sequences.The third one is using the dynamic programming.
The following is a function which returns the length of the longest increasing subsequence in a.

int lis(int*a,int n)
{
int length[n],path[n],i,j,max=0;

for(i=0;i < N;i++)
length[i]=1,path[i]=i; //path contains the longest subsequence.

for(i=1;i < N;i++)
for(j=0;j < i;j++)
if(a[i] > a[j] && length[i] < length[j]+1)
length[i]=length[j]+1,path[i]=j;

for(i=0;i < N;i++)
if(max < length[i])
max=length[i];

return max;
}


Click here for the questions

22.Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?

Solution:This is a repeated question, same as the 16th. So please refer to the 16th answer.

Click here for the questions

23.Write a function to find the middle node of a single link list.

Solution:

typedef struct linklist
{
int no;
struct linklist*next;
}list;

void midvalue(list*start)
{
list*head;
head=start;
while(1)
{
if(start->next==NULL)
{
if(head->next==NULL)
{
printf("Only one node in the list which is %d\n",head->no);
}
else
{
printf("Middle node is %d\n",head->next->no);
}
break;
}
if(start->next->next==NULL)
{
printf("Middle nodes are %d and %d\n",head->no,head->next->no);
}
start=start->next->next;
head=head->next;
}
return;
}

This algorithm loops for n/2 times where n is the length of the list.Thus its complexity is O(n).


Click here for the questions

24.Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.

Solution:The following is a function to check if the two trees are similar or not.It returns true if they are similar else false.

int compareTree(struct node* a, struct node* b) {
if (a==NULL && b==NULL)
return(true);
else if (a!=NULL && b!=NULL) {
return(
a->data == b->data &&
compareTree(a->left, b->left) &&
compareTree(a->right, b->right)
);
}
else return(false);
}


Click here for the questions

25.Implement put/get methods of a fixed size cache with LRU replacement algorithm.

Solution:Each cache unit consists of an id,data and its age.In the Least recently used algorithm if the cache is full and we need to put some data, we replace it an the unit whose age is the least.
Getting some data is just a search for the data thereby incrementing it age and resorting the cache units.

get(id)
{
z=search(id);
data=cache[z].data;
cache[z].age++;
sort(cache);
return(x);
}

put(id,x)
{
if(top==cachesize) //if cache is full
top--
cache[top].id=id;
cache[top].data=x;
cache[top].age=0;
top++;
}


Click here for the questions

26 You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.

Distance is defined like this :

If a[i], b[j] and c[k] are three elements then

distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"

Please give a solution in O(n) time complexity


Solution:Point to the first elements of the three arrays, namely a[0],b[0],c[0].
Find the smallest and second smallest of the three.Let us say that a[0] is the smallest and b[0] is the second smallest. Increment the pointer of a until you find a[i]>b[0]. Calculate the difference between a[i-1] and c[0] and store it as current min. Now,again find the smallest and second smallest between a[i], b[0], and c[0] and repeat the above process. If the new difference is smaller than current min,update the value of current min.
Repeat the above process until one of the arrays are finished.

Click here for the questions

27.Classic - Egg Problem

You are given 2 eggs.You have access to a 100-storey building.

Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.

Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.


Solution:Let d be the number of drops required.
Now we need to find an optimal solution no matter at which floor the egg breaks.
So we find d such that it doesn't depend on the floor number.

Let us break the egg at floor d. If the egg breaks then we have atmax d-1 floors to test for the highest floor,thus making it d breaks in total.
If the egg doesn't break at floor d,then proceed to floor 2d-1,where we make the 2nd attempt.If it breaks here we have d-2 breaks in the worst case to find the highest floor.
We proceed in this fashion,till we reach the 100th floor.

Thus we break at d,2*d-1,3*d-2,....

thus d+(d-1)+(d-2)+.... 1 <=100
=>d=14
Thus we need atmax of 14 attempts for any case.


Click here for the questions

Solutions to the remaining puzzles will be posted soon. If we have a solution then please comment it.

38 comments:

  1. For Q17.
    Steps-
    1.Create a bit map of 4 billion bits.
    It will use 4B/8 bytes memory.

    2.Intiliase all bits to 0.
    3. Traverse the integers ,and set the particular bit that corresponds to number to 1.
    For example say there is number 8 in the file then set the 8th bit to 1.
    4.If while traversing the ,you find the number whose bit is already 1 then this is the number.

    Complexity: O(n)

    ReplyDelete
  2. For Q17.
    Note that in my solution provided I have assumed that there is ample main memory.

    ReplyDelete
  3. Q5 says to use only constant space however the solution as provided in Ans1 uses another array, basically O(n) space. Any neater solution for Q5?

    ReplyDelete
  4. In Q13 you can sort the M strings of length L in O(LM) using radix sort.

    Also the overall better solution to this problem can be to simple has the M smaller strings of length L taking O(M) time and for each of the N-L+1 strings of larger strings lookup in O(1) time. Which should make the overall time complexity to -
    O(M) + O(N-L+1)

    ReplyDelete
  5. Q 1 . the solution given here is o(n2)

    but,it is told to be done in o(n)

    ReplyDelete
  6. Q13. Aho-Corasick algorithm O(N+L*M)

    ReplyDelete
  7. >Smile
    >April 13, 2008 9:59 AM

    >Q 1 . the solution given here is o(n2)

    >but,it is told to be done in o(n)

    I am not sure how you got that value, but it is O(n), at least there isn't a loop inside another loop in the implementation.

    ReplyDelete
  8. For Q-13:

    Without sorting, it is pssible to design an algorithm with hashing as follows which is better:

    1 - Create a hashtable/hashmap data structure and put the L small strings in it using the string as a key and value as count (initially 0) -> O(L)
    2 - Traverse the string of length N and for each traversal take the next M substring from the current char position. Check the substring in the hashtable (lookup hashtable is O(1) or constant time) and if it exists increment the count/value. -> O(N-M) why N-M because we need M length substring.
    3 - Traverse the hashtable and print those keys/strings whose value is greater than 0. -> O(L)

    Therefore, the overall time growth of this approach is 2*O(L) + O(N-M), which is a linear growth in O(n)

    Can we do it better? I would love to hear....

    ReplyDelete
  9. For Q8. The divide and conquer suggested solution doesn't seem correct. If you have i1-i16, c1-c16, then divide and conquer takes you to [i1..i2,c1..c2 | i3..i4,c1..c4], which then leads to
    solving [i1..i2,c1..c2] and [i3..i4,c3..c4]. So one needs to solve solve[i1..i2,c1..c2]. Problem is, while we want c1 where i2 was, we do NOT want i2 where c1 was. We want i2 where i3 originally was. And c2 goes where i4 originally was.
    Worse, is that when working on [i3..i4,c3..c4], the eventual homes should be where i3, c3, i4, c4 go to where i5, i6, i7, i8 originaly were. Conquer for [i3..i4, c3..c4] doesn't now that.

    The requested algorithm is supposed to be an in-place algorithm. See http://en.wikipedia.org/wiki/In-place .
    A divide and conquer solution for Q8 should NOT build/load a new array.

    While I have a solution that is an in-place order n squared algorithm, one would hope for a order n algorithm.

    ReplyDelete
    Replies
    1. here is the code which is valid for all situations.
      Space Complexity : O(1) //Auxiliary space
      Time Complexity : O(N/4 * Log N)

      http://ideone.com/Z4QEoJ

      Delete
  10. #7 solution doesn't seem correct to me. For instance find 3rd maximum value for this tree

    http://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/150px-Binary_search_tree.svg.png

    it should be 10, not 14.

    ReplyDelete
    Replies
    1. I think the algorithm gives 14 actually.

      Delete
  11. >Smile
    >April 13, 2008 9:59 AM

    >Q 1 . the solution given here is o(n2)

    >but,it is told to be done in o(n)

    I am not sure how you got that value, but it is O(n), at least there isn't a loop inside another loop in the implementation.


    Q1. goit is actually right.

    There is no loop inside another loop so it's not O(n^2), but there are 2 loops in total so complexity is O(2 * n).

    O(n) and O(2*n) are not the same, although they are both called linear time complexity.

    Maybe the final question is wrong.I think it should be:

    Solve it without division operator and in linear time.

    instead of

    Solve it without division operator and in O(n).

    I don't think it is possible to solve this strictly in O(n) time. :)

    Thanks for the questions!

    ReplyDelete
  12. Qs 17
    using bitmap as suggested by you:

    base = n/8; (base is the char whose certain bit needs to be set)

    offset = 1 << (n mod 8); (offset is the bit to be set)

    if (b_array[base] & offset)
    // found the number which repeats
    more than once
    else{
    //number could not be found, so
    add entry for it
    b_array[base] |= offset;
    }

    Lemme know if its wrong...

    ReplyDelete
  13. consider this Problem:
    find no. of trees possible with n leaf nodes?
    If we put this restriction: The left and right sub trees are not distinct for any node.
    The problem is similar to Q16.
    So Soln is
    F(N)=1/2*(sum(NCi*F(N-i)*F(i))); i from 1 to N-1 & NCi=no of ways to select i items from N items

    ReplyDelete
  14. For Q3
    Isn't solution provided provided is of O(n) complexity? Binary search because array is already sorted is of O(log n) complexity.

    ReplyDelete
  15. q5) you need to create a n-sized output array, how can that be constant space

    ReplyDelete
  16. Q2. Use reservoir sampling to get random numbers with equal probability

    http://blogs.msdn.com/spt/archive/2008/02/05/reservoir-sampling.aspx

    ReplyDelete
  17. for the #4 question:

    ReplyDelete
  18. Solution to problem # 27 is wrong. It should be the solution to min[100/n+n-1] which gives n =10.
    This is number of divisions to be done.
    And the number of iterations would be 19.

    ReplyDelete
  19. Use xor for #17

    ReplyDelete
  20. Q5 is not the same as Q1 because it is asking for solving the problem using constant space. A constant space, linear time solution is as follows:

    - Take the log of A[i] for all i and sum up log values.
    - B[i] = exp(sum - log(A[i]))

    This is correct because log(xy) = log x + log y

    ReplyDelete
  21. Solution for Q1 in O(n):

    fillArray(0, 1, 1);
    fillArray(int i, int before, int after)
    {
    if ( i == N - 1 )
    {
    after *= array[i];
    array[i] = before;
    }
    else if ( i == 0 )
    {
    after = fillArray(i + 1, array[i], after);
    array[i] = after;
    }
    else if ( i != N )
    {
    after = fillArray( i + 1, before * array[i], after);
    int temp = array[i];
    array[i] = before * after;
    return after * temp;
    }
    return after;
    }

    ReplyDelete
  22. Q2. Makes little sense: what is "n"? If n=N, just do it in two passes through the list - first pass finds N, next pass collects k numbers. This solution seems better except in the odd case that following a pointer is more expensive than generating and comparing (several times) a random float.

    ReplyDelete
  23. Q3: I posted my solution at
    http://odinlake.net/wordpress/?page_id=128

    ReplyDelete
  24. Q6: It's much simpler than that. Just use pre-order traversal to write the nodes to an array. Reading the array back in will always create the same tree, e.g.:

    3
    / \
    1 4

    becomes, as an array: {3, 1, 4}

    creating a tree from this, always gives us back the original, because of the properties of a binary tree.

    ReplyDelete
  25. Q19 is not correct.

    Say you have popped the minimum once, and S2 is empty in your solution. Then you don't know what is the miminum anymore.

    Following this idea, I don't think you can have a solution with all O(1) for this question. To maintain a sorted sequence in increasing order can not be constant time.

    ReplyDelete
  26. for Anonymous on 23 july 2008 - just use the following code for Q8. It works at least for a size which is a power of 2 - I didn't check otherwise : the divide and conquer *does* work :

    void permutVector(std::vector &vec, int left, int right) //l r included
    {
    if (left>=right-1) return;

    int nelem = right-left+1;
    int blocksize = nelem/4;
    for (int i=0; i<blocksize; i++)
    std::swap(vec[left+blocksize+i], vec[left+2*blocksize+i]);

    int middle = (left+right)/2;
    permutVector(vec, left, middle);
    permutVector(vec, middle+1, right);
    }

    For ruslan, the answer provided in Q7 is also correct and also works for the tree you provided. In-order traversal allows for traversing along sorted values in a BST, so it's normal that it works.

    ReplyDelete
  27. Prob 8: solution in C with details: http://dailyjobquestions.com/2011/10/16/divide-and-conquer/

    Prob 22: solutions for LCS and LIS in C: http://dailyjobquestions.com/2011/10/06/longest-common-subsequence-c/
    http://dailyjobquestions.com/2011/10/07/longest-increasing-subsequence-c/

    ReplyDelete
  28. Hello,

    Regarding Question 17:
    Why not to maintain bit map of 2^32 bits. Each bit for each integer in range [0:2^32]. Traverse the file once and for each integer you read from file lit the bit in your bitmap in the appropriate position.
    If you encounter with the bit that is already 1, then you found the integer that appears at least twice.

    The time complexity is O(N)
    Storage is always 2^27 addresses

    ReplyDelete
  29. 13. can be solved by a collapsed suffix tree of the long string. It can be constructed in O(N) and takes O(N) space. Each of the small strings can be matched in O(L) time then. So the overall time is O(N + ML).

    ReplyDelete
  30. These articles have got thorough discernment without unclear the readers.
    all vectors

    ReplyDelete
  31. These articles are great. Thanks for the help !

    ReplyDelete
  32. This comment has been removed by the author.

    ReplyDelete
  33. Q26. I'm considering how one would prove the solution given above is true:

    If you were to line the numbers up like beads on poles with height as their value, and then merge the poles together, you would get a merged list. If you walked along that merged list from low to high, you'd get an ordering as the algorithm is suggesting. The one furthest in back, then the next furthest in back, etc.

    You consider a set of three bead positions, current for a, current for b, and current for c. Each time you encounter a new bead on the pole you would choose it for your current a, b, or c value (assume beads are labeled a, b, or c so you know which they should be). You compute max(abs(a-b),abs(a-c),abs(b-c)) each time you encounter a bead to see if you have found a value any smaller than before.

    Now if the solution exists as a contiguous set of 3 beads: involving a, b, and c, this algorithm will definitely find it, because it walks along every possible contigous set of 3.

    What about if the solution is not a contigous set of 3 beads. I believe there is just one type of case where they would not be contigous. It's were you have one type repeated inbetween the other two types. For example, you could have something like a1, b1, b2, b3, c1 in that order. There might be some concern here that you won't pick b correctly. However, it should be OK. They are not contiguous, but consider how the metric uses the max: By the time you visit c1, you will end up with a=a1, b=b3, c=c1, compute max(abs(a-b),abs(a-c),abs(b-c)), and decide that a1 to c1 is the max. Given a1, b1, b2, b3, c1 does contain the best set a, b, and c, it doesn't really even matter what you pick for b because that won't change the evaluation metric.

    Comments/criticisms welcome.

    ReplyDelete
  34. any one please help me..I need a binary search tree program to search the country name using javascript..the output must contain a drop down box with 10 country name and search box.if i type the alphabets of the country name in the search box automatically it appear in the drop down box.

    ReplyDelete