Samaresh
BAN USER- 0of 0 votes
AnswersCalculate the number of barber's shop in your city.
- Samaresh in India| Report Duplicate | Flag | PURGE
Microsoft Program Manager
Lets assume that there are 100,00,000 people in the city and each people go to barber shop once in a month. So in one month total 100,00,000 person's hair needs to be cut.
Not make assumption that 70% people go for hair cut in weekend i.e. saturday & sunday.
Hence in one month 70,00,000 person's hair needs to be cut. Similarly in one week 70,00,000/4 = 1,750,000 hair needs to be cut on Sat & Sun. So on Sat or Sunday total hair cuts = 875,000. Now lets say one barber cuts 50 hair in a day then total barber required = 875,000/50 = 175,00 approx. Not sure ans was correct or not. Interviewer did not get impressed from this.
So second answer given was lets say total diameter of the city is 50 KM and there should be at least one barber shop in each and every KM. So draw and circle having radius 25 and calculate the circumfrance. Then put barber shop at each KM on outer circumfrance of radius 50. so total number of barber shop = 2 * PI * r = (2 * 22/7 * 50/2 -1).
Again draw another circle inside the bigger one of radius 24 and calculate the barber's shop = ( 2* 22/7 * 24 -1). Now keep on doing till center.
Finally you will get sum as.
So total barber shop = (2*22/7*25 -1) + (2*22/7*24 -1) + (2*22/7*23 -1).......................+1
But interviewer was not impressed from this ans also and got rejected in the first round. This was the only question what i faced in 1st round and returned back empty.
Best ans coming to my mind is.
- Samaresh September 04, 20121. Fist create an bit array of size(n) equal to max element of the input arrary and reset the array with all zeros.
2. Process input array elements and set the corresponding index of the array to 1 for each element.
3. now get the first element say k from the array at zeroth index.
4. Check for (n-k)th index in new array whether it is set or not.
5. If (n-k)th index is set then you get the element.
Thats it.