Puzzles Flashcards
You have 20 bottles of pills. 19 bottles have 1.0 gram pills, but one has pills of weight
1.1 grams. Given a scale that provides an exact measurement, how would you find the heavy bottle?
You can only use the scale once.
We can only use the scale once so weighting subsets of bottles doesn’t make sense.
Using the scale is defined as getting a result.
Take an increasing amount of pills from each bottle and calculate expected weight (1 from first, 2 from second… 20 from 20th). Anything over divided by an extra weight of biased pill will give an index of the bottle with heavy pills.
Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
BFS or DFS, track which nodes were visited to prevent infinite loop
Majac 2 liny, ktore spalaja sie w godzine, odmierz 15minut
Podpal 2 konce pierwszej liny i 1 koniec drugiej; gdy pierwsza lina splinie podpal drugi koniec drugiej liny - w tym momencie pozostalosc drugiej liny splonie w 15 minut;
8 kul + 1 cięższa; waga mówiąca, ktora strona przeważa; w 2 wazeniach znajda ciezsza
Podziel kule na 3 zbiory po 3; zważ dowolne 2; jesli waga jest w równowadze, wiemy, ze trojka, której nie zważyliśmy zawiera trefna kule; jesli któraś przeważa - ta zawiera trefna kule;
Wez troike z trefna kula i zważ dowolne 2 kule; jesli sa w równowadze, na stole została trefna kula a jesli nie - cięższa jest trefna;
Minimal Tree: Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.
Divide and conquer problem - take middle element to get a root of current subtree and recursively repeat with left and right half
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?
Probability of winning at game 2 is probability we hit 2 out of 3 tries or all 3 which probability is
3pp(1-p) + ppp
We need to solve:
3pp(1-p) + ppp > p = 3pp(1-p) + pp*p - p > 0
0 < p < 1
If p > 0.5 it’s worth trying game 2, otherwise just take one shot.
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).
Not possible
At first, it seems like this should be possible. It’s an 8 x 8 board, which has 64 squares, but two have been cut
off, so we’re down to 62 squares. A set of 31 dominoes should be able to fit there, right?
When we try to lay down dominoes on row 1, which only has 7 squares, we may notice that one domino
must stretch into the row 2. Then, when we try to lay down dominoes onto row 2, again we need to stretch
a domino into row 3.
For each row we place, we’ll always have one domino that needs to poke into the next row. No matter how
many times and ways we try to solve this issue, we won’t be able to successfully lay down all the dominoes.
There’s a cleaner, more solid proof for why it won’t work. The chessboard initially has 32 black and 32 white
squares. By removing opposite corners (which must be the same color), we’re left with 30 of one color and
32 of the other color. Let’s say, for the sake of argument, that we have 30 black and 32 white squares.
Each domino we set on the board will always take up one white and one black square. Therefore, 31 dominos
will take up 31 white squares and 31 black squares exactly. On this board, however, we must have 30 black
squares and 32 white squares. Hence, it is impossible.
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.
2(1/21/2*1/2) they pick the same direction (clockwise or counter clockwise) so probability of any collision is 1 minus that.
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.
Empty 5 Fill three Pour three to five twice We're left with 1 quart in the three-one Empty 5 Pour 1 quart to 5 Fill three Pour 3 quart to 5 Done, we got 4
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?
Wiemy, ze jest min 1
Mozemy spotkac wszystkich i ogarnac jaki maja kolor oczu
Jesli jest jeden to po pierwszym dniu nie widze nikogo niebieskookiego, wiec wiem, ze musze odejsc
Jesli jest 2 to, jesli drugiego dnia go spotkam, to bede wiedzial, ze on tez spotkal niebieskookiego pierwszego dnia a skoro ja nie spotkalem innego, wiec oba musimy odejsc
Jesli jest 3 to, jesli trzeciego dnia dalej spotkam 2 niebieskookich, to oni musieli spotkac jednego wiecej - mnie. itd
Power Set: Write a method to return all subsets of a set.
P(0) = {}
p(1) = {}, {a1}
p{2) = {}, {a1}, {a1,a2,}, {a2}
P(n) = P(n-1) + P(n-1)+an
Majac wszystkie zbiory dla n-1, wystarczy je sklonowac, dodac nty element i zwrocic oba.
Mozna tez wykorzystac bitset (wszystkich zbiorow jest 2^n - element jest lub go nie ma w zbiorze) i przeiterowac wszystkie kombinacje.
Magic Index: A magic index in an array A [ 0 ••• n -1] is defined to be an index such that A[ i] =
i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in
array A.
Posortowane, wiec mozna zrobic binary search
Wez srodkowy element i jesli jest wiekszy od indeksu to idz w prawo a jesli nie to w lewo. Elementy sa unikalne, wiec to zadziala. Jesli nie, to musimy po prostu sprawdzic obie polowki rekurencyjnie az do skutku.
Missing Int: Given an input file with four billion non-negative integers, provide an algorithm to
generate an integer that is not contained in the file. Assume you have 1 GB of memory available for
this task.
FOLLOW UP
What if you have only 10 MB of memory? Assume that all the values are distinct and we now have
no more than one billion non-negative integers.
int is 32bit, so there’re around 4 bilion unique ints
We have 4 bilion ints in the file - there must be duplicates
We can make a bit-set to find missing ints
as with 1GB we have 8 bilions bits so we can map each distinct int to a bit
If we have 10 MB of distinct ints we can make subranges and count histograms of data to find subrange where some int is missing. Then do second scan using bitvector of subrange size to find which int is missing
How to find subrange - we need bit vector of subrange so we must be able to store subrange bits also we need to store MAX_INT/subrange counters
