McDowell

Gayle Lakmann McDowell

• 

  McDowell2021

• 

  McDowell2013

• 

  McDowell2015

• 

  McDowell2014

McDowell2021:

Gayle Laakmann McDowell, Jackie Bavaro. Cracking the PM Career: The Skills, Frameworks, and Practices to Become a Great Product Manager. - CareerCup, 2021. - 551p.

McDowell2013:

Gayle Laakmann McDowell, Jackie Bavaro. Cracking the PM Interview: How to Land a Product Manager Job in Technology. - CareerCup; First Edition, 2013.- 364p.

McDowell2015:

Gayle Lakmann McDowell. Cracking the Coding Interview: 189 Programming Questions and Solutions. - CareerCup, 2015.- 687p.

McDowell2014:

Gayle Lakmann McDowell. Cracking the Tech Career: Insider Advice on Landing a Job at Google, Microsoft, Apple, or any Top Tech Company. - Wiley, 2014.- 288p.

---

1. The Heavy Pill: You have 20 bottles of pills. 19 bottles have 1.0 gram pills, but one has pills of weir 1.1 grams. Given a scale that provides an exact measurement, how would you find the heavy bot? You can only use the scale once.

Hints:

• You can only use the scale once. This means that all, or almost all, of the bottles must be used. They also must be handled in different ways or else you couldn't distinguish between them. [McDowell2015q186]

• What happens if you put one pill from each bottle on the scale? What if you put two pills from each bottle on the scale? [McDowell2015q252]

• Imagine there were just three bottles and one had heavier pills. Suppose you put different numbers of pills from each bottle on the scale (for example, bottle 1 has 5 pills, bottle 2 has 2 pills and bottle 3 has 9 pills). What would the scale show? [McDowell2015q319]

• You should be able to have an equation that tells you the heavy bottle based on the weight. [McDowell2015q387]

2. Basketball: You have a basketball hoop and someone says that you can play one of two games.
Game 1: You get one shot to make the hoop.
Game 2: You get three shots and you have to make two of three shots.
If p is the probability of making a particular shot, for which values of p should you pick one game the other?

Hints:

• Calculate the probability of winning the first game and winning the second game, then compare them. [McDowell2015q181]

• To calculate the probability of winning the second game, start with calculating the probability of making the first hoop, the second hoop, and not the third hoop. [McDowell2015q239]

• If two events are mutually exclusive (they can never occur simultaneously), you can add their probabilities together. Can you find a set of mutually exclusive events that represent making two out of three hoops? [McDowell2015q284]

• The probability of making two out of three shots is probability (make shot 1, make shot 2, miss shot 3) + probability (make shot 1, miss shot 2, make shot 3) + probability(miss shot 1, make shot 2, make shot 3) + probability (make shot 1, make shot 2, make shot 3). [McDowell2015q323]

3. Dominos: There is an 8x8 chessboard in which two diagonally opposite corners have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board? Prove your answer by providing an example or showing why it's impossible).

Hints:

• Picture a domino laying down on the board. How many black squares does it cover? How many white squares? [McDowell2015q367]

• How many black squares are there on the board? How many white squares? [McDowell2015q397]

4. Ants on a Triangle: There are three ants on different vertices of a triangle. What is the probability of collision (between any two or all of them) if they start walking on the sides of the triangle? Assume that each ant randomly picks a direction, with either direction being equally likely to be chosen, and that they walk at the same speed. Similarly, find the probability of collision with n ants on an -vertex polygon.

Hints:

• In what cases will they not collide? [McDowell2015q157]

• The only way they won't collide is if all three are walking in the same direction What's the probability of all three walking clockwise? [McDowell2015q195]

• You can think about this either as the probability (3 ants walking clockwise)+ probability (3 ants walking counter-clockwise). Or, you can think about it as: The first and picks a direction. What's the probability of the other ants picking the same directions? [McDowell2015q296]

5. Jugs of Water: You have a five-quart jug, a three-quart jug, and an unlimited supply of water (but no measuring cups). How would you come up with exactly four quarts of water? Note that the jugs are oddly shaped, such that filling up exactly "half" of the jug would be impossible.

Hints:

• Play around with the jugs of water, pouring water back and forth, and see if you can measure anything other than 3 quarts or 5 quarts. That's a start. [McDowell2015q149]
• If you fill the 5-quart jug and then use it to fill the 3-quart jug, you'll have two quarts left in the 5-quart jug. You can either keep those two quarts where they are, or you can dump the contents of the smaller jug and pour the two quarts in there. [McDowell2015q379]
• Once you've developed a way to solve this problem, think about it more broadly. If you are given a jug of size X and another jug of size Y, can you always use it to measure Z? [McDowell2015q400]

6. Blue-Eyed Island: A bunch of people are living on an island, when a visitor comes with a strange order: all blue-eyed people must leave the island as soon as possible. There will be a flight out at 8:00 pm every evening. Each person can see everyone else's eye color, but they do not know their own (nor is anyone allowed to tell them). Additionally, they do not know how many people have blue eyes, although they do know that at least one person does. How many days will it take the blue-eyed people to leave?

Hints:

• This is a logic problem, not a clever word problem. Use logic/math/algorithms to solve it. [McDowell2015q218]
• Suppose there were exactly one blue-eyed person. What would that person see? When would they leave? [McDowell2015q282]
• Now suppose there were two blue-eyed people. What would they see? What would they know? When would they leave? Remember your answer from the prior hint. Assume they know the answer to the earlier hint. [McDowell2015q341]
• Build up from this. What if there were three blue-eyed people? What if there were four blue-eyed people? [McDowell2015q370]

7. The Apocalypse: In the new post-apocalyptic world, the world queen is desperately concerned about the birth rate. Therefore, she decrees that all families should ensure that they have one girl or else they face massive fines. If all families abide by this policy that is, they have continue to have children until they have one girl, at which point they immediately stop -what will the gender ratio of the new generation be? (Assume that the odds of someone having a boy or a girl on any given pregnancy is equal.) Solve this out logically and then write a computer simulation of it.

Hints:

• Observe that each family will have exactly one girl. [McDowell2015q154]
• Think about writing each family as a sequence of Bs and Gs. [McDowell2015q160]
• You can attempt this mathematically, although the math is pretty difficult. You might find it easier to estimate it up to families of, say, 6 children. This won't give you a good mathematical proof, but it might point you in the right direction of what the answer might be. [McDowell2015q171]
• Logic might be easier than math. Imagine we wrote every birth into a giant string of Bs and Gs. Note that the groupings of families are irrelevant for this problem. What is the probability of the next character added to the string being a B versus a G? [McDowell2015q188]
• Observe that biology hasn't changed; only the conditions under which a family stops having kids has changed. Each pregnancy has a 50% odds of being a boy and a 50% odds of being a girl. [McDowell2015q201]

8. The Egg Drop Problem: There is a building of 100 floors. If an egg drops from the nth floor or above, it will break. If it's dropped from any floor below, it will not break. You're given two eggs. Find N, while minimizing the number of drops for the worst case.

Hints:

• This is really an algorithm problem, and you should approach it as such.Come up with a brute force, compute the worst-case number of drops, then try to optimize that. [McDowell2015q156]
• As a first approach, you might try something like binary search. Drop it from the 50th floor, then the 75th, then the 88th, and so on. The problem is that if the first egg breaks at the 50th floor, then you'll need to start dropping the second egg stating from the 1st floor and going up. This could take, at worst, 50 drops (the 50th floor drop the 1st drop, the 2nd floor drop, and up through the 49th floor drop). Can you beat this? [McDowell2015q233]
• It's actually better for the first drop to be a bit lower. For example, you could drop at the 10th floor, then the 20th floor, then the 30th floor, and so on. The worst case here will be 19 drops (10, 20, ., 100, 91, 92,... 99). Can you beat that? Try not randomly guessing at different solutions. Rather, think deeper. How is the worst case defined? How does the number of drops of each egg factor into that? [McDowell2015q294]
• If the drop Egg 1 at fixed intervals (e.g., every 10 floors), then the worst case is worst case + the worst case for Egg 2. The problem with our earlier solutions is that as Egg 1 does more work, Egg 2 doesn't do any less work. Ideally, we'd like to balance this a bit. As Egg 1 does more work (has survived more drops), Egg 2 should have less work to do. What might this mean? [McDowell2015q333]
• Try dropping Egg 1 at bigger intervals at the beginning and then at smaller and smaller intervals. The idea is to keep the sum of Egg 1 and Egg 2's drops as constant as possible. For each additional drop that Egg 1 takes, Egg 2 takes one fewer drop. What is the right interval? [McDowell2015q357]
• Let Xbe the fist drop of Egg 1. This means that Egg 2 would do X - 1 drops if Egg 1 broke. We want to try to keep the sum of Egg 1 and Egg 2's drops as constant as possible. If Egg 1 breaks on the second drop, then we want Egg 2 to do X - 2 drops. If Egg 1 breaks on the third drop, then we want Egg 2 to do X - 3 drops. This keeps the sum of Egg 1 and Egg 2 fairly constant. What is X? [McDowell2015q374]
• I got 14 drops in the worst case. What did you get? [McDowell2015q395]

9. 100 Lockers: There are 100 closed lockers in a hallway. A man begins by opening all 100 lockers. Next, he closes every second locker. Then, on his third pass, he toggles every third locker (closes it if it is open or opens it if it is closed). This process continues for 100 passes, such that on each pass i, the man toggles every i th locker. After his 100th pass in the hallway, in which he toggles only locker #100, how many lockers are open?

Hints:

• Given a specific door X, on which rounds will it be toggled (open or closed)? [McDowell2015q139]
• In which cases would a door be left open at the end of the process? [McDowell2015q172]
• Note: if an integer x is divisible by a, and b = x/a, then x is also divisible by b. Does this mean that all numbers have an even number of factors? [McDowell2015q264]
• The number 3 has an even number of factors (1 and 3). The number 12 has an even number of factors (1, 2, 3, 4, 6, 12). What numbers do not? What does this tell you about the doors? [McDowell2015q306]

10. Poison: You have 1000 bottles of soda, and exactly one is poisoned. You have 10 test strips which can be used to detect poison. A single drop of poison will turn the test strip positive permanently. You can put any number of drops on a test strip at once and you can reuse a test strip as many times as you'd like (as long as the results are negative). However, you can only run tests once per day and it takes seven days to return a result. How would you figure out the poisoned bottle in as few days as possible?

FOLLOW UP

Write code to simulate your approach.

Hints:

• Solution 1: Start with a simple approach. Can you just divide up the bottles into groups. Remember that you can't re-use a test strip once it is positive, but you can re-use it long as it's negative. [McDowell2015q146]
• Solution 1: There is a relatively simple approach that works in 28 days, in the worst case. There are better approaches though. [McDowell2015q163]
• Solution 2: Why do we have such a time lag between tests and results? There's a reason the question isn't phrased as just "minimize the number of rounds of testing." The time lag is there for a reason. [McDowell2015q183]
• Solution 2: Consider running multiple tests at once. [McDowell2015q191]
• Solution 2: Think about trying to figure out the bottle, digit by digit. How can you detect the first digit in the poisoned bottle? What about the second digit? The third digit? [McDowell2015q205]
• Solution 2: Be very careful about edge cases. What if the third digit in the bottle number matches the first or second digit? [McDowell2015q221]
• Solution 2: You can run an additional day of testing to check digit 3 in a different way. But again, be very careful about edge cases here. [McDowell2015q230]
• Solution 3: Think about each test strip as being a binary indicator for poisoned vs. non-poisoned. [McDowell2015q241]

PAUSE FOR A MOMENT AND CONSIDER THIS SCENARIO FOR YOURSELF.
Imagine you work at Google. How do you prove that IP addresses match people's locations, when you don't actually know people's locations?

There are likely many answers, but here's how I tackled it.

First, I realized that a subset of users had, at some point, typed in a zip code (presumably their own) while searching for weather forecasts or movie times. I could confirm that their IP address's location roughly matched the zip code. So far, so good.

But IP addresses could still be miles away from their location, even if it's the right zip code. How do we determine if the IP address is better than the zip code? Again, imagine you're at Google tackling this same problem. What data might be helpful to you?

I realized that those same users also periodically searched for specific restaurants or stores. So the question was: when they searched for specific places, was it more likely to match the zip code or the IP address?

It turned out that the IP address was much better than the zip code, which means that it was likely quite accurate. I now had the confidence to start an experiment, knowing that we would rarely be wrong about their location. The experiment proved successful, and we launched this change.

All of this was only possible because I knew what data existed. [McDowell2021p53]