Placement Papers - Microsoft
MICROSOFT PLACEMENT PAPER (TECHNICAL-C, DATA STRUCTURE)
Posted by :
Shaju
(17)
PAPER: MICROSOFT PLACEMENT PAPER (TECHNICAL-C, DATA STRUCTURE)
1. Besides communication cost, what is the other source of inefficiency in RPC? (answer : context switches, excessive buffer copying). How can you optimize the communication? (ans : communicate through shared memory on same machine, bypassing the kernel _ A Univ. of Wash. thesis)
2. Write a routine that prints out a 2-D array in spiral order!
3. How is the readers-writers problem solved? - using semaphores/ada .. etc.
4. Ways of optimizing symbol table storage in compilers.
5. A walk-through through the symbol table functions, lookup() implementation etc. - The interviewer was on the Microsoft C team.
6. A version of the "There are three persons X Y Z, one of which always lies".. etc..
7. There are 3 ants at 3 corners of a triangle, they randomly start moving towards another corner.. what is the probability that they don\'t collide.
8. Write an efficient algorithm and C code to shuffle a pack of cards.. this one was a feedback process until we came up with one with no extra storage.
9. The if (x == 0) y = 0 etc..
10. Some more bit wise optimization at assembly level
11. Some general questions on Lex, Yacc etc.
12. Given an array t[100] which contains numbers between 1..99. Return the duplicated value. Try both O(n) and O(n-square).
13. Given an array of characters. How would you reverse it. ? How would you reverse it without using indexing in the array.
14. Given a sequence of characters. How will you convert the lower case characters to upper case characters. ( Try using bit vector - solutions given in the C lib -typec.h)
15. Fundamentals of RPC.
16. Given a linked list which is sorted. How will u insert in sorted way.
17. Given a linked list How will you reverse it.
18. Give a good data structure for having n queues ( n not fixed) in a finite memory segment. You can have some data-structure separate for each queue. Try to use at least 90% of the memory space.
19. Do a breadth first traversal of a tree.
20. Write code for reversing a linked list.
21. Write, efficient code for extracting unique elements from a sorted list of array. e.g. (1, 1, 3, 3, 3, 5, 5, 5, 9, 9, 9, 9) -> (1, 3, 5, 9).
22. Given an array of integers, find the contiguous sub-array with the largest sum.
ANS. Can be done in O(n) time and O(1) extra space. Scan array from 1 to n. Remember the best sub-array seen so far and the best sub-array ending in i.
1. Besides communication cost, what is the other source of inefficiency in RPC? (answer : context switches, excessive buffer copying). How can you optimize the communication? (ans : communicate through shared memory on same machine, bypassing the kernel _ A Univ. of Wash. thesis)
2. Write a routine that prints out a 2-D array in spiral order!
3. How is the readers-writers problem solved? - using semaphores/ada .. etc.
4. Ways of optimizing symbol table storage in compilers.
5. A walk-through through the symbol table functions, lookup() implementation etc. - The interviewer was on the Microsoft C team.
6. A version of the "There are three persons X Y Z, one of which always lies".. etc..
7. There are 3 ants at 3 corners of a triangle, they randomly start moving towards another corner.. what is the probability that they don\'t collide.
8. Write an efficient algorithm and C code to shuffle a pack of cards.. this one was a feedback process until we came up with one with no extra storage.
9. The if (x == 0) y = 0 etc..
10. Some more bit wise optimization at assembly level
11. Some general questions on Lex, Yacc etc.
12. Given an array t[100] which contains numbers between 1..99. Return the duplicated value. Try both O(n) and O(n-square).
13. Given an array of characters. How would you reverse it. ? How would you reverse it without using indexing in the array.
14. Given a sequence of characters. How will you convert the lower case characters to upper case characters. ( Try using bit vector - solutions given in the C lib -typec.h)
15. Fundamentals of RPC.
16. Given a linked list which is sorted. How will u insert in sorted way.
17. Given a linked list How will you reverse it.
18. Give a good data structure for having n queues ( n not fixed) in a finite memory segment. You can have some data-structure separate for each queue. Try to use at least 90% of the memory space.
19. Do a breadth first traversal of a tree.
20. Write code for reversing a linked list.
21. Write, efficient code for extracting unique elements from a sorted list of array. e.g. (1, 1, 3, 3, 3, 5, 5, 5, 9, 9, 9, 9) -> (1, 3, 5, 9).
22. Given an array of integers, find the contiguous sub-array with the largest sum.
ANS. Can be done in O(n) time and O(1) extra space. Scan array from 1 to n. Remember the best sub-array seen so far and the best sub-array ending in i.
Quick links
Quantitative Aptitude
Verbal (English)
Reasoning
Programming
Interview
Placement Papers