MICROSOFT,GOOGLE,DESHAW

DESHAW PAPER

2007-05-07T05:36:00.000-07:00

This paper comprises of an Aptitude test and C-language test
Aptitude-20 questions (2 marks each)
C-language - 20 questions(3 marks each)
******************************************
APTITUDE TEST
20 QUESTIONS;2 MARKS EACH
TIME-20MINUTES
1) ONE RECTANGULAR PLATE WITH LENGTH 8INCHES,BREADTH 11
INCHES AND 2 INCHES THICKNESS IS THERE.WHAT IS THE LENGTH
OF THE CIRCULAR ROD WITH DIAMETER 8 INCHES AND EQUAL TO
VOLUME OF RECTANGULAR PLATE?
ANS: 3.5INCHES
2) WHAT IS THE NUMBER OF ZEROS AT THE END OF THE PRODUCT
OF THE NUMBERS FROM 1 TO 100
3) in some game 139 members have participated every time
one fellow will get bye what is the number of matches to
choose the champion to be held?
ans: 138
4) one fast typist type some matter in 2hr and
another slow typist type the
same matter in 3hr. if both do combinely in how much time
they will finish.
ans: 1hr 12min
5) in 8*8 chess board what is the total number of squares
refer odel
ans:204
6) falling height is proportional to square of the time.
one object falls 64cm in 2sec than in 6sec from how much
height the object will fall.
7) gavaskar average in first 50 innings was 50 . after the 51st
innings his average was 51 how many runs he made in the 51st
innings
8) 2 oranges,3 bananas and 4 apples cost Rs.15 . 3 ornages
2 bananas 1 apple costs Rs 10. what is the cost of 3 oranges,
3 bananas and 3 apples
ans Rs 15.
9)in 80 coins one coin is counterfiet what is minimum number of
weighings to find out counterfiet coin
10)in a company 30% are supervisors and 40% employees are male
if 60% of supervisors are male. what is the probability
that a randomly choosen employee is a male or female?
11)statement: all green are blue are blue, all blue are white
conclusion:
I) some blue are green II) some white are green
III)some green are not white IV) all white are blue
a) he has given four choices like gre type
12)all teachers are students. some students are girls.
this type of questions are there.
we cant able to reproduce them.

D.E.shaw 1997
SECTION B (all multiple choices)
(each q carries 3 marks)
1.while((*p++=*q++)!=0){}
is equal to
a) b) c) d)
2.the function strcmp(str1,str2) returns
3. int *x[](); means
4.#define PRINT(int) printf("int=%d",int);
main()
{
int x,y,z;
x=03;y=-1;z=01;
PRINT(x^x);
z<<=3;PRINT(x);
y>>=3;PRINT(y);
}
5. struct list{
int x;
struct list *next;
}*head;
the struct head.x =100
above is correct / wrong
6. '-'=45 '/'=47
printfr(%d/n,'-','-','-','-','/','/','/');
o/p =?
12.o/p=?
int i;
i=1;
i=i+2*i++;
printf(%d,i);
8.{ ch='A';
while(ch<='F'){
switch(ch){
case'A':case'B':case'C':case'D':ch++;continue;
case'E':case'F':ch++;
}
putchar(ch);
}
} a)ABCDEF b.EFG c.FG d.error
9. FILE *fp1,*fp2;
fp1=fopen("one","w")
fp2=fopen("one","w")
fputc('A',fp1)
fputc('B',fp2)
fclose(fp1)
fclose(fp2)}
a.error b. c. d.
10. int a=1; b=2; c=3; *pointer;
pointer=&c;
a=c/*pointer;
b=c;
printf("a=%d b=%d",a,b);
a. a=1 b=3
b a=3 b=3
c 3 2
d. error
11.#include
char *f()
{
char *s=malloc(8);
strcpy(s,"goodbye")
}
main()
{
char *f()_;
printf("%c",*f()='A');
}
o/p=?
13. int sum(n)
int n;
if(n<1)return n;
else return(n+sum(n-1))
a 10 b 16 c 14 d 15
14. when a function is recursively called all ,
automatic variables are a. stored in stack b . c. d
15) #define MAN(x,y) (x)>(y)?(x):(y)
{ int i=10;j=5;k=0;
k= MAN(i++,++j)
printf(%d %d %d %d,i,j,k)
}
16) a=10;b=5; c=3;d=3;
if(a < b)&&(c=d++)
printf(%d %d %d %d a,b,c,d)
else printf("%d %d %d %d a,b,c,d);

19. what is o/p
#include
show(int t,va_list ptr1)
{
int a,x,i;
a=va_arg(ptr1,int)
printf("\n %d",a)
}
display(char)
{int x;
listptr;
va_star(otr,s);
n=va_arg(ptr,int);
show(x,ptr);
}
main()
{
display("hello",4,12,13,14,44);
}
a) 13 b) 12 c) 44 d) 14
.........................

17. if the following program (my prog)
main(int size of ,char *arg[])
{ while(size of arg) printf("%s",arg[--size of arg)
}
is run from the command line as myprog jan feb mar apr
what would be the o/p
a)myprog jan,feb,mar,apr
b)rev
c)jan,feb,mar,apr
d)error
.......................

18.what is o/p
main()
{int i=3;
while(i--)
{
int i=100
i--;
printf("%d..",i);
}
}
a) infinite loop
b) error
c) 99..99..99..99
d) 3..22..1..
..........................
20)what is the o/p of the program
main()
{
int rows=3,colums=4;
int a[rows][colums]={1,2,3,4,5,6,7,8,9,10,11,12};
i=j=k=99;
for(i=0;i < rows;i++)
for(j=0;j < colums;j++)
if(a[k][j] < k) k=a[i][j];

printf("%d\n",k);

DESHA @ IITKGP 1997

2007-05-07T05:30:00.000-07:00

PART 1 TIME:20 MIN
* 20 QUESTIONS , EACH QUESTION CARRIES 2 MARKS

1. A SOLID ICE OF 11 X 8 X2 INCHES IS MADE INTO ROD OF DIA 4 INCH. WHAT
IS THE LENGE OF ROD?

ANS: 3.5 INCH

2. THERE WERE 750 PEOPLE WHEN THE FIRST SONG WAS SUNG. AFTER EACH
SONG 50 PEOPLE ARE LEAVING THE HALL. HOWMANY SONGS ARE SUNG TO MAKE
THEM ZERO?

ANS:16

3. A PERSON IS CLIMBING OF 60 MTS . FOR EVERY MINUTE HE IS CLIMBING 6 MTS
AND SLIPPING 4 MTS . AFTER HOWMANY MINUTES HE MAY REACH THE TOP?

ANS: (60-6)/2 +1 :28

4. HOWMANY ZEROS ARE THERE IN THE PRODUCT OF THE INTEGER FROM 1TO 100?

ANS: 24( NOT GIVEN)

1 TO 10 -2 ZEROS
21 TO 30 -3 ZEROS : BECAUSE 25 = 5*5
22 *5
24 *5

5. A CAN DO WORK IN 2 HOURS B CAN DO A WORK IN 3 HOURS WHAT IS THE
SHORTEST TIME TYEY CAN FINISH THE WORK?

ANS: 1HOUR 12 MIN.

6..SALARY IS INCREASED BY 1200 ,TAX IS DECREASED FROM 12% TO 10% BUT PAYING
SAME AMOUNT AS TAX . WHAT IS THE PREVISIOUS SALARY?

ANS:6000

7. THE LEAST NO. WHICH IS WHEN DEVIDED BY 4,6,7 LEAVES A REMAINDER OF 2 ?

ANS: 86

8. A MAN DRIVING THE CAR AT TWICE THE SPEED OF AUTO ONEDAY HE WAS DRIVEN
CAR FOR 10 MIN. AND CAR IS FAILED. HE LEFT THE CAR AND TOOK AUTO TO GOTO
THE OFFICE . HE SPENT 30 MIN. IN THE AUTO. WHAT WILL BE THE TIME TAKE BY
CAR TO GO OFFICE?

ANS:25 MIN

9. A REPORT HS 20 WHEETS, EACH OF 55 LINES AND EACH SU;CH A LINE CONSISTS
OF 65 CHARACTERS. IF THE REPORT HAS TO BE RETYPED WITH EACH SHEET HAVING 65
LINES AND EACH LINE HAVE 75 CHARACTERS, THE PERCENTAGE OF REDUCTION OF
NO OF SHEETS IS CLOSEST IS TO?

ANS: 25%

10. OUT OF 100 FAMILIES IN NEIGHBOUR HOOD , 55 OWN RADIO, 75 OWN T.V
AND 25 OWN VCR. ONLY 10 FAMILIES HAVE ALLOF THESE, AND EACH VCR OWNER
HAS TV . IF 25 FAMILIES HAVE THE RADIO ONLY, THE NO. OF FAMILIES HAVE
ONLY TV ARE?

ANS: 30

APTITUDE: ( QUESTIONS 16 T019)

KYA KYA IS AN ISLAND IN THE SOUTH PACIFI . THE INHABITANTS OF KYA KYA
ALWAYS ANSWER ANY QUESTION WITH TWO SENTENCES, ONE OR WHICH IS ALWAYS
TRUE AND OTHER IS ALWAYS FALSE.

1. YOU ARE WALKING ON THE ROAD AND COME TO A FORK. YOU ASK ,THE INHABITANTS
RAM.LAXMAN, AND LILA AS" WHICH ROAD WILL TAKE ME TO THE VILAGE?

RAM SAYS: I NEVER SPEAK TO STRANGERS. IAM NEW TO THIS PLACE
LAXMAN SAYS: IAM MARRIED TO.LILA. TAKE THE LEFT ROAD
LILA SAYS: IAM MARRIED TO RAM. HE IS NOT NEW TO THIS PLACE

ANS: LEFT ROAD TAKE YU TO THE VILLAGE

2. YOU FIND THAT YOUR BOAT IS STOLLEN. U QUESTIONED THREE INHABITANTS OT
ISLANDS AND THEIR REPLIES ARE

JOHN : I DIDNOT DO IT. MATHEW DIDNOT DO IT
MATHEW : I DIDNOT DO IT. KRISHNA DIDNOT DO IT
KRISHNA: I DID NOT DO IT; I DONOT KNOW WHO DID IT

ANS: MATHEW STOLEN THE BOAT

3. YOU WANT TO SPEAK TO THE CHIEF OF VILLAGE , U ASK THREE FELLOWS AMAR
BOBBY, CHARLES AND BOBBY IS WEARING RED SHIRT

AMAR : IAM NOT BOBBY`S SON ; THE CHIEF WEARS RED SHIRT
BOBBY : IAM AMARS FATHER ; CHARLES IS THE CHIEF
CHARLES : THE CHIEF IS ONE AMONG US; IAM THE CHIEF

ANS: BOBBY IS THE CHIEF

4. THERE IS ONLY OPNE POLOT IN THE VILLAGE(ISLAND). YOU INTERVIEWED THREEM MAN
KOISK ,LORRY AND MISHRA
U ALSO NOTICE THAT KOISK IS WEARING CAP.

M SAYS : LARRY IS FATHER IN THE PILOT .LARRY IS NOT THE PRIESTS SON
KOISK : IAM THE PRIEST ON THEIS ISLAND ONLY PRISTS CAN WEAR THE CAPS
LARRY : IAM THE PRIEST SON . KOISK IS NOT THE PREST

ANS : KOISK IS THE PILOT

THIS PAPER HAS GIVEN IN IIT DELHI , SO GO THROUGH THIS IT WILL GIVE
ROUGH IDEA;

1. typedef struct{
char *;
nodeptr next;
} * nodeptr;
what does nodeptr stand for?

2. supposing thaty each integer occupies 4 bytes and each charactrer
1 byte , what is the output of the following programme?

#include
main()
{
int a[] ={ 1,2,3,4,5,6,7};
char c[] = {' a','x','h','o','k'};
printf("%d\t %d ", (&a[3]-&a[0]),(&c[3]-&c[0]));
}
ans : 3 3

3. what is the output of the program?

#include
main()
{
struct s1 {int i; };
struct s2 {int i; };
struct s1 st1;
struct s2 st2;
st1.i =5;
st2 = st1;
printf(" %d " , st2.i);
}

ans: nothing (error)
expl: diff struct variables should not assigned using "=" operator.

4.what is the output of the program?

#include
main()
{
int i,j;
int mat[3][3] ={1,2,3,4,5,6,7,8,9};
for (i=2;i>=0;i--)
for ( j=2;j>=0;j--)
printf("%d" , *(*(mat+j)+i));
}

ans : 9 6 3 8 5 2 7 4 1

5.

fun(n);
}
int fun( int n)
{
int i;
for(i=0;i<=n;i++)
fun(n-i);
printf(" well done");

}
howmany times is the printf statement executed for n=10?

ans: zero
expl: Befire reaching to printf statement it will goes to infinite loop.

6.what is the output of the program?

main()
{
struct emp{
char emp[];
int empno;
float sal;
};
struct emp member = { "TIGER"};
printf(" %d %f", member.empno,member.sal);

ans: error. In struct variable emp[], we have to give array size.
If array size given
ans is 0, 0.00

7. output of the program?

# define infiniteloop while(1)
main()
{
infiniteloop;
printf("DONE");
}

ans: none
expl: infiniteloop in main ends with ";" . so loop will not reach end;
and the DONE also will not print.

8. output of the program?

main()
{
int a=2, b=3;
printf(" %d ", a+++b);
}

ans:5
expl: here it evaluates as a++ + b.

9. output of the program?

#define prn(a) printf("%d",a)
#define print(a,b,c) prn(a), prn(b), prn(c)
#define max(a,b) (a < b)? b:a

main()
{
int x=1, y=2;
print(max(x++,y),x,y);
print(max(x++,y),x,y);
}

ans: 3 4 2

10. which of the following is the correct declaration for the function main() ?

ans: main( int , char *[])

11. if ptr is defined as

int *ptr[][100];
which of the following correctly allocates memory for ptr?

ans: ptr = (int *)(malloc(100* sizeof(int));

FEW MORE PROGRAMS HERE BUT NOT AVAILABLE:

DESHA PAPER 2

2007-05-07T05:29:00.001-07:00

1)minimum #of ip addresses requiered for an router
ans)2
2)the worst case booth complexity for
ans)101010101010101010
3)disadvantage of pcm
ans)forgot
4)two binary 8bits are added overflow will come for
a)ones complement
b)twos complement
c)ones complement with signed magnitude
c)twos complement with signed magnitude
5)two 8 bit nuos are multiplied and the result is stored in an rom the size
of the rom is
ans)64*64 doubt
6)how many no of 4x1 muxs are required for making an 16x1 mux
ans)5
7)a simple nand gate problem
ans)simple
8)the shannon hartley therom give the
ans)channel capacity with no error
9)the bandwidth for 500bps is
ans)1000bps doubt
10)a problem with lower triangular matrix
ans)x[i]=b[i]-a[i][j]*x[i]
11)a c program with
if x>y
x=x-y
else
y=y-x
ans)gcd
12)microwave propogation along the curvature of earth is called
ans)ductpropogation
13)a simple bit on recurssion

14)csma/cd is used in
ans)ethernet
15)what is used for knowing its own ip address
ans)rarp
16)no signalling is needded to establish connection in
ans ) ip
17)a simple problem, on newton rapshon method
18)(A-B)U(B-A)U(AnB)=
ANS)AUB
19)
if a number is choosen between 100 and 999 includeing these numberrs what is the provbabilty that the number selected does not contain a 7 is
ans)workitout
20)a packet trabvelling in the internet forever can be controlled by having the field
ans)time to live (ttl)
21)c code with the follwing choices
a)call with value
b)call with address
c)call with value result
ans)call with value result
22) when the following sequence is inserted in the binary search tree no of nodes int left subtree and right sub tree is
ans )7,4
23)simple problem in recurssion
x(x(5))
ans)17
24)study about reentrant code reusable code recursive code
25)given edges nodes and components of a graph find out its rank
26)in a tree a parent is greater than all its children in folling
ans)heap
27)question on pcm signal=3khz 8levels are used
ans)18000bps
28)to get the numberr in ascending order the traversal used is
ans)inorder traversal
29)a problem in multiprocessing ,multithreading ,multiprogramming
ans)multithreading

DESHAW PAPER

2007-05-07T05:26:00.000-07:00

SECTION-A

you should write the programs for the following problems in C.

1. swapping two variables x,y without using a temporary variable.
2. a program has been given asking to find the output
ans. it is algorithm for finding G.C.D
3. write a program for reversing the given string.
4. the integers from 1 to n are stored in an array in a random
fashion. but one integer is missing. write a program to find the
missing integer.
ans. idea. the sum of n natural numbers is = n(n+1)/2.
if we subtract the above sum from the sum of all the
numbers in the array , the result is nothing but the
missing number.
5. some bit type of questions has been given on pointers asking to
to find whether it is correct from syntax point of view. and if
it is correct explain what it will do.(around 15 bits).

SECTION-B

ANSWER AS MANY AS POSSIBLE.

6.& 7. two programs on pre-processor directions has been given asking
to find the output.
8. simple question given on pointer
a) kernighan & richie page no. 122
b) schaum series page no. 323
try to understand the pointer problems given here he asked to
explain
in the interview if answer it in exam.
9. write a c program to find whether a stack is progressing in forward
or reverse direction.
10. write a c program that reverses the linked list.

GUIDELINES:
the interview is very tough he is asking to do the problems in
front of him. he is also giving some new problems to solve before
him.
you should have a very good funda of C language.

-----------------------------------------------------------------------
P . V . THATAYYA NAIDU
M.S ( CS) Hostel : 91-044-2351326
Research Scholar (PP: #341 Naidu)

341, BrahmaPutra Hostel Infotech Lab : 91-044-2351365
IIT MADRAS - 600036 ext:3529/3530
INDIA
EMAIL : naidu@indy.iitm.ernet.in
naidu%bronto@iitm.ernet.in
-----------------------------------------------------------------------

DESHAW 99

2007-05-07T05:25:00.000-07:00

> Deshaw99(WILCO99)
>
>
> THERE ARE THREE SECTIONS:
>
> SECTION A: APPITUDE TEST 20 BITS
> SECTION B: C BITS 20 BITS
> SECTION C: 1 QUESTION (NOT A BIT)
> IT IS LONG ANSWER
> THE QUESTION IS:FIND THE NEXT PERMUTATION IN
> LEXICOGRAPHIC
> ORDER FROM THE GIVEN PERMUTATION
>
> NOTE: MAXIMUM QUESTIONS ARE FROM OLD QUESTION PAPERS
> SECTION A:
>
> 1. THERE WERE 750 PEOPLE WHEN THE FIRST SONG WAS
> SUNG. AFTER EACH
> SONG 50 PEOPLE ARE LEAVING THE HALL. HOWMANY SONGS
> ARE SUNG TO MAKE
> THEM ZERO?
>
> ANS:16
>
> SECTION B:
>
> 1. typedef struct{
> char *;
> nodeptr next;
> } * nodeptr;
> what does nodeptr stand for?
>
>
> 2. 2 oranges,3 bananas and 4 apples cost Rs.15 . 3
> ornages 2 bananas
> 1 apple costs Rs 10. what is the cost of 3 oranges,
> 3 bananas and
> 3 apples ANs Rs 15.
>
>
> 3. int *x[](); means
> expl: Elments of an array can't be functions.
>
> 4. struct list{
> int x;
> struct list *next;
> }*head;
> the struct head.x =100
> above is correct / wrong
>
>
> expl: Before using the ptr type struct variable we
> have to give memory
> to that .
> And also when ever the struct variable is ptr then
> we access the
> members
> by "->" operator.
>
>
>
>
> 5.o/p=?
> int i;
> i=1;
> i=i+2*i++;
> printf(%d,i);
> ans: 4
>
> 6. FILE *fp1,*fp2;
> fp1=fopen("one","w")
> fp2=fopen("one","w")
> fputc('A',fp1)
> fputc('B',fp2)
> fclose(fp1)
> fclose(fp2)}
> a.error b. c. d.
> ans: no error. But It will
> over writes on same
> file.
>
>
> 7.#include
> char *f()
> {char *s=malloc(8);
> strcpy(s,"goodbye")}
> main()
> {
> char *f();
> printf("%c",*f()='A');
> o/p=?
>
>
> 8) #define MAN(x,y) (x)>(y)?(x):(y)
> { int i=10;j=5;k=0;
> k= MAX(i++,++j)
> printf(%d %d %d %d,i,j,k)}
> 9) a=10;b=5; c=3;d=3;
> if(a> printf(%d %d %d %d a,b,c,d)
> else printf("%d %d %d %d a,b,c,d);
>
> : .............................................
> 10. what is o/p
> #include
> show(int t,va_list ptr1)
> {
> int a,x,i;
> a=va_arg(ptr1,int)
> printf("\n %d",a)
> }
> display(char)
> {int x;
> listptr;
> va_star(otr,s);
> n=va_arg(ptr,int);
> show(x,ptr);
> }
> main()
> {
> display("hello",4,12,13,14,44);
> }
> a) 13 b) 12 c) 44 d) 14
> .............................................
>
>
> 11.main()
> {
> printf("hello");
> fork();
> }
>
>
> 12.main()
> {
> int i = 10;
> printf(" %d %d %d \n", ++i, i++, ++i);
> }
>
>
> 13.#include
> main()
> {
> int *p, *c, i;
> i = 5;
> p = (int*) (malloc(sizeof(i)));
> printf("\n%d",*p);
> *p = 10;
> printf("\n%d %d",i,*p);
> c = (int*) calloc(2);
> printf("\n%d\n",*c);
> }
>
> 14.#define MAX(x,y) (x) >(y)?(x):(y)
> main()
> {
> int i=10,j=5,k=0;
> k= MAX(i++,++j);
> printf("%d..%d..%d",i,j,k);
> }
>
> 15.#include
> main()
> {
> enum _tag{ left=10, right, front=100, back};
> printf("left is %d, right is %d, front is
> %d, back is
> %d",left,right,front,back);
> }
>
> 16.main()
> {
> int a=10,b=20;
> a>=5?b=100:b=200;
> printf("%d\n",b);
> }
>
>
>
>
> 17.#define PRINT(int) printf("int = %d ",int)
> main()
> {
> int x,y,z;
> x=03;y=02;z=01;
> PRINT(x^x);
> z<<=3;PRINT(x);
> y>>=3;PRINT(y);
> }

GOOGLE RECRUITMENT PROCESS

2007-05-07T04:58:00.000-07:00

---------------------------- Original Message ----------------------------
Subject: Google recruitment process... (fwd)
From: "Pemmaraju Rama Krishna;04410118;" Date:
Fri, May 19, 2006 12:51 am
To: "K NARENDRA;05410127"
--------------------------------------------------------------------------
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
LEARN FROM UR EXPERIENCES
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

---------- Forwarded message ----------
Date: Sun, 27 Nov 2005 14:46:36 +0530 (IST)
From: "M Thirumala Reddy;04410114;"
To: cse04m@iitg.ernet.in
Subject: Google recruitment process...

Hi Friends,

Here I am forwarding a mail written by my friend about Google interview.

She is a comp.sci university gold medalist from a
reputed university in Haryana and currently doing M.E in BITS. She could
make till the final round of Google. She has an offer from Cisco.

They have signed a non-disclosure agreement, so she gave a brief interview
questions and pattern (may not be exactly the same ...).

regards..,
Thirumal.

---------- Forwarded message ----------

hi,

regarding the process,they had a written test,first,20 questions,mostly
from datastructures...20 multiple choice & one algo to be written..

then,we has two inteviews here.those were also related toDS.something bout
projects they asked...

then we has four more innterviews in bagalore, all of them were for
knowing ur approch towards a problem...

so this was the whole process...

regarding test questins, idon't remember all.but some were like
1. complwxity of which sort is best for sotes arrray..how much
2. how many swaps needed for insertiion sort..
3.in a party, if n pople, everyone shakes hand with every other,how many
handshakes.
4. some questions on probability...

all the questions were easy, don't worry for them...
algoo that we were supposed towrite was...
if given a treee,find the hightest node of it..binary search tree was given.

in interview, questions on linked list,like reversal, sortinf,hair
&tortoise problem.
test cases for website development. array soorting in less tahn o(nlgn).
c++ abstract class,virtual polymorphism,hybrid inheritance,destuctors
overriding, etc...

problem solving included if u r to store all the web pages for easy
retrievalk.how will u store,
rows, column sum equal problem.
convert a link list into tree, gen questions on networking....

that is allwot i remember at this time...

say all the best to all of ur friends from my side too..,

take care.

BYE

MICROSOFT 2006

2007-05-07T04:53:00.000-07:00

---------------------------- Original Message ----------------------------
Subject: Microsoft Test and Interview .... (fwd)
From: "Pemmaraju Rama Krishna;04410118;"
Date: Fri, May 19, 2006 12:51 am
To: "K NARENDRA;05410127"
--------------------------------------------------------------------------
REAL HAPPINESS LIES IN MAKING OTHERS HAPPY
P.RAMA KRISHNA,
ROOM NO:009,
SIANG HOSTEL,
IIT GUWAHATI,
GUWAHATI-781039,
ASSAM.
Ph no : 09954211409

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
LEARN FROM UR EXPERIENCES
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
---------- Forwarded message ----------
Date: Sun, 18 Dec 2005 20:06:39 +0530 (IST)
From: "M Thirumala Reddy;04410114;"
To: cse04m@iitg.ernet.in
Subject: Microsoft Test and Interview ....

hi friends,
this was the paper asked by MS at NIT Warangal
recently. they took 6 guys frm there.

all the best.

Paper :

To start with, we had a written test for 1 and a half
hours.
Round 1 : Written Test
In total there were 6 questions:1st three of 4 marks &
next 3 for 6
marks.
1) Output was to be given for a program which
had a
recursive
function..simple one....well there was a catch as (int
i = 96573) was given.
We must know the size of the integer on the machine &
then answer
accordingly.
2) An incorrect program was given. We had to
find the
bugs.......there
were four bugs....the most important one was: a
locally defined char
array was being returned....which is not allowed....
3)There is an array A(MXN).......it is rotated
clockwise and then
shifted row-wise with wrap-around to get the array
B(NXM)......an example
was shown.....we have to just give a formula in one
line for A[i][j] =
B[......][.......]. Assume that the boundaries of an
array are from 0 to
M-1 as usual. Frankly speaking I got stuck in this
formula after
completing the 1st 2 ques in 15 min....but finally it
was a very cool
answer... [(j+1)%N][(i+1)%M]...
4)You are given a linked list of numbers:
1-6-3-9-7-54. U will be
given an input - 'n'. You have to insert 0 after every
nth element in the
list. For example if n=2, then o/p:
1-6-0-3-9-0-7-54-0. U must give the
best complexity algo to get thro'
5)Write the various test cases for Q4. How does
ur
program handle
them? I gave abt 5 test cases (obviously meaningful)..
6)There is a document containing words. A fn
'getNextWord' returns
next word in the document, u have to count the number
of occurences of
each word in the document.
a)What data structure will u choose ?
b)Write the algorithm to buid the database,i.e
the
complete account of
the frequency of each word?
c)What is the time complexity of your algorithm?

We had abt 63 ppl sitting for the test..24 got
shortlisted..
Round 2( by Padmapriya):
Now, we were divided into 3 groups of 8 each. There
were 3
interviewers. Each was assigned a group. 3 questions
were shown on the projector
one by one. I suppose we were given ample time to
solve each of them. We
had to solve them and the interviewer assigned to the
grp talked with
us...basically an interview.
1) 3 buckets. 1 contains apples, 1 contains
oranges,
1 contains apples
& oranges. All are wrongly labelled. U r allowed to
pick 1 fruit from 1
basket. What will u do to identify all the baskets
correctly.
2)There is an array containing R, G, B. Write a
program to get all the
R's, G's & B's together. For example: i/p:
RGBBBGGRRGB;;;;;o/p:
RRRBBBBGGGG....it was a simple one....but frnds u need
to go for just 1 pass &
use least space to earn points.
3)U r given two sorted arrays:----A & B. B
contains
enough extra
spaces at the end to store all the elements of A.
Merge A with B...without
removing duplicates.
for ex: A: 1 3 5 7 ;;; B: 4 5 8 X X X X ;;; X stands
for empty space.
o/p: B: 1 3 4 5 5 7 8 ;;;;;
Frnds u hv to give the best algo here too..........
Test cases were asked for every algo.

Out of 24, 14 went thro this round.....

Round 3(Tech Interview by Govind):
Asked abt the Round 2 solutions....then gave 2
questions:
1) Write a fn: deletenth(node *l, int n). This
function deletes every
nth element in the list...A simple one(he told
me)...just allowed 1
pass.... Govind told me to check the code and then
only show it to
him...he wanted error-free, damn best, fast written
algo. I gave him the
best....got impressed...
2)Write a class bit....It contains two
functions:
bool getBit(int n),
setBit(int n). The constructor is passed an integer n
that specifies
the number of bits to be handled.....setBit fn sets
the nth bit while
getBit fn returns the nth bit. Hint: Dont use an
element array to store
the bits...in fact use all the bits of the data type.

Round 4(Tech Interview by Niranjan Naik):
He asked abt the projects,favourite subject(mine is
OS)....if it is not
still he will anyhow ask ques on os....this part of
the interview was
basically tp. He posed just one ques:
1)There is a sorted array A. Now the elements in
the
array are shifted
(wrap-around) by 'n' positions to get the modified
array B. Write a
program which takes as input the modified array B and
outputs 'n'. ex: A:
1 3 5 7 9 11 14
B: 11 14 1 3 5 7 9
n = 2
I gave him 1 pass O(log n) algo. You have to
take
care that it
considers ALL the possible test cases.

I cleared just these many rounds to get hired. Some of
my clasmates had
to go thro' one more interview by govinda before being
hired.
In total 6 were hired.

Some of the ques asked to others:
1)There is a linked list containing nodes
that hv an
extra pointer
other than 'next' which points to any other node in
the list. You hv to
make a copy of such a list.
2)Remove duplicates from a list.

Well I beleive this is enough to give an overview of
the selection
process of MS.
My tips
Simple problems will be given and you must give the
best, error-free
solutions in terms of time complexity & space
complexity.
Best Of Luck.
--
Yours Friendly,
Thirumal.
Narendra.K
1st year M.Tech(CSE)
IIT Guwahati