Microsoft Placement Papers

[Kalyan]

Microsoft Placement Papers

Networks and Security

1. How do you use RSA for both authentication and secrecy?

2. What is ARP and how does it work?

3. What's the difference between a switch and a router?

4. Name some routing protocols? (RIP,OSPF etc..)

5. How do you do authentication with message digest(MD5)? (Usually MD is used for finding tampering of data)

6. How do you implement a packet filter that distinguishes following cases and selects first case and rejects second case.

i) A host inside the corporate n/w makes a ftp request to outside host and the outside host sends reply.

ii) A host outside the network sends a ftp request to host inside. for the packet filter in both cases the source and destination fields will look the same.

7. How does traceroute work? Now how does traceroute make sure that the packet follows the same path that a previous (with ttl - 1) probe packet went in?

8. Explain Kerberos Protocol ?

9. What are digital signatures and smart cards?

10. Difference between discretionary access control and mandatory access control?
Java

1. How do you find the size of a java object (not the primitive type) ?

ANS. type cast it to string and find its s.length()

2. Why is multiple inheritance not provided in Java?

3. Thread t = new Thread(); t.start(); t = null; now what will happen to the created thread?

4. How is garbage collection done in java?

5. How do you write a "ping" routine in java?

6. What are the security restrictions on applets?
Graphics

1. Write a function to check if two rectangles defined as below overlap or not. struct rect { int top, bot, left, right; } r1, r2;

2. Write a SetPixel(x, y) function, given a pointer to the bitmap. Each pixel is represented by 1 bit. There are 640 pixels per row. In each byte, while the bits are numbered right to left, pixels are numbered left to right. Avoid multiplications and divisions to improve performance.
Databases

* 1. You, a designer want to measure disk traffic i.e. get a histogram showing the relative frequency of I/O/second for each disk block. The buffer pool has b buffers and uses LRU replacement policy. The disk block size and buffer pool block sizes are the same. You are given a routine int lru_block_in_position (int i) which returns the block_id of the block in the i-th position in the list of blocks managed by LRU. Assume position 0 is the hottest. You can repeatedly call this routine. How would you get the histogram you desire?

Hints and Answers

1. Simply do histogram [lru_block_in_position (b-1)] ++ at frequent intervals... The sampling frequency should be close to the disk I/O rate. It can be adjusted by remembering the last block seen in position b. If same, decrease frequency; if different, increase, with exponential decay etc. And of course, take care of overflows in the histogram.
Semaphores

1. Implement a multiple-reader-single-writer lock given a compare-and-swap instruction. Readers cannot overtake waiting writers.

[sajiv]

Aptitude Paper :

Algorithms & Coding : Microsoft Examination Papers

(Avg. of 25 ) : You have b boxes and n dollars. If I want any amount of
money from 0 to n dollars, you must be able to hand me 0 to b boxes so
that I get exactly what I request." The two questions were "What are
the restrictions on b and n, and how is money distributed among the
boxes?

(Avg. of 49 ) : What is the sum of the numbers from 1 to 1000?

(Avg. of 39 ) : You are an employer. You have ten employees. Each
month, each one of your ten employees gives you ten bags of gold. Each bag
of gold has ten pieces of gold in it. Each piece of gold weighs one
pound. One of your employees is cheating you by only putting nine pieces of
gold in each of his ten bags of gold. You have a scale (not a balance,
a scale), and you can only take one measurement from the scale, only
one (1) reading.

How can you tell which of the ten employees is cheating you by using
this scale and only taking one measurement?

(Avg. of 38 ) : How many points are there on the globe where by walking
one mile south, one mile east and one mile north you reach the place
where you started.

(Avg. of 23 ) : How would go about finding out where to look for a book
in a library? (You do not know how the books are organized beforehand)

(Avg. of 25 ) : Imagine you are standing in front of a mirror, facing
it. Raise your left hand. Raise your right hand. Look at your
reflection. When you raise your left hand your reflection raises what appears to
be his right hand. But when you tilt your head up, your reflection does
too, and does not appear to tilt his/her head down. Why is it that the
mirror appears to reverse left and right, but not up and down?

(Avg. of 21 ) : You have a bucket of jelly beans. Some are red, some
are blue, and some green. With your eyes closed, pick out 2 of a like
color. How many do you have to grab to be sure you have 2 of the same?

(Avg. of 18 ) : You are given a scale which you are to use to measure
eight balls. Seven of these balls have the same weight: the eigth ball
is heavier than the rest. What is the minimum number of weighs you could
perform to find the heaviest of the eight balls?. Remmber it's a scale
not a balance. (i.e. It can just tell you if one side is heavier than
the other it can't give you the exact weight).

(Avg. of 13 ) : How would you design a toaster?

(Avg. of 10 ) : How would you design an universal remote control?

(Avg. of 22 ) : How would you design a clock for a blind person?

(Avg. of 30 ) : How many miles of road are there in the US

(Avg. of 64 ) : There are n couples attending a party. Each one shakes
hands with the persons he doesn't know. (Assuming each person knows
his/her partner) Mary and John are a couple. John asked the rest of the
party-attenders how many times he has shaken hands. Each one gives a
unique answer. How many times does Mary shake hands?

[sajiv]

      Databases : Microsoft Examination Papers

      What are two methods of retrieving SQL?

      (Avg. of 588 ) : What cursor type do you use to retrieve multiple
      recordsets?

      (Avg. of 35 ) : What action do you have to perform before retrieving
      data from the next result set of a stored procedure?

      (Avg. of 36 ) : What is the basic form of a SQL statement to read data
      out of a table?

      (Avg. of 29 ) : What structure can you have the database make to speed
      up table reads?

      (Avg. of 16 ) : What is a "join"?

      (Avg. of 17 ) : What is a "constraint"?

      (Avg. of 11 ) : What is a "primary key"?

      (Avg. of 11 ) : What is a "functional dependency"? How does it relate
      to database table design?

      (Avg. of 15 ) : What is a "trigger"?

      (Avg. of 7 ) : What is "index covering" of a query?

      (Avg. of 42 ) : What is a SQL view?