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 is “the house is blue”, the return value would be “blue is house the”. the words are reversed, but the letters are still in order (within the word).
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 only visit the 100th door.
question: what state are the doors in after the last pass? which are open which are closed?
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 jar.
Chance! chance is easy if you know how to do the formula. we know that we have two choices to make. first we’ll pick a jar, and each jar will have a 1/2 chance of being picked. then we’ll pick a marble, and depending how we stack the marbles, we’ll have a (# of red marbles in jar)/(# of total marbles in jar) chance of getting a red one.
for example, say we put all the red marbles into jar A and all the blue ones into jar B. then our chances for picking a red one are:
1/2 chance we pick jar A * 50/50 chance we pick a red marble 1/2 chance we pick jar B * 0/50 chance we pick a red marble
do the math and you get 1/2 chance for a red marble from jar A and a 0/2 chance for a red marble from jar B. add ‘em up and you get the result = 1/2 chance for picking a red marble.
think about it for awhile and see if you can figure out the right combination. we had a 50/50 (guaranteed) chance in picking a red marble from jar A, but we didn’t have to have 50 red marbles in there to guarantee those fantastic odds, did we? we could’ve just left 1 red marble in there and the odds are still 1/1. then we can take all those other marbles and throw them in jar B to help the odds out there.
let’s look at those chances:
1/2 we pick jar A * 1/1 we pick a red marble 1/2 we pick jar B * 49/99 we pick a red marble
do the math and add them up to get 1/2 + 49/198 = 148/198, which is almost 3/4.
we can prove these are the best odds in a somewhat non-formal way as follows. our goal is to maximize the odds of picking a red marble. therefore we can subdivide this goal into maximizing the odds of picking a red marble in jar A and maximizing the odds of picking a red marble in jar B. if we do that, then we will have achieved our goal. it is true that by placing more red marbles into a jar we will increase the chances of picking a red marble. it is also true that by reducing the number of blue marbles in a jar we will increase the odds also. we’ve maximized the odds in jar A since 1/1 is the maximum odds by reducing the number of blue marbles to 0 (the minimum). we’ve also maximized the number of red marbles in jar B. if we added any more red marbles to jar B we would have to take them out of jar A which reduce the odds there to 0 (very bad). if we took any more blue ones out of jar B we would have to put them in jar A which reduce the odds there by 50% (very bad).
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 trains collide in a fiery explosion in the middle of the tunnel (the bee survives). how far did the bee travel?
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, the programmer must understand the difference between the integer 0 and the character ‘0’, and how converting ‘0’ to an int, will not result in 0. in other words, they have to understand what ascii is all about.
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 the same as the number on that building over there..” first: “right, ok.. oh wait.. hmm, i still don’t know” second: “oh sorry, the oldest one just started to play the piano” first: “wonderful! my oldest is the same age!”
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!)
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 constraint?)
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 solution does the most senior pirate propose? assume they are very intelligent and extremely greedy (and that they would prefer not to die).
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 gives the wrong answer; then the assassin moves on to the next programmer. the programmers in front get to hear the answers of the programmers behind them, but not whether they live or die. they can consult and agree on a strategy before being lined up, but after being lined up and having the hats put on, they can’t communicate in any way other than those already specified. what strategy should they choose to maximize the number of programmers who are guaranteed to be saved?
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 still kill the king. furthermore, it takes one month to have an effect. The bad king decides he will get some of the prisoners in his vast dungeons to drink the wine. Being a clever bad king he knows he needs to murder no more than 10 prisoners - believing he can fob off such a low death rate - and will still be able to drink the rest of the wine at his anniversary party in 5 weeks time.
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?
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 flashlight. plus the bridge is only big enough for two people to cross at once. the four people walk at different speeds: one fella is so fast it only takes him 1 minute to cross the bridge, another 2 minutes, a third 5 minutes, the last it takes 10 minutes to cross the bridge. when two people cross the bridge together (sharing the flashlight), they both walk at the slower person’s pace. can they all get across before the bridge blows up?
person A: 1 minute person B: 2 minutes person C: 5 minutes person D:10 minutes
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. he honestly picks out 5 cards that i cannot see. he hands the five cards to me (joel can’t see any of this). i look at the cards and i pick 1 card out and give it back to babak. i then arrange the other four cards in a special way, and give those 4 cards all face down, and in a neat pile, to joel. joel looks at the 4 cards i gave him, and says out loud which card babak is holding (suit and number).
i did not convey any information to joel other than the way i ordered the 4 cards, (all face down, aligned in line with one another) so how did i encode babak’s card using that method?
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 where they get to see more of the other pirates die. how can pirate 6 save his skin?
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 time?
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. (so he only has ten hours left). save dave (or maybe, let him burn :-) ! what to do?
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, someone has to be in it to row it across.
a much harder river crossing problem will appear later this week.
A - anthropologist C - cannibal ++ - boat
river AAA |============| |++ | CCC |============|
need to make it river |============| AAA | ++| |============| CCC
note that if you violate the “anthropologists > cannibals” rule at any point in time, it is illegal.. for example if a boat with a cannibal and an anthropologist travels to a shore with one cannibal on it, then # cannibals > # anthropologists, even if you say the anthropologist immediately takes the boat back.
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 expect on a MENSA test. i’m not too sure whether getting this right constitutes intelligence in a way that would benefit computer scientists, but maybe it does. if you figure it out, then you can say it does. if you can’t figure it out, then you can just say it’s all hogwash and it’s a stupid question.
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 points. overall scores were determined by adding up the individual scores from each search engine.
Allen got the highest number of karma points - 24. Kottke was consistent in his scores: he got the same karma points from 4 different search engines. Spolsky got 5 points from lycos, and 3 from msn.
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 isn’t there to control him, he’ll bite. the dad can’t be left with any of the daughters when the mom isn’t there. likewise, the mom can’t be trusted alone with either of the sons when the dad isn’t there.
remember! only an adult can operate the boat, AND the boat can’t drive itself.
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 take care of the evil queen who tried to poison him. of course, her trusty guards catch the assassin before any harm is done. the queen notices that the assassin is quite handsome and doesn’t really want to punish him by death. she decides to test his wisdom.
the queen gives the assassin 12 pills which are all completely identical in shape, smell, texture, size, except 1 pill has a different weight. the queen gives the man a balance and tells him that all the pills are deadly poison except for the pill of a different weight. the assassin can make three weighings and then must swallow the pill of his choice. if he lives, he will be sent back to the bad king’s kingdom. if he dies, well, thats what you get for being an assassin.
only one pill is not poison and it is the pill which has a different weight. the assassin does not know if it weighs more or less than the other pills. how can he save his skin?
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 doors with a goat behind it and asks you if you would like to keep the door you chose, or switch to the other unknown door.
Should you switch? If so, why? What is the probability if you don’t switch? What is the probability if you do.
Lots of people have heard this problem.. so just knowing what to do isn’t sufficient. its the explanation that counts!
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 chain to facilitate this arrangement and how does that guarantee payment?
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.)
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 reaches the bottom. what is the probability that at some time during the second day, he is in the exact same spot he was in on the first day?
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 cannon again, walk toward the coconut tree while counting your steps. when you reach the coconut tree, turn 90 degrees to your right and walk the same number of paces. mark that spot on the ground with a stake.
c. find the midpoint between the two stakes and dig for the treasure.
you set off in secrecy to the deserted island. upon reaching the shore you site the coconut tree and the palm tree, but someone has removed the cannon. without digging randomly all over the island, is it still possible to find the treasure?
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 slow. but that’s why you get what you pay for. (i didn’t pay anything so i shouldn’t really expect anything in return.)
D. those screwy pirates are at it again. this time there are 13 pirates and they need to protect their treasure chest. they decide that they should only be able to open the chest if the majority (at least 7) agree that it should be opened. they ask a locksmith to come and put a specific number of locks on the safe. every lock must be opened to open the chest. there can be multiple keys for each lock, but each key only opens one lock (i.e. no skeleton keys). the locksmith can give more than one key to each pirate. how many locks should the locksmith use and what strategy should he use to distribute the keys, such that only when a majority of the pirates agree can the chest be opened?
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 tell you now, there is more than one. in fact, there are more than two. also be advised that walking north from the north pole (or south from the south pole) is illogical and therefore does not enter into the problem. all normal assumptions about directions will be used.
there are no tricks involved with this question. it just forces you to really think about the problem to come up with all the solutions.
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 can rotate them so that they appear identical in color, they are the same cube.
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 see that fisherman B has a white hat on. Fisherman D can see that C has a black hat, and B has a white hat. The fisherman have been told that there are four hats, two white and two black, so they know that they must have either a white or a black hat on. who shouts out the color of their hat and how do they know?
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 wants to go first.
Being the smart programmer you are, you realize that if the devil goes first, he may automatically win. so you convince him to let you go first, which makes your day because you know you can’t lose. what is your winning strategy?
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?
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 - i.e. it is solvable and has nothing to do with religion, being sneaky, or how au dente the pasta might be ;-)
1/3 of the time, the door to heaven will be chosen, so 1/3 of the time it will take zero days. 1/3 of the time, the 1-day door is chosen; of those, the right door will be chosen the next day, so 1/9 trips take 1 day. Similarly, 1/9 will take two days (choosing the 2-day door, then the right door).
After that, the cases split again, and again, and again. I can’t seem to make a nice infinite sum this way, so let’s try again.
Suppose the average days spent is X. 1/3 of the cases are done in zero days as before. 1/3 of the cases are 1 day plus X. 1/3 are 2 + X. So:
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. tails?
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 next flip, I win. (its not a speed race, we both flip at the same time, except i’m only concerned with what appears on my coin, and you are only concerned with whats on your coin). Are the odds fair? (obviously not, otherwise this wouldn’t be a question). who has the advantage and why?
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.).
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 in the bag keeps decreasing). What will be the color of the last ball left in the bag?
Once you tackle that, what if there are 20 blue balls and 13 red balls to start with?
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. Remember that a quarter roll is $10, a dime roll is $5, nickels $2, pennies 50 cents. So I go to the Banking Supply Store and buy empty paper rolls.
The Banking supply store, conveniently, sells assortment packs of coin rolls. Each assortment pack contains W quarter rolls, X dime rolls, Y nickel rolls, and Z penny rolls.
The question: what is the optimum ratio of W to X to Y to Z to maximize the probability that I will use up the assortment packs at the same rate, e.g. without lots of leftover nickel tubes and stuff?
P.S. this problem should ideally be solved using Excel (but if you really like doing these things by hand, be my guest).
paul brinkley makes these assumptions which are all good assumptions to make: Assumption 1: The price of purchases made, modulo $1, is an even distribution from 0 cents to 99 cents. Assumption 2: The cashier will always give you the least number of coins mathematically possible, and will always have enough of each type of coin to do this. So you’ll never get 99 pennies as change for a $1.01 purchase, for example. Assumption 3: Half dollars don’t exist.
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?
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?
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 have to do in order to find the right floor? (i.e. what’s the most efficient way you could drop the orbs to find your answer?)
You are allowed to break both orbs, provided that in doing so you uniquely identify the correct floor.