Paper 4

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


28. Write a routine that prints out a 2-D array in spiral order!


29. How is the readers-writers problem solved? - using semaphores/ada .. etc.


30. Ways of optimizing symbol table storage in compilers.


31. A walk-through through the symbol table functions, lookup() implementation etc. - The interviewer was on the Microsoft C team.


32. A version of the "There are three persons X Y Z, one of which always lies".. etc..


33. 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.


34. 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.


35. The if (x == 0) y = 0 etc..


36. Some more bitwise optimization at assembly level


37. Some general questions on Lex, Yacc etc.


38. Given an array t[100] which contains numbers between 1..99. Return the duplicated value. Try both O(n) and O(n-square).


39. Given an array of characters. How would you reverse it. ? How would you reverse it without using indexing in the array.


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



41. Fundamentals of RPC.




42. Given a linked list which is sorted. How will u insert in sorted way.


43. Given a linked list How will you reverse it.

44. 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.
45. Do a breadth first traversal of a tree.



46. Write code for reversing a linked list.


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



48. 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.



49. Given an array of length N containing integers between 1 and N, determine if it contains any duplicates.

ANS. [Is there an O(n) time solution that uses only O(1) extra space and does not destroy the original array?]



50. Sort an array of size n containing integers between 1 and K, given a temporary scratch integer array of size K.

ANS. Compute cumulative counts of integers in the auxiliary array. Now scan the original array, rotating cycles! [Can someone word this more nicely?]