February 2011
1 post
Getting a fair result with an unfair coin
How can you get a fair coin toss if someone hands you a coin that is weighted to come up heads more often than tails?
January 2011
1 post
We are NY Tech asks:
“How many unique areas of human knowledge have the right size of passionate users to make it as a Stack Exchange site?”
Answer: 30,000.
November 2010
1 post
2 tags
Storing 1 million phone numbers
What is the most efficient way, memory-wise, to store 1 million phone numbers? Apparently this is an interview question at Google, although this seems like its a bit too easy.
April 2010
62 posts
Reverse a String
A typical programming interview question is “reverse a string, in place”. if you understand pointers, the solution is simple. even if you don’t, it can be accomplished using array indices. i usually ask candidates this question first, so they get the algorithm in their head. then i play dirty by asking them to reverse the string word by word, in place. for example if our string...
100 Doors in a Row
Problem: you have 100 doors in a row that are all initially closed. you make 100 passes by the doors starting with the first door every time. the first time through you visit every door and toggle the door (if the door is closed, you open it, if its open, you close it). the second time you only visit every 2nd door (door #2, #4, #6). the third time, every 3rd door (door #3, #6, #9), etc, until you...
Red Marbles, Blue Marbles
Problem: you have two jars, 50 red marbles, 50 blue marbles. you need to place all the marbles into the jars such that when you blindly pick one marble out of one jar, you maximize the chances that it will be red. (when picking, you’ll first randomly pick a jar, and then randomly pick a marble out of that jar) you can arrange the marbles however you like, but each marble must be in a...
Bumblebee
problem: two trains enter a tunnel 200 miles long (yeah, its a big tunnel) travelling at 100 mph at the same time from opposite directions. as soon as they enter the tunnel a supersonic bee flying at 1000 mph starts from one train and heads toward the other one. as soon as it reaches the other one it turns around and heads back toward the first, going back and forth between the trains until the...
int atoi( char* pStr )
Problem: write the definition for this function without using any built-in functions. if pStr is null, return 0. if pStr contains non-numeric characters, either return 0 (ok) or return the number derived so far (better) (e.g. if its “123A”, then return 123). assume all numbers are positive. plus or minus signs can be considered non-numeric characters. in order to solve this program,...
Daughters' Ages
Two MIT math grads bump into each other at Fairway on the upper west side. They haven’t seen each other in over 20 years.
the first grad says to the second: “how have you been?” second: “great! i got married and i have three daughters now” first: “really? how old are they?” second: “well, the product of their ages is 72, and the sum of their ages is...
Palindromes
Problem: this year on October 2, 2001, the date in MMDDYYYY format will be a palindrome (same forwards as backwards). 10/02/2001 when was the last date that this occurred on? (see if you can do it in your head!)
Solution
olution: we know the year has to be less than 2001 since we already have the palindrome for 10/02. it can’t be any year in 1900 because that would result in a day of 91....
Sum it Up
Problem: you are given a sequence of numbers from 1 to n-1 with one of the numbers repeating only once. (example: 1 2 3 3 4 5). how can you find the repeating number? what if i give you the constraint that you can’t use a dynamic amount of memory (i.e. the amount of memory you use can’t be related to n)? what if there are two repeating numbers (and the same memory...
Pirates
Five pirates have 100 gold coins. they have to divide up the loot. in order of seniority (suppose pirate 5 is most senior, pirate 1 is least senior), the most senior pirate proposes a distribution of the loot. they vote and if at least 50% accept the proposal, the loot is divided as proposed. otherwise the most senior pirate is executed, and they start over again with the next senior pirate. what...
Fog Creek Programmers
100 fogcreek programmers are lined up in a row by an assassin. the assassin puts red and blue hats on them. they can’t see their own hats, but they can see the hats of the people in front of them. the assassin starts in the back and says “what color is your hat?” the fogcreek programmer can only answer “red” or “blue.” the programmer is killed if he...
Bad King
A bad king has a cellar of 1000 bottles of delightful and very expensive wine. A neighbouring queen plots to kill the bad king and sends a servant to poison the wine. (un)fortunately the bad king’s guards catch the servant after he has only poisoned one bottle. Alas, the guards don’t know which bottle but know that the poison is so strong that even if diluted 1,000,000 times it would...
Jelly Beans
You have three jars that are all mislabeled. one contains peanut butter jelly beans, another grape jelly jelly beans, and the third has a mix of both (not necessarily a 50/50 mix, could be a 1/99 mix or a 399/22 mix). how many jelly beans would you have to pull out, and out of which jars, to find out how to fix the labels on the jars?
| | | | | | |jar 1| |jar 2| ...
Bridge
Problem: this one is a classic that many of you have probably already heard, but all the more reason why it should definitely be included here. four people are on this side of the bridge. the bridge will be destroyed by a bomb in 17 minutes. everyone has to get across before that. problem is that it’s dark and so you can’t cross the bridge without a flashlight, and they only have one...
Card Trick Without the Trick
This is a card trick without the trick. there is no sleight of hand, no tricks up my sleeve, no magic whatsoever. it’s all done with logic, yet it will amaze most people.
Joel and i are working together as a team to do the trick. Babak will be the culprit.
i ask babak to pick 5 cards out of a deck. he can pick any five cards, he can shuffle the deck 7 times, it really doesn’t matter....
Pirates Revisited
A slightly different version of the original pirates problem (read that one first to get all the rules). 6 pirates, only one gold coin. as before, the pirates are super-smart, and they value, in this order: (i) their lives, (ii) getting money, (iii) seeing other pirates die. so if given the choice between two outcomes, in which they get the same amount of money, they’d choose the outcome...
Fuse on Fire
A mad bomber is out on the job, making bombs. he has two fuses (pieces of string) of varying thickness which each burn for 30 seconds. unfortunately he wants this bomb to go off in 45 seconds. he can’t cut the one fuse in half because the fuses are different thicknesses and he can’t be sure how long it will burn. how can he arrange the fuses to make his bomb go off at the right...
Dave's on Fire
dave winer is stuck on a deserted island, with lots of trees, which is very thin and ten miles long (east to west). large cliffs surround the entire island and if he jumped off, he wouldn’t survive the fall. a fire starts burning at the west side of the island. unfortunately this island always has a west to east blowing wind blowing at 2mph and this moves the fire slowly toward dave at 1mph....
Chessboard
problem: using 31 dominoes, where one domino covers exactly two squares, can you cover all the empty squares on this chessboard (which has 62 spaces). if so, how? if not, why?
Solution
i think everyone’s first inclination is to try and figure out how it is possible. then again, if you’ve heard a bunch of these questions before, you usually know that if the question says “if...
Easy River Crossing
Three cannibals and three anthropologists have to cross a river. the boat they have is only big enough for two people. if at any point in time there are more cannibals on one side of the river than anthropologists, the cannibals will eat them. what plan can the anthropologists use for crossing the river so they don’t get eaten?
remember! the boat can’t cross the river by itself,...
Shapes
Part I: draw a square. divide it into four identical squares. remove the bottom left hand square. now divide the resulting shape into four identical shapes.
Part II: draw an equilateral triangle (all sides same length). divide it into four identical shapes. remove the bottom left hand shape. now divide the resulting shape into four identical shapes.
This is the sort of problem that i would...
Webloggers
Five webloggers - joshua Allen, meg Hourihan, jason Kottke, robert Scoble, and joel Spolsky - were competing for karma points on the major search engines: google, yahoo, altavista, lycos, and msn. karma was distributed on a five point scale. the most popular weblog received 5 points, and the least popular received 1 point. for each search engine, no two webloggers received the same number of...
Hard River Crossing
a disfunctional family has to cross the river. on one side of the river are a mom and 2 daughters, dad and 2 sons, the maid and the dog. there is a boat only big enough to hold 2 people (counting the dog as 1 person). only the adults are capable of operating the boat. everyone has to get to the other side, without anything bad happening.
difficulties: if the dog is left with anyone and the maid...
Classic Weighing
this is a classic problem which i have heard many times before. this is the “harder” of the two problems, since in this one, you do not know if the invalid item weighs more or less than the others.
solving it is only half the battle. writing up a solution that anyone including your grandma could understand, is very hard.
problem: the evil king from before sends his own assassin to...
Monty Hall Problem
Another well known problem in probability is the Monty Hall problem.
You are presented with three doors (door 1, door 2, door 3). one door has a million dollars behind it. the other two have goats behind them. You do not know ahead of time what is behind any of the doors.
Monty asks you to choose a door. You pick one of the doors and announce it. Monty then counters by showing you one of the...
Gold Chain
A man has a gold chain with 7 links. he needs the service of a laborer for 7 days at a fee of one gold link per day. however, each day of work needs to be paid for separately. in other words, the worker must be paid each day after working and if the laborer is ever overpaid he will quit with the extra money. also he will never allow himself to be owed a link.
what is the fewest # of cuts to the...
Surgeons
A one armed surgeon with a hand wound needs to operate on three patients. the surgeon only has two gloves. how can he operate on the three patients in turn without risking exchange of fluids? (remember he only has one arm so he only needs to wear one glove at a time.)
Solution
The surgeon places both gloves on his hand (1 and 2). he operates on patient A. he then takes the top glove off (#2),...
Clock
Part I: what is the angle between the minute hand and the hour hand at 3:15 on an analog clock? no, its not 0.
Part II: how often does the minute hand pass the hour hand on an analog clock?
Solution
part I: 12 hours on the clock make 360 deg. so one hour is 30 deg. the hour hand will be directly on the 3 when the minute hand is at 12 (3:00). after 15 minutes or 1/4 of an hour, the hour hand...
Mountain Man
At 6 a.m. a man starts hiking a path up a mountain. he walks at a variable pace, resting occasionally, but never actually reversing his direction. at 6 p.m. he reaches the top. he camps out overnight. the next morning he wakes up at 6 a.m. and starts his descent down the mountain. again he walks down the path at a variable pace, resting occassionally, but always going downhill. at 6 p.m. he...
Treasure Island
You find an old treasure map in your grandma’s attic. the map shows a cannon, a coconut tree, and a palm tree. the map states that to find the treasure you must:
a. start at the cannon, walk toward the palm tree while counting your paces. when you reach the palm tree, turn 90 degrees to your left and walk the same number of paces. mark that spot on the ground with a stake.
b. start at the...
Screwy Pirates
A. first i would just like to say i am so glad jenna got voted off survivor. yuck, i couldn’t stand her ever since she accused that guy of eating beef jerky when he was chewing on grass.
B. recruit meyer on boot camp rocks. did you see how he made himself cry to get sympathy? and it worked! he is the funniest part of the show. i hope he wins.
C. i apologize for this site being soooooo...
Ants on a Triangle
There are three ants on a triangle, one at each corner. at a given moment in time, they all set off for a different corner at random. what is the probability that they don’t collide?
Solution
Consider the triangle ABC. We assume that the ants move towards different corners along the edges of the triangle.
Total no. of movements: 8 A->B, B->C, C->A A->B, B->A, C->A...
One Mile South
How many places are there on the earth that one could walk one mile south, then one mile east, then one mile north and end up in the same spot? to be precise, let’s assume the earth is a solid smooth sphere, so oceans and mountains and other such things do not exist. you can start at any point on the sphere and walk in any direction you like.
think you’ve figured it out? i’ll...
Cube
This is difficult to describe in words, so read this carefully, lest there be any confusion. You have a normal six sided cube. i give you six different colors that you can paint each side of the cube with (one color to each side). How many different cubes can you make?
Different means that the cubes can not be rotated so that they look the same. This is important! If you give me two cubes and I...
More Hat Puzzles
I buried four fishermen up to their necks in the sand on the beach at low tide for keeping their fishing spot a secret from me. I put a hat on each of their heads and told them that one of them must shout out the correct color of their own hat or they will all be drowned by the incoming tide. I give them 10 minutes to do this. Fisherman A and B can only see the sand dune I erected. Fisherman C can...
Coin on a Table
You die and the devil says he’ll let you go to heaven if you beat him in a game. the devil sits you down at a round table. he gives himself and you a huge pile of quarters. He says “ok, we’ll take turns putting quarters down, no overlapping allowed, and the quarters must rest on the table surface. The first guy who can’t put a quarter down loses.” the devil says he...
Noodles
There is a pot of N noodles. (so there are 2N ends). A person randomly grabs two ends and merges them. The person keeps doing it, until there are no more noodles, (and only loops), left in the pot. what’s the average number of loops in the pot?
Solution
OK, all the answers so far just list formulae, without giving any explanation. I’ll try to work it out out loud. (At this point I...
Heaven
A person dies, and arrives at the gate to heaven. there are three doors. one of them leads to heaven. another one leads to a 1-day stay at hell, and then back to the gate, and the other leads to a 2-day stay at hell, and then back to the gate. every time the person is back at the gate, the three doors are reshuffled. How long will it take the person to reach heaven?
this is a probability question...
Flipping Coins
Someone walks into your room and dumps a huge bag of quarters all over the floor. They spread them out so no quarters are on top of any other quarters. a robot then comes into the room and is programmed such that if it sees a head, it flips it to tails. If it sees a tail, it throws it in the air. the robot moves around randomly forever. Will there be a convergence in distribution of heads vs....
Pennies
I challenge you to a game. we each get one penny and we flip them at the same time. (so on turn 1, we each flip our respective pennies - turn 2, we flip them again, and so on until someone wins). I am looking to get heads then tails. You are looking to get heads then heads. So if you flip heads on any flip and then heads on the next flip, you win. If I flip heads on any flip and then tails on the...
Linked List
How does one find a loop in a singly linked list in O(n) time using constant memory? You cannot modify the list in any way (and constant memory means the amount of memory required for the solution cannot be a function of n.).
Solution
I first figured this out when I was asked the question in a Microsoft interview, so there’s verification that one question in the book was from a real...
Last Ball
You have 20 blue balls and 14 red balls in a bag. you put your hand in and remove 2 at a time. If they’re of the same color, you add a blue ball to the bag. If they’re of different colors, you add a red ball to the bag. (assume you have a big supply of blue & red balls for this purpose. note: when you take the two balls out, you don’t put them back in, so the number of balls...
Coin Rolls
Every night, I dump all the change in my pocket into a big bucket.
When I buy things, I never hand over coins. always bills. So I accumulate a lot of coins. Even if the purchase price is $1.01, and I have lots of coins in my pocket, I pay $2 and take the 99 cents in change. All the more coins to dump in my change bucket!
After about 10 years of this, I decide to roll all the coins into rolls....
Calendar Cubes
A man has two cubes on his desk. every day he arranges both cubes so that the front faces show the current day of the month. what numbers are on the faces of the cubes to allow this?
Solution
First, to show all possible days, we’d need one of each of the ten digits. We’d also need two 1s and two 2s to show 11 and 22. That’s twelve numbers right there. Two cubes, twelve faces,...
Boys and Girls
In a country in which people only want boys, every family continues to have children until they have a boy. if they have a girl, they have another child. if they have a boy, they stop. what is the proportion of boys to girls in the country?
Solution
Pretty simple. Half the couples have boys first, and stop. The rest have a girl. Of those, half have a boy second, and so on.
So suppose there are...
Painfully Easy
I flip a penny and a dime and hide the result from you. “one of the coins came up heads”, i announce. what is the chance that the other coin also came up heads?
Solution
Assuming complete honesty on the part of the flipper, wouldn’t the solution be 33%?
There are four possible scenarios:
HH TH HT TT
Obviously the TT possibility can be discounted because it does not result in...
Nuggets
You can go to a fast food restaurant to buy chicken nuggets in 6-pack, 9-pack or 20-packs. is there such a number N, such that for all numbers bigger than or equal to N, you can buy that number of chicken nuggets?
Solution
Here’s another way of looking at it:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44...
Orbs
You have two identical crystal orbs. you need to figure out how high an orb can fall from a 100 story building before it breaks. you know nothing about the toughness of the orbs: they may be very fragile and break when dropped from the first floor, or they may be so tough that dropping them from the 100th floor doesn’t even harm them.
What is the largest number of orb-drops you would ever...