Tuesday, October 19, 2010

Red Marbles, Blue Marbles

Problem: you have two jars, 50 red marbles, 50 blue marbles. you need to place all the marbles into the jars such that when you blindly pick one marble out of one jar, you maximize the chances that it will be red. (when picking, you’ll first randomly pick a jar, and then randomly pick a marble out of that jar) you can arrange the marbles however you like, but each marble must be in a jar.


Solution

Chance! chance is easy if you know how to do the formula. we know that we have two choices to make. first we’ll pick a jar, and each jar will have a 1/2 chance of being picked. then we’ll pick a marble, and depending how we stack the marbles, we’ll have a (# of red marbles in jar)/(# of total marbles in jar) chance of getting a red one.

for example, say we put all the red marbles into jar A and all the blue ones into jar B. then our chances for picking a red one are:

1/2 chance we pick jar A * 50/50 chance we pick a red marble
1/2 chance we pick jar B * 0/50 chance we pick a red marble

do the math and you get 1/2 chance for a red marble from jar A and a 0/2 chance for a red marble from jar B. add ‘em up and you get the result = 1/2 chance for picking a red marble.

think about it for awhile and see if you can figure out the right combination. we had a 50/50 (guaranteed) chance in picking a red marble from jar A, but we didn’t have to have 50 red marbles in there to guarantee those fantastic odds, did we? we could’ve just left 1 red marble in there and the odds are still 1/1. then we can take all those other marbles and throw them in jar B to help the odds out there.

let’s look at those chances:

1/2 we pick jar A * 1/1 we pick a red marble
1/2 we pick jar B * 49/99 we pick a red marble

do the math and add them up to get 1/2 + 49/198 = 148/198, which is almost 3/4.

we can prove these are the best odds in a somewhat non-formal way as follows. our goal is to maximize the odds of picking a red marble. therefore we can subdivide this goal into maximizing the odds of picking a red marble in jar A and maximizing the odds of picking a red marble in jar B. if we do that, then we will have achieved our goal. it is true that by placing more red marbles into a jar we will increase the chances of picking a red marble. it is also true that by reducing the number of blue marbles in a jar we will increase the odds also. we’ve maximized the odds in jar A since 1/1 is the maximum odds by reducing the number of blue marbles to 0 (the minimum). we’ve also maximized the number of red marbles in jar B. if we added any more red marbles to jar B we would have to take them out of jar A which reduce the odds there to 0 (very bad). if we took any more blue ones out of jar B we would have to put them in jar A which reduce the odds there by 50% (very bad).

it wasn’t really a good proof, but QED anyway :-P

100 Doors in a Row - Solution

Problem: you have 100 doors in a row that are all initially closed. you make 100 passes by the doors starting with the first door every time. the first time through you visit every door and toggle the door (if the door is closed, you open it, if its open, you close it). the second time you only visit every 2nd door (door #2, #4, #6). the third time, every 3rd door (door #3, #6, #9), etc, until you only visit the 100th door.

question: what state are the doors in after the last pass? which are open which are closed?
Solution

For example, after the first pass every door is open. on the second pass you only visit the even doors (2,4,6,8…) so now the even doors are closed and the odd ones are opened. the third time through you will close door 3 (opened from the first pass), open door 6 (closed from the second pass), etc..

question: what state are the doors in after the last pass? which are open which are closed?

solution: you can figure out that for any given door, say door #42, you will visit it for every divisor it has. so 42 has 1 & 42, 2 & 21, 3 & 14, 6 & 7. so on pass 1 i will open the door, pass 2 i will close it, pass 3 open, pass 6 close, pass 7 open, pass 14 close, pass 21 open, pass 42 close. for every pair of divisors the door will just end up back in its initial state. so you might think that every door will end up closed? well what about door #9. 9 has the divisors 1 & 9, 3 & 3. but 3 is repeated because 9 is a perfect square, so you will only visit door #9, on pass 1, 3, and 9… leaving it open at the end. only perfect square doors will be open at the end.

Reverse a String - Solution


Reverse a String

A typical programming interview question is “reverse a string, in place”. if you understand pointers, the solution is simple. even if you don’t, it can be accomplished using array indices. i usually ask candidates this question first, so they get the algorithm in their head. then i play dirty by asking them to reverse the string word by word, in place. for example if our string is “the house is blue”, the return value would be “blue is house the”. the words are reversed, but the letters are still in order (within the word).
Solution

Solving the initial problem of just reversing a string can either be a huge help or a frustrating hinderance. most likely the first attempt will be to solve it the same way, by swapping letters at the front of the string with letters at the back, and then adding some logic to keep the words in order. this attempt will lead to confusion pretty quickly.

for example, if we start by figuring out that “the” is 3 letters long and then try to put the “t” from “the” where the “l” from “blue” is, we encounter a problem. where do we put the “l” from “blue”? hmm… well we could have also figured out how long “blue” was and that would tell us where to put the “l” at… but the “e” from “blue” needs to go into the space after “the”. argh. its getting quite confusing. in fact, i would be delighted to even see a solution to this problem using this attack method. i don’t think its impossible, but i think it is so complex that it’s not worth pursuing.

here’s a hint. remember before when we just reversed “the house is blue”? what happened?
initial: the house is blue
reverse: eulb si esuoh eht

look at the result for a minute. notice anything? if you still don’t see it, try this.
initial: the house is blue
reverse: eulb si esuoh eht
wanted : blue is house the

the solution can be attained by first reversing the string normally, and then just reversing each word.

The Circular Lake Monster solution

For #1, how about row in a circle a bit smaller 1/4r in size. Since he won't be able to keep up with you, when he is on the opposite shore you can make a brake for it. You have r*3/4 to travel, but 4*3/4 is less then pi, so he won't be able to catch you in time




part 2: Assume x is the monster's speed. Then to get the circle trick to work, you row a circle a little less than 1/x of the radius, leaving you 1 - 1/x to row when he is opposite of you. If the monster can travel pi times the radius faster than you can travel the radius, you're hosed. In the time you travel 1 - 1/x, he'll travel x times that. Set that equal to pi, and you x * (1 - 1/x) = pi, which solves to x = pi + 1.

pi + 1 would be my guess for the speed that impossible to escape from, but I could be making an easy mistake.

Wednesday, January 6, 2010

Array of 0 and 1, put 0's at even position and 1's at odd position

you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY.

input array:
{0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 }
output array:
{0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 }

Thursday, May 15, 2008
 
 
This is similar to an implementation of partition method of quick sort.

oddInd==0;
evenInd=1;

while(true)
{
  while(oddInd
  if(oddInd>=strLen) break;
  while(evenInd
  if(evenInd>=strLen) break;
  swap(str[evenInd], str[oddInd]);
}

Well, one more challenging version of this problem is to consider an array containing 0s,1s and 2s and do the same thing. This question was asked in one microsoft internship interview.
jigsaw Send private email
Thursday, May 15, 2008
 
 
OOPS!!! There was a big mistake in the above code.
This is similar to an implementation of partition method of quick sort.

oddInd==0;
evenInd=1;

while(true)
{
  while(oddInd  if(oddInd>=strLen) break;
  while(evenInd  if(evenInd>=strLen) break;
  swap(str[evenInd], str[oddInd]);
}

Well, one more challenging version of this problem is to consider an array containing 0s,1s and 2s and do the same thing. This question was asked in one microsoft internship interview.
jigsaw Send private email
Thursday, May 15, 2008
 
 
Perish the thought that anyone should use extra memory!

BTW, the indexes into the array are extra memory.

Too many of these questions are isomorphic with:
"Oh, so you can type in your code?  How about if we tie one arm behind your back?  YANK!  Still typing?  How about if we keep hitting you with this baseball bat?  Whack, whack, whack!  Still at it, huh?  Well, at least we got him down to 2 WPM."

Sincerely,

Gene Wirchenko
Gene Wirchenko Send private email
Thursday, May 15, 2008
 
 
:) That's funny. BTW when he said extra memory, he meant variable amt of memory i guess.
jigsaw Send private email
Friday, May 16, 2008
 
 
That seems to be what they mean when they say no extra memory. Heck making a function call allocates a frame on the stack so does that mean no function calls either?

  I always took it to mean no building a data structure.  Which can be a  valid restriction if data is going to be changing often(high rebuild costs) or you have a truly large dataset. It can be hard to get a std::vector to hit 100mb if you already have a number of other 100mb chunks floating around.
soup
Friday, May 16, 2008
 
 
soup,

The usual complexity-theoretic definition of "no extra memory" is that the program can use a constant number of registers just large enough to index the input.
d
Friday, May 16, 2008
 
 
I tried JigSaw's solution in to java(http://pastebin.com/f41fe39d1). I might have mis-understood the code but the resulting array is
1 0 1 0 1 0 1 0 1 0  1  0  1  0  1  1
ved Send private email
Monday, May 26, 2008
 
 
I think there is a problem in jigsaw's solution.His solution says:
oddInd==0;
evenInd=1;

while(true)
{
  while(oddInd  if(oddInd>=strLen) break;
  while(evenInd  if(evenInd>=strLen) break;
  swap(str[evenInd], str[oddInd]);
}
First of all.it will produce an an arrangement of 10101010 type of string.But that can be solved by using str[oddInd]==0 and str[evenInd]==1. But more serious problem is if the array is such that it has even no. of elements and each even positions are correctly filled with 0s and there are some extra 0s in odd positions because in that case the first inner while loop executes and then the outer while loop terminates by break statement.
sagsriv Send private email
Friday, June 13, 2008
 
 
@sagsriv

i guess the depend on understanding of "and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched"

e.g., input array:
{0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 }
output array should be:
a)
{0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 }
since in the question, it states
"if 0s exceed no. of 1s or vice versa then keep them untouched"

or

b)
{0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 }
to move "0s" to the end.which should can be also done in one pass.

which looks better..lol
ray Send private email
Monday, July 07, 2008
 
 
Add all the numbers in the array to get the sum. The sum equals to number of ONEs in the array? Then prepare the sequence of 0,1,0,1 ... based on the no. of ONEs using a simple for loop.

Monday, December 7, 2009

What is the least number of links you can cut in a chain of 21 links to be able to give someone all possible number of links up to 21

Assume that a chain of length k for every 1<=k<=length(chain)
must be doable with the open links. Then you can reach

links length dissection

0 1 1
1 5 1-(1)-3
2 13 1-(1)-3-(1)-7
3 29 1-(1)-3-(1)-7-(1)-15
4 61 1-(1)-3-(1)-7-(1)-15-(1)-31
n 2^(n+2)-3
we have taken links as 2^k-1...and hence get such answer.
The question can be modified a bit...
You are having 31kg of rice. You are provided with a 1kg stone for weighing. In how many weights the 31kg of rice can be weighed.
Now we can't have empty selection...so for 
n we have 2^(n+1)-3...
so we have 2^(n+1)-3 = 31
n+1 = 6 (because 2^5 < 35 < 2^6 )
n=5

CTS Aptitude Question paper(Yellow)

1. If all the 6 are replaced by 9, then the algebraic sum of all the numbers from 1 to 100(both inclusive) varies by Ans: 330

2. The total no. of numbers that are divisible by 2 or 3 between 100 and 200(both inclusive) are Ans:67

3. From a pack of cards Jack, Queen, King & ace are removed. Then the algebraic sum of rest of the cards is Ans:216

4. The average temperature of days from Monday to Wednesday is 37 degree Celsius and that of from Tuesday to Thursday is 34 degrees. The temperature of Thursday is 4/5th of Monday. Then the temperature of Thursday is
Ans: 36 degrees
5. Swetha, Tina, Uma and Vidya are playing a gambling. In this different people lose in different games-in the reverse alphabetical order. The rule is that if one loses she should double the amount of others. At the end of 4th game each of them have same amount of money (Rs.32). Which one of them started with the least amount? (6) Which one of them started with the largest amount of money? (7.) At the end of the 2nd game what is the amount of money with uma?
Ans: Vidya, Swetha, Rs.8
8. A cube of 12 mm is painted on all its side. If it is made up of small cubes of size 3mm. If the big cube is splitted into those small cubes, the number of cubes that remain unpainted is Ans: 8

9. B is 50% faster than A. If A starts at 9 A.M. and B starts at 10 A.M. A travels at a speed of 50 km/hr. If A and B are 300 kms apart, The time when they meet when they travel in opposite direction is Ans:12 noon

10. A graph will be there. Inside the graph sheet there will be a Quadrilateral. We have to count the number of squares in the Quadrilateral.

11. You are having 31kg of rice. You are provided with a 1kg stone for weighing. In how many weights the 31kg of rice can be weighed. Ans: 5

12. A starts at 11:00AM and travels at a speed of 4km/hr. B starts at 1:00PM and travels at 1km/hr for the first 1hr and 2km/hr for the next hr and so on. At what time they will meet each other. Ans:

13. There are 80 coins, among them one coin weighs less compared to other. You are given a physical balance to weigh. In how many wieghings the odd coin can be found. Ans:
14. Dia of the circle 4cm. The shaded part is 1/3 of the square area. What is the side of the square. Ans: root of 3pi

15. A,B,C, can do a work in 8,14,16 days respectively. A does the work for 2 days. B continues from it and finishes till 25% of the remaining work. C finishes the remaining work. How many days would have taken to complete the work Ans:

16. Raja went to a beauty contest .his wife was eager to know the result he told that the lady wear a yellow sari was winner. Miss. Andhra Pradesh Miss. Utter Pradesh, Miss. Maharashtra, Miss. West Bengal were the participants all the participants sat in a row. The conditions are (A) The woman wore yellow sari won the competition. (B) Miss. West Bengal was neither the runner-up or winner.(C) Miss. West Bengal was not at either ends.(D) Miss. Maharastra wore the white sari.(E) The women wore white sari and yellow sari sat at extreme ends.(F) The runner-up and winner did not sit together. [This was the passage given and the questions were easy]

17. The ratio of white balls and black balls is 1:2. If 9 gray balls is added it becomes 2:4:3. Then what is number of black balls. Ans:12

18. There are 10 coins. 6 coins showing head. And 4 showing tail. Each coin was randomly flipped (not tossed) seven times successively.after flipping the coins are 5 heads 4 tails one is hided the hided coin will have what.

19. Two cars are 500 cm apart. each is moving forward for 100 cm at a velocity of 50 cm/s and receding back for 50 cm at 25 cm/s at what time they will collide with each other.

20. People near the sea shore are leading a healthy life as they eat fish.but people at other part of the city are also healthy. Inference.

21. It is found from research that if u r a drunken then u have a less chance for chronic heart diseases. Inference.

22. A-B+c>A+B-C i) B is +ve, ii) B is ?ve when it will hold true.
23. i) C.P is Rs 120 and profit is 30%
ii) C.P is Rs 210 and profit is 20%
we can find the S.P by using
i)only ii)only both i &ii neither i&ii

24. How will u find distance between Nagpur and Mumbai?
I took one hour more when I travel at 80 km/hr than at 90 km/hr.

25. 100 coins were collected by four persons each collected more than 10 each collected a different number each was an even number find what is the max possible no of coins, two more questions based on the same passage.

26. A car travels from B at a speed of 20 km/hr. The bus travel starts from A at a time of 6 A.M. There is a bus for every half an hour interval. The car starts at 12 noon. Each bus travels at a speed of 25 km/hr. Distance between A and B is 100 km. During its journey , The number of buses that the car encounter is

27. The ratio of the ages of the father and the son is 5:3, After 10 years it will be in the ratio 3:2. What will be their ages.
28. There was a Island. In that Island there was Rubys and Emeralds. Those were available in plenty. 0.3 kg of ruby is 4 lakhs and 0.4 kg of emeralds is 5 lakhs. Jayanth is buying 12 kg of Ruby and emerald. Choices will be given . Jayanth has to carry both ruby and emerald to the maximum profit.
29. Varun buys 8 books,10 pens and 2 pencils and Babu buys 6 books, 5pens and 5 pencils. Babu pays 50% more than Varun. What is the amount Varun spends in buying pencils.
30. Prakash and Revathi rent a fancy shop. Prakash imposes the following restrictions on Revathi for buying clips,stickers and lip sticks. The number of clips is twice the no. of stickers. The no. of lipsticks should be more than the sum of clips and stickers. Cost of clip is 1 rupee. Cost of lipstick is twice the clips. Cost of 1 lipstick is the cost of four stickers. Then What is the amount that Prakash spents for Revathi. Answer choices will be given.