# Interview questions

by daigo
Tags: interview
 Share this thread:
 P: 98 Does #9 have a solution?
P: 216
These are typical google/facebook interviews.

I was successfully able to answer question #6 in one of my interviews.
 6) You have two robots placed randomly on the number line. When they land, they place a marker. You are to program the robots so that they meet, and you are given the following 3 commands: Go left, go right, or if you are on a marker, change strategy. Specify the two strategies so that the robots eventually meet.
while(!markerSet) {

go left;
go left;
go right;
set marker;
};
while(!peerFound) {
go left;
}

 7) Give an algorithm to reverse the order of the letters of each word in a sentence. Do not change the order of the words. For instance if your sentence is "I like cookies", this algorithm should return "I ekil seikooc"
for(c=each character in the string) {
if (c == NULL || c == 'space') {
while (!stackEmpty)) {
print(pop(stack));
}
}
if (c == NULL) {
break;
} else {
push(stack, c);
}
}
 P: 98 Yeah, these I found trivial. I didn't bother about them. And I didn't bother about #1 though I don't know the answer by heart. I don't believe you got the right answers though. The #6 should be something like 'forall n: do n steps left, retreat, do n steps right, retreat' But the question is underspecified, you need to know that the robots take alternate turns. The #7 is easy too. Should be something like: 'split on space, reverse the words, concatenate the result.' You didn't do anything that resembles that.
P: 216
 Quote by MarcoD I don't believe you got the right answers though. The #6 should be something like 'forall n: do n steps left, retreat, do n steps right, retreat' But the question is underspecified, you need to know that the robots take alternate turns.
My answer is correct.

The logic is,
Move slow (left,left, right) in one direction until you find a marker set. And while moving, set the marker.

Once you find the marker set (that means, the other robot has visited this spot), move faster (continuous left), so you would eventually meet the other robot that is moving slower (left, left, right).

 The #9 is easy too. Should be something like: 'split on space, reverse the words, concatenate the result.' You didn't do anything that resembles that.
I didn't expand the push() and pop(). Look for stack data structures.
 P: 772 I could do four of them for sure, and I could take a pretty good stab at about another three of them. Only having a minute each would be trouble, because I don't always think that quickly.
 P: 98 Oh, I understood that both robots drop a marker where they are dropped. My answer would work too. Now I look at it more closely, hmm, I guess you can't do something n times, so you're answer is better. Hmm, I'll look at it again.
P: 98
 Quote by Jack21222 I could do four of them for sure, and I could take a pretty good stab at about another three of them. Only having a minute each would be trouble, because I don't always think that quickly.
The only interesting for me was #9 I think. (But I didn't really bother doing most of them under a minute.)
 P: 98 Ah, I was afk for a moment. The trivial answer is 'walk left until you hit a marker, then double your speed.' Which is your answer. ;-) Ah well.
 P: 98 I am still annoyed about #9. I have the feeling it can't have a solution, but I am not sure why or how to prove it. Anyone?
Mentor
P: 26,658
 Quote by Jimmy Snyder I just picked a few low hanging fruit. Spoiler 2) 3.5 because the rule that makes you stop playing has no effect on the expected value. 7) While there are input letters take an input letter and see if it is a space. If it is not a space, put it into a LIFO queue. If it is a space, then take the letters off of the LIFO queue one at a time and print them, then print the space. When there are no more letters, take the letters off of the LIFO queue one at a time and print them. Stop. 10) Spin the barrel again for a 2/3 chance of surviving. If you pull the trigger without spinning you will have a 1/2 chance of surviving. 11) 1400 is cheaper because you subtract the strike price from the sale price to determine the value. 12) This one is weird. Options sell in a market that is independent of their underlying securities. However, in general, there is some correlation to: The underlying security, the strike price and the expiration date.
Since people are trying to find answers, I'm restoring Jimmy's early post.
 P: 98 #2 from Jimmy I think is wrong. The expected value, I guessed, is: chance you get to the 1st throw * expected return on the 1st throw + chance you get to the 2nd throw * expected return on the 2nd throw + ... = 1.0 * 3.5 + 0.5 * 3.5 + 0.25 * 3.5 + ... = 7. (Difference is that I read the question as if you get a return on each throw.) (Hmm, I guess it's Jimmies interpretation? Which means 3.5 since it doesn't make sense to role a dice again if you got a better result than the expectancy?)
 P: 98 #10 from Jimmy is wrong I think. Spin the barrel for a 1/3 chance of dying, and pull the trigger for a 1/4 chance of dying. So you pull the trigger.
 P: 98 #12 I read as a reference to Black-Scholes.
 P: 98 #11 I don't know either. You don't know if it's call or put, you don't know the spot price. If it's call, the lowest strike price is probably the best. Look here, monetary value.
P: 772
 Quote by MarcoD #10 from Jimmy is wrong I think. Spin the barrel for a 1/3 chance of dying, and pull the trigger for a 1/4 chance of dying. So you pull the trigger.
I think this is correct. It can be shown this way.

1 2 3 4 + +

The numbers are the blank spaces, the +s are bullets. If you pulled the trigger on 1, you're safe to pull again. If you pulled the trigger on 2, you're safe. If you pulled the trigger on 3, you're safe. If you pulled the trigger on 4, you're dead. That's 1 in 4.
 P: 98 I am probably the only one who reads #9 as: an algorithm such that you end up either with exactly 200 or 0 in the end. Right?
 P: 2,179 Indeed, I was wrong about #10 the russian roulette and about #2, the die game.
 P: 98 I am not sure about the die game, it depends on how you read the question. If you get a return each round, I think the answer is seven, if you are allowed to 'modify' the outcome by throwing the die again, 3.5 should be correct.

 Related Discussions Fun, Photos & Games 6 Engineering, Comp Sci, & Technology Homework 1 Mechanical Engineering 3 Academic Guidance 1