## Thursday, October 30, 2014

### Quant/Programming Interview Question of the Day

These are simple warm up type questions meant to help you prep for interviews. They are each designed to be solved within 3-7 minutes, never more. Questions like these are routinely asked in job interviews where you have to demonstrate even the least bit of quantitative talent. I plan to post a new question every few days, with solutions before posting the next question. [While I try to provide sources for every question if I am aware of them, some of these were either asked by, or asked to, friends in interviews, so I cannot always definitively say which book they came from.] Good luck with your preparation and to landing the job of your dreams.

Edit: while I started posting questions with solutions, speaking with some candidates sometimes leads me to believe a lot of people tend to simply read the questions and solutions, and this does more harm than good. So going forward, I will still post questions as regularly as I can, but solutions only relatively infrequently.

Question for 2 Feb 2016:
A spherical shell is constructed such that the outer radius is equal to that of a circumscribing sphere for a cube of side S, and the inner radius is equal to the radius of the largest completely contained sphere in the same cube. If two regular tetrahedra (four equilateral triangle faces) T1 and T2 are constructed with corresponding parallel faces such that T1 is the largest one that can be contained in the outer bound of the spherical shell, and T2, the largest one that can be contained in the inner sphere, the volume enclosed between T1 and T2 is?

Question for 31 Jan 2016:
Derive tight lower and upper bounds for the sum sigma(i=1 to N) sqrt(i). i.e. sqrt(1)+sqrt(2)+...+sqrt(N). What about the sum sqrt(1/1)+sqrt(1/2)+sqrt(1/3)+...+sqrt(1/N)?

Question for 25 Jan 2016:
You enter a casino with \$1,000,000. You repeatedly spin a "fair" roulette wheel wagering \$1 each time on red or black. The wheel has 18 red slots, 18 black slots, and 2 white slots (marked 0 and 00). Each time you win, you get \$1 plus the money you wagered, when you lose, you get back nothing. You leave happy if you make \$100, you leave sad if you go broke (lose all \$1,000,000). Which is more likely? Why?

Question for 20 Jan 2016:
There are N boys and N girls in a group of 2N people. Each boy has a list of the N girls ranked in decreasing order of preference. Each girl has a list ranking each of the N boys in her order of preference as well. Is there a way to ensure the creation of N pairs each with a boy and girl, such that no boy B has a better preferred girl X than the one he is paired with, where X also prefers him to her own boy B'? Explain an algorithm to achieve this.

Question for 18 Jan 2016:
You are given a 22 ounce glass and an 11 ounce glass. Can you measure out 4 ounces exactly using these two glasses? How, or why not?

Question for 17 Jan 2016:
Given an n x n square grid or chessboard (n=2^k), with any one square removed. Prove that it can always be completely tiled with L-shaped tiles each made up of three 1 x 1 square tiles.

Question for 16 Jan 2016:
Is it possible to arrange the dots on the faces of two dice such that they are completely different from each other, but yet, when they are rolled together, the probability of obtaining every "score" is the same with the modified pair of dice as it is with the original pair? [variant of the Sicherman Dice problem.]

Question for 16 Jan 2016:
In how many ways can you make change for a dollar (100 cents) using half-dollars (50 cents), quarters (25 cents), dimes (10 cents), and nickels (5 cents)? [Note: an elegant solution would use generating functions.]

Question for 14 Jan 2016:
Alice and Bob pick natural numbers p and q respectively completely at random uniformly from the range [2, inf). What is the probability that the larger of p or q is a multiple of the other?

Question for 6 Jan 2016:
The integers 1 through K, both inclusive, are arranged in a circle. You start at 1, then remove every mth integer from the circle, continuing with this operation till you are left with only one integer. Write a program that takes integers K and m, and returns the single integer you are left with at the end.

Question for 13 Dec 2015: [source: Quora]
Which is greater? The number of molecules of water in a glass, or the number of glasses of water in the ocean? You may choose any reasonable volume for a typical glass to perform your calculations.

Question for 20 Aug 2015:
1. Write a program to lexicographically sort a list of integers without using strings. (5 mins)
e.g. [1,11,121,1211,20,22,221,33] etc
2. Write a function that reverses the digits of an integer again without using strings. (3 mins)

Question for 30 Jun 2015:
There are three cops (C) and three thieves (T) on the right bank of a river. A boat is also moored to the right bank at the start. They need to get to the left bank. The boat can carry at most two people at a time. Cops are only safe if there are equal in number, or outnumber the thieves. Write a computer program that gives a sequence of crossings that is feasible without the cops getting attacked. [You have 20 minutes to write, debug, and run the program.]

Question for 26 Jun 2015:
In how many ways can you sample 3 letters from the English alphabet without replacement, such that the three are in lexicographic order?

Question for 20 May 2015:
Tommy goes completely unprepared for a 20 question multiple choice (4 options per question) quiz, and guesses randomly on each question without leaving any out. If each correct question is scored with 1 point and there is no negative marking, what is the probability that Tommy passes the test given the passing grade is 50% or more? What if there was a 1 point negative marking per incorrectly answered question as well?

Question for 7 Apr 2015: [credit: Quora]
Given a set of N people with birth dates and death dates (where applicable) - all between 1900 and 2000 inclusive - for people in this set, write a program that tells in which year the largest number of these N people were alive at the same time.

Question for 5 Apr 2015:
Given a sorted set of 1000 numbers, describe an efficient algorithm to generate a random permutation of this set - such that the random permutation has equal probability of being generated as any other random permutation that might be produced.

Question for 1 Apr 2015:

1. Write equations using any mathematical symbols of your choice, and three of each number 1-9 to equal 6. E.g. write 9 equations using {1,1,1}, then {2,2,2}, ..., then {9,9,9}, but in each case, the equation must evaluate to 6.
2. Write equations using any mathematical symbols of your choice, and three 9s each time, such that the equations evaluate to numbers from 1-9 both inclusive.

Question for 25 Mar 2015:

Prove that there are infinitely many prime numbers.

Question for 25 Mar 2015:
1. Solve x = sqrt(2+sqrt(2+sqrt(2+ ... to infinity)
2. Write a Python program to evaluate the expression in (1) to prove your answer is correct.

Question for 15 Mar 2015:

1. Solve x = 1+2/(1+2/(1+2/(1+2/.... to infinity)
2. Write a Python program to evaluate the expression in (1) to prove your answer is correct.

Question for 10 Mar 2015:

1. Write a function that takes a string s of some number in base integer p, and returns its decimal representation. [getting this right on your first try is a prerequisite to advance to parts (2) and (3) below.]
2. Write a function F (x,y) that takes a decimal integer x and returns a string representation of x to base y.
3. Write a function P (x) that takes a decimal integer x and returns a list of all the prime factors of x - repeating factors appear as many times as they occur.

Question for 4 Mar 2015:
"Pi Compression". The transcendental number Pi has a never ending stream of non-repeating digits. So one might imagine that it contains absolutely any sequence of digits one might require, within its expansion, at some point in the sequence. Let us suppose you have a file p that has 1000 characters. Further suppose that you reduce this file into a sequence of digits from 0-9 using some transformation. Can you now compress file p by specifying the tuple (x,y) where x is the location in the infinite stream of digits in Pi where the sequence of digits for file p begins, and y is the length of p (whatever it takes to represent your 1000 characters in the numeric representation)? Would this work? Why or why not? [Answer will not be provided.]

Question for 4 Mar 2015:
You are given an n x n grid of cells where each cell in an instance of the grid is randomly colored either black or white. A grid is called "open" if white cells are connected to form a path from the top of the grid to the bottom - two cells are "connected" if they share an edge. Else the grid is "closed". Explain what algorithm you will use to determine if a given grid is open or not. Implement it.

Question for 2 Mar 2015:
Write a Python code snippet that asks for a three digit integer as input then returns the sum of its digits. You are given credit proportional to the number of exception cases you handle as you code this. [Answer will not be provided.]

Question for 28 Feb 2015:  (c) ChiPrime
A cube and a sphere can intersect in at most how many points?

Question for 27 Feb 2015:  (c) ChiPrime

Given 4 circles with centers at A, B, C and D each with radius R, which intersect each other in exactly one point P, what is the area of quadrilateral ABCD?

Solution:
It should be obvious that A, B, C, and D cannot be coplanar. Imagine A and C are centers of two circles that are tangential to one another. B and D can then be circles that are similarly tangential to one another, with the same point of tangency P in any plane containing the tangent line of Circles A and C, or even any plane containing the line joining the centers of Circles A and C. In either configuration, the largest area of quadrilateral ABCD occurs when the two planes containing the circle centers are perpendicular to one another, so ABCD is a square with diagonals of length 2r or sides of length r*sqrt(2) for an area of 2r^2. The minimum area of ABCD would occur when two vertices in either plane are almost coincident with those in the other, giving an area that tends to 0.

Question for 10 Jan 2015:

There are 5 green and 45 red marbles in an urn. You pick blindfolded, ten marbles from the urn, without replacement. What is the probability that exactly 4 of the ten are green?

Solution:
This is an example of the hyper-geometric distribution. The problem cannot be modeled as a binomial distribution because the probability of a "success" event changes with each draw. Please see this wikipedia article for more details. The problem is also discussed and solved there. The answer is given by the expression (5C4)*(45C6)/(50C10) = 0.003964.

Question for 5 Jan 2015:

What is the probability that given a standard deck of 52 cards, a thorough random shuffling of the deck will produce an ordering where not a single card is in the same position (as it was before the shuffle)?

Solution:

This is again a problem of derangements. The ratio of the number of derangements to the total number of permutations approaches 1/e as n increases (beyond about 7 or so). Here we have a deck of 52 cards, so the probability of getting a derangement is about 1/e or about 37%. See this wikipedia article for details.
http://en.wikipedia.org/wiki/Derangement

Question for 2 Jan 2015:

1. In a knock-out tournament, if there were 39 matches played in total, how many players participated in the tournament in total?
2. Using only three 9s and any mathematical symbols you like, write an expression that equals 20.
3. Using only three 4s and any mathematical symbols you like, write an expression that equals 100.
4. Using only five 0s, and any mathematical symbols you like, write an expression that equals 120.
Solution:
I believe all the first three questions came from a book by Peter Winkler, but I don't have it, so I cannot be sure of the source. The last is one I ask(ed) in interviews.

1. If there are 39 matches played, there were 39 players that lost and one that won the championship, for a total of 40 players (remember, this is a knock-out tournament).
2. (9+9)/.9
3. (4*4!+4)
4. (0!+0!+0!+0!+0!)!

Question for 29 December 2014:

In a class of 4 students, A, B, C and D, the professor has each student grade another student's homework (of course, no student can grade his own work). How many possible ways can papers be distributed to accomplish this?

Solution:

The answer is equal to the number of derangements of 4 items, denoted by !4.
The (recurrence) formula for derangements !n=(n-1)(!(n-1)+!(n-2)). So for n=4, we get 9 as the answer, as shown on that wikipedia page.

Question for 3 December 2014:

1. Given two strings S1 and S2, how would you determine if one was a permutation of the letters of another?
2. Given a string S1 with some repeating letters, how would you construct a permutation of S1 that is closest to a palindrome? [a palindrome is a string that reads the same back to front as it does front to back.]

(c) ChiPrime 2014

Solution:

1. First compute the set of all letters in strings S1 and S2. If the intersection of these sets is equal to either of S1 or S2, next check if the number of occurrences of each element of the intersection set in each of S1 and S2 is the same.
2. First, split all characters in S1 into two lists - list X of all repeating letters, and list Y of all non-repeating letters. Now if X contains an odd number of any letter, move it out to Y, so X only has an even number of every letter. Now construct the palindrome string P with one letter each from letters in X (order does not matter here), making sure to end the string with the same letters in reverse order. Plop the set Y in the middle in any order. P is the string you need.

Question for 1 December 2014:
A domino is a tile that has two positive integer numbers on it, or one number and a blank, where each number is drawn from numbers below and including the maximum number specified. How many unique tiles can be created with a maximum number of 12 on the set of dominos?

(c) ChiPrime 2014

Solution:
This is a trick question - there are two tricks here. First, remember that though the maximum number in the set of dominos is 12, there is a blank (or zero) as well that needs to be factored in. So the number of dominos with two distinct numbers is given by 13C2=13!/(2!11!)=13*12/2=13*6=78. But that is not all. Recall that in a box of dominos, there is also one domino for each number that has two of the same number on it. This special case gives us 13 more dominos, with digits blank|blank, 1|1, 2|2, ..., 12|12 on them, for a total of 78+13=91 dominos in the box.

Question for 29 November 2014:
[Quora] What is the probability of selecting two numbers x and y from the entire set of Real Numbers, such that x+y=5?

Solution:
Thinking geometrically, this is the probability of picking a random point in the x-y plane such that it lies on the line x+y=5. This probability is a very small number, equal to zero for all practical purposes.

(c) ChiPrime 2014

Question for 21 November 2014:
Given a square A with integer length side s has the same area as circle C with integer length radius r, where both the side and the radius are measured in the same units, what is the relationship between s and r?

(c) ChiPrime 2014

Solution:
This question is asking whether you can "square a circle" and the answer to that is that it is impossible, per the detailed explanation in the article here.

Question for 15 November 2014:
You are standing on a ladder with 11 steps to go to the top. You can either go up one step or two steps at a time. In how many different ways can you climb these 11 steps?

(c) ChiPrime 2014

Solution:
Let us first find the maximum number of two step moves we can make with 11 steps left. This is obviously 5. So the different sets of moves to chose from are all the permutations of:
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1, 1, 1, 1, 1, 1], [2, 2, 1, 1, 1, 1, 1, 1, 1], [2, 2, 2, 1, 1, 1, 1,1],[2, 2, 2, 2, 1, 1, 1], [2, 2, 2, 2, 2, 1].
y
Permutations of n objects, not all distinct are given by:
if there are n1 objects of one type, n2 of another, n3 of a third, ... such that n1+n2+...+nk=n,
then, permutations=n!/(n1!*n2!*...*nk!).

So our answer is: 1+10!/9!+9!/(2!7!)+8!(3!5!)+7!/(4!3!)+6!/5!=1+10+36+56+35+6=144 ways.

(c) ChiPrime 2014

Question for 12 November 2014:
[due to Martin Gardner?] ABCD-A'B'C'D' is a cube where ABCD is a square A is the origin, and AB, AD, and AA' are coincident with the x-, y-, and z- axes respectively. BB', CC' and DD' are parallel to AA'. What is the measure of angle A'C'D?

Solution:
Both A'C' and C'D are diagonals of their respective surfaces, as is A'D. So triangle A'C'D is an equilateral triangle, and the angle A'C'D is 60 degrees.

(c) ChiPrime 2014

Question for 9 November 2014:
In how many ways can different cubes' faces be painted with three colors (say red, yellow and blue), painting two sides with each, so you get distinct color configurations where reorienting a colored cube will not result in another cube from the set?

(c) ChiPrime 2014

Solution:
Take a cube, paint opposite planes with the same color. This is one.
The second cube, paint three pairs of two adjacent sides each separated by a single edge, with the same color.
Next, take three other cubes, paint the first one with two opposite faces red, then the two pairs of remaining adjacent sides with yellow and blue respectively. Then paint the second of these three cubes with opposite faces colored yellow, and two pairs of remaining adjacent sides with red and blue respectively. And finally, the third of these three with opposite faces colored red and two pairs of remaining adjacent sides with yellow and blue respectively.
With this set of five cubes as a basis, you can achieve all other configurations by reorienting cubes from this set.

Challenge question to interested programmers:
Write a program to find the above solution. Not too easy!

(c) ChiPrime 2014

Question for 6 November 2014:
What is the probability of selecting a random three digit number such that the three digits in order from left to right, are in geometric progression? What is the probability if the "in order" restriction were removed?

(c) ChiPrime 2014

Solution:
For both cases, all numbers of type ppp where p is a digit, satisfy the condition with common ratio=1.
For the first case, numbers like 124, 139, 248, 469 and their palindromes qualify. Giving us 17 numbers that qualify from 900 numbers, for a probability of ~0.019.
For the second case, in addition to the numbers above, distinct permutations of digits of qualifying numbers also qualify, so we also get 142, 193, 214, 241, 284, 319, 391, 412, 428, 482, 496, 649, 694, 824, 913, 946. (each 3 digit number has 3!=6 permutations, of which 2 are already covered previously, so 4 more cases exist for each of the numbers with different digits = 4*4=16). So a total of 33 (=17+16) numbers qualify for a probability of 33/900=~0.0367

You can also write simple code to solve for this as below:

import os, sys;

cnt=0;
r,u=[],[];

for i in range(100,1000):
s=str(i);
a,b,c=int(s[0]),int(s[1]),int(s[2]);
z=[int(s[0]),int(s[1]),int(s[2])];
z.sort();
m,n,p=z[0],z[1],z[2];
if b!=0 and c!=0 and a/float(b)==b/float(c): r+=[i];
if n!=0 and p!=0 and m/float(n)==n/float(p): u+=[i];
cnt+=1;

print "The probability with the in-order restriction:", float(len(r))/cnt;
print "The probability without the in-order restriction:", float(len(u))/cnt;

(c) ChiPrime 2014