s**x
发帖数: 7506 | 1 大家多多贡献吧。这里那里有好多，还是集中一下比较方便。
先从偶知道的说吧。主要集中在 algorithms and puzzles.
Q1. how to verify a binary tree is a binary search tree?
A. the trick is to have a max and min value node for the function.
Q2.25 horses problem. 25 horses, 1 track, each race can race 5 horses only,
no timer, find the top 3 horses running the fastest with min races.
A: skip as this is well known.
Q3. all the numbers in an array occur twice except one only occur once, find
the one that occurs once.
A: simply xor all the numbers.
Q4: how to check if a number is power of 2?
A: x & (x-1)
Q5: N*M 2D number array, all rows are sorted from left to right, all columns
are sorted from top to bottom, to find a number in the array.
A: start from top right or bottom left corner, O(N+M) complexity.
Q6: prisoner question. each prisoner will get sent to a room which has a switch (On/off state only). how the prisoners can tell if they all have entered the room at least once.
A: assign one person to turn the switch from on to off and count, all the other people turn the switch from off to on if they are the first time to enter the room.
Q7:another prisoner question. prison to give 2 baskets, 50 black balls and 50 white balls, he will be asked to pick up one ball from a basket, if he gets a blackball, he is free, other wise he will be killed, how to arrange the balls?
A: 1 black ball in one basket, 49 black balls and 50 white balls in another basket.
Q8: a box has lots of Black balls and white balls, pick up any 2 balls each time, if they the same color, put one black ball back, otherwise, put one white back. how can you decide the color of the last ball?
A: based on the number of white balls is even or not. even, black, odd, white.
Q9: famous 9 ball weighing.
A: skip.
Q10: 10 baskets of balls, all the balls are the same weight except balls in one basket, you have a scale to check the actual weight, find the special basket with the minimum times of weighing.
A: ???
Q11: reverse words in a string. "mitbbs job hunting" => "hunting job mitbbs".
A: reverse the whole string first and then reverse each word.
Q12: given a list of numbers, find a pair whose sum equal to some number.
A: sort, compare the pair on the two ends, equal done. larger than the given number, move the left pointer, smaller move the right pointer, continue.
Q13: switch or not. 3 boxes, only has the treasure. you pick one, and someone will tell you a box that is sure no treasure. switch or not? which case has the high chance to find the treasure?
A: switch.
Q14: fair coin tossing, tail and head same chance. let's keep tossing the coin, if we see HHT, mike wins, if we see THH, Ron wins, whose chance is higher?
A: HHT. | i***d
发帖数: 28 | | n********y
发帖数: 66 | 3 why Q14 is not "same chance" | n********y
发帖数: 66 | 4 Q10:
take one ball from each basket and mark them as 1 to 10.
then same as Q9 | s**x
发帖数: 7506 | 5 once you see HH, you sure will see another T because if it is H, you are
still see HH. it is a series of continue tossing.
【在 n********y 的大作中提到】
: why Q14 is not "same chance"
| s**x
发帖数: 7506 | 6 I updated the question to make it clear, the scale is not a balance scale,
it can tell the exact weight. so it is different than Q9.
【在 n********y 的大作中提到】
: Q10:
: take one ball from each basket and mark them as 1 to 10.
: then same as Q9
| g**u
发帖数: 583 | 7 Q14:
why the prob is not the same? since it is a fair coin, the H and T is
interchangable.
Q15:
I do not understand it. Why not directly using Xor OXFF(1111 1111), then
all the bits 1 will be 0, all the bits 0 will be 1.
Could you please elaborate your algo? | f*******4
发帖数: 1401 | 8 不同的那个桶里的球 重/轻多少已知吗？
scale,
【在 s**x 的大作中提到】
: I updated the question to make it clear, the scale is not a balance scale,
: it can tell the exact weight. so it is different than Q9.
| f*******4
发帖数: 1401 | | s**x
发帖数: 7506 | 10 it does not matter I think.
【在 f*******4 的大作中提到】
: 不同的那个桶里的球 重/轻多少已知吗？
:
: scale,
| | | s**x
发帖数: 7506 | 11 I updated to make it clearer.
【在 f*******4 的大作中提到】
: Q6描述不清楚 题目看不懂。。。
| c******n
发帖数: 4965 | 12 q3 I see it all the time
bit I don't understand why XOR would work here
eg. 1 2 3 3
we look for 3. can u show me?
l
【在 s**x 的大作中提到】
: 大家多多贡献吧。这里那里有好多，还是集中一下比较方便。
: 先从偶知道的说吧。主要集中在 algorithms and puzzles.
: Q1. how to verify a binary tree is a binary search tree?
: A. the trick is to have a max and min value node for the function.
: Q2.25 horses problem. 25 horses, 1 track, each race can race 5 horses only,
: no timer, find the top 3 horses running the fastest with min races.
: A: skip as this is well known.
: Q3. all the numbers in an array occur twice except one only occur once, find
: the one that occurs once.
: A: simply xor all the numbers.
| s**x
发帖数: 7506 | 13 it is 1, 1, 2, 3, 3 , 5, 5. finding 2.
【在 c******n 的大作中提到】
: q3 I see it all the time
: bit I don't understand why XOR would work here
: eg. 1 2 3 3
: we look for 3. can u show me?
: l
| l*****a
发帖数: 559 | 14 i buy it.
【在 s**x 的大作中提到】
: once you see HH, you sure will see another T because if it is H, you are
: still see HH. it is a series of continue tossing.
| j*j
发帖数: 5564 | 15 this is not right except for the case where HH happen to be the result of
the first two tossings.
For other cases, since it's continuous tossing, for every HH or HH...HH,
there must be a T before them. So we can see that THH will always win before
HHT can win.
Suppose the tossing doesn't have to start over after each win, then the chance
will be equal for THH and HHT if they play long enough.
If the tossing has to be started over after each win, HHT only wins
in the case where HH happens to come at the fist two tossing. So, HHT's chance is 25%.
THH's chance is 75%.
【在 s**x 的大作中提到】
: once you see HH, you sure will see another T because if it is H, you are
: still see HH. it is a series of continue tossing.
|
|
