dell怎么还没有便宜的 xps台式机卖啊# Hardware - 计算机硬件
s*x
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.
先从偶知道的说吧。主要集中在 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.
