Puzzles Cheatsheet Cheatsheet

🧠

How to Approach Puzzles

STRATEGY

Step	Action	Details
1. Listen	Understand the problem fully	Listen to the entire problem before responding. Do not interrupt the interviewer.
2. Clarify	Ask clarifying questions	Confirm constraints, edge cases, and what is being asked. Is the answer a number, an algorithm, or a yes/no?
3. Think Aloud	Verbalize your thought process	Interviewers want to see HOW you think, not just the answer. Narrate your reasoning.
4. Start Simple	Try small examples first	Reduce the problem to the simplest case (n=1, n=2). Look for patterns as you scale up.
5. Identify the Type	Categorize the puzzle	Is it logic, math, probability, algorithmic, pattern-based, or lateral thinking?
6. Solve Systematically	Apply a framework	Use binary search thinking, induction, elimination, or contradiction.
7. Verify	Check your answer	Test with a different example. Does your solution handle edge cases? Is it optimal?

Common Problem Frameworks

Framework	When to Use	Example
Binary Elimination	When you can divide the search space in half each step	Poisoned wine, counterfeit coin
Induction	Build solution from base case upward	Tower of Hanoi, number series
Pigeonhole Principle	When items exceed containers	Birthday paradox, drawer problems
Symmetry	When the problem has identical elements	Ants on a triangle, Monty Hall
Recursion / DP	Subproblems overlap or reduce	Fibonacci, grid walking
Complementary Counting	Easier to count the opposite	Collision probability

What Interviewers Look For

Quality	Why It Matters	How to Show It
Clarity of Thought	Can you break down complex problems?	Structure your approach step-by-step
Creativity	Can you think of unconventional solutions?	Try different angles, challenge assumptions
Communication	Can you explain your reasoning?	Think aloud, use examples
Resilience	How do you handle being stuck?	Stay calm, try simpler cases, pivot
Optimization	Can you find a better approach?	After solving, ask "can I do better?"
Verification	Do you validate your answer?	Test with edge cases explicitly

Types of Puzzles Companies Ask

Category	Frequency	Key Skills	Examples
Logic Puzzles	Very High	Deduction, elimination	25 horses, bridge crossing, ants on triangle
Math / Arithmetic	High	Number sense, algebra	Gold bar, rope burning, coin weighing
Probability	High	Bayes theorem, counting	Birthday paradox, Monty Hall, card probabilities
Algorithmic	High	Optimization, recursion	Two eggs, 8 queens, Tower of Hanoi
Pattern Recognition	Medium	Observation, sequences	Number series, matrix patterns
Lateral Thinking	Medium	Creative assumptions	Elevator man, dead man in field
Estimation / Guesstimate	Medium	Fermi estimation	Piano tuners in Chicago

It is OK to ask questions!Asking clarifying questions shows analytical thinking, not weakness. Confirm constraints (e.g., "Can we measure time with a stopwatch?", "Can the horses share a race?"). If you are stuck, state your assumptions and proceed. Interviewers often want to see your approach more than the correct answer. Budget your time: spend 1-2 minutes understanding, 3-5 minutes exploring, then converge on a solution.

🎲

Logic Puzzles

LOGIC

Puzzle 1: 25 Horses — Find Top 3 in Minimum Races

Problem: You have 25 horses and a race track that can race exactly 5 horses at a time. You cannot measure speed with a stopwatch — you can only determine the relative ranking of horses in each race. What is the minimum number of races needed to find the top 3 fastest horses?

25-horses-solution

STEP-BY-STEP SOLUTION (7 Races Total)

Race 1-5: Divide 25 horses into 5 groups of 5. Race each group.
  After 5 races, we know the ranking within each group:
    Group A: A1 > A2 > A3 > A4 > A5
    Group B: B1 > B2 > B3 > B4 > B5
    Group C: C1 > C2 > C3 > C4 > C5
    Group D: D1 > D2 > D3 > D4 > D5
    Group E: E1 > E2 > E3 > E4 > E5

KEY INSIGHT: Any horse that is 4th or 5th in its group CANNOT be in top 3 overall.
  Eliminate A4, A5, B4, B5, C4, C5, D4, D5, E4, E5. (15 eliminated, 10 remain)

Race 6: Race the winners — A1, B1, C1, D1, E1.
  Suppose result: A1 > B1 > C1 > D1 > E1
  Then: A1 is the FASTEST horse overall.
  Also eliminate: D1, D2, D3, E1, E2, E3 (their group winners are 4th/5th, 
  so no horse from D or E can be in top 3).

  Remaining candidates for positions 2 and 3:
    A2, A3  (could be 2nd or 3rd, lost only to A1)
    B1, B2  (B1 lost to A1, could be 2nd or 3rd)
    C1      (lost to A1 and B1, could be 3rd)
  
  C2 and C3 are eliminated (C1 lost to A1 AND B1, so C2, C3 cannot be top 3).
  B3 is eliminated (B1 lost to A1, so B3 at best is 4th).

Race 7: Race A2, A3, B1, B2, C1.
  The top 2 from this race are the 2nd and 3rd fastest horses overall.

ANSWER: 7 races (guaranteed minimum)

💡

Key Insight: After racing group winners (Race 6), you can eliminate entire groups. Only horses that could possibly be 2nd or 3rd remain. The candidates are limited to at most 5 horses: A2, A3, B1, B2, C1 — hence one final race suffices.

Puzzle 2: 3 Ants on a Triangle — Probability of Collision

Problem: Three ants are placed at the three corners of an equilateral triangle. Each ant randomly chooses a direction (clockwise or counter-clockwise) and starts walking along the edge of the triangle at the same constant speed. What is the probability that none of the ants collide?

ants-on-triangle

STEP-BY-STEP SOLUTION

Each ant has 2 choices: clockwise (CW) or counter-clockwise (CCW).
Total possible outcomes = 2 x 2 x 2 = 8 equally likely scenarios.

For NO collision, all ants must move in the SAME direction:
  Scenario 1: All CW  → ants chase each other, never collide ✓
  Scenario 2: All CCW → ants chase each other, never collide ✓

For collision: If even one ant goes a different direction, 
  two ants will approach each other on the same edge.

Successful outcomes = 2 (all CW or all CCW)
P(no collision) = 2 / 8 = 1/4 = 25%

ANSWER: 1/4 or 25%

EXTENSION: For N ants on a polygon with N sides:
  P(no collision) = 2 / 2^N = 2^(1-N)
  (Only 2 scenarios work: all CW or all CCW)

💡

Key Insight: Use complementary counting — it is easier to count the scenarios where ants do NOT collide (only 2) than to enumerate all collision scenarios. Total outcomes = 2^N for N ants.

Puzzle 3: Bridge Crossing — 4 People, Torch, Different Speeds

Problem:Four people need to cross a bridge at night. The bridge holds at most 2 people at a time. They have one torch and it is too dark to cross without it. Each person walks at a different speed: Person A = 1 min, Person B = 2 min, Person C = 5 min, Person D = 10 min. When two cross together, they walk at the slower person's pace. What is the minimum total time for all four to cross?

bridge-crossing

STEP-BY-STEP SOLUTION (Minimum: 17 minutes)

Naive approach (always send fastest back): 1+10+1+5+1+2 = 20 min ✗

Optimal Strategy — Two techniques to use:

TECHNIQUE 1 (for large speed differences):
  Send two slowest together, using the two fastest as shuttlers.

  Step 1: A and B cross together → 2 min (B is slower)
          Side A: [C, D] | Side B: [A, B]     Total: 2 min
  Step 2: A returns with torch → 1 min
          Side A: [A, C, D] | Side B: [B]     Total: 3 min
  Step 3: C and D cross together → 10 min (D is slower)
          Side A: [A] | Side B: [B, C, D]     Total: 13 min
  Step 4: B returns with torch → 2 min
          Side A: [A, B] | Side B: [C, D]     Total: 15 min
  Step 5: A and B cross together → 2 min
          Side A: [] | Side B: [A, B, C, D]   Total: 17 min ✓

WHY THIS WORKS:
  The key insight is that sending the two slowest (C and D) together 
  costs only 10 minutes instead of 5+10 = 15 minutes (sending them separately).
  The "cost" of this strategy: 2 + 1 + 10 + 2 + 2 = 17 min

DECISION RULE:
  For speeds sorted as a < b < c < d:
  Strategy 1 cost: a + 3b + d     (always send fastest back)
  Strategy 2 cost: 2a + b + c + d  (send two slowest together)
  Use whichever is smaller!
  If 2b < a + c, use Strategy 2. Otherwise, use Strategy 1.

ANSWER: 17 minutes

💡

Key Insight: When speed differences are large, it is better to send the two slowest people together. The cost of sending them separately (each escorted by the fastest) is a + c + d, while sending them together costs 2b + c + d. Choose the minimum.

Puzzle 4: 100 Doors — Open/Close Pattern

Problem: You have 100 doors (all initially closed) and 100 people. Person 1 toggles every door. Person 2 toggles every 2nd door. Person 3 toggles every 3rd door, and so on up to Person 100. After all 100 people have gone, which doors remain open?

100-doors

STEP-BY-STEP SOLUTION

Door k is toggled by every person whose number divides k.
  Door 6 is toggled by: 1, 2, 3, 6 (4 times → closed)
  Door 7 is toggled by: 1, 7 (2 times → closed)
  Door 16 is toggled by: 1, 2, 4, 8, 16 (5 times → OPEN)

KEY INSIGHT: A door ends up OPEN if toggled an ODD number of times.
  A number has an odd number of divisors if and only if it is a PERFECT SQUARE.
  
  Why? Divisors come in pairs: (1, n), (2, n/2), ...
  For perfect squares, one divisor is repeated: e.g., 16 has (4, 4).
  So perfect squares have an odd count of divisors.

Perfect squares ≤ 100: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100

ANSWER: Exactly 10 doors remain open — doors numbered 1, 4, 9, 16, 25, 36, 49, 64, 81, 100

💡

Key Insight: This puzzle is about the parity of divisor counts. Only perfect squares have an odd number of divisors. So the answer is always the perfect squares up to N, and there are exactly floor(sqrt(N)) such doors.

Puzzle 5: 1000 Bottles of Wine — Find the Poisoned One

Problem: You have 1000 bottles of wine, exactly one of which is poisoned. The poison takes exactly 1 hour to show effect and kills the person. You have exactly 1 hour to determine which bottle is poisoned. What is the minimum number of testers (prisoners) needed?

poisoned-wine

STEP-BY-STEP SOLUTION

Use BINARY representation!

Each prisoner represents one BIT in a binary number.
10 prisoners can represent 2^10 = 1024 unique combinations.

Strategy:
  Number the bottles 0 to 999 in binary (10 bits each).
  Prisoner 1 drinks from all bottles where bit 1 is set.
  Prisoner 2 drinks from all bottles where bit 2 is set.
  ...
  Prisoner 10 drinks from all bottles where bit 10 is set.

Example: Bottle 13 = 0000001101 in binary
  Prisoners 1, 3, 4 drink from this bottle.

After 1 hour:
  If prisoners 1, 3, and 4 die → the poisoned bottle is 13.
  The binary pattern of dead/alive prisoners directly encodes the bottle number.

Dead prisoners = bit is 1, Alive prisoners = bit is 0.

ANSWER: 10 prisoners (since 2^10 = 1024 ≥ 1000)

FORMULA: ceil(log2(N)) testers for N bottles.
  1000 bottles → ceil(log2(1000)) = ceil(9.97) = 10

💡

Key Insight: Use binary encoding. Each tester represents a bit position. If k testers are available, you can test up to 2^k bottles simultaneously because the set of dead testers uniquely identifies the poisoned bottle.

Puzzle 6: 100 Prisoners and a Light Bulb

Problem: 100 prisoners are in solitary confinement. Each day, the warden randomly picks one prisoner to visit a room with a light bulb that is initially OFF. The prisoner can toggle the bulb (ON/OFF) or do nothing. No other communication is possible. All prisoners are freed when one prisoner can correctly declare that every prisoner has visited the room at least once. Devise a strategy.

100-prisoners

STEP-BY-STEP SOLUTION

Designate ONE prisoner as the "Counter." The other 99 are "Regulars."

RULES FOR REGULARS (99 prisoners):
  - If you visit the room and the bulb is OFF, AND you have NOT yet 
    turned it ON before (first time doing so), turn it ON.
  - Otherwise, do nothing.

RULES FOR THE COUNTER (1 prisoner):
  - If you visit the room and the bulb is ON, turn it OFF and add 1 
    to your mental count.
  - Otherwise, do nothing.

WHEN TO DECLARE:
  - The Counter declares "all have visited" when their count reaches 99.

WHY IT WORKS:
  - Each Regular can only turn the bulb ON once.
  - Each time the Counter turns the bulb OFF, they know that a new 
    (previously uncounted) Regular has visited.
  - After the Counter has counted 99 ON→OFF cycles, every Regular 
    has visited at least once.

EXPECTED TIME:
  - The expected number of days is approximately 2 × 100 × 99 ≈ 19,800 days 
    (about 54 years), but the strategy guarantees correctness.

OPTIMIZATION (expected ~27.5 years):
  - Regulars turn ON the bulb only after seeing it OFF twice (they must 
    accumulate 2 "credits" before spending one).
  - Counter counts to 2×99 = 198 instead.
  - This reduces the frequency of false signals.

💡

Key Insight: Designate a single Counter who aggregates information. Regular prisoners signal their visit exactly once by turning the bulb ON. The Counter tallies these signals. This transforms a distributed problem into a centralized counting problem.

Puzzle 7: Birthday Problem — How Many People for a Shared Birthday?

Problem: In a room of N people, what is the probability that at least two people share the same birthday? How many people are needed for the probability to exceed 50%? (Assume 365 equally likely birthdays, ignore leap years.)

birthday-problem

STEP-BY-STEP SOLUTION

Use complementary probability: P(at least one match) = 1 - P(all different)

P(all different for n people):
  = (365/365) × (364/365) × (363/365) × ... × ((365-n+1)/365)
  = 365! / (365^n × (365-n)!)

Calculation:
  n=10:  P(match) ≈ 11.7%
  n=20:  P(match) ≈ 41.1%
  n=23:  P(match) ≈ 50.7%  ← exceeds 50%!
  n=30:  P(match) ≈ 70.6%
  n=40:  P(match) ≈ 89.1%
  n=50:  P(match) ≈ 97.0%
  n=70:  P(match) ≈ 99.9%

Approximation formula (for large 365):
  P(all different) ≈ e^(-n(n-1)/(2×365))
  P(match) ≈ 1 - e^(-n(n-1)/730)

ANSWER: Only 23 people are needed for a >50% chance of a shared birthday!
  This is surprisingly low because we are checking ALL pairs: C(n,2) = n(n-1)/2
  For n=23: C(23,2) = 253 pairs — more than half of 365.

💡

Key Insight:The intuition gap arises because people think about "someone sharing MY birthday," but the problem asks about ANY pair. With 23 people, there are 253 pairs, each with a 1/365 chance — creating a much higher probability than expected.

Puzzle 8: Monty Hall Problem — To Switch or Not?

Problem:You are on a game show with 3 doors. Behind one door is a car; behind the other two are goats. You pick a door. The host (who knows what is behind each door) opens one of the remaining doors, revealing a goat. He then asks: "Do you want to switch your choice?" Should you switch?

monty-hall

STEP-BY-STEP SOLUTION

Answer: YES — you should ALWAYS switch. Switching doubles your chance of winning!

ENUMERATION of all cases:

Case 1: You pick Door 1 (Car is behind Door 1)
  Host opens Door 2 or 3 (reveals goat)
  If you STAY → WIN (1/3 probability)
  If you SWITCH → LOSE

Case 2: You pick Door 1 (Car is behind Door 2)
  Host MUST open Door 3 (only door with goat)
  If you STAY → LOSE (1/3 probability)
  If you SWITCH → WIN

Case 3: You pick Door 1 (Car is behind Door 3)
  Host MUST open Door 2 (only door with goat)
  If you STAY → LOSE (1/3 probability)
  If you SWITCH → WIN

Results:
  P(win by staying)  = 1/3
  P(win by switching) = 2/3

INTUITIVE EXPLANATION:
  Your initial pick has a 1/3 chance of being correct and 2/3 chance of being wrong.
  The host always reveals a goat, concentrating the 2/3 probability on the remaining door.
  Switching = betting that your initial guess was wrong (2/3 chance).

GENERALIZATION: With N doors, host opens (N-2) goats:
  P(win by switching) = (N-1)/N
  For N=100: switching gives you 99% chance to win!

💡

Key Insight:The host's actions are NOT random — they are constrained by knowledge. This constraint transfers probability mass to the unopened door. The key is that the host will ALWAYS reveal a goat, which gives you additional information.

🔢

Math Puzzles

MATH

Puzzle 1: Gold Bar Cutting — Pay a Worker for 7 Days

Problem: You need to pay a worker exactly 1 gold unit per day for 7 days of work. You have one gold bar worth 7 units. You may make exactly 2 cuts to the bar. How do you pay the worker each day?

gold-bar

STEP-BY-STEP SOLUTION

Make 2 cuts to divide the gold bar into pieces of: 1, 2, and 4 units.
(Pieces: [1] [2] [4])

Daily payment using binary/exchange:
  Day 1: Give [1]                 → Worker has: 1
  Day 2: Give [2], take back [1]  → Worker has: 2
  Day 3: Give [1]                 → Worker has: 1+2 = 3
  Day 4: Give [4], take back [1],[2] → Worker has: 4
  Day 5: Give [1]                 → Worker has: 4+1 = 5
  Day 6: Give [2], take back [1]  → Worker has: 4+2 = 6
  Day 7: Give [1]                 → Worker has: 4+2+1 = 7

ANSWER: Cut into pieces of 1, 2, and 4 units (powers of 2).

INSIGHT: This works because every integer from 1 to 7 can be uniquely 
represented as a sum of powers of 2 (binary representation).
  1 = 001, 2 = 010, 3 = 011, 4 = 100, 5 = 101, 6 = 110, 7 = 111

💡

Key Insight: Powers of 2 can represent any number through binary representation. With pieces of 1, 2, 4, 8, 16, ... you can pay any amount by giving and taking back pieces. This is the binary number system applied to a physical problem.

Puzzle 2: Rope Burning — Measure 45 Minutes

Problem: You have two ropes. Each rope takes exactly 60 minutes to burn from end to end. However, the ropes do NOT burn uniformly — some parts burn faster than others. You have no stopwatch. How do you measure exactly 45 minutes?

rope-burning

STEP-BY-STEP SOLUTION

Step 1: Light BOTH ends of Rope 1 and ONE end of Rope 2 at the same time.

  Rope 1: burning from both ends → will finish in exactly 30 minutes
    (regardless of non-uniform burning, since both ends meet in the middle)
  Rope 2: burning from one end → has 30 minutes of burn time remaining

Step 2: When Rope 1 is completely burned (exactly 30 min have passed),
  immediately light the OTHER end of Rope 2.

  Rope 2 has 30 minutes of burn left, but now burns from BOTH ends.
  It will finish in exactly 15 more minutes.

Step 3: When Rope 2 is completely burned, exactly 45 minutes have passed.

  Total time: 30 + 15 = 45 minutes ✓

ANSWER: Light Rope 1 from both ends and Rope 2 from one end. 
  When Rope 1 finishes, light the other end of Rope 2.
  When Rope 2 finishes, 45 minutes have elapsed.

💡

Key Insight: Burning a rope from both ends halves its burn time, regardless of non-uniform burning. This works because the total burn time is fixed — burning from both ends simply means the two flames meet in half the time.

Puzzle 3: Blue-Eyed Islanders (Hardest Logic Puzzle)

Problem:On an island, there are 100 blue-eyed people, 100 brown-eyed people, and 1 green-eyed foreigner. No one knows their own eye color, but everyone can see everyone else's eye color. There is a rule: if you discover your own eye color, you must leave the island at midnight that night. One day, the foreigner announces: "I see someone with blue eyes." What happens?

blue-eyed-islanders

STEP-BY-STEP SOLUTION (by Mathematical Induction)

Let us prove by induction on n = number of blue-eyed islanders:

Base case (n=1):
  If only 1 blue-eyed person exists, they see 0 blue-eyed people.
  When foreigner says "I see someone with blue eyes," they realize 
  it must be themselves. They leave on Day 1.

Inductive case (n=k):
  Assume k blue-eyed people leave on Day k.
  
For n=100:
  Day 1: No one leaves (each blue-eyed person sees 99 others)
  Day 2: No one leaves (each blue-eyed person thinks maybe there 
          are only 99 blue-eyed people, waiting to see if they leave)
  ...
  Day 99: No one leaves
  Day 100: All 100 blue-eyed people leave simultaneously!

WHY: Each blue-eyed person sees 99 blue-eyed people. They think:
  "If there are only 99 blue-eyed people, they will leave on Day 99."
  When no one leaves on Day 99, they conclude: "There must be 100 
  blue-eyed people, and I am the 100th!" All reach this conclusion 
  on Day 99 → all leave on Day 100.

The brown-eyed people also figure it out on Day 101 and leave.

ROLE OF THE FOREIGNER'S STATEMENT:
  It provides COMMON KNOWLEDGE — everyone now knows that everyone 
  knows that ... there is at least one blue-eyed person. Without 
  it, no one would have a starting point for the inductive chain.

💡

Key Insight:Mathematical induction on nested levels of knowledge. The foreigner's statement creates common knowledge, establishing the base case that enables the inductive chain. This is considered one of the hardest logic puzzles ever devised.

Puzzle 4: 12 Coins — Find the Fake with 3 Weighings

Problem:You have 12 coins. One is counterfeit (either heavier or lighter — you don't know which). You have a balance scale. Find the counterfeit coin and determine whether it is heavier or lighter in exactly 3 weighings.

coin-weighing

STEP-BY-STEP SOLUTION

Strategy: Divide into 3 groups of 4 coins each: A, B, C.

WEIGHING 1: A vs B
  ┌─ BALANCED → fake is in C (coins 9-12), all of A and B are genuine
  │   WEIGHING 2: Compare {9,10,11} vs {1,2,3} (genuine)
  │   ┌─ BALANCED → fake is coin 12
  │   │   WEIGHING 3: 12 vs 1 → heavier or lighter? Done!
  │   └─ UNBALANCED → fake is in {9,10,11}, and we know if 
  │       it's heavier or lighter from the tilt direction
  │       WEIGHING 3: 9 vs 10
  │       ┌─ BALANCED → fake is 11 (known heavy/light from W2)
  │       └─ UNBALANCED → direction matches W2 → fake is 9 or 10
  │
  └─ UNBALANCED → fake is in A or B, C is genuine
      (Say A is heavier — either A has a heavy fake or B has a light fake)
      WEIGHING 2: {A1,A2,B1} vs {A3,B2,C1(genuine)}
      ┌─ BALANCED → fake is in {A4, B3, B4}
      │   WEIGHING 3: B3 vs B4
      │   ┌─ BALANCED → fake is A4 (must be heavy)
      │   └─ LEFT LIGHT → B3 is light (since B was light side)
      │   └─ RIGHT LIGHT → B4 is light
      │
      └─ SAME TILT as W1 (left heavy) → fake is A1, A2, or B2
      │   WEIGHING 3: A1 vs A2
      │   ┌─ BALANCED → B2 is light
      │   └─ LEFT HEAVY → A1 is heavy
      │   └─ RIGHT HEAVY → A2 is heavy
      │
      └─ OPPOSITE TILT → fake is A3 or B1
          WEIGHING 3: A3 vs C1(genuine)
          ┌─ BALANCED → B1 is light
          └─ LEFT HEAVY → A3 is heavy

ANSWER: 3 weighings always suffice for 12 coins (with 24 possible states: 
12 coins × heavy/light). 3 weighings can distinguish 3^3 = 27 states ≥ 24.

💡

Key Insight: Each weighing has 3 outcomes (left heavy, balanced, right heavy), so 3 weighings can distinguish 3^3 = 27states. We need to identify 24 states (12 coins × 2 directions). The key is designing weighings that split the remaining possibilities roughly into thirds each time.

Puzzle 5: Probability of Two Sons

Problem:A man says: "I have two children. At least one of them is a boy." What is the probability that both children are boys? Now: "I have two children. The older one is a boy." What is the probability now?

two-sons

STEP-BY-STEP SOLUTION

Sample space for two children (ordered by age): {BB, BG, GB, GG}
Each outcome has equal probability = 1/4.

SCENARIO 1: "At least one is a boy"
  Possible outcomes: {BB, BG, GB} (GG is eliminated)
  P(both boys | at least one boy) = 1/3

SCENARIO 2: "The older one is a boy"  
  Possible outcomes: {BB, BG} (GB and GG are eliminated)
  P(both boys | older is boy) = 1/2

SCENARIO 3: "I have a boy named Tuesday" (more specific)
  Sample space becomes much larger. P ≈ 13/27 (approximately 48%)
  
WHY THE DIFFERENCE?
  "At least one boy" is LESS specific → more possibilities remain
  "Older one is a boy" is MORE specific → fewer possibilities remain
  More specific information narrows the sample space differently.

  In Scenario 1, we can't distinguish BB from "a boy and a girl"
  In Scenario 2, knowing which child is a boy eliminates one BG case

ANSWER: Scenario 1 = 1/3, Scenario 2 = 1/2

💡

Key Insight:The probability changes based on how the information was obtained. Self-selected information ("at least one is a boy") vs. randomly observed information ("older is a boy") lead to different conditional probabilities. Always consider the sampling method.

Puzzle 6: Infinite Monkey Theorem

Problem:If a monkey types randomly on a keyboard (26 letters + space), what is the probability that it types "HAMLET" in exactly 6 keystrokes? What can we say about infinite time?

infinite-monkey

STEP-BY-STEP SOLUTION

Probability of typing "HAMLET" in 6 keystrokes:
  P = (1/27)^6 = 1/387,420,489 ≈ 2.58 × 10^-9

This is incredibly small for any finite number of attempts.
But as attempts → infinity:

Expected number of attempts: 27^6 = 387,420,489

THE THEOREM:
  Given infinite time, a monkey randomly typing on a keyboard will 
  almost surely type ANY given finite text (Hamlet, the complete 
  works of Shakespeare, etc.).

  "Almost surely" = probability 1 (in the mathematical sense).
  P(eventually types HAMLET) = 1 - lim(n→∞) (1 - 1/27^6)^n
                             = 1 - 0 = 1

PRACTICAL REALITY:
  Even for just "to be or not to be" (18 chars):
  P = (1/27)^18 ≈ 1.7 × 10^-26
  At 1 keystroke per second, expected time ≈ 10^18 years 
  (universe is ~10^10 years old)

ANSWER: P("HAMLET" in 6 keys) ≈ 2.58 × 10^-9. In infinite time, 
the probability approaches 1 (almost surely).

💡

Key Insight:"Almost surely" in probability means the event has probability 1 but it does not mean it necessarily happens — individual infinite sequences where it never occurs have measure zero. This is related to the Borel-Cantelli lemma.

Puzzle 7: Expected Coin Flips for 3 Heads in a Row

Problem: You flip a fair coin repeatedly. What is the expected number of flipsuntil you get 3 consecutive heads (HHH)?

expected-coin-flips

STEP-BY-STEP SOLUTION (Using States / Markov Chain)

Define states based on the current run of consecutive heads:
  S0: No consecutive heads (start, or last flip was T)
  S1: Exactly 1 consecutive head (last flip was H, before that was T or start)
  S2: Exactly 2 consecutive heads (last two flips were HH)
  S3: Three consecutive heads (GOAL — absorbing state)

Let E_n = expected additional flips from state S_n to reach S3.

E0 = expected flips from start to get HHH

Transition equations:
  E0: flip → H (go to S1) or T (stay at S0)
      E0 = 1 + (1/2)E1 + (1/2)E0
      → (1/2)E0 = 1 + (1/2)E1
      → E0 = 2 + E1       ... (i)

  E1: flip → H (go to S2) or T (go to S0)
      E1 = 1 + (1/2)E2 + (1/2)E0       ... (ii)

  E2: flip → H (go to S3 = DONE) or T (go to S0)
      E2 = 1 + (1/2)(0) + (1/2)E0
      → E2 = 1 + (1/2)E0              ... (iii)

Solving:
  From (i): E1 = E0 - 2
  From (iii): E2 = 1 + E0/2
  
  Substitute into (ii):
  E0 - 2 = 1 + (1/2)(1 + E0/2) + (1/2)E0
  E0 - 2 = 1 + 1/2 + E0/4 + E0/2
  E0 - 2 = 3/2 + 3E0/4
  E0/4 = 3/2 + 2 = 7/2
  E0 = 14

ANSWER: Expected 14 flips to get 3 consecutive heads.

GENERAL FORMULA:
  For n consecutive heads with a fair coin:
  E(n) = 2^(n+1) - 2
  E(1) = 2, E(2) = 6, E(3) = 14, E(4) = 30, E(5) = 62

💡

Key Insight: Model the problem as a Markov chain with states representing the current streak. Set up linear equations for expected value at each state and solve. The general formula for n consecutive heads with a fair coin is E(n) = 2^(n+1) - 2.

Puzzle 8: Water Jug Problem — Measure 4L with 3L and 5L Jugs

Problem: You have a 3-liter jug and a 5-liter jug. Neither has markings. You have an unlimited water supply. How do you measure exactly 4 liters?

water-jug

STEP-BY-STEP SOLUTION

Method 1 (Fill the 5L jug first):

  Step   3L jug   5L jug   Action
  ────   ──────   ──────   ───────────────────────
  Start    0        0       Both empty
  1        0        5       Fill 5L jug completely
  2        3        2       Pour from 5L into 3L (fills 3L)
  3        0        2       Empty 3L jug
  4        2        0       Pour 2L from 5L into 3L
  5        2        5       Fill 5L jug completely
  6        3        4       Pour from 5L into 3L (only 1L fits)
                              5L jug now has exactly 4L ✓

Method 2 (Fill the 3L jug first):

  Step   3L jug   5L jug   Action
  ────   ──────   ──────   ───────────────────────
  Start    0        0       Both empty
  1        3        0       Fill 3L jug
  2        0        3       Pour 3L into 5L
  3        3        3       Fill 3L jug again
  4        1        5       Pour from 3L into 5L (only 2L fits)
  5        1        0       Empty 5L jug
  6        0        1       Pour 1L from 3L into 5L
  7        3        1       Fill 3L jug
  8        0        4       Pour 3L into 5L → 5L has 4L ✓

MATHEMATICAL INSIGHT:
  This uses the Extended Euclidean Algorithm.
  We want: 3x + 5y = 4, where x and y are pour operations.
  Solution: 3(3) + 5(-1) = 4 → fill 3L three times, empty into 5L, 
  and empty 5L once.

ANSWER: 6 steps (Method 1) or 8 steps (Method 2). The 4L ends up in the 5L jug.

💡

Key Insight:This is the classic water jug problem from the movie "Die Hard with a Vengeance." Mathematically, it is solvable if and only if the desired amount is a multiple of gcd(jug1, jug2). Since gcd(3,5) = 1, any integer amount is achievable.

📊

Probability Puzzles

PROBABILITY

Puzzle 1: Card Probabilities

Problem: From a standard 52-card deck, you draw 5 cards. What is the probability of: (a) A flush (all same suit)? (b) A full house (3 of a kind + pair)? (c) Exactly 2 aces?

card-probabilities

STEP-BY-STEP SOLUTION

Total ways to draw 5 cards: C(52,5) = 2,598,960

(a) FLUSH (all 5 cards same suit):
  Choose suit: C(4,1) = 4
  Choose 5 cards from that suit: C(13,5) = 1,287
  P(flush) = (4 × 1,287) / 2,598,960 = 5,148 / 2,598,960 ≈ 0.198%
  
  Note: This includes straight flushes. 
  P(flush, excluding straight flush) = (5,148 - 40) / 2,598,960 ≈ 0.197%

(b) FULL HOUSE (3 of one rank + 2 of another):
  Choose rank for triplet: C(13,1) = 13
  Choose 3 suits from 4: C(4,3) = 4
  Choose rank for pair: C(12,1) = 12
  Choose 2 suits from 4: C(4,2) = 6
  P(full house) = (13 × 4 × 12 × 6) / 2,598,960 = 3,744 / 2,598,960 ≈ 0.144%

(c) EXACTLY 2 ACES (and 3 non-aces):
  Choose 2 aces from 4: C(4,2) = 6
  Choose 3 non-aces from 48: C(48,3) = 17,296
  P(exactly 2 aces) = (6 × 17,296) / 2,598,960 ≈ 3.99%

💡

Key Insight: Most card probability problems reduce to counting combinations. Always start with the total sample space C(52,5) and carefully count favorable outcomes using the multiplication principle.

Puzzle 2: Dice Problems

Problem: (a) Roll two fair dice. What is the probability the sum is 7? (b) Roll two dice. What is the probability at least one shows a 6? (c) Roll a die until you get a 6. What is the expected number of rolls?

dice-problems

STEP-BY-STEP SOLUTION

Total outcomes for two dice: 6 × 6 = 36 (all equally likely)

(a) P(sum = 7):
  Favorable: (1,6), (2,5), (3,4), (4,3), (5,2), (6,1) → 6 outcomes
  P(sum = 7) = 6/36 = 1/6 ≈ 16.7%
  
  Note: 7 has the most combinations, making it the most likely sum.
  Distribution: 2→1, 3→2, 4→3, 5→4, 6→5, 7→6, 8→5, 9→4, 10→3, 11→2, 12→1

(b) P(at least one six) — Use COMPLEMENT:
  P(no sixes) = (5/6) × (5/6) = 25/36
  P(at least one six) = 1 - 25/36 = 11/36 ≈ 30.6%

(c) Expected rolls to get a 6:
  This is a Geometric distribution with p = 1/6
  E = 1/p = 6 rolls
  
  General: E(rolls for first k) = 1/(1/6) = 6

COMMON TRAP in (b): 
  "At least one is 6" is NOT 2/6 = 1/3.
  P(at least one 6) = P(first is 6) + P(second is 6) - P(both are 6)
  = 1/6 + 1/6 - 1/36 = 11/36

💡

Key Insight:For "at least one" problems, always use complementary counting. For "expected time until success," use E = 1/p(geometric distribution). Be careful not to double-count in "at least one" scenarios.

Puzzle 3: Coin Flip Sequences

Problem: (a) Flip a fair coin 10 times. What is the probability of getting exactly 5 heads? (b) What is the probability of getting at least 9 heads in 10 flips? (c) Two players alternately flip a coin. Player A wins if HHH appears first; Player B wins if THH appears first. Who has the advantage?

coin-sequences

STEP-BY-STEP SOLUTION

(a) Exactly 5 heads in 10 flips:
  This follows Binomial(n=10, p=0.5)
  P(X=5) = C(10,5) × (0.5)^10 = 252/1024 ≈ 24.6%
  
  General: P(X=k) = C(n,k) × p^k × (1-p)^(n-k)

(b) At least 9 heads in 10 flips:
  P(X≥9) = P(X=9) + P(X=10)
  P(X=9) = C(10,9) × (0.5)^10 = 10/1024
  P(X=10) = C(10,10) × (0.5)^10 = 1/1024
  P(X≥9) = 11/1024 ≈ 1.07%

(c) Penney's Game — THH vs HHH:
  PLAYER B (THH) has a significant advantage!
  
  Why? Consider what happens after the first flip:
  - If first flip is T: B needs HH to win. A needs HHH.
    If A gets HH but then T, B wins immediately (the T starts THH).
  - If first flip is H: Both need HH next.
    If we get HHT → B wins (the last HTH... no, HHT → the TH in HHT 
    doesn't help B directly, but if we then get H → THH wins).
  
  P(B wins with THH) = 3/4 = 75%
  P(A wins with HHH) = 1/4 = 25%
  
  PENNY'S GAME RULE: For any pattern of length 3, you can always find 
  another pattern that beats it with probability ≥ 2/3.

💡

Key Insight:Coin flip sequences follow the Binomial distribution. Penney's Game shows a non-transitive relationship in pattern matching — no pattern is universally "best." For any 3-length pattern, choosing the pattern that starts with the complement of their second element gives you an advantage.

Puzzle 4: Birthday Paradox — Detailed Calculation

Problem: Derive the exact probability formula for the birthday problem and compute probabilities for key values. Also find the minimum group size for 99.9% probability.

birthday-detailed

STEP-BY-STEP DETAILED DERIVATION

P(no shared birthday among n people):
  = P(2nd person ≠ 1st) × P(3rd ≠ 1st and 3rd ≠ 2nd) × ...
  = (365/365) × (364/365) × (363/365) × ... × ((365-n+1)/365)
  = product from k=0 to n-1 of (365-k)/365
  = 365! / ((365-n)! × 365^n)

Using natural log for computation:
  ln(P) = sum from k=0 to n-1 of ln(365-k) - ln(365)
  P = e^(sum of ln terms)

Key values:
  n=10:  P(match)  = 0.1169 (11.69%)
  n=15:  P(match)  = 0.2529 (25.29%)
  n=20:  P(match)  = 0.4114 (41.14%)
  n=23:  P(match)  = 0.5073 (50.73%) ← 50% threshold
  n=30:  P(match)  = 0.7063 (70.63%)
  n=40:  P(match)  = 0.8912 (89.12%)
  n=50:  P(match)  = 0.9704 (97.04%)
  n=60:  P(match)  = 0.9941 (99.41%)
  n=70:  P(match)  = 0.9992 (99.92%)

For 99.9%: n = 70 people needed.

PAIR COUNT INSIGHT:
  The number of pairs grows as C(n,2) = n(n-1)/2
  n=23 → 253 pairs, each with ~1/365 chance → 253/365 ≈ 0.693
  
  Using the approximation P ≈ 1 - e^(-C(n,2)/365):
  n=23: P ≈ 1 - e^(-253/365) = 1 - e^(-0.693) = 1 - 0.500 ≈ 0.500 ✓

Puzzle 5: Conditional Probability — Bayes' Theorem

Problem: A disease affects 1 in 1000 people. A test is 99% accurate (both sensitivity and specificity). You test positive. What is the probability you actually have the disease?

bayes-theorem

STEP-BY-STEP SOLUTION (Bayes' Theorem)

Given:
  P(Disease) = 0.001 (prior probability)
  P(Positive | Disease) = 0.99 (sensitivity / true positive rate)
  P(Negative | No Disease) = 0.99 (specificity / true negative rate)
  P(Positive | No Disease) = 0.01 (false positive rate)

Bayes' Theorem:
  P(Disease | Positive) = P(Positive | Disease) × P(Disease)
                         ─────────────────────────────────────────
                         P(Positive)
  
  P(Positive) = P(Positive | Disease)×P(Disease) + P(Positive | No Disease)×P(No Disease)
              = 0.99 × 0.001 + 0.01 × 0.999
              = 0.00099 + 0.00999
              = 0.01098

  P(Disease | Positive) = 0.00099 / 0.01098 ≈ 0.0902 = 9.02%

NATURAL FREQUENCY APPROACH (easier to understand):
  Imagine 100,000 people tested:
    100 have the disease → 99 test positive (true positives)
    99,900 are healthy → 999 test positive (false positives)
  
  Total positives = 99 + 999 = 1,098
  P(disease | positive) = 99 / 1,098 ≈ 9.02%

ANSWER: Only about 9% chance you actually have the disease!
  Even with a 99% accurate test, a positive result is most likely a false alarm
  because the disease is so rare (low prior probability).

💡

Key Insight:With rare diseases, false positives vastly outnumber true positives. Always consider the base rate (prior probability). The natural frequency approach (testing 100,000 people) makes Bayes' theorem intuitive. This is the classic "base rate fallacy" — ignoring prior probabilities leads to wrong conclusions.

Puzzle 6: Poker Hand Probabilities

Problem: What are the probabilities of each poker hand from a 5-card draw?

poker-hands

POKER HAND PROBABILITIES (5-card draw from 52 cards)
Total combinations: C(52,5) = 2,598,960

┌────────────────────┬────────────┬─────────────┐
│ Hand               │ Ways       │ Probability │
├────────────────────┼────────────┼─────────────┤
│ Royal Flush        │ 4          │ 0.000154%   │
│ Straight Flush     │ 36         │ 0.00139%    │
│ Four of a Kind     │ 624        │ 0.0240%     │
│ Full House         │ 3,744      │ 0.1441%     │
│ Flush              │ 5,108      │ 0.1965%     │
│ Straight           │ 10,200     │ 0.3925%     │
│ Three of a Kind    │ 54,912     │ 2.1128%     │
│ Two Pair           │ 123,552    │ 4.7539%     │
│ One Pair           │ 1,098,240  │ 42.2569%    │
│ High Card          │ 1,302,540  │ 50.1177%    │
└────────────────────┴────────────┴─────────────┘

KEY CALCULATIONS:

Royal Flush: C(4,1) = 4 (one per suit)
Straight Flush: C(10,1) × C(4,1) - 4 = 36 (10 starting values × 4 suits, minus royals)
Four of a Kind: C(13,1) × C(4,4) × C(12,1) × C(4,1) = 624
Full House: C(13,1) × C(4,3) × C(12,1) × C(4,2) = 3,744
Flush: C(4,1) × C(13,5) - 36 = 5,108 (minus straight flushes)
Straight: 10 × 4^5 - 36 = 10,200 (minus straight flushes)
Three of a Kind: C(13,1) × C(4,3) × C(12,2) × 4^2 = 54,912
Two Pair: C(13,2) × C(4,2)^2 × C(11,1) × C(4,1) = 123,552
One Pair: C(13,1) × C(4,2) × C(12,3) × 4^3 = 1,098,240

Puzzle 7: Expected Value Problems

Problem: (a) You roll a fair die. You get paid the number shown in dollars. You can re-roll once if you want. What is the optimal strategy and expected value? (b) A fair coin is tossed until the first head. You get &dollar;2^n if it takes n tosses. What is the expected payout?

expected-value

STEP-BY-STEP SOLUTION

(a) Die with one re-roll:
  If you keep the first roll: E(keep) = value shown
  If you re-roll: E(re-roll) = E(die) = (1+2+3+4+5+6)/6 = 3.5
  
  Optimal strategy: Re-roll if first roll < 3.5, i.e., if you roll 1, 2, or 3.
  Keep if you roll 4, 5, or 6.
  
  E(overall) = P(roll ≤ 3) × E(re-roll) + P(roll ≥ 4) × E(roll | roll ≥ 4)
  = (3/6) × 3.5 + (3/6) × (4+5+6)/3
  = 0.5 × 3.5 + 0.5 × 5
  = 1.75 + 2.50
  = 4.25

(b) St. Petersburg Paradox:
  P(first head on toss n) = (1/2)^n
  Payout = 2^n dollars
  
  E(payout) = sum of 2^n × (1/2)^n for n=1,2,3,...
            = sum of 1 for n=1,2,3,...
            = 1 + 1 + 1 + ... = INFINITY
  
  The expected value is INFINITE, yet no rational person would pay 
  more than ~&dollar;10-25 to play. This is the St. Petersburg Paradox.
  
  Resolution: Expected UTILITY (not dollars) is finite if utility is 
  logarithmic: E(log(2^n)) = sum of n × (1/2)^n = 2 (finite!).

💡

Key Insight: For decision problems, compare the expected value of each action and choose the maximum. The St. Petersburg Paradox demonstrates that infinite expected monetary value does not mean infinite real-world value — utility theory resolves this.

Puzzle 8: Random Walk — Will You Return to the Start?

Problem: You start at position 0 on a number line. Each step, you move +1 or -1 with equal probability (1D random walk). (a) What is the probability of eventually returning to 0? (b) What about a 2D random walk on a grid?

random-walk

STEP-BY-STEP SOLUTION

(a) 1D Random Walk — Returning to origin:
  P(return to 0 eventually) = 1 (CERTAIN)
  
  After 2n steps: P(at origin) = C(2n,n) × (1/2)^(2n)
  This is related to the Catalan numbers.
  
  Expected time to return to origin: INFINITE!
  Pólya's theorem: In 1D, a random walk is RECURRENT (returns 
  to every point infinitely often with probability 1).

(b) 2D Random Walk — Returning to origin:
  P(return to 0 eventually) = 1 (CERTAIN)
  
  Pólya's theorem: In 2D, the walk is also RECURRENT.
  The walk returns to the origin infinitely often, but the 
  expected return time is infinite.

(c) 3D Random Walk (bonus):
  P(return to 0 eventually) ≈ 0.3405 (about 34%)
  
  Pólya's theorem: In 3D+, the walk is TRANSIENT — there is 
  a positive probability of NEVER returning!

PÓLYA'S RECURRENCE THEOREM:
  ┌─────────────────┬──────────────────────────────┐
  │ Dimension       │ P(return to origin)          │
  ├─────────────────┼──────────────────────────────┤
  │ 1D              │ 1 (certain, recurrent)       │
  │ 2D              │ 1 (certain, recurrent)       │
  │ 3D              │ ≈ 0.3405 (transient)         │
  │ 4D+             │ Decreasing (transient)       │
  └─────────────────┴──────────────────────────────┘

QUOTE: "A drunk man will find his way home, but a drunk bird may get lost forever." — Shizuo Kakutani

💡

Key Insight:Pólya's recurrence theorem is a beautiful result: random walks in 1D and 2D are recurrent (always return), but in 3D and above they become transient (may never return). This is because the probability of being at the origin after n steps decreases differently in different dimensions.

⚙️

Algorithmic Puzzles

ALGORITHMIC

Puzzle 1: Two Eggs Problem — Find the Critical Floor

Problem: You have a 100-story building and 2 identical eggs. You need to find the highest floor from which an egg can be dropped without breaking. What is the minimum number of drops guaranteed to find the answer in the worst case?

two-eggs

STEP-BY-STEP SOLUTION

With 2 eggs and 100 floors, we want to minimize worst-case drops.

Strategy: Start at floor X. If egg breaks, use 2nd egg linearly from floor 1.
If it doesn't break, go up by X-1 floors (to balance worst case).

KEY INSIGHT: The sum of steps must equal 100.
  1st drop: floor X → if breaks, worst case = X drops (X + X-1 tests)
  2nd drop: floor X + (X-1) → if breaks, worst case = X drops
  3rd drop: floor X + (X-1) + (X-2) → if breaks, worst case = X drops
  
  X + (X-1) + (X-2) + ... + 1 ≥ 100
  X(X+1)/2 ≥ 100
  X(X+1) ≥ 200
  X = 14: 14 × 15 / 2 = 105 ≥ 100 ✓
  X = 13: 13 × 14 / 2 = 91 < 100 ✗

OPTIMAL STRATEGY:
  Start at floor 14. If no break: floor 27, then 39, 51, 60, 68, 
  75, 81, 86, 90, 93, 95, 97, 98, 99, 100
  
  If egg breaks at floor 14: test floors 1-13 linearly with 2nd egg
  Worst case: 14 drops (13 + 1)
  
  If egg breaks at floor 27: test floors 15-26 linearly
  Worst case: 14 drops (2 + 12)

ANSWER: 14 drops (minimum guaranteed in worst case)

GENERAL FORMULA:
  For N floors and 2 eggs: minimum drops = ceil((-1 + sqrt(1 + 8N)) / 2)
  For N floors and K eggs: use dynamic programming
  dp[k][n] = 1 + dp[k-1][x-1] + dp[k][n-x]  (minimize over x)

💡

Key Insight: Decrease the step size by 1 after each non-breaking drop to keep the worst case constant. This transforms the problem into finding the smallest X where X(X+1)/2 ≥ N. The solution is X = ceil((-1 + sqrt(1 + 8N)) / 2).

Puzzle 2: 8 Queens Problem

Problem:Place 8 queens on an 8×8 chessboard so that no two queens attack each other. (Queens attack horizontally, vertically, and diagonally.) How many solutions exist?

8-queens

STEP-BY-STEP SOLUTION

BACKTRACKING APPROACH:

Place queens one row at a time. For each row, try placing a queen in 
each column. Check if it conflicts with previously placed queens.

Algorithm:
  solve(row):
    if row == 8: found a solution, record it
    for col in 0..7:
      if isSafe(row, col):
        place queen at (row, col)
        solve(row + 1)  // recurse
        remove queen from (row, col)  // backtrack

  isSafe(row, col):
    Check: no queen in same column
    Check: no queen in same diagonal (row-col constant or row+col constant)

SOLUTION STATS:
  Total solutions: 92
  Distinct solutions (excluding rotations/reflections): 12
  Fundamental solutions: 12

ONE SOLUTION (column positions for each row):
  Row 0: col 4  (Queen at position 0,4)
  Row 1: col 1  (Queen at position 1,1)
  Row 2: col 5  (Queen at position 2,5)
  Row 3: col 8  (Queen at position 3,8) — WAIT, 0-indexed: col 7
  
  Actually: [1, 5, 8, 6, 3, 0, 7, 4] (1-indexed columns per row)
  Visual: . Q . . . . . .
          . . . . . Q . .
          . . . . . . . Q
          . . . . . . Q .
          . . . Q . . . .
          Q . . . . . . .
          . . . . . . Q .
          . . . . Q . . .

GENERALIZATION:
  N-Queens has solutions for all N ≥ 4.
  N=4: 2 solutions, N=5: 10, N=8: 92, N=10: 724

💡

Key Insight: This is a classic backtracking problem. Place queens row by row, checking for column and diagonal conflicts. Pruning invalid branches early is crucial for efficiency. The number of solutions grows rapidly with N.

Puzzle 3: Tower of Hanoi

Problem: You have 3 pegs and N disks of different sizes. Initially all disks are on the leftmost peg (stacked largest to smallest). Move all disks to the rightmost peg, one at a time, never placing a larger disk on a smaller one. What is the minimum number of moves?

tower-of-hanoi

STEP-BY-STEP SOLUTION

RECURSIVE STRATEGY:
  To move N disks from Source to Destination using Auxiliary:
  1. Move top N-1 disks from Source to Auxiliary (using Destination)
  2. Move the largest disk from Source to Destination
  3. Move N-1 disks from Auxiliary to Destination (using Source)

Minimum moves: 2^N - 1

Examples:
  1 disk: 1 move
  2 disks: 3 moves
  3 disks: 7 moves
  4 disks: 15 moves
  5 disks: 31 moves
  ...
  64 disks: 2^64 - 1 = 18,446,744,073,709,551,615 moves

ALGORITHM (Pseudocode):
  function hanoi(n, source, dest, aux):
    if n == 1:
      print "Move disk 1 from " + source + " to " + dest
      return
    hanoi(n-1, source, aux, dest)
    print "Move disk " + n + " from " + source + " to " + dest
    hanoi(n-1, aux, dest, source)

ITERATIVE APPROACH (Frame-Stewart):
  For even N: Move disk between Source and Aux (clockwise)
  For odd N: Move disk between Source and Dest (clockwise)
  Alternate between making the legal move with the smallest disk 
  and the only legal move without the smallest disk.

THE 64-DISK LEGEND:
  At 1 move per second: 2^64 - 1 seconds ≈ 585 billion years
  (Much longer than the age of the universe ≈ 13.8 billion years)

💡

Key Insight: The recurrence relation is T(n) = 2T(n-1) + 1, which solves toT(n) = 2^n - 1. The algorithm is optimal — no strategy can do it in fewer moves. This is an exponential time problem.

Puzzle 4: Find Missing Number in 1-100

Problem: An array contains 99 unique numbers from 1 to 100 (one number is missing). Find the missing number.

missing-number

SOLUTION 1: Sum Formula (O(n) time, O(1) space)

  Sum of 1 to 100 = 100 × 101 / 2 = 5050
  Missing number = 5050 - sum(array)
  
  Example: array = [1,2,3,5,...,100]
  sum(array) = 5050 - 4 = 5046
  Missing = 5050 - 5046 = 4 ✓

SOLUTION 2: XOR Method (O(n) time, O(1) space)

  XOR all numbers from 1 to 100, then XOR with all array elements.
  All paired numbers cancel out, leaving the missing number.
  
  result = 0
  for i = 1 to 100: result = result XOR i
  for each x in array: result = result XOR x
  // result is the missing number

SOLUTION 3: Sorting (O(n log n) time, O(1) space)

  Sort the array and scan for the gap.
  array[i] should equal i+1 (if no gap). When array[i] != i+1, 
  the missing number is i+1.

BEST APPROACH: Sum formula — simplest, O(n) time, O(1) space.

CAUTION: For very large n (up to 2^31), the sum might overflow.
  Use XOR method or long arithmetic in that case.

Puzzle 5: Trapping Rain Water

Problem: Given an array representing elevation heights, compute how much water can be trapped after raining. Example: [0,1,0,2,1,0,1,3,2,1,2,1] → 6 units.

trapping-rain-water

STEP-BY-STEP SOLUTION

INTUITION: Water above each position = min(max_left, max_right) - height[i]

SOLUTION 1: Two Arrays (O(n) time, O(n) space)

  For each position i, find:
    left_max[i] = max height from 0 to i
    right_max[i] = max height from i to n-1
  
  water[i] = min(left_max[i], right_max[i]) - height[i]
  Total water = sum of all positive water[i]

SOLUTION 2: Two Pointers (O(n) time, O(1) space) — OPTIMAL

  left = 0, right = n-1
  left_max = 0, right_max = 0
  water = 0
  
  while left < right:
    if height[left] < height[right]:
      if height[left] >= left_max:
        left_max = height[left]
      else:
        water += left_max - height[left]
      left++
    else:
      if height[right] >= right_max:
        right_max = height[right]
      else:
        water += right_max - height[right]
      right--
  
  return water

EXAMPLE WALKTHROUGH: [0,1,0,2,1,0,1,3,2,1,2,1]
  Position 2: min(1,3) - 0 = 1
  Position 4: min(2,3) - 1 = 1
  Position 5: min(2,3) - 0 = 2
  Position 6: min(2,3) - 1 = 1
  Position 9: min(3,2) - 1 = 1
  Total = 1+1+2+1+1 = 6 ✓

Puzzle 6: Maximum Subarray — Kadane's Algorithm

Problem: Given an integer array, find the contiguous subarray with the largest sum. Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → answer is [4,-1,2,1] with sum 6.

kadanes-algorithm

STEP-BY-STEP SOLUTION

KADANE'S ALGORITHM (O(n) time, O(1) space):

Core idea: At each position, decide whether to:
  (a) Extend the previous subarray, OR
  (b) Start a new subarray from current position

max_ending_here = max(nums[i], max_ending_here + nums[i])
max_so_far = max(max_so_far, max_ending_here)

WALKTHROUGH: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
  i=-2: max_end=-2, max_far=-2
  i= 1: max_end= 1, max_far= 1  (restart: 1 > -2+1=-1)
  i=-3: max_end=-2, max_far= 1
  i= 4: max_end= 4, max_far= 4  (restart: 4 > -2+4=2)
  i=-1: max_end= 3, max_far= 4
  i= 2: max_end= 5, max_far= 5
  i= 1: max_end= 6, max_far= 6  ← ANSWER
  i=-5: max_end= 1, max_far= 6
  i= 4: max_end= 5, max_far= 6

ANSWER: Maximum sum = 6, subarray = [4, -1, 2, 1]

EDGE CASES:
  All negative: [-5, -2, -8] → max sum = -2 (largest single element)
  All positive: [1, 2, 3] → max sum = 6 (entire array)
  Single element: [5] → max sum = 5

TO TRACK SUBARRAY BOUNDS:
  When max_ending_here restarts (nums[i] > max_ending_here + nums[i]),
  update the start index. When max_so_far updates, update end index.

💡

Key Insight:Kadane's algorithm maintains a running sum and resets when the running sum becomes negative (because extending a negative sum only decreases the total). It runs in O(n) with O(1) space.

Puzzle 7: Merge Intervals Concept

Problem: Given a collection of intervals, merge all overlapping intervals. Example: [[1,3], [2,6], [8,10], [15,18]] → [[1,6], [8,10], [15,18]].

merge-intervals

STEP-BY-STEP SOLUTION

Algorithm:
  1. Sort intervals by start time
  2. Iterate through sorted intervals
  3. If current interval overlaps with the last merged interval, merge them
  4. Otherwise, add current interval to result

Algorithm (detailed):
  sort intervals by start time
  result = [intervals[0]]
  
  for each interval in intervals[1:]:
    last = result[-1]
    if interval.start <= last.end:  // overlap
      last.end = max(last.end, interval.end)  // merge
    else:
      result.append(interval)  // no overlap

WALKTHROUGH: [[1,3], [2,6], [8,10], [15,18]]
  After sorting: same (already sorted)
  
  result = [[1,3]]
  
  [2,6]: 2 ≤ 3 → overlap. Merge: [1,6]. result = [[1,6]]
  [8,10]: 8 > 6 → no overlap. result = [[1,6], [8,10]]
  [15,18]: 15 > 10 → no overlap. result = [[1,6], [8,10], [15,18]]

ANSWER: [[1,6], [8,10], [15,18]]

Time: O(n log n) for sorting + O(n) for merging = O(n log n)
Space: O(n) for the result array (O(1) extra if output doesn't count)

VARIATIONS:
  - Insert interval into sorted list of non-overlapping intervals: O(n)
  - Remove interval(s): split merged intervals
  - Find minimum number of intervals to remove to make non-overlapping: 
    greedy, sort by end time, O(n log n)

Puzzle 8: N-Puzzle (Sliding Puzzle)

Problem:The N-puzzle (or 15-puzzle) consists of N+1 tiles on an N×N grid with one empty space. Slide tiles to reach the goal state. How do you determine if a solution exists? What algorithms solve it?

n-puzzle

STEP-BY-STEP SOLUTION

SOLVABILITY CHECK:
  A puzzle state is solvable if:
  For a grid of width W:
    - If W is odd: the puzzle is solvable if and only if the number 
      of inversions is even.
    - If W is even: solvable if (inversions + row of blank from bottom) 
      is odd.
  
  An INVERSION occurs when tile A precedes tile B in the linear 
  arrangement but A > B in value.

ALGORITHMS TO SOLVE:

  1. A* Search with Manhattan Distance heuristic (optimal)
     - Manhattan distance: sum of |current_row - goal_row| + 
       |current_col - goal_col| for each tile
     - Always finds shortest solution
     - Time: depends on state space, but works well for 3×3 and 4×4

  2. IDA* (Iterative Deepening A*)
     - Memory-efficient version of A*
     - Uses threshold-based depth-first search
     - Preferred for 15-puzzle and larger

  3. Pattern Database Heuristics
     - Pre-compute optimal solutions for sub-problems
     - Very effective for 15-puzzle
     - Can solve hardest instances in seconds

COMPLEXITY:
  8-puzzle (3×3): 181,440 reachable states → solvable optimally
  15-puzzle (4×4): ~10^13 reachable states → very hard
  24-puzzle (5×5): practically unsolvable optimally

NOTE: The 14-15 puzzle (specifically tiles 14 and 15 swapped) is 
the famous UNSOLVABLE configuration that drove people crazy in the 1880s.

🔍

Pattern Puzzles

PATTERNS

Number Series Patterns

Common patterns to look for in number series problems during interviews.

Pattern Type	Example	Rule	Next
Arithmetic	2, 5, 8, 11, 14	+3 each time	17
Geometric	3, 6, 12, 24, 48	×2 each time	96
Fibonacci-like	1, 1, 2, 3, 5, 8	Sum of previous 2	13
Squares	1, 4, 9, 16, 25	n² for n=1,2,3...	36
Cubes	1, 8, 27, 64, 125	n³ for n=1,2,3...	216
Triangular	1, 3, 6, 10, 15	n(n+1)/2	21
Factorial	1, 2, 6, 24, 120	n! for n=1,2,3...	720
Alternating	2, 5, 3, 7, 4, 9	+3, -2, +4, -3, +5	5 or 11
Differences	2, 4, 8, 14, 22	2nd diff = 2	32
Prime gaps	2, 3, 5, 7, 11, 13	Prime numbers	17

Classic Sequence Puzzles

These frequently appear in aptitude tests and interviews.

Sequence	Pattern	Answer for "..."
1, 4, 9, 16, 25, ...	Perfect squares: n²	36
1, 1, 2, 3, 5, 8, 13, ...	Fibonacci: F(n) = F(n-1) + F(n-2)	21
2, 6, 12, 20, 30, ...	n(n+1) = 2, 6, 12, 20, 30	42
1, 3, 7, 15, 31, ...	2^n - 1	63
3, 6, 11, 18, 27, ...	+3, +5, +7, +9, +11	38
1, 2, 6, 15, 31, ...	+1, +4, +9, +16 (squares)	56
1, 11, 21, 1211, 111221, ...	Look-and-say (read aloud)	312211
1, 2, 4, 7, 11, 16, ...	+1, +2, +3, +4, +5	22

💡

Look-and-Say Sequence:Each term describes the previous term. "1" is read as "one 1" = "11". "11" is read as "two 1s" = "21". "21" = "one 2, one 1" = "1211". This sequence was introduced by John Conway and has fascinating mathematical properties.

Clock Angle Problems

Problem: What is the angle between the hour and minute hands at a given time?

clock-angles

FORMULA:
  Angle = |30H - 5.5M|
  where H = hour, M = minutes

DERIVATION:
  Minute hand moves: 360° / 60 = 6° per minute
  Hour hand moves: 360° / 12 = 30° per hour = 0.5° per minute
  
  Minute hand angle from 12: 6M
  Hour hand angle from 12: 30H + 0.5M
  
  Angle between them: |(30H + 0.5M) - 6M| = |30H - 5.5M|
  If angle > 180°, take 360° - angle (smallest angle).

EXAMPLES:
  3:00 → |30(3) - 5.5(0)| = 90° ✓
  9:00 → |30(9) - 5.5(0)| = 270° → 360-270 = 90°
  3:15 → |30(3) - 5.5(15)| = |90 - 82.5| = 7.5°
  6:30 → |30(6) - 5.5(30)| = |180 - 165| = 15°
  12:00 → |30(12) - 5.5(0)| = 0° (overlapping)
  6:00 → |30(6) - 5.5(0)| = 180° (straight line)

COMMON INTERVIEW QUESTION:
  "How many times do the hands overlap in 12 hours?"
  Answer: 11 times (every 65 + 5/11 minutes)
  They overlap at: 12:00, ~1:05:27, ~2:10:54, ~3:16:21, ...
  NOT 12 times because from 11:00 to 12:00, the overlap happens at exactly 12:00.

Calendar Problems — Day of Week Calculation

Problem: Given a date, determine the day of the week without using a calendar.

calendar-calculation

ZELLER'S CONGRUENCE (for Gregorian calendar):

h = (q + floor((13(m+1))/5) + K + floor(K/4) + floor(J/4) - 2J) mod 7

Where:
  h = day of week (0=Saturday, 1=Sunday, 2=Monday, ..., 6=Friday)
  q = day of month (1-31)
  m = month (3=March, 4=April, ..., 14=February)
    Note: January and February are counted as months 13 and 14 
    of the PREVIOUS year
  K = year of century (year mod 100)
  J = zero-based century (floor(year / 100))

ALTERNATIVE: Tomohiko Sakamoto's Algorithm
  t = [0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4]  (month offsets)
  If month < 3: year -= 1
  day = (year + year/4 - year/100 + year/400 + t[month-1] + date) % 7
  (0=Sunday, 1=Monday, ..., 6=Saturday)

QUICK MENTAL CALCULATION TRICK:
  1. Remember the "doomsday" for each century:
     1800s: Friday, 1900s: Wednesday, 2000s: Tuesday, 2100s: Sunday
  2. Key dates that always fall on the doomsday:
     4/4, 6/6, 8/8, 10/10, 12/12, 5/9, 9/5, 7/11, 11/7
  3. Count days from the nearest known date to your target date.

EXAMPLE: What day was January 15, 2024?
  Using Sakamoto: 
  year=2024, month=1, date=15
  Since month < 3: year = 2023
  day = (2023 + 505 - 20 + 5 + 0 + 15) % 7 = 2528 % 7 = 1 → Monday ✓

Age and Relationship Problems

Common age problem patterns and approaches.

Problem Type	Key Setup	Example
Sum of ages	Create equations from given sums	"A is twice as old as B was 5 years ago" → A = 2(B-5)
Ratio of ages	Use ratio + total to find individual ages	A:B = 3:5 and A+B = 40 → A=15, B=25
Future ages	Use (current age + years) for future	"In 10 years, A will be twice B" → A+10 = 2(B+10)
Age difference	Age difference stays constant!	If A is 5 years older than B now, A was always 5 years older

age-example

CLASSIC EXAMPLE: 
"A is 3 times as old as B. In 10 years, A will be twice as old as B."

Solution:
  A = 3B
  A + 10 = 2(B + 10)
  
  Substituting: 3B + 10 = 2B + 20
  B = 10
  A = 30
  
  Verify: In 10 years → A=40, B=20 → 40 = 2×20 ✓

TWO MORE EXAMPLES:

1. "The sum of a father and son's age is 66. The father's age is 
   the son's age reversed. How old are they?"
   
   Let son = 10a + b, father = 10b + a
   (10a+b) + (10b+a) = 66
   11(a+b) = 66 → a+b = 6
   
   Possibilities: (06,60), (15,51), (24,42), (33,33)
   Valid (father > son): (15,51), (24,42)
   "Reversed" means one specific: The son is 24, father is 42. ✓

2. "A says to B: I am 4 times as old as you were when I was 
   as old as you are now. The sum of our ages is 65."
   
   Let current ages be A and B. Age difference = A - B.
   "When I was as old as you are now" → A - (A-B) years ago = B years ago.
   At that time: A was B, B was B - (A-B) = 2B - A.
   "I am 4 times as old as you were" → A = 4(2B - A)
   A + B = 65
   
   A = 8B - 4A → 5A = 8B → B = 5A/8
   A + 5A/8 = 65 → 13A/8 = 65 → A = 40
   B = 25

Speed, Distance, Time Problems

Core formulas and common problem patterns.

Concept	Formula / Approach	Example
Basic	Speed = Distance / Time	60 km in 2 hrs → 30 km/h
Average Speed	Total distance / Total time (NOT average of speeds!)	30 km at 30 km/h + 30 km at 60 km/h → 40 km/h (not 45)
Relative Speed (same dir)	S1 - S2	Two trains 70 and 50 km/h same dir → 20 km/h relative
Relative Speed (opposite)	S1 + S2	Two trains 70 and 50 km/h opposite → 120 km/h relative
Circular Track	Same dir: relative = S1-S2, Opp: S1+S2	Laps = time × relative speed / circumference

speed-distance

COMMON TRAP: Average speed is NOT the arithmetic mean of speeds!

Correct formula: Average Speed = Total Distance / Total Time

Example: Drive 60 km at 30 km/h, then 60 km at 60 km/h.
  Time 1 = 60/30 = 2 hours
  Time 2 = 60/60 = 1 hour
  Total distance = 120 km, Total time = 3 hours
  Average speed = 120/3 = 40 km/h (NOT 45 km/h)

Harmonic mean for equal distances at different speeds:
  V_avg = 2×V1×V2 / (V1+V2) = 2×30×60/(30+60) = 3600/90 = 40 ✓

TRAINS PASSING EACH OTHER:
  Time to pass = (L1 + L2) / relative speed
  Example: Train A (200m, 60 km/h) and Train B (300m, 40 km/h), opposite direction
  Relative speed = 100 km/h = 100 × 5/18 m/s ≈ 27.78 m/s
  Time = (200 + 300) / 27.78 ≈ 18 seconds

Work-Rate Problems

Core concept and common problem patterns for work-rate questions.

Concept	Formula	Example
Work Rate	If A can do a job in n days, rate = 1/n per day	A: 6 days → rate 1/6
Combined Rate	Rate(A+B) = Rate(A) + Rate(B)	A: 1/6, B: 1/3 → together: 1/6+1/3 = 1/2 → 2 days
Pipes (fill/drain)	Fill pipe = positive rate, Drain = negative rate	Fill: 1/4 hr, Drain: 1/6 hr → net: 1/4-1/6 = 1/12 → 12 hrs

work-rate-examples

EXAMPLE 1: "A can finish a job in 10 days, B in 15 days. 
  How long to finish together?"
  
  A's rate = 1/10, B's rate = 1/15
  Combined rate = 1/10 + 1/15 = 3/30 + 2/30 = 5/30 = 1/6
  Time = 1 / (1/6) = 6 days

EXAMPLE 2: "A is twice as efficient as B. Together they finish in 
  10 days. How long would each take alone?"
  
  Let B's rate = r, A's rate = 2r
  Combined rate = 3r
  3r = 1/10 → r = 1/30
  B takes 30 days, A takes 15 days

EXAMPLE 3: "Pipe A fills a tank in 4 hours. Pipe B fills it in 6 hours. 
  Pipe C drains it in 3 hours. If all three are open, how long to fill?"
  
  Net rate = 1/4 + 1/6 - 1/3
           = 3/12 + 2/12 - 4/12
           = 1/12
  Time = 12 hours

💡

Key Insight:For work-rate problems, always convert to "work per unit time" (rates). Combined rate is the sum of individual rates. For pipes, drain pipes have negative rates. The average speed trap (arithmetic vs. harmonic mean) is one of the most common mistakes in interviews.

💡

Lateral Thinking Puzzles

LATERAL THINKING

Puzzle 1: The Man in the Elevator

Problem: A man lives on the 20th floor of a building. Every morning he takes the elevator to the ground floor to go to work. Every evening when he returns, he takes the elevator to the 10th floor and walks up the remaining 10 flights of stairs — except when it rains, in which case he rides all the way to the 20th floor. Why?

man-in-elevator

ANSWER: The man is a dwarf (or very short person).

EXPLANATION:
  - He can reach the button for the ground floor (1) without any issue.
  - On the way up, he can only reach up to the 10th floor button.
  - When it rains, he uses his UMBRELLA to press the 20th floor button.
  
KEY PRINCIPLE: Challenge your assumptions! The puzzle never says 
the man is of average height. Ask yourself: "Why can he only reach 
the 10th floor button?" → physical limitation. "What changes 
when it rains?" → he carries an umbrella → extends his reach.

GOOD QUESTIONS TO ASK THE INTERVIEWER:
  - Is there something about the elevator itself? (No)
  - Does he have a physical condition? (Yes, in a way)
  - Is he afraid of heights? (No)
  - Does the elevator have a weight limit issue? (No)
  - Is there someone else involved? (No)
  - Does he want the exercise? (No)

💡

Approach: In lateral thinking puzzles, the answer usually involves a creative interpretation of the scenario. Ask yes/no questions to narrow down the possibilities. The key is challenging assumptions you did not even know you were making.

Puzzle 2: Dead Man in the Field

Problem: A dead man is found lying face down in a field, next to an unopened package. There are no footprints around him. How did he die?

dead-man-field

ANSWER: The man died when his parachute failed to open.

EXPLANATION:
  - He was skydiving and jumped from an airplane.
  - His parachute (the "unopened package") did not deploy.
  - He landed in the field and died from the fall.
  - There are no footprints because he fell from the sky.

KEY PRINCIPLE: The "unopened package" is a parachute. "No footprints" 
suggests the man did not walk to his location — he arrived from above.

GOOD QUESTIONS TO ASK:
  - Is the field in a remote area? (Irrelevant)
  - Was he murdered? (No, not in the traditional sense)
  - Is the package important? (Yes, very!)
  - Did someone else place him there? (No)
  - Was he alive when he arrived? (Yes, briefly)
  - Did he arrive by vehicle? (No)
  - Is this a real-world scenario? (Yes)

Puzzle 3: Man in Bar Asks for Water

Problem:A man walks into a bar and asks for a glass of water. The bartender pulls out a gun and points it at him. The man says "Thank you" and leaves. Why?

man-bar-water

ANSWER: The man had hiccups. The gun scare cured them.

EXPLANATION:
  - The man had the hiccups and wanted a glass of water to cure them.
  - The bartender heard him hiccuping and realized what the problem was.
  - Instead of giving water, he used a sudden scare (pointing a gun) 
    to cure the hiccups — an old folk remedy.
  - The scare worked, the hiccups were gone, and the man said "thank you."

KEY PRINCIPLE: The bartender's action was HELPFUL, not threatening. 
What seems aggressive was actually a remedy.

GOOD QUESTIONS TO ASK:
  - Was the man thirsty? (Yes, but that is not the main issue)
  - Did the bartender want to hurt him? (No)
  - Was the gun real? (Yes)
  - Did the gun fire? (No)
  - Was the man in danger? (No, not really)
  - Did the man have a medical condition? (Yes!)

Puzzle 4: Two Barbers

Problem: A town has only two barbers. One has a neat, clean shop and a great haircut. The other has a messy shop and a terrible haircut. Which barber should you go to?

two-barbers

ANSWER: Go to the barber with the MESSY shop and TERRIBLE haircut.

EXPLANATION:
  - There are only TWO barbers in town.
  - Each barber cuts the other's hair!
  - The barber with the terrible haircut → the OTHER barber (messy shop) 
    did that haircut. So the messy barber gives great haircuts.
  - The barber with the great haircut → the NEAT barber did it. 
    So the neat barber is skilled.
  
  Wait — re-read: the NEAT barber has a great haircut (done by the 
  messy barber) and the MESSY barber has a bad haircut (done by the 
  neat barber).
  
  → Go to the MESSY barber, because he gave the neat barber that 
  great haircut!

KEY PRINCIPLE: Self-reference / mutual dependency. If A cuts B's 
hair and B cuts A's hair, the quality of each's haircut reflects 
the OTHER barber's skill.

CORRECT ANSWER: The barber with the messy shop. His great work is 
on display (the other barber's head).

Puzzle 5: Broken Light Switch

Problem: You are in a room with 3 light switches. Each corresponds to one of 3 light bulbs in another room. You can only visit the other room once. How do you determine which switch controls which bulb?

light-switch

ANSWER: Use heat as a second signal!

STEP-BY-STEP:
  1. Turn ON Switch 1 and wait for 5-10 minutes.
  2. Turn OFF Switch 1, turn ON Switch 2.
  3. Leave Switch 3 OFF.
  4. Go to the other room.

OBSERVATIONS:
  - The bulb that is ON → Switch 2
  - The bulb that is OFF but WARM → Switch 1 (was on, now off)
  - The bulb that is OFF and COLD → Switch 3 (never turned on)

KEY PRINCIPLE: You have 3 switches but only visual information 
(ON/OFF) gives 2 states — not enough for 3 bulbs. By adding 
the TEMPERATURE dimension (warm/cold), you create a third state 
and can distinguish all 3 bulbs with one visit.

This puzzle tests whether you think beyond the obvious (ON/OFF) 
to consider other properties of the system (heat generation).

Puzzle 6: Cabin on the Mountain

Problem: A cabin is found on the side of a mountain. Inside, there are two dead people. How did they die?

cabin-mountain

ANSWER: It is the cabin of an airplane that crashed into the mountain.

EXPLANATION:
  - The "cabin" is an AIRPLANE CABIN, not a mountain cabin.
  - The two dead people were the pilot and co-pilot (or passengers).
  - The plane crashed into the mountain, killing everyone inside.

KEY PRINCIPLE: Word ambiguity. "Cabin" most commonly means a 
wooden house, but it can also mean the passenger compartment of 
an aircraft. The puzzle exploits this double meaning.

OTHER POSSIBILITIES:
  - Could it be a ship's cabin on a mountain? (Unlikely)
  - A space capsule? (Possible but less common)
  - An elevator cabin? (Does not make sense on a mountain)

This is the quintessential lateral thinking puzzle that demonstrates 
how language ambiguity can completely change the interpretation.

💡

General Strategy for Lateral Thinking:(1) Ask yes/no questions to narrow the problem. (2) Challenge every assumption. (3) Consider alternative meanings of words. (4) Think about what is NOT said. (5) Ask "What if the obvious interpretation is wrong?"

✅

Tips & Resources

TIPS & RESOURCES

Interview Tips for Puzzles

Tip	Details	Impact
Think Aloud	Verbalize every thought, even wrong ones. Interviewers want to see your process.	Critical
Start with Examples	Use small cases (n=1,2,3) to build intuition before generalizing.	High
State Assumptions	Clearly state any assumptions you make. It shows structured thinking.	High
Draw Diagrams	Visualize the problem. Trees, tables, and diagrams clarify complex scenarios.	Medium-High
Simplify First	Solve a simpler version of the problem, then add complexity.	High
Verify with Edge Cases	Test your answer with boundary values (0, 1, n, maximum).	Medium
Stay Calm	If stuck, take a breath. Try a different approach. Ask for a hint.	Critical
Time Management	Spend 2 min understanding, 5 min exploring, then converge. Do not spiral.	High

Common Mistakes to Avoid

Mistake	Why It Is Bad	What to Do Instead
Silent thinking	Interviewers cannot evaluate your reasoning process	Think aloud constantly
Jumping to answers	Premature answers miss edge cases	Explore multiple approaches first
Ignoring constraints	Solving the wrong version of the problem	Re-read the problem, confirm constraints
Giving up too fast	Shows lack of perseverance	Try 2-3 approaches before asking for hints
Overcomplicating	Simple solutions often exist	Start simple, add complexity only if needed
Not verifying	Wrong answers look worse than slow correct ones	Always test with examples
Bad body language	Shows frustration, low confidence	Stay positive, smile, maintain eye contact
Not asking questions	Missed clarifications lead to wrong answers	Ask 2-3 questions upfront

How to Handle Being Stuck

Follow this systematic approach when you hit a wall:

Step	Action	Example
1	Restate the problem in your own words	"So we need to find the minimum number of races..."
2	Try the smallest possible example	"Let me try with 3 horses instead of 25..."
3	Look for a pattern	"For 3 horses: 1 race. For 9 horses: 3+1=4 races..."
4	Try a completely different approach	Switch from greedy to binary search thinking
5	State what you have figured out	"I know we need 5 races for the first pass..."
6	Ask a targeted question	"Can I eliminate horses based on their group performance?"
7	If truly stuck after 5 min	Politely ask: "May I have a hint?"

🚫

When to ask for hints vs. keep trying: If you have explored at least 2-3 approaches and made some progress, it is better to ask for a hint than to sit in silence for 5+ minutes. Interviewers generally prefer candidates who engage and ask thoughtful questions over those who freeze. However, never ask for a hint in the first 2-3 minutes — show initiative first.

Practice Resources

Resource	Type	Description
"How Would You Move Mount Fuji?"	Book	Classic book by William Poundstone — the bible of interview puzzles
"Heard on the Street" (Tim Falcon Crack)	Book	Quantitative/probability questions for finance interviews
"Puzzles to Puzzle You" (Shakuntala Devi)	Book	Famous Indian puzzle book — great for aptitude prep
"Aha! Solutions" (Martin Erickson)	Book	Mathematical puzzles with elegant solutions
Brilliant.org	Website	Interactive problem-solving courses in math, CS, logic
LeetCode (Interview section)	Website	Coding + brainteaser problems with company tags
GeeksforGeeks (Puzzles)	Website	Large collection of interview puzzles with solutions
Puzzle Baron	Website	Logic puzzles, brain teasers, and more
YouTube: MindYourDecisions	Channel	Math puzzles by Presh Talwalkar — excellent explanations
YouTube: 3Blue1Brown	Channel	Visual math explanations — great for probability and algorithms
YouTube: TED-Ed Riddles	Channel	Animated riddles with step-by-step solutions

Company-Wise Puzzle Frequency

Company	Puzzle Frequency	Common Types	Notes
Google	Low-Medium	Estimation, probability, algorithmic	Shifted away from puzzles toward DSA + system design
Microsoft	Medium	Logic, algorithmic, behavioral	Still asks puzzles in some divisions
Adobe	Medium-High	Logic, math, pattern	Known for brain teasers in engineering interviews
Directi (Media.net)	High	Logic, math, probability, lateral	Famous for asking multiple puzzles per interview
Goldman Sachs	High	Probability, math, estimation	Quant-heavy — expected to be very comfortable with numbers
Amazon	Low	Leadership principles + DSA	Rarely asks pure puzzles, focuses on behavioral + coding
Meta	Low	DSA + system design	Coding and systems focused, puzzles very rare
JP Morgan	Medium-High	Probability, brainteasers, estimation	Finance-oriented puzzles and guesstimates
DE Shaw	High	Math, probability, algorithms	Quant firm — expects strong analytical skills
Citadel	High	Probability, math, optimization	Hedge fund — very challenging quantitative puzzles

💡

Final Advice: Puzzles test your problem-solving approach more than the correct answer. Practice regularly (at least 2-3 puzzles per day for 2-3 weeks before interviews). Focus on understanding the underlying principles rather than memorizing solutions. If you understand WHY a solution works, you can adapt it to new problems. Most importantly: think aloud, stay calm, and show enthusiasm for the challenge!

quick-reference-formulas

╔══════════════════════════════════════════════════════════╗
║              QUICK FORMULA REFERENCE CARD                 ║
╠══════════════════════════════════════════════════════════╣
║ P(no event) = 1 - P(event) [complementary counting]     ║
║ P(A or B) = P(A) + P(B) - P(A and B) [inclusion-excl]  ║
║ P(A|B) = P(B|A)·P(A) / P(B) [Bayes' theorem]           ║
║ E(geometric) = 1/p [expected trials for first success]  ║
║ C(n,r) = n! / (r!(n-r)!) [combinations]                 ║
║ n! ≈ sqrt(2πn)·(n/e)^n [Stirling's approximation]      ║
║ 2^k tests → test up to 2^k items [binary encoding]      ║
║ T(n) = 2^n - 1 [Tower of Hanoi]                         ║
║ E(n heads in row) = 2^(n+1) - 2 [fair coin]             ║
║ Clock angle = |30H - 5.5M|                              ║
║ Average speed (equal dist) = 2·V1·V2/(V1+V2) [harmonic] ║
║ Work rate: combined = sum of individual rates            ║
╚══════════════════════════════════════════════════════════╝

⏳

Loading cheatsheet...