Interview Questions 4

1.a) Design a data structure to store an arbitrarily large number
b) How will you use it to store two such number and add them.
c) Write down the class (code) for the data structure.

2.Given a file with a lot of words (10 million) find out the top 10% most frequently occuring words.

3. How will you convert an unsigned int into base -2.

4. There are two binary trees T1 and T2 which store character data, duplicates allowed.
How can I find whether T2 is a subtree of T1 ? .
T1 has millions of nodes and T2 has hundreds of nodes.

5. here are 3 sorted lists. We have to choose an element from each of the 3 lists such that, distance is minimum where distance is: |a-b| + |b-c| + |a-c|. ‘a’ being the element from the 1st list, ‘b’ from the second list and ‘c’ from the 3rd list.
Need to do it in O(n) time, ‘n’ being sum-total of length of the 3 lists

6. Suppose the positive integer n is odd. I write the numbers 1, 2, 3, …, 2n on the blackboard. Then I pick two numbers a, b, erase them and write, instead, |a-b|. Continue this practice till a single number remain on the board. Prove that an odd number will remain at the end.

7. Given an array with some repeating numbers. Like 12,6,5,12,6.
output should be printed as 12,12,6,6,5; i.e, all occurences of the no. should come together and nos. should come in the order given in the array.


About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

2 Responses to Interview Questions 4

  1. Divya says:

    1. using linked list
    2. using trie tree.. where the leaf node stores the count
    4. serialize both tree and apply pattern searching algo like kmp

    correct me if I am wrong or better approach exists for above

    6. please provide its solution

    • Avi Dullu says:

      1. incomplete solution. How?? 1st digit of number as head of LL or tail ?
      2. trie uses way too much space for such constraints (10 million words)
      4. what do u mean by serialize ?
      6. will think and update soon. 😀

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: