Interview Questions 22

1. Given an integer array, sort the integer array such that the concatenated integer of the result array is max. e.g. [4, 94, 9, 14, 1] will be sorted to [9,94,4,14,1] where the result integer is 9944141

2. I have a card pack of 313 cards. I remove the topmost card from card pack and place it on desk and I remove the next one and put it below the pack of cards(that you are holding). keep doing this till all the cards are on desk. Pick up the card stack from desk and repeat these steps till you find retrieve the original cards order.

3. [Design + Graph Traversal] Assume you have a set of 1500 independent pieces of code. We’ll call them projects. Each project can either be:
1) completely independent
2) dependent on other projects
3) dependent on other projects and have other projects dependent on it
The combined build times of all 1500 projects is 24 hours(so build project 1, when it finished, build project 2, etc). A build consists of compiling and linking all the requisite code. You can assume you don’t have to worry about a budget. If there’s a tool that would help you out, you can use it if you can describe how it works. How would you speed up the build process?

4. Given a BST in a language where memory must be handled manually, how do you completely remove BST from memory? Recursion is not allowed. [O(N), O(1)]

5. [Don’t vomit out TRIE] You are developing a system for a cell phone which will automatically predict what word a user is typing. Talk about the data structures and algorithms you would use to make this, keeping in mind that cell phones have limited memory/CPU power.

6. There are N web servers. Each web server has a huge file containing random 1 million numbers (numbers can repeat). Find the median of these N million numbers given that only 1 million numbers can be brought into memory at a time.

7. Many irregular shape objects are moving in random direction. provide data structure and algo to detect collision. Remember that objects are in million.

8. A complete ternary tree is a tree in which each and every node has either 0 or 3 children . Given preorder of a complete ternary tree , construct the tree . Preorder will be a string containing characterd i and l where i represents an internal node and l represent a leaf node .

9. [Math] Find the number of strings of length n having u distinct uppercase letters , l distinct lowercase letters and d distinct digits.

10. Given a sorting order string, sort the input string based on the given sorting order string.
Ex. sorting order string -> dfbcae
Input string -> abcdeeabc
output -> dbbccaaee


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

6 Responses to Interview Questions 22

  1. amit says:


    convert the bst to linked list in O(n) and O(1) and then delete the LL

    • Avi Dullu says:

      Please notice in a language where memory must be handled manually in the question. Can you post a method to convert a BST into linked list without using recursion in O(n)? In the algorithm you propose, this (conversion by manually handling memory) is the most important part which demands details.
      With any algorithm you propose, also do provide the details of the critical steps involved if not the code (preferably 🙂 )

  2. Amar says:

    10. Counting sort can do it in O(n) with 2 passes and will take O(k) extra space where k is the size of sorting order string.
    Without extra space, just use substitution and sort O(nlogn).

  3. beginner says:

    1. Sort numbers on each machine.
    2. Make a mean heap of N elements by taking 1st element from each machine along with the information to which machine number belongs.
    3. Now remove the minimum element (top of heap), and add the number from the same machine as removed element. Again min heapify.
    4. Repeat 3 for (N*One million)/2 + 1 times. Min element of the heap is required median.

    Total complexity.
    Let M = 1 Million.
    1. Sorting M elements on N machines. N*Mlog(M).
    2. For step 2,3,4 ((N*M)/2 + 1)log (N).
    3. So Time complexity is O(N*Mlog(M))

  4. Prateek Caire says:

    5th question

    1. Initialize current as root
    2. While current is not NULL
    If current does not have left child
    a. Print current’s data
    b. Go to the right, i.e., current = current->right
    a. In current’s left subtree, make current the right child of the rightmost node
    b. Go to this left child, i.e., current = current->left


  5. Prateek Caire says:

    Find max element so that max digits can be found
    pad each element with lsd
    print in sorted order

    for each i from 0 to n-1
    if(a[i] > max)
    max = a[i]
    c = 0
    max = max/10
    for each i from 0 to n-1
    l[i] = a[i]%10
    t = a[i]
    tc = 0
    t = t/10
    p[i] = c-tc
    for each i from 0 to n-1
    for each j from 0 to p[i]
    a[i] = a[i]*10 + l[i]
    qs(a) //quicksort
    for each i from 0 to n-1
    a[i] = a[i]/10
    print a[i]

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: