Posts

Showing posts from 2013

Determinant of Matrix (17-11)

Source: Mailed by Sudeep Kamath (EECS PhD Student, UC Berkeley, EE IITB 2008 Alumnus)

Problem:

A is a 300 x 300 matrix with 17 on the diagonal, and the rest of the entries being 11. What is det (A) ?

Update: (21 June 2014):

Solution posted by Gowtham R (Stanford), Justin Rising, Pavan Bharadwaj, Hansaplatz and gaurushh in comments! Thanks






Open Ended Search Problem

Disclaimer: It is a made up problem. Not to be attempted by light hearted.

Problem:
I have a 300 word text. I have a large list of indexed strings (Length of string ~ 20, Number of strings ~ 1M). I need to figure out phrases in the 300 word text that match exactly to one of the strings in the large list of strings I have.

A naive approach:
Taking all 45000 (300 C 2) phrases, search in the large list of strings. Can we do better than this? We need to minimize calls to list of indexed strings!


Picking K elements randomly

Problem 1: Consider the problem of picking K elements randomly from N elements. Suggest an algorithm. What is the time and space complexity of your algorithm?

Problem 2: Now consider that the stream is infinitely long (i.e. N is unknown). Now how do we pick K elements randomly.

Update (24 June 2014):
Solution: Posted by Himanshu (Prob 1), PlacementIITB2014 (Prob2) and Sid (Prob1 and Prob2) in comments! Thanks
claimtoken-52ac74fbddf1e

Technical Interview Brain Teaser - IBM Ponder This - Neighbour Configuration

Source: IBM Ponder This Dec 12 ( http://domino.research.ibm.com/comm/wwwr_ponder.nsf/challenges/December2012.html ) - Mailed to me by Aashay Harlalka (Final Year Student, CSE, IITB)

Problem:

36 people live in a 6x6 grid, and each one of them lives in a separate square of the grid. Each resident's neighbors are those who live in the squares that have a common edge with that resident's square.

Each resident of the grid is assigned a natural number N, such that if a person receives some N>1, then he or she must also have neighbors that have been assigned all of the numbers 1,2,...,N-1.

Find a configuration of the 36 neighbors where the sum of their numbers is at least 90.

As an example, the highest sum we can get in a 3x3 grid is 20:
1 2 1
4 3 4
2 1 2

Update (24 June 2014):
Solution: Available on IBM Research Ponder This - December 2012 Solution

Two Coin Tossing Puzzle - Expected Number of Tosses

Source: Mailed to me by Vashist Avadhanula (PhD Student at Columbia Business School, EE IITB 2013 Alumnus)

Problem:
Consider a case where you flip two fair coins at once (sample space is HH, HT, TH & TT) you repeat this experiment many times and note down the outputs as a sequence. What is the expected number of flips (one flip includes tossing of two coins) to arrive at the sequence HHTHHTT.

Calculus Limit Puzzle

Source: Mailed to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008)

Problem:

Tricky Question.

Let f be a continuous, real-valued function on reals such that
limit_{n \rightarrow \infty} f(nx) = 0 for all real x.

Show limit_{x\rightarrow \infty} f(x) = 0.

Weighing Problem - Discrete Mathematics Puzzle

Source: Sent to me by Aashay Harlalka (Final Year Student, CSE, IITB)

Problem: For a given positive integer n, what would be the minimum no. of weights required so that we can weigh all positive integers <= n

Follow up Generalized problem:
If we have k copies of each distinct weight, then what is the minimum no. of distinct weights required ?

Old Related Puzzle:
There is a very different popular problem but knit in the same story (posted 4 years back on the blog): Weighing Problem
Note : Weights are of integer values only.

Discrete Mathematics Problem - Grouping Students

Source: Sent to me by Vinayak Gagrani (CSE IITB Alumnus 2013)

Problem:

There are 289 students. We have to divide them into 17 groups of 17 each every day. The groups have to be such that no two students who have been previously on some group together can be formed a group again. How many days can we do this ?

Extension:
Can this be generalized for any N^2 students?

Prime Power Math Puzzle

Source:IBM Ponder This - June 2012 - Sent to me by Aashay Harlalka (Final Year Student, CSE, IITB)

Problem:

Two players starts with the number N and play in turns. In each turn the player chooses a prime power p^m > 1, which divides N and updates N to be N/(p^m). The player who sets N to be 1 - wins.
What are all the winning moves from the initial state of N=1,506,009,006,001,500,000,000 ?

We are looking for all the moves the first player can make which, assuming he plays correctly, can guarantee him winning the game.

Update (24 June 2014):
Solution: Posted by Gowtham Kumar (PhD Student, Stanford, IITM Alumnus) and me in comments!




Odd Even Algorithm Puzzle

Source:http://thomer.com/riddles/

Problem:

If you have an array with random odd and even numbers, what is the most efficient algorithm you can think of to put all even numbers on one side and all odd numbers on the other side in this array? What is the complexity of your algorithm?

Update ( 21 June 2014)

Solution posted by nick, Abhishek, Khalil Sawant, Sandeep, Stainless (Ameya Ranade - CSE IITB 2009 Alumnus, Google Engineer, Facebook Engineer), Piyush Sao, Sakshi, Kaushal and Pankaj Jindal in comments! Thanks.

Chess 5 Piece Puzzle

Image
Source: Mailed to me by Smriti Mittal (Final year student, IIT Bombay)

Problem:
Green numbers indicate how many pieces could move to that square on the next move. Blue squares show the possible locations of the following five different chess pieces: King Queen Rook Bishop Knight

How are the five pieces arranged?



Lets mark the squares as (r,c) where r is the row number and c is the column number. So, the squares where the pieces are to be kept are: (1,1), (1,8), (5,8), (6,3), (8,2)



Number of Paths in Rectangular Grid

Image
Source: Solved it during Algorithms Course under Prof Diwan, and discussed with Nikhil Jain (IT BHU 2008 Alumnus, Product Manager at AskLaila)
Problem:
1. (Easy) 
Consider a n x m rectangular grid. The problem is to find the number of shortest (or monotonic in this case) paths along the edges of the cell that start at (0,0) and end at (n,m).
A monotonic path is a path always moving towards the goal, i.e. consists of moving up or right but not down or left. Figure 1 illustrates such a path for a grid of size 5 x 3.


2. (Difficult) 
Now we need to print all monotonic paths that do not go above the diagonal y = x. Figure 2 shows such a path. Note that the path in figure 1 goes above the diagonal, hence not desirable in this case. How many such paths exist for n x m grid (n >= m)?

Disclaimer: The first problem is too simple, and the second is very challenging. Have fun :-)


Divisibility Problem

Image
Source:
Posted by JDGM (James Miles) in comments on http://www.puzzletweeter.com ( A fanstastic blog by Gowtham Kumar, PhD Student, Stanford, IITM Alumnus)

Problem:
Prove that from the numbers 1 to 200 we cannot pick 101 of them such that none divide any other.


Update (24 June 2014):
Solution: Posted by Suman Datta, Stainless (Ameya Ranade, CSE IITB 2009 Alumnus, Microsoft, Google, Facebook Engineer) and Wei Chen in comments!

Most popular Puzzle Books for Technical / Quant Finance Interviews

Find Fixed Point (x[i]=i) in an Array

Source: Asked in an Amazon interview to a friend

Problem:

Given an array of size n, x[0 .. n-1] of integers sorted into ascending order with no duplicates, find an array item that is also its index, so that x[i] = i.

For example, x[3] = 3 in the array shown below:

i           0 1 2 3 4 5
x[i]     -3 0 1 3 5 7

Your task is to write a program that finds i.

Disclaimer:
Yes, its a very easy problem, as far as algorithm is concerned. Its here for people preparing for interviews to see if they can write code.


Walking Ant Problem - Part 2

Image
Source: Original problem adapted from the "Ants Problem" (Link removed) at "CMU ACM Programming Contest" . Extension to the 4 year old problem on CSE Blog - Walking Ants Puzzle . Problem also available at J. Paulson Programming Blog

Problem:


You have a bunch of ants on a meter stick, each walking 1cm/s in some direction. If an ant hits the end of the stick, it falls off. If two ants collide, they both reverse direction.

Walking Ants Puzzle earlier essentially asked: Given the starting positions and directions of all the ants, how long until the last ant falls off?

The new problem is :
Given the starting positions and directions of all the ants, which ant(s) are the last to fall off?

Disclaimer: I do not have the solution to the problem. It just looks like an interesting problem to solve.

( Readers Please ignore: Technorati claim: 6QVZ8YSY6XSD )

Update (24 June 2014):
Solution: Posted by Strilanc and me in comments!



Guide to Wall Street Quant Jobs for IITians

Minimum Point in a Rotated Sorted Array

Source: Asked for a data scientist position at a technology startup in financial services sector in London

Problem:

What is the optimal algorithm to find the minimum element given a rotated sorted array of integers?
A rotated sorted array of integers is the output array of a rotation operation performed on a sorted array.
Eg: 3 5 6 1 2

Update (24 June 2014):
Solution: Posted by Gaurav Bijay Kumar (CSE IITB 2006, Goldman Sachs Quant, Morgan Stanley Quant, Chicago Booth MBA, Credit Suisse IB, Goldman Sachs Strat), Sandeep, Khalil Sawant, Himanshu, ciddhi and gaurushh.

Probability Puzzle: Expected Number of Expression Evaluations

Source: Asked for a data scientist position at a technology startup in financial services sector in London
Problem:
Given python code to calculate maximum in an array of integers x

def find_max(x):

    max_num = x[0]

    for i in x[1:]:
        if i > max_num:
            max_num = i<< Expected number of times this expression was evaluated

    return max_num


Calculate the expected number of times the expression max_num = i was evaluated, given that array x was taken from a uniform random distribution.

Combinatorics + Game Theory Puzzle

Source: Random search on http://math.stackexchange.com/

Problem:

Two players A and B play the following game:

Start with the set S of the first 25 natural numbers: S={1,2,…,25}.

Player A first picks an even number x_0 and removes it from S: We have S:=S−{x_0}.

Then they take turns (starting with B) picking a number x_n∈S which is either divisible by x_n-1 or divides x_n-1 and removing it from S.

The player who can not find a number in S which is a multiple or is divisible by the previous number looses.

Which player has the winning strategy and what is it?

Self Referential Problem - from "What would Martin Gardner Tweet"

Source:The Math Factor (contains spoilers) - also tweeted on What Would Martin Gardner Tweet

Problem:
The number of 1′s in this paragraph is ___; the number of 2′s is ___; the number of 3′s is ____; and the number of 4′s is ___.

Bonus Research Follow-up Problem:
The number of 1′s in this paragraph is ___; the number of 2′s is ___; …..(and so on) and the number of N’s is ___.
For N=2 or 3, there are no solutions (Asking that all the numbers we fill in are between 1 and N); for N=4 there are two. For N=5 there is just one, for N=6 there are none and beyond that there is just one.
Prove it.

claimtoken-51f4577649b8d

Edit Distance Problem

Source:http://people.csail.mit.edu/bdean/6.046/dp/

Problem: 
Given two text strings A of length n and B of length m, you want to transform A into B with a minimum number of operations of the following types: delete a character from A, insert a character into A, or change some character in A into a new character. The minimal number of such operations required to transform A into B is called the edit distance between A and B.

Given two strings A and B, what is the path from A to B with minimum edit distance?


Math Game of Zero String

Source: Quantnet

Problem:

You have a string of bits. You scan from right to left.

If you encounter a '1', you have the option to flip it to a 0 or keep it as is.

If you encounter a '0', your adversary has the option to flip it to a 1 or keep it as is.

Your goal is to zero all the bits once you reach the end of a scan (i.e. at the left most bit), whilst you adversary wishes to prolong the game indefinitely.

We continually re-scan until we reach the aforementioned goal state.

Can you prove that the game will eventually terminate?

Math in Movies

List of 25 movies - where Mathematics was a core part of the Movie

Shared as an IMDB List http://www.imdb.com/list/zyWjUfnfwdY

Taken from http://www.math.harvard.edu/~knill/mathmovies/

Math in Movies (IMDB List)Good Will Hunting (1997)
Twelve Monkeys (1995)
A Beautiful Mind (2001)
Equilibrium (2002)
Moneyball (2011)
Pi (1998)
Die Hard: With a Vengeance (1995)
Cube (1997)
Rites of Love and Math (2010)
23 (1998)
Colossus: The Forbin Project (1970)
Breaking the Code (1996)
Sneakers (1992)
Pay It Forward (2000)
Real Genius (1985)
The Code Conspiracy (2002)
21 (2008)
Fermat's Room (2007)
The Bank (2001)
Enigma (2001)
The Number 23 (2007)
Hackers (1995)
Infinity (1996)
The Time Machine (2002)
Cube²: Hypercube (2002)

5 Books for Quantitative Analyst Beginners

Nine Digit Number - Math Puzzle

Source: Sent to me by Sudeep Kamath via http://puzzletweeter.com/2013/06/21/884/

Problem: 
Find a nine digit number abcdefghi that uses all the digits 1,2,3,...9 exactly once and satisfies:
a is divisible by 1
ab (2 digit number with digits a and b) is divisible by 2
abc (3 digit number with digits a, b and c) is divisible by 3
.......
.......
abcdefghi is divisible by 9.

Update (29/06/2013):
Solution: Posted by JDGM, Anti, Meghana Kolan, Shwetabh Sameer and Unknown in comments! A more detailed solution provided by me in comments!

Matrix Puzzle - Math Puzzle

Source: www.puzzletweeter.com

Problem:
Let A,B be 2x2 matrices with integer entries.
Suppose the matrices A,A+B,A+2B,A+3B,A+4B are all invertible and their inverses are also integer matrices.

Then show that A+5B is invertible and it's inverse is an integer matrix.

Update (24 June 2014):
Solution: Posted by Yashoteja Prabhu (Ex-RA at Microsoft Research, IITB CSE 2011 Alumnus) and Sanchit Gupta in comments!


Art of Puzzle Solving

Equations Puzzle

Source: Interview Street

Problem: Find the number of positive integral solutions for the equations 
(1/x) + (1/y) = 1/N! 
(read 1 by x plus 1 by y is equal to 1 by n factorial) 
Print a single integer which is the no of positive integral solutions modulo 1000007.

Update (24 June 2014):
Solution: Posted by JDGM (James D G Miles) in comments!




Candy Game - Math Puzzle

Source: Mailed to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008) - He found it at http://puzzletweeter.com/

Problem:
A group of students are sitting in a circle with the teacher in the center. They all have an even number of candies (not necessarily equal). When the teacher blows a whistle, each student passes half his candies to the student on his left. Then the students who have an odd number of candies obtain an extra candy from the teacher.

Show that after a finite number of whistles, all students have the same number of candies.

Update (20 May 2013):
Partial Solution posted by JDGM in comments. Completed by me.

Black and White Squares Puzzle

Source: Mailed to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008) - He found it at http://puzzletweeter.com/

Problem:

Consider an n x n chessboard, where each square is arbitrarily chosen to be either black or white. Your goal is to make all squares in the chessboard white. At each step, you are allowed to "switch" a square, but each switch will toggle not only the particular square being switched, but also the 4 squares that are adjacent to it: Two vertically up and down and two horizontally up and down the square being switched. Note : At corners only 4/3 squares are toggled, while at the center all 5 squares are toggled.
Show how you can make the entire chessboard white.
Update (May 20 2013):
Solution: Posted by JDGM in comments! Very academic solution to a very interesting problem! :) Thanks

Penny Roll Puzzle

Source: Quantnet

Problem:
Roll a penny around another fixed penny in the center with edges in close contact. After moving half circle around the center penny, you will find the penny in motion has rotated 360 degrees.
Why?

Update (29/06/2013):
Solution posted by Sanket Patel and Suyash Jain (IITB Mech 2008 Aumnus, Ex-Credit Suisse Analyst, Ex-Deutsche Bank Analyst) in comments!


Integer Points

Source: Mailed to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008) - He found it at http://puzzletweeter.com/

Problem:

An integer point in a plane is a point whose coordinates are integers.

Suppose we arbitrarily choose 5 integer points in a plane.

Show that we can always find 2 among these 5 integer points such that the line segment joining the 2 points contains at least 1 more integer point.

100 sided die probability problem

Source: Jane Street Capital Interview (Quantnet)

Problem:
You are given a 100 sided die. After you roll once, you can choose to either get paid the dollar amount of that roll OR pay one dollar for one more roll. What is the expected value of the game?
(There is no limit on the number of rolls.)

Update (22 June 2014):
Solution posted by me, Felix, JDGM, Sebastian, Fu Shi and Dumb Phoenix in comments!




World Series Puzzle

Image
Source: Discussion with Ashwin Rao (http://zlemma.com, Ex-MD Morgan Stanley) and Gaurav Kumar (Credit Suisse IB, Ex-MS, GS, IITB CSE 2006, Booth 2012)



Problem:
Suppose teams A and B play in the world series of up to 7 games in which the first team to win 4 games wins the series and then no more games are played. Suppose that you want to bet on each individual game in such a way that when the series ends you will be ahead by exactly $100 if your team wins the series, or behind by exactly $100 if your team loses the series, no matter how many games it takes. How much would you bet on the first game?

Update (22 June 2014):
Solution posted by Alex, JDGM, Arnab in comments!


Simple Divisor Problem - Math Puzzle

Source: http://www.math.utah.edu/~cherk/puzzles.html

Problem:
Prove that for any natural N, 1000^N - 1 cannot be a divisor of 1978^N - 1

Short and Sweet :)

Clear Out Puzzle

Image
Source: David Richards' Puzzle Collection

Problem:
A semi-infinite chess board (vary from zero to infinity in both dimensions) with counters in the three bottom left squares, as shown below.



How to move: If the squares above and to the right are free, a counter can be removed and replaced by two counters, one in the square above and one in the square to the right - as shown below



Prove that it is not possible to leave the three bottom left squares empty.

Update (March 07 2013)
Solution posted by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008), Takaki and Rahul in comments! All solutions are essentially the same. Interesting discussion and links by Sudeep.

Mad Hat Party

Source: Australian Mathematical Society Gazette - Puzzle Corner 28

Problem: 
The Mad Hatter is holding a hat party, where every
guest must bring his or her own hat. At the party,  whenever two guests greet each other, they have to  swap their hats. In order to save time, each pair of  guests is only allowed to greet each other at most  once.


After a plethora of greetings, the Mad Hatter notices that it is no longer possible
to return all hats to their respective owners through more greetings. To sensibly  resolve this maddening conundrum, he decides to bring in even more hat wearing  guests, to allow for even more greetings and hat swappings. How many extra guests  are needed to return all hats (including the extra ones) to their rightful owners?

Other "Hat" Problems on the blog: Puzzle: What's the number on my Hat? Another Hat Puzzle Fair Hat Game Another Hat Problem Hats in a circle Hats and Rooms Number of Rounds of Derangements Cap Puzzle Derangement - Complete FAIL! Cap Puzzle…

Broken Clock Puzzle

Image
Source:http://www.ocf.berkeley.edu/~wwu/riddles/medium.shtml



Problem:
My fancy new digital alarm clock is broken! The time 'jumps' around.

When I reset it, it reads 12:00:00. Then it runs as it should, but after 12:04:15 it resets back to 12:00:00. It counts up to 12:04:15 again and then it jumps to ... 12:08:32 ! Weird stuff.

Do you know what's wrong with my alarm clock?

Update (12/02/2013)
Solution posted by Saumya Gupta, Abhimanyu Dhamija (CSE IITB 2011 Alumnus, Citibank Analyst) and Naga Vamsi Krishna in comments!


Probability Puzzle: Guess Position of Card

Image
Source:Counter-intuitive Conundrums


Problem:
Someone hands you a deck of cards which you thoroughly shuffle. Next, you start to deal them, face-up, counting the cards as you go. “One, Two, Three …”

The aim is to predict what the count will be when you encounter the second black Ace in the deck.

If you had to select one position before you started to deal, what number would you select that maximizes your chance of guessing the location of the second black Ace?


Determinant of Binary Matrix

Source: Introduced to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008)

Problem:

An N by N matrix M has entries in {0,1} such that all the 1's in a row appear consecutively. Show that determinant of M is -1 or 0 or 1.

Disclaimer: I could not solve it but I have an awesome solution sent by Pritish Kamath (MSR Research Assistant, CSE IITB Alumnus 2012)
Update (2/4/2013):
Solution posted by Amol Sahasrabudhe (IITB 2004 Alumnus, Ex-Morgan Stanley Quant Associate, Deutsche Bank Quant Associate) and Piyush Sao (EE IITM Alumnus, Georgia Tech Grad Student) in comments! Thanks a ton. I have posted the solution provided by Pritish Kamath (MSR Research Assistant, CSE IITB Alumnus 2012). All three solutions are essentially the same.

Evenly Spaced Ones in Binary String

Image
Source: Sent to me by Piyush Sao (EE IITM Alumnus, Georgia Tech Grad Student)



Problem:
Given a arbitrary binary string of length n, find three evenly spaced ones within the string if they exist. Write an algorithm which solves this in O(n * log(n)) time.

Update (29th January 2013):
Solution posted by JDGM in comments!



Fermat Theorem Puzzle

Image
Source: Andrej Cherkaev's List of Puzzles



Problem:
A computer scientist claims that he proved somehow that the Fermat theorem is correct for the following 3 numbers:

x=2233445566,
y=7788990011,
z=9988776655

He announces these 3 numbers and calls for a press conference where he is going to present the value of N (to show that

x^N + y^N = z^N

and that the guy from Princeton was wrong). As the press conference starts, a 10-years old boy raises his hand and says that the respectable scientist has made a mistake and the Fermat theorem cannot hold for those 3 numbers. The scientist checks his computer calculations and finds a bug.

How did the boy figure out that the scientist was wrong?

Update (06/01/2012):
Solution posted by a lot of people in comments!