## CS interview questions

发信站: BBS 未名空间站 (Fri Jan 28 22:15:07 2011, 美东)

大家多多贡献吧。这里那里有好多，还是集中一下比较方便。

先从偶知道的说吧。主要集中在 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. we have 100 prisoners, each prisoner will be sent to a room which has a switch, the switch can be turned on and off. prisoners are picked randomly, so some can enter more than once. prisoners can not communicate to each other once they decide a plan at the beginning. how the prisoners can tell if they all have entered the room at least once some time later.

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. the scale is a scale to tell the exact weight, not a balance scale.

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.

Q15: reverse bits in a byte.

A: using ‘&’ and ‘|’. swap bits with neighbors first, then swap every 2 bits with their neighbors, then swap 4 bits with their neighbors.

Q16: 给定字符串，求其不出现重复字符的子字符串的最大长度，如何测试。

比如，“abcabcbb”最大的就是“abc”长度3

“bbbbb”最大就是“b”长度1

A: from forever84 (to be with you).

随便想的：

用一个256的table记录字符出现的情况，一快一慢两个指针，

快指针每向前移动一个字符就判断是不是已经出现过了，若没

出现过则继续前进，若出现过了则更新最大长度值，然后让慢

指针前进到快指针遇到的那个字符的后一个（因为只要有一个

重复的就不符合要求） 复杂度O(N)吧

Q17: remove any characters from string A that shows up in string B.

A: a trick is that you can use a small buffer to pre-process B so to speed up the lookup.

Q18: in 2-dimension situation, you have lots of rectangles and one given point, the rectangles may overlap, how to quickly find all the rectangles that the given point are inside of them?

A: google R-tree.

Q19: Maximum subarray problem

A: http://en.wikipedia.org/wiki/Maximum_subarray_problem

Q20: check if a single linked list has a loop.

A: two pointers, one advances one node each time, the second one advances 2 each time, if there is a loop, the two will meet.

Q21: Largest Rectangle in a Histogram

A: http://blog.csdn.net/arbuckle/archive/2006/05/06/710988.aspx