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)

Aug 26, 2014

"Flawless Harmony" Puzzle

Source: AUSTMS Puzzle Corner 35

Problem:

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.


Aug 11, 2014

Minimum sum of numbers in an array

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

Problem:

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

Problem:




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?

Jul 11, 2014

3D Tic Tac Toe Puzzle

Source: Shared by Alok Mittal (Cannan Partners)

Problem:
A 3x3 tic tac toe has 8 "winning lines" (3 horizontal, 3 vertical and 2 diagonals). How many "winning lines" does the 3x3x3 3D tictactoe have? There is a brute force solution, and then there is the aha! solution.


Jul 3, 2014

Mad Robot Puzzle

Source: http://nrich.maths.org/

Problem:



A mad robot sets off towards the North East on a journey from the point (0,0) in a coordinate system. It travels in stages by moving forward and then rotating on the spot. It follows these pseudo-code instructions:

SUB JOURNEY
    DISTANCE = 1000
    WHILE (DISTANCE > 0.001)
        MOVE DISTANCE
        STOP
        ROTATE(90, DEGREES, CLOCKWISE)
        DISTANCE = DISTANCE / 2
    END WHILE
    EXPLODE
END SUB

Where does the robot explode?