skip to main |
skip to sidebar
We've had enough of logic puzzles! Here goes a data structures problem:
You have a linked list of nodes with the following fields:
struct Node {
int data;
Node * next;
Node * random;
}
The random pointer here can point to any node in the list including itself.
Now given a pointer to such a list, your task is to create a similar copy! The structure of the links should remain the same.
To clarify, all the nodes in the list are linked through the next pointer;
Mind you, You may or may not reach all the nodes if you try to access random pointers.
Link to the Solution
Link to the Problem
Manikandan's solution was almost correct and Yash correctly modified it!
Here's my solution:
In such type of problems always try decreasing the number of parameters (i.e. Use induction).
If there was only 1 blue eyed person, he would have left at the end of the first day itself as he doesn't see any other blue eyed person there (and he knows that there is at least one blue eyed person).
If there were 2 blue eyed people, then the first would see one other blue eyed person on the first day and vice versa and hence both won't leave on the first day (as they can't determine their own eye colour). However, on the second day they know that there are more than one blue eyed persons (if there was only one blue eyed person then he would have left the first day itself). And since the blue eyed persons see only one other blue eyed person, each of them themselves is the other blue eyed person creating confusion on the first day. So the two blue eyed persons know that their eye colour is blue on the second day and hence would leave at the end of that day.
Similarly, if there were 3 blue eyed people, these three blue eyed people would be confused for the first two days as they see 2 other blue eyed people not leaving the island, however on the third day they would know there is one more blue eyed person and it could be only be he himself (as they know that if there were only 2 blue eyed people, they would have left at the end of the 2nd day by above argument). So these three blue eyed people would leave at the end of the 3rd day.
By similar argument we can prove that if there are N blue eyed people, they would be confused till N-1 days but on the Nth day they would all come to know that their eye colour is blue! And hence all the N blue eyed people leave at the end of the Nth day.
Hence in this case all the 100 Blue eyed people leave on the 100th day and no one else leaves!
Two hundred and one perfect logicians with assorted eye colours are stuck in a deserted island. Of these, 100 have blue eyes, 100 have brown eyes and one has green eyes which however they don't know. These people can see everyone else (and hence know their eye colours) but they don't know their own eye colour (they don't even know the all colours present there)! Also, they cannot communicate with each other by any means. Every midnight a ship comes to the island and takes away only those people who know their own eye colour for sure at that point of time. The Guru (who happens to have green eyes) is allowed to speak one sentence to the islanders (at noon) after which no one speaks (communicates) and he says, "I see blue eyes!"
Now the question is: Who all leave the island and at what time?
Link to the Solution
Link to the Problem
Nice try by Mythalez, Vivek and Ankit! I had never thought of such a solution!
Here goes my Solution:
2^11 = 2048 which is greater than 2009. Hence, all numbers from 1 to 2009 can be represented
using 11 bits! Now represent each bottle number in 11 bit binary format and list them row wise. Each row now has a 11 bit number representing a bottle number. Let each column be a single bit. So, each column would contain either a 0 or a 1 corresponding to each bottle(row). Keep one slave per column and make the slave drink from all the bottles which have a 1 in that column! Hence, you get the poisoned bottle using the combination of slaves who die (write 1's for the slaves who die and 0's for the slaves who don't and the binary number hence formed gives the bottle number corresponding to the poisoned bottle).
e.g.
Let's say the third bottle was poisoned.
1 2 3 4 5 6 7 8 9 10 11 - Slave numbers
0 0 0 0 0 0 0 0 0 0 1 - 1st bottle
0 0 0 0 0 0 0 0 0 1 0 - 2nd bottle
0 0 0 0 0 0 0 0 0 1 1 - 3rd bottle
0 0 0 0 0 0 0 0 1 0 0 - 4th bottle
.
.
.
.
Now the slaves from 1 to 9 wont die and 10th and 11th slave would die after 10 to 15 hrs. From this we can decode the bottle number by writing nine 0s followed by two 1s i.e. 00000000011 which is 3. Hence, we conclude that the third bottle is poisoned!
Here time of death was included just to introduce some confusion while solving the problem. However, if Vivek's time window concept is used (which seems reasonable) we can achieve this using ceil(11/3) slaves i.e. 4 slaves!!!!
You are an emperor of a huge kingdom and are conducting a party tomorrow in which you have invited very important guests. You had ordered for 2009 bottles of expensive wine for the celebration. However, you come to know that the wine in one of these bottles has been poisoned (but you don't know which one) and that this poison exhibits no symptoms until death. Also, death occurs within ten to fifteen hours after consuming even the minutest amount of this poison. Since the guests are very important you cannot risk serving them poisoned wine. You have slaves at your disposal who could be made to drink the wine in order to detect the poisoned bottle. Since you don't want to disturb the other important tasks the slaves are carrying out, you want to do this with the least number of slaves possible. How would you go about doing this so that you could have a smooth celebration tomorrow and what is the minimum number of slaves you would have to use?
Link to the Solution
Link to the Problem
Manikandan's solution to this problem was absolutely correct!
My solution:
Since there are 5 cards and only 4 suits there has to be at least 2 cards of the same suit! So one of those cards can be kept as the 5th card and one card can be sent first to denote the suit of the 5th card to the second prisoner. Knowing the suit brings down the number of possibilities of the 5th card from 52 to 12 (as one card of that suit has already been sent). An absolute ordering can be established between the other three cards breaking ties by giving different weightage to different suits. So there are three cards, low, mid and high with which we can make 6 combinations. So the prisoners could decide to denote numbers from 1 to 6 by the different orders in which these cards are sent (low mid high as 1, low high mid as 2 etc.). Now there are 12 possibilities for the 5th card but only 6 numbers can be encoded using the 3 cards. So we need some other information. The beauty is you can send any of the 2 cards of the same suit and any of these two cards can be kept as the card to be guessed. So choose the first card such that the difference between the fifth and the first card is less than or equal to 6 (on a circular scale). After sending the first card, the difference between the first and the fifth card can be sent using the other three cards. For example if u have 3 and Jack of the same suit, send Jack first and then 3 so that the difference is 5.
Hence, send the first card to denote the suit and the other 3 cards in the order encoding the difference between the fifth and the first card!
