Question in computer science

For the final set of three balls, we simply repeat this: put one ball off to the side and weigh two. Pick the heavier of the two. Or$,$ if the balls are the same weight, pick the third one.

Algorithm Approaches

If you're stuck, consider applying one of the approaches for solving algorithm questions $($starting on page $67).$ Brainteasers are often nothing more than algorithm questions with the technical aspects removed. Base Case and Build and Do It Yourself $($DIY$)$ can be especially useful.

Additional Reading: Useful Math $($pg $629).$

Interview Questions

$6\mathrm{.}1$ The Heavy Pill: You have $20$ bottles of pills. $19$ bottles have $1\mathrm{.}0$ gram pills, but one has pills of weight $1\mathrm{.}1$ grams. Given a scale that provides an exact measurement, how would you find the heavy bottle? You can only use the scale once.

Hints: #$186,$ #$252,$ #$319,$ #$387$

Chapter $6|$ Math and Logic Puzzles

$6\mathrm{.}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 or the other?

Hints:#$181,$ #$239,$ #$284,$ #$323$

$6\mathrm{.}3$ Dominos: There is an $88$ chessboard in which two diagonally opposite comers 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: #$367,$ #$397$

pg $291$

$6\mathrm{.}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 $n-$vertex polygon.

Hints: #$157,$#$195,$ #$296$

$6\mathrm{.}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: #$149,$ #$379,$ #$400$

$6\mathrm{.}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: #$218,$ #$282,$ #$341,$ #$370$

$6\mathrm{.}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:#$154,$ #$160,$ #$171,$#$188,$ #$201$

CrackingTheCodingInterview.com$|6$th Edition

$123$

Chapter $6|$ Math and Logic Puzzles

$6\mathrm{.}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: #$156,$ #$233,$ #$294,$ #$333,$ #$357,$ #$374,$ #$395$

pg $296$

$6\mathrm{.}9100$ Lockers: There are $100$ closed lockers j a$-$ iallway. A man begins by opening all $100$ lockers. Next, he closes every second locker. Then, on his th$)$ Ird pass, he toggles every thiralocker $($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 ith locker. After his $100$th pass in the hallway, in which he toggles only locker