dawninghu
BAN USERSDE
- -1of 0 votes
AnswersMicrosoft onsite multithread synchronization interview question
- dawninghu
1. Suppose we have a class:
class Foo {
Public:
A(.....); //if A is called, a new thread will be created and the corresponding function will be executed.
B(.....); //if B is called, a new thread will be created and the corresponding function will be executed.
C(.....); //if C is called, a new thread will be created and the corresponding function will be executed.
......
}
Suppose we have the following code to use class Foo (We do not know how the threads will be scheduled in the OS.)
Foo f;
f.A(.....);
f.B(.....);
f.C(.....);
Questions (Part A):
1. Can you explain multithread synchronization mechanism?
2. Can you design a mechanism to make sure that B is executed after A, and C is executed after B?
Questions (Part B):
Suppose we have the following code to use class Foo (We do not know how the threads will be scheduled in the OS.)
Foo f;
f.A(.....);
f.B(.....);
f.C(.....);
f.A(.....);
f.B(.....);
f.C(.....);
Q: 1. Can you design a mechanism to make sure that all the methods will be executed in sequence?
Questions (Part C):
2. Can you design a mechanism to make sure that all the methods will be executed in sequence, in this case the caller should
be nonblocked?
3. Can you design a mechanism to make sure that all the methods will be executed in sequence, in this case the caller and the
called methods should be nonblocked? (hint: use call back).
Please write the corresponding code.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Threads
I believe this is the correct solution:
- dawninghu February 02, 2008(it is not my credit, I just copy and paste from techinterview discussion.)
If you must start at the root, then the following will work (but can probably be improved upon):
Traverse your tree, changing it so that the value at each node changes to the value of it's parent node + it's original value. Thus the values are in this tree are the sum of the values in the unchanged tree from the root to the given point. If the value you currently have is the one you want, then add the path to this node to your list.
If you don't have to start at the root, then traverse your tree as before, but at each node replace its value with a list containing it's original value (head of the list), and its's original value summed with each element of it's parent's list (tail of list). Thus each node has a list of numbers, indicating the sum to that node starting from different ancestors, the number of ancestors required being the position in the list. If any of these values turn out to be the one you want, then store it in the list.
NB The above methods take no advantage of it being a binary search tree. A simple improvement is found by knowing that if your current value is too high and current node is non-negative, then you only need to search the left-hand branch. Similarly, if your current value is too low and the current node is non-positive, only search the right-hand tree. If you know in advance that the numbers are all non-negative or all non-positive, then you can stop searching altogther when you reach a sum that is too high/too low. (Stop at a value that is too extreme in the second algorithm).
If the paths must stop at a leaf, traverse the tree as above, but only store paths that sum to the correct value if they are a leaf node. Speed-ups still apply.