Log In

Monthly Archives for August, 2013


Posted on: August 11th, 2013 by
Comments Disabled
Suppose you have an infinite checkerboard where every edge is a resistance of 1 Ohm. What is the effective resistance between two adjacent vertices? via Math overflow

Distance between dots

Posted on: August 10th, 2013 by
Comments Disabled
Suppose every point in a plane is arbitrarily colored either black or white. There is at least 1 black dot and at least 1 white dot. Show that there exists a black dot and a white dot such that the distance between the black dot and the white dot is exactly 1 unit. - Goldman Sachs interview question for technology analyst position.

Find the median

Posted on: August 9th, 2013 by
Comments Disabled
Give an algorithm to find the median of n real numbers in an array in linear time. - You maybe asked this question in an interview.

Coin triplets

Posted on: August 8th, 2013 by
Comments Disabled
A 2 player game of successive coin tosses is as follows: First player 1 selects a triplet among the 8 triplets {HHH,HHT,HTH,... TTT} where H stands for Heads and T for tails. Player 2 then selects his triplet. After choices are made, a coin is tossed successively until one of the two triplets occurs. If player 1's triplet occurs before player 2's then player 1 Continue reading the story "Coin triplets"

Probability of difference

Posted on: August 7th, 2013 by

Let X and Y be two independent and identically distributed random variables. Show P{|X-Y|<=2} <= 3P{|X-Y|<=1}. (|x| is the absolute value of x.) - via Yeow Khiang Chia

Divisibility test

Posted on: August 6th, 2013 by

Show that for any natural number n, 1000^n-1 cannot be a divisor of 1978^n-1. via Math puzzles

Array shuffle

Posted on: August 5th, 2013 by
Comments Disabled
Suppose you have 2n elements in an array as a1,a2,...an, b1,b2,...bn. You want to reorder the elements so that the array is a1,b1,a2,b2,... an,bn. Show how to achieve this using O(log n) space and O(n) time. (It is trivial if you have O(n) space.) SPOILER WARNING: Solution can be found in this paper.

card shuffles

Posted on: August 4th, 2013 by

52 cards numbered 1,2,...52 are shuffled and kept face-down. Then you inspect the top card. If the top card is k, then you remove it and replace it in the k-th position in the deck. You keep repeating this procedure until there is a 1 on the top. Show that after finitely many steps there will eventually be a 1 on the top. via Stack Continue reading the story "card shuffles"

Find intervals by divisibility

Posted on: August 3rd, 2013 by

Suppose you have an array of natural numbers a_1,a_2,...a_n. An interval [i:j] is said to be divisible by k if the sum a_i+a_{i+1}+.... a_j is divisible by k. Give an algorithm to find the number of intervals that are divisible by k in O(n) time. -via A friend from Stanford

Divide into two groups

Posted on: August 2nd, 2013 by

Can you divide the numbers 1,2,3,...,15 into two groups, with group A containing 13 numbers and group B containing 2 numbers such that the sum of the numbers in group A equals the product of the numbers in group B? - via 1999 Russian math olympiad. This problem was brought to my attention by Subhashini

{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}