|
|
|
|
|
|
|
|
|
|
|
| Q.1 |
Palindrome no? |
| Ans. |
palindromes also offer another great string question.
write a function that tests for palindromes
bool isPalindrome( char* pStr )
if you start a pointer at the beginning and the end of the string and
keep comparing characters while moving the pointers closer together, you
can test if the string is the same forwards and backwards. notice that
the pointers only have to travel to the middle, not all the way to the
other end (to reduce redundancy).
bool isPalindrome( char* pStr )
{
if ( pStr == NULL )
return false;
char* pEnd = pStr;
while ( *pEnd != '' )
pEnd++;
pEnd--;
while(pEnd > pStr)
{
if ( *pEnd != *pStr )
return false;
pEnd--;
pStr++;
}
return true;
} |
| Q.2 |
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 |
| Ans. |
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).
|
| Q.3 |
Surgeons?a one armed surgeon with a hand wound needs to
operate on three patients. the surgeon only has two gloves. how can he
operate on the three patients in turn without risking exchange of
fluids? (remember he only has one arm so he only needs to wear one glove
at a time.)
|
| Ans. |
the surgeon places both gloves on his hand (1 and 2). he
operates on patient A. he then takes the top glove off (#2), leaving on
the bottom glove (#1) and operates on patient B. then he carefully
reverses glove #2, so the clean side is on the outside, and he places it
on top of glove #1 which is on his hand, and operates on patient C.
this problem is kind of dumb because how's the surgeon going to change
the gloves on his hand when he only has one hand. plus no offense, but
how often do you come across a one-armed surgeon (i'm sure there are
plenty of one-armed doctors, but a surgeon!?!). anyway, i had to make
this problem child friendly and changing the story to the above was the
only way to do it. consider for a minute what the initial problem was.
the surgeon was just a guy, the patients were women, and the glove
was... well, i won't insult your intelligence. |
| Q.4 |
you die and the devil says he'll let you go to heaven if
you beat him in a game. the devil sits you down at a round table. he
gives himself and you a huge pile of quarters. he says "ok, we'll take
turns putting quarters down, no overlapping allowed, and the quarters
must rest on the table surface. the first guy who can't put a quarter
down loses." the devil says he wants to go first.
being the smart programmer you are, you realize that if the devil goes
first, he may automatically win. so you convince him to let you go
first, which makes your day because you know you can't lose. what is
your winning strategy? |
| Ans. |
First, put the first quarter exactly in the center of the (perfectly circular) table.
Next, for each quarter the opponent places, place one directly opposite
it. That is, place it so that the center of the table is halfway between
your piece and the opponent's previous piece.
This will generate a completely symettric (about the center) layout of
quarters on the table. This means that whenever the opponent selects a
free space to place a quarter in, the space opposite is guaranteed to be
free as well. Since we are always guaranteed an open space, we will
never lose with this strategy (and thus win when there are finally no
more spaces for the opponent to use). |
| Q.5 |
Remember to be yourself, know your strengths and be honest with the interviewer
7.Practice is the keys to interviewing
|
| Ans. |
35/45 |
|
|
Blogger Comment
Facebook Comment