There are n coins in a line. (Assume n is even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.
Would you rather go first or second? Does it matter?
Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.
Note that the strategy to pick maximum of two corners may not work. In the following example, first player looses the game when he/she uses strategy to pick maximum of two corners.
Example 18 20 15 30 10 14
First Player picks 18, now row of coins is
20 15 30 10 14
Second player picks 20, now row of coins is
15 30 10 14
First Player picks 15, now row of coins is
30 10 14
Second player picks 30, now row of coins is
10 14
First Player picks 14, now row of coins is
10
Second player picks 10, game over.
The total value collected by second player is more (20 + 30 + 10) compared to first player (18 + 15 + 14). So the second player wins.

Going first will guarantee that you will not lose. By following the strategy below, you will always win the game (or get a possible tie).
(1) Count the sum of all coins that are odd-numbered. (Call this X)
(2) Count the sum of all coins that are even-numbered. (Call this Y)
(3) If X > Y, take the left-most coin first. Choose all odd-numbered coins in subsequent moves.
(4) If X < Y, take the right-most coin first. Choose all even-numbered coins in subsequent moves.
(5) If X == Y, you will guarantee to get a tie if you stick with taking only even-numbered/odd-numbered coins.
You might be wondering how you can always choose odd-numbered/even-numbered coins. Let me illustrate this using an example where you have 6 coins:
Example
18 20 15 30 10 14
Sum of odd coins = 18 + 15 + 10 = 43
Sum of even coins = 20 + 30 + 14 = 64.
Since the sum of even coins is more, the first player decides to collect all even coins. He first picks 14, now the other player can only pick a coin (10 or 18). Whichever is picked the other player, the first player again gets an opportunity to pick an even coin and block all even coins.

One day a really rich old man with two sons died. In his will he said that he would give one of his sons all of his fortune. He gave each of his sons a horse and said they would compete in a horse race from Los Angeles to Sacramento, but the son whose horse came in second would get the money.
So one day they started the race. After one whole day they had only ridden one mile. At night they decided they should stop at a hotel. While they were booking in they told their problem to the wise old clerk, who made a suggestion. The next day the two brothers rode as fast as they could. What did the clerk suggest that they do?

The clerk told them to swap horses. The father said that whoever's horse crossed the finish line second would get the money. He didn't say that the owner of the horse had to be on it.

The owner of a banana plantation has a camel. He wants to transport his 3000 bananas to the market, which is located after the desert. The distance between his banana plantation and the market is about 1000 kilometer. So he decided to take his camel to carry the bananas. The camel can carry at the maximum of 1000 bananas at a time, and it eats one banana for every kilometer it travels.
What is the most bananas you can bring over to your destination?

First of all, the brute-force approach does not work. If the Camel starts by picking up the 1000 bananas and try to reach point B, then he will eat up all the 1000 bananas on the way and there will be no bananas left for him to return to point A.
So we have to take an approach that the Camel drops the bananas in between and then returns to point A to pick up bananas again.
Since there are 3000 bananas and the Camel can only carry 1000 bananas, he will have to make 3 trips to carry them all to any point in between.
When bananas are reduced to 2000 then the Camel can shift them to another point in 2 trips and when the number of bananas left are <= 1000, then he should not return and only move forward.
In the first part, P1, to shift the bananas by 1Km, the Camel will have to
Move forward with 1000 bananas – Will eat up 1 banana in the way forward
Leave 998 banana after 1 km and return with 1 banana – will eat up 1 banana in the way back
Pick up the next 1000 bananas and move forward – Will eat up 1 banana in the way forward
Leave 998 banana after 1 km and return with 1 banana – will eat up 1 banana in the way back
Will carry the last 1000 bananas from point a and move forward – will eat up 1 banana
Note: After point 5 the Camel does not need to return to point A again.
So to shift 3000 bananas by 1km, the Camel will eat up 5 bananas.
After moving to 200 km the Camel would have eaten up 1000 bananas and is now left with 2000 bananas.
Now in the Part P2, the Camel needs to do the following to shift the Bananas by 1km.
Move forward with 1000 bananas – Will eat up 1 banana in the way forward
Leave 998 banana after 1 km and return with 1 banana – will eat up this 1 banana in the way back
Pick up the next 1000 bananas and move forward – Will eat up 1 banana in the way forward
Note: After point 3 the Camel does not need to return to the starting point of P2.
So to shift 2000 bananas by 1km, the Camel will eat up 3 bananas.
After moving to 333 km the camel would have eaten up 1000 bananas and is now left with the last 1000 bananas.
The Camel will actually be able to cover 333.33 km, I have ignored the decimal part because it will not make a difference in this example.
Hence the length of part P2 is 333 Km.
Now, for the last part, P3, the Camel only has to move forward. He has already covered 533 (200+333) out of 1000 km in Parts P1 & P2. Now he has to cover only 467 km and he has 1000 bananas.
He will eat up 467 bananas on the way forward, and at point B the Camel will be left with only 533 Bananas.

You have just purchased a small company called Company X. Company X has N employees, and everyone is either an engineer or a manager. You know for sure that there are more engineers than managers at the company.
Everyone at Company X knows everyone else's position, and you are able to ask any employee about the position of any other employee. For example, you could approach employee A and ask "Is employee B an engineer or a manager?" You can only direct your question to one employee at a time, and can only ask about one other employee at a time. You're allowed to ask the same employee multiple questions if you want.
Your goal is to find at least one engineer to solve a huge problem that has just hit the company's factory. The problem is so urgent that you only have time to ask N-1 total questions.
The major problem with questioning the employees, however, is that while the engineers will always tell you the truth about other employees' roles, the managers may lie to you if they like. You can assume that the managers will do their best to confuse you.
How can you find at least one engineer by asking at most N-1 questions?

You can find at least one engineer using the following process:
Put all of the employees in a conference room. If there happen to be an even number of employees, pick one at random and send him home for the day so that we start with an odd number of employees. Note that there will still be more engineers than managers after we send this employee home.
Then call them out one at a time in any order. You will be forming them into a line as follows:
If there is nobody currently in the line, put the employee you just called out in the line.
Otherwise, if there is anybody in the line, then we do the following. Let's call the employee currently at the front of the line Employee_Front, and call the employee who we just called out of the conference room Employee_Next.
So ask Employee_Front if Employee_Next is a manager or an engineer.
If Employee_Front says "manager", then send both Employee_Front and Employee_Next home for the day.
However, if Employee_Front says "engineer", then put Employee_Next at the front of the line.
Keep doing this until you've called everyone out of the conference room. Notice that at this point, you'll have asked N-1 or less questions (you asked at most one question each time you called an employee out except for the first employee, when you didn't ask a question, so that's at most N-1 questions).
When you're done calling everyone out of the conference room, the person at the front of the line is an engineer. So you've found your engineer!
But the real question: how does this work?
We can prove this works by showing a few things.
First, let's show that if there are any engineers in the line, then they must be in front of any managers.
We'll show this with a proof by contradiction. Assume that there is a manager in front of an engineer somewhere in the line. Then it must have been the case that at some point, that engineer was Employee_Front and that manager was Employee_Next. But then Employee_Front would have said "manager" (since he is an engineer and always tells the truth), and we would have sent them both home. This contradicts their being in the line at all, and thus we know that there can never be a manager in front of an engineer in the line.
So now we know that after the process is done, if there are any engineers in the line, then they will be at the front of the line. That means that all we have to prove now is that there will be at least one engineer in the line at the end of the process, and we'll know that there will be an engineer at the front.
So let's show that there will be at least one engineer in the line. To see why, consider what happens when we ask Employee_Front about Employee_Next, and Employee_Front says "manager". We know for sure that in this case, Employee_Front and Employee_Next are not both engineers, because if this were the case, then Employee_Front would have definitely says "engineer". Put another way, at least one of Employee_Front and Employee_Next is a manager. So by sending them both home, we know we are sending home at least one manager, and thus, we are keeping the balance in the remaining employees that there are more engineers than managers.
Thus, once the process is over, there will be more engineers than managers in the line (this is also sufficient to show that there will be at least one person in the line once the process is over). And so, there must be at least one engineer in the line.
Put altogether, we proved that at the end of the process, there will be at least one engineer in the line and that any engineers in the line must be in front of any managers, and so we know that the person at the front of the line will be an engineer.

As I was going to St. Ives
I met a man with seven wives
The seven wives had seven sacks
The seven sacks had seven cats
The seven cats had seven kits
Kits, cats, sacks and wives
How many were going to St. Ives?

One person is going to St. Ives (the narrator). Because the narrator "met" all of the others mentioned in the poem, this implies that they walked past each other in opposite directions, and thus none of the wives, sacks, cats, or kits was actually headed to St. Ives.
If you (like many) think this answer is a bit silly, you can assume that all the people, sacks, and animals mentioned were heading for St. Ives. In this case, we would have 1 narrator + 1 man + 7 wives + 49 sacks + 343 cats + 2401 kits = 2802 total going to St. Ives. However, this isn't the traditional answer.

A guard is stationed at the entrance to a bridge. He is tasked to shoot anyone who tries to cross to the other side of the bridge, and to turn away anyone who comes in from the opposite side of the bridge. You are on his side of the bridge and want to escape to the other side.
Because the bridge is old and rickety, anyone who tries to cross it does so at a constant speed, and it always takes exactly 10 minutes to cross.
The guard comes out of his post every 6 minutes and looks down the bridge for any people trying to leave, and at all other times he sits in his post and snoozes. You know you can sneak past him when he's sleeping, but the problem is that you won't be able to make it all the way to the other side of the bridge before he sees you (since he comes out every 6 minutes, but it takes 10 minutes to cross).
One day a brilliant idea comes to you, and soon you've successfully crossed to the other side of the bridge without being shot. How did you do it?

Right after the guard goes back to his post after checking the bridge, you sneak by and make your way down the bridge. After a little bit less than 6 minutes, you turn around and start walking back toward the guard. He will come out and see you, and assume that you are a visitor coming from the other side of the bridge, since you're only about 4 minutes from the end of the other side of the bridge. He will go back into his post since he doesn't plan to turn you away until you reach him, and then you turn back around and make your way the rest of the way to the other side of the bridge.

Two men ride their horses to the town blacksmith to ask for his daughter's hand in marriage. To help decide who will get to marry her, the blacksmith proposes a very strange race:
"You will race your horses down the mile-long road from here to the center of town, and the man whose horse passes through city hall's gates LAST will get to marry my daughter."
The men have no idea how to proceed, but after a few minutes of thinking, they come up with a great idea to abide by the blacksmith's rules. 30 minutes later, one of the men is gloating, having won the daughter's hand in marriage.
What was the idea the men had?

Each man rides the other man's horse. They race as they normally would. The blacksmith said the man whose horse crosses last would win, so the man who wins the race would have his horse finish last.