gavinashg
BAN USER- 0of 0 votes
AnswersDesign middle tier for facebook type application.
- gavinashg
i.e design a service which accepts IIS requests from client and updates the database.
What are the various interfaces to be exposed on middle tier.
I was asked multiple questions around desgining a component and discuss about the APIs to be exposed. How do we approach such issues.
PS: They wanted me to talk about request context, notifications, callback, thread safe etc| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer
Step 1: Since m is small, find the sum, call it SumB.
Step 2: Take first m elements from Array A, find sum, call it SumA
Step 3: Compare SumA and SumB. If equal, check if substring from A is an anagram of B.
Step 4: Otherwise slide window by 1 char, and repeat Step 2.
1. User can input the speed and google maps shows the video as if a person is driving on the steet. The user should be able to see the surrondings as if he/she was driving.
This can be useful to familiarize with the route before we start
2. Have mobile application to enable GPS functionality. We need to improve speach here. When there are multiple exits on highway it should be able to clearly distinguish between them with minimum efforts required for a driver to understand.
3. European/Asian country names should be in English. Option should be to change the language so that text can be printed in that language
4. Avoid highway does not always show optimal path
1. Arrange the n persons in decreasing order of weight
2. Have an array of size n, which stores {humanChainSize if person is included, index of previous person}
3. For heaviest person, let Array[0] = {1, 0}. Here 1 corresponds to humanChainSize because the heaviest person is included and since he is the lowest person in human chain, there is no previous person to him and hence the index is set to 0.
4. For second heaviest person if it can stand on top of previous person(height should be lower that previous element), then Array[1] = {2, 0} and if the previous person cannot be included then let Array[1] = {1,1}
5. For the ith person, go through all elements Array[0] to Array[i-1] and find the index 'temp' (corresponding to person) where it can standup on. Update Array[i] = {Array[temp].humanChainSize+1,temp}. As we iterate, we need to update Array[i] if the new humanChainSize is greater.
6. When the iteration finishes, go through the Array from n to 0, find the element which has highest humanChainSize value, print the currentIndex. Find the index stored in the current element and go to Array[index] and print the element. Do it till currentIndex = index.
Complexity O(nlog(n)).
Let {x1,y1,z1}, {x2,y2,z2} .... be the co-ordinates of people.
Let x=mean{x1,x2,..}, y=mean{y1,y2,..}, z=mean{z1,z2,..}
We keep {x,y,z} as our pivot and start exploring from this point.
We need to explore in a rectangular shape(3D) from the pivot point. The direction in which we explore depends upon how close the people are in each direction. Hence we explore in direction where the difference in co-ordinates are high.
We can do push/pop in Best case O(1), worst case O(logn).
Have an HeapTable which stores freequency of an element such that the parent has a higher freequency than the two childs. It Have a HashTable to store the element.
HeapTable has a pointer into HashTable and viceversa for each element.
Push operation
Hash the element into the hash table.
1. If it exists, follow the pointer into the HeapTable and increment the freequency. We may have to compare with the parent node and ensure that the HeapTable remains in sorted order. worst case - O(logn), best case O(1).
2. If the element does not exist, add the element in the hash table and take the next space in HeapTable and update the freequency to 1. Add pointers from hash table to HeapTable amd vice versa.
Pop operation
1. Take the root element from HeapTable, decrement count, follow the pointer and return the element.
2. Adjust the HeapTable such that it remains in sorted order. Best case O(1), worst case O(logn).
3. If count becomes 0, we need to remove the element from hash table.
This is a tricky question and is expensive to to solve using traditional methods.
One alternative method is to use a large Array. Each element of this Array is a pointer to string.
Now read each string from the book. Take a random no in range 0 to Max_Array_Size. Replace the existing Array[randomNo] with the recently read string.
At the end of reading all words from book, check the array and find the string which is occuring maximum times.
I was asked similar question and argued that the solution will not work. Interviewer explained the following
1. Algorithm most of the times work. I forgot the algorithm name.
2. Array size has to be of certain size according to a formula. I don't remember that
3. The algorithm is very fast and efficient.
4. Can we used in search type applications like google/bing etc where you don't need 100% accurate results.
5. If a word occurs many times in the book, there is higher probability that the word is present at multiple places in the Array.
The logic is to count the numbers of 'a', 'b'...'z' that occurs in the first or last position of each string. To form a chain, only two of two letter count can be odd.
Step 1.
Have an array of 26 elements (hash table) where array[0] corresponds to 'a' and array[25] corresponds to z.
Step 2.
For each element
{
array[element[0]]++;
array[element[last]]++;
}
Step 3.
For i = 0 to 25
if array[i] is odd count++
Step 4.
If count > 2, then we cannot chain.
Most efficient Algorithm
Read all entries from file.
Create a hash table and for each entry read from the file, hash it based on the start node_id
Add the cost,dest node_id to the hash table.
Now each entry of hash table is a linked list. So Adding in the above step means add to the linked list.
Please don't write long code. Please explain algorithm.
The logic is -
1. Find the total no of elements i.e sum of elements in two arrays. Call is n
2. We know median is the n/2 smallest element
3. Have two index, one for each array.
4. Compare the two array in a loop. Increment the index of the array which has smaller element. At each comparison also increment a counter.
5. When counter = n/2, the smaller of the two array element, will be the median
Simple problem.
Use quick sort. Find no of elements which are on the right side of pivot.
1. If < than 1 million, let new pivot be an element from the left side of pivot so that we can have more elements on the right side of new pivot
2. If > than 1 million, let new pivot be an element from the right side of pivot so that we can have less elements on the right side of new pivot
Repeat till we have 1 million no on the right side of pivot.
We have to choose the new pivot carefully otherwise the above algorithm will not end.
I leave that as an exercise for others.
Worst case analysis - sorting would be nlogn. So the above algorithm will be much better than that. It may be as good as O(n).
Most of the above solutions are wrong.
Correct solution is below.
void ReverseNodePointers(Node* node, Node* parent)
{
if(node == null) return;
Node* leftNode = node->left; // temp child pointer since the node's pointer will be changed.
Node* rightNode = node->right; // temp child pointer since the node's pointer will be changed.
node->left = parent;
node->right = parent;
traverse(leftNode, node);
traverse(rightNode, node);
}
ReverseNodePointers(head, head);
Logic is to find the node with smallest element(BST), add to linked list and remove the node from tree.
RecursiveBST(Node *node)
{
if(node->left == null && mode->right == null) return node;
if(node->left != null)
{
Node *leftNode = RecursiveBST(node->left);
list.push_back(leftNode);
node->left = null;
}
if(node->right != null)
{
Node *rightNode = RecursiveBST(node->right);
list.push_back(rightNode);
node->right = null;
}
}
There are enough flaws in this.
- gavinashg September 29, 2011Please google reader-writer implementation online