# Interview Questions 22

February 18, 2011 6 Comments

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

4.

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

Please notice

in a language where memory must be handled manuallyin 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

detailsof thecriticalsteps involved if not the code (preferably 🙂 )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).

6.

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))

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

Else

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

source: http://stackoverflow.com/questions/5502916/please-explain-morris-inorder-tree-traversal-without-using-stacks-or-recursion

Find max element so that max digits can be found

pad each element with lsd

Sort

Unpad

print in sorted order

MCI()

for each i from 0 to n-1

if(a[i] > max)

max = a[i]

c = 0

while(max)

max = max/10

if(max)

c++

for each i from 0 to n-1

l[i] = a[i]%10

t = a[i]

tc = 0

while(t)

t = t/10

if(t)

tc++

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

while(p[i])

a[i] = a[i]/10

print a[i]