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)

Oct 18, 2014

Diminishing Differences Puzzle

Source: Australian Mathematical Society Gazette Puzzle Corner 34

Problem: Begin with n integers x1, . . . , xn around a circle. At each turn, simultaneously replace all of them by the absolute differences

Repeat this process until every number is 0, then stop. Prove that this process always terminates if and only if n is a power of 2.

Shameless plug:
Follow CSE Blog on CSE Blog - Twitter and CSE Blog on Quora. :-)

Sep 19, 2014

Balancing Act Puzzle

Source: Australian Mathematical Society Gazette Puzzle Corner 35

There are some weights on the two sides of a balance scale. The mass of each weight is an integer number of grams, but no two weights on the same side of the scale share the same mass. At the moment, the scale is perfectly balanced, with each side weighing a total
of W grams. Suppose W is less than the number of weights on the left multiplied by the number of weights on the right.

Is it always true that we can remove some, but not all, of the weights from each side and still keep the two sides balanced?

Aug 26, 2014

"Flawless Harmony" Puzzle

Source: AUSTMS Puzzle Corner 35


Call a nine-digit number flawless if it has all the digits from 1 to 9 in some order. An unordered pair of flawless numbers is called harmonious if they sum to 987654321. Note that (a, b) and (b, a) are considered to be the same unordered pair.

Without resorting to an exhaustive search, prove that the number of harmonious pairs is odd.

Update (23 Oct 2014):
Solution: Posted by me (Pratik Poddar) in comments!

Aug 11, 2014

Minimum sum of numbers in an array

Source: Asked to me on quora ( cseblog.quora.com )


Given an array of n positive numbers (n ~ 100000), what is the algorithmic approach to find the minimum possible sum (>=0) by using all the numbers in an array?

Example 1:
1 2 2 3 4
Answer : 0 (-1+2-2-3+4)

Example 2:
2 3 4 7 13
Answer: 1 (+2-3-4-7+13)

Aug 6, 2014

Caterer's Problem

Source: Puzzle Toad CMU


You are organizing a conference, with a festive dinner on the first day. The catering service has 1024 different dinner choices they know how to make, out of which you need to choose 10 to be in the dinner menu (each participant will choose one of these during the dinner). You send an email to the 6875 participants of the conference, with the list of all 1024 choices, asking them to rank the choices in linear order from their favorite to their unfavorite.

You want to find a list L of 10 choices, such that for any dinner choice d not in the list L, if we run a vote of d against L, at least half of people will favor one of the choices in L over d (it may be different dish for different people).

Is it always possible to produce such a list?