Microsoft Interview Question
InternsCountry: United States
Interview Type: Phone Interview
This question can be thought of as a specialized case of the generalized problem set :
Given a rod of length n, divide it into minimum number of parts such that you can generate a rod of each length from 1 to number n. For given n, 2^m<= n < 2^(m+1) , number of cuts will be m and hence numbers of parts will be m+1. In present case n=7 lies in the range [4,8), so number of cuts(divide/break) = 2 (It is true not only for 7 but all the numbers from 4 through 7) and parts = 1,2,4 (for 7).
Cut the bar Across the segment num-3 which will give u chain (1)-(2) ,, 3rd-segment and the rest (4)-(5)-(6)-(7) ....
1st day-give 3rd segment
2nd day-give chain 1-2 and get 3rd segment
3rd day(u have 3rd and chain 4-5-6-7): so give 3rd segment
4th day:give chain 4---7 and get 3rd and chain 1-2
5th day u have(3rd and chain1-2):so give 3rd segment
6th day- give chain 1-2 and get back 3rd segment
7th day: Give 3rd segment
this is just like counting in binary base.
notice that for 7 days we need log(7) (rounded upwards)= 3 parts. each of those parts will be represented by a binary bit.
the smallest part (1) is the LSB, the largest part (4) is the MSB.
where the number 000 represents that the emplyee has 0 of the fisrt part(which is of size 2^0=1), zero of the second part(which is of size 2^1=2) and zero of the third part(which is 2^2 = 4). respectively, on the seventh day of the week the employee will have all parts, so the binary number will be 111. during the days of the week, the emplyee will have an increacng amount of parts like a binary counter: 000,001,010,011,100,101,110,111.
the first bit is 1 iff the emplyee has part1. the second bit is 1 iff the employee holds that second part (2). the third bit (which is the MSB) is 1 iff the employee holds the third part.
it made it easier for me to think about it that way. hopefully to you too.
You break the bar so that you get 1 peace, 2 peaces and 4 peaces.
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> November 16, 2013**** | ** | *
first day you give 1 peace
2dn you give the one with 2 and get back the other with only 1
3rd you give the 2 and 1
4.- you give the one with 4
5.- 4 & 1
6.- 4 & 2
7.- All