Browsing the blog archives for January, 2010

Nth-to-Last Element in a Singly Linked List

Question: Devise an algorithm to determine the Nth-to-Last element in a singly linked list of unknown length. If N = 0, then your algorithm must return the last element. Answer: Given that the only way to traverse a singly linked list is forwards from the head, it is not possible to just count N elements […]

Three Switches

Question: You are standing outside a room next to three switches, all of which are off. Each switch operates a different light bulb in the room. The room door is closed, so you cannot see which switch operates which bulb. You are only allowed to go into the room once. Determine which switch operates which […]

0 Comments

Pick a Random Byte

Question: You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal. Answer: Since we can only store […]

C Keywords – Review

Static Static keyword can be used for both variables and functions. By default, functions and global variables defined in a file are available for use in other files. However, if the static keyword is used, they are restricted to the current file only. They will not be available in other files even if the extern […]

0 Comments

9 Minutes

Question: You are given two hourglasses. One measures 4 minutes and one measures 7 minutes. How would you measure exactly 9 minutes? Answer: This question is similar to 4 Quarts of Water. With water, we were able to fill and pour out the pail multiple times. We can use the same logic and easily come […]

4 Comments

Singly Linked List – Delete Node

Question: You are given a pointer to a node (not the tail node) in a singly linked list. Delete that node from the linked list. Write code in C. Answer: To delete a node, you have to redirect the next pointer of the previous node to point to the next node instead of the current one. Since […]

Chess Squares

Question: How many squares are on a chess board? Answer: If you thought the answer was 64, think again! How about all the squares that are formed by combining smaller squares on the chess board (2×2, 3×3, 4×4 squares and so on)? A 1×1 square can be placed on the chess board in 8 horizontal […]

2 Comments

6 Pirates Fight for 1 Gold Coin

Question: Six pirates discover a chest containing 1 gold coin. They decide to sit down and devise a distribution strategy. The pirates are ranked based on their experience (Pirate 1 to Pirate 6, where Pirate 6 is the most experienced). The most experienced pirate gets to propose a plan and then all the pirates vote […]

4 Comments

Bulb Or No Bulb?

Question: There are 100 bulbs arranged in a row. Each bulb has its own switch and is currently turned off.  In the first round, you turn every switch on. In the second round, you flip the switch of every second bulb (i.e. bulb 2, 4, 6, 8 and so on). In the third round, you […]

1 Comment

What’s Your Eye Color?

Question: On a certain island there are people with assorted eye colors. There are 100 people with blue eyes and 100 people with brown eyes. Since there are no mirrors on this island, no person knows the color of their own eyes. The people on the island are not allowed to talk or communicate with […]

9 Comments