CSE Blog - quant, math, computer science puzzles

Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Jan 23, 2015

Box in Box problem

Source: Sent to me by Sudeep Kamath

Problem:

Airline check-in baggage has size restriction by ​so-called ​linear dimension: length + breadth + height should not exceed 62 inches. Prove that you can't "cheat" by packing a box with higher linear dimension into a box with ​lower​ linear dimension.


Jan 21, 2015

Fibonacci Multiple Puzzle

Source: Mailed to me by Kushagra Singhal, IIT Kanpur, PhD Student at University of Illinois at Urbana-Champaign

Problem:

Prove that for any positive K, every Kth number in the Fibonacci sequence is a multiple of the Kth number in the Fibonacci sequence.

More formally, for any natural number n, let F(n) denote Fibonacci number n. That is, F(0) = 0, F(1) = 1, and F(n+2) = F(n+1) + F(n). Prove that for any positive K and natural n, F(n*K) is a multiple of F(K).

Jan 19, 2015

Gold Silver Numbers Puzzle

Source: Mailed to me by JDGM ("regular commenter JDGM")

Problem:

The integers greater than zero are painted such that:

• every number is either gold or silver.
• both paints are used.
• silver number + gold number = silver number
• silver number * gold number = gold number

Given only this information, for each of the following decide whether it is a gold number, a silver number, or could be either:

1.) gold number * gold number
2.) gold number + gold number
3.) silver number * silver number
4.) silver number + silver number

Dec 28, 2014

Maximum Number of Collinear Points

Source: Asked to me by a friend - who was asked this question in an interview at Facebook

Problem:

Given n points on a 2D plane, find the equation of the line with maximum number of collinear points. What is the time complexity of your algorithm?






Dec 21, 2014

Mathematics of SET game

Source: Sent to me by Pritish Kamath (http://www.mit.edu/~pritish/)

Problem:



Have you ever played "SET"? You have to play it.
http://www.setgame.com/learn_play
http://www.setgame.com/sites/default/files/Tutorials/tutorial/SetTutorial.swf

Even if you have not played the game, the game can be stated in a more abstract way as follows:
There are 12 points presented in F34 and the first person to observe a "line" amongst the 12 given points gets a score. Then the 3 points forming the line are removed, and 3 random fresh points are added.

Problem 1: How many points in F34 are needed to be sure that there exists a line among them?
Problem 2: Given 12 random points in F34, what is the probability that there exists a line among them?

Disclaimer:
We have not solved the problem yet. It can be very difficult or very easy.

Update (22/12/14):
It turns out to be a very very difficult problem.
Paper: http://www.math.rutgers.edu/~maclagan/papers/set.pdf
Links: http://www.setgame.com/teachers-corner/research
The answer to Problem 1 is 21.