## Super-rational Pirates

“There has not been a king since the first brethren court, and that is not likely to change!”, Captain Chevalle sighed. Elizabeth Swann wondered, “Why not?”. “Because the pirate king is elected by popular vote…”, as Mr. Gibbs started to explain, Captain Barbossa finished the sentence, “…and each pirate only votes for himself.”~Pirates of the Caribbean.

Yesterday I was having lunch with my friends Jocelyn, Johnson, and Adrian. One thing lead to another, we started talking about pirates. In one of her interviews, Jocelyn came across a question about how a senior pirate would divide some gold coins among 4 other pirates so that they would not vote to kill him. It was immediately apparent that the senior pirate would not give any gold to 2 of the pirates, but how much he should give the other 2 pirates was not obvious to me. It was stuck in my mind. I concluded that there must be some missing pieces of the question. It turns out that this problem is of a significant theoretical interest to many people. Let’s define the problem first.

There are 5 pirates of different ranks in a ship and they have a treasure of 100 gold coins. The current highest ranking pirate will divide the coins, and all 5 pirates will vote for or against it. If half or more of the pirates vote for it, then the coins will be divided that way. Otherwise, the pirate proposing the scheme will be killed, and the process is repeated with the pirates that remain. The most important thing for a pirate is his life. After that he wants to get as much coins as possible. As every pirate is bloodthirsty, if voting for or against will give him the same number of coins, he will vote against so that the pirate who proposed the plan will be killed. All 5 pirates are intelligent, rational, and good at math. How will the highest ranking pirate divide the coins?

## The unexpected hanging paradox

“A paradox is an argument that produces an inconsistency, typically within logic or common sense.”-Wikipedia.

Computer scientists study paradoxes to learn about logical inconsistencies because computers (being as stupid as they are!) can not handle them. This is particularly important in the fields of Operating Systems, Artificial Intelligence, Machine Learning, etc. On top of that, paradoxes are extremely fun thought exercises! The unexpected hanging paradox is described as follows:

A judge tells a prisoner that he will be hanged at noon on one weekday in the following week, but the execution will be a surprise to the prisoner.

## The beauty of Linked Lists

Linked list is one of the simplest but most popular datastructures, perhaps because good linked list problems can be solved within 15-20 minutes. Linked list problems are interesting, fun, thought provoking, and easy to describe, which is why they are very common in a programming interview. Microsoft loves asking linked list questions, I mean, you WILL get at least one linked list question if you ever interview with Microsoft!

Wikipedia defines, “a linked list is a data structure consisting of a group of nodes that together represent a sequence”. So, a typical linked list node will have a reference to the next node and a data field. This is called a singly linked list. Therefore, the first node (commonly known as the head) can represent the entire linked list, since one can traverse all the nodes from head by using the next reference. The Java code for the traversal of a linked list is below: Continue reading