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… Read More »
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… Read More »
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… Read More »
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?
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%?
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… Read More »
Three coworkers would like to know their average salary. how can they do it, without disclosing their own salaries? Solution How about: Person A writes a number that is her salary plus a random amount (AS + AR) and hands it to B, without showing C. B then adds his salary plus a random amount… Read More »
You have $10,000 dollars to place a double-or-nothing bet on the Yankees in the World Series (max 7 games, series is over once a team wins 4 games). Unfortunately, you can only bet on each individual game, not the series as a whole. how much should you bet on each game, so that, if the… Read More »