Riddles

11 prisoners are held by a malicious warden. He offers them a game for their freedom: In an empty room are two lamps. The warden will repeatedly select prisoners at random and bring them to the lamp room, where each must flip exactly one lamp (on or off).

The prisoners may meet once to discuss strategy, but after that, they are isolated and can only communicate via the lamps. Their goal: determine with certainty when every prisoner has visited the lamp room at least once. If any prisoner can declare this correctly, all go free; if the claim is made too early, all are executed. The warden can observe their strategy meeting, choose the order of visits, and set the initial lamp states.

Question: What strategy guarantees eventual success?

A banker receives 12 coins, one of which is counterfeit and may be heavier or lighter than the others. Using a balance scale and exactly 3 weighings, he must determine which coin is counterfeit and whether it is heavier or lighter.

Question: How can this be done? (A solution should include a decision tree for each weighing, contingent on previous results.)

A group of four people stand in a line, each wearing either a black or white hat. Each person can see the hats in front of them, but not their own or those behind. Due to a wall, people 1, 2, and 3 cannot see person 4’s hat.

They all know that there are exactly two black hats and two white hats among them.

Question: Which one of the people will be able to confidently call out the color of their own hat?

A prince must choose to marry one of three sisters:

- The oldest always tells the truth.

- The youngest always lies.

- The middle sometimes tells the truth, sometimes lies.

He wants to avoid marrying the middle sister. He may ask one yes/no question to one sister, then must choose. The sisters know each other's truth-telling patterns.

Question: What question can he ask to guarantee he does not pick the middle sister?

100 monks live in a monastery, forbidden from communicating. One night, they are told that some (at least one) have been unfaithful and will wake with an 'X' on their forehead. They have no mirrors, but see everyone else at dinner. The marked monks must commit suicide, but only if they know they are marked.

Question: How do the marked monks figure out their fate, and after how many days will all have acted?

A polar bear walks 1 mile south, 1 mile west, and 1 mile north, ending up where she started.

Question: Where could she have started? (Assume Earth is a perfect sphere.)

You stand before two identical doors: one leads to heaven, the other to hell. Each is guarded by a man—one always tells the truth, the other always lies. You do not know which is which.

Question: What single yes/no question can you ask one guard to guarantee you choose the door to heaven?

A prisoner is told: "If you tell a lie, we will hang you. If you tell the truth, we will shoot you."

Question: What can the prisoner say to save himself?

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You can insert, delete, or replace a character.

Example: word1 = "horse", word2 = "ros" → 3 operations

(horse → rorse → rose → ros)

Given n items, each with a weight and a value, determine the maximum value that can be carried in a knapsack of capacity W. Each item can be taken at most once.

Example: items = [[1, 1], [3, 4], [4, 5], [5, 7]], capacity = 7 → max value = 9

(Take items [3, 4] and [4, 5])

Given an array of n strings containing lowercase English letters, determine the maximum number of palindromic strings that can be obtained. You may perform any number of character swaps between any positions in any two strings.

Example: arr = ["xy", "tz", "abab"] → 2

(Can form ["aa", "bb", "xtyz"] through swaps)

Example: arr = ["pass", "sas", "asps", "df"] → 3

(Can form palindromes "paap", "ssss", "sas")

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals k.

Example: nums = [1, 1, 1], k = 2 → 2

(Subarrays [1, 1] at indices 0-1 and 1-2)

Example: nums = [1, 2, 3], k = 3 → 2

(Subarrays [1, 2] and [3])

There are n children standing in a line, each with a rating value. You need to distribute candies such that: (1) Each child has at least one candy, (2) Children with higher ratings get more candies than their neighbors. Return the minimum number of candies needed.

Example: ratings = [1, 0, 2] → 5

(Distribute [2, 1, 2])

Example: ratings = [1, 2, 2] → 4

(Distribute [1, 2, 1])