贡献几道CS电面题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

贡献几道CS电面题

贡献几道CS电面题# JobHunting - 待字闺中

l*a2009-12-07 08:12

1 楼

1. one array filled with numbers from 1 to N, but one number is missing. wha
t's the most efficient way to find the missing item? what about two or more
numbers are missed?
2. find the repetative chars in a string and delete them
3. find the binary tree from its preorder and inorder traversal

m*f2009-12-07 08:12

2 楼

有空间时间复杂度要求么?

H*M2009-12-07 08:12

3 楼

1. if one number is missing, we can sum them up and compute the difference;
if more is missing, maybe we need hash table?
2.keep an array of bool for all ASCII chars
We loop from the beginning, if we see a new element, check if it already a
ppeared, if not mark the array; if yes, delete it.
I think the key is do it in O(n) time. We can not simply delete each char.
We need to keep two pointers, one for one element past the clean section,
one pointer to the current index.

wha
more

【在 l**a 的大作中提到】

: 1. one array filled with numbers from 1 to N, but one number is missing. wha
: t's the most efficient way to find the missing item? what about two or more
: numbers are missed?
: 2. find the repetative chars in a string and delete them
: 3. find the binary tree from its preorder and inorder traversal

H*L2009-12-07 08:12

4 楼

2. find the repetative chars in a string and delete them
does it mean:
input: abcbda
output: abcd or cd?

wha
more

【在 l**a 的大作中提到】

h*e2009-12-07 08:12

5 楼

1. IMHO, if the array is sorted, then binary search O(lgN). If it's not,
then bit sort O(N). 0 bits are the missing numbers.

h*e2009-12-07 08:12

6 楼

3.我只想出recursive的方法。
preorder第一个肯定是root。找到root在inorder里的位置，就能确定左右子树。然后
递归。

m*f2009-12-07 08:12

7 楼

no need to sort, just xor the array and then xor 1 to n, done

【在 h*********e 的大作中提到】

: 1. IMHO, if the array is sorted, then binary search O(lgN). If it's not,
: then bit sort O(N). 0 bits are the missing numbers.

h*e2009-12-07 08:12

8 楼

This is nice. It saves space.
But still O(N), and cannot be applied to multiple missing problem.

c*n2009-12-07 08:12

9 楼

如果少2个数，xor怎么解决呢？

【在 m*****f 的大作中提到】

: no need to sort, just xor the array and then xor 1 to n, done

m*f2009-12-07 08:12

10 楼

少两个数没法用xor

【在 c*********n 的大作中提到】

: 如果少2个数，xor怎么解决呢？

n*r2009-12-07 08:12

11 楼

可以的
先对array求和，找出两个missing number的和,设为M
则必然一个小于M/2,一个大于M/2
对array里所有对array里所有>M/2的数xor，再和{floor[M/2]+1,...,N}xor得到第二个数

【在 m*****f 的大作中提到】

: 少两个数没法用xor

H*M2009-12-07 08:12

12 楼

妙啊.
不过三个数就不行了..

【在 n******r 的大作中提到】

: 可以的
: 先对array求和，找出两个missing number的和,设为M
: 则必然一个小于M/2,一个大于M/2
: 对array里所有: 对array里所有>M/2的数xor，再和{floor[M/2]+1,...,N}xor得到第二个数

n*r2009-12-07 08:12

13 楼

两个以上的数要通过sum或者xor包含的信息来区分可能就不行了
sort一下，多少个数都是能找出来的

【在 H*M 的大作中提到】

: 妙啊.
: 不过三个数就不行了..

n*r2009-12-07 08:12

14 楼

刚才算了一下
发现到四个数都是可以用xor O(N)的。。。

【在 H*M 的大作中提到】

: 妙啊.
: 不过三个数就不行了..

c*n2009-12-07 08:12

15 楼

怎么做的？给点hints?

【在 n******r 的大作中提到】

: 刚才算了一下
: 发现到四个数都是可以用xor O(N)的。。。

m*f2009-12-07 08:12

16 楼

三个数也可以吧，以n/3为界，必有一个或者两个小与n/3
因为现在有求和和xor两种方法求一个missing number, 如果这两种方法在1-n/3 结果
是一样的，那么就求得一个数，否则说明这段有两个数，再重复使用上面求两个数
的方法就可以了
四个数的话，先分成两半，确定每段是不是>1个数，然后再重复以上阶段
五个好象就不灵了，因为没法判断是一段中丢失的是两个数还是三个数..

【在 H*M 的大作中提到】

: 妙啊.
: 不过三个数就不行了..

n*r2009-12-07 08:12

17 楼

五个的情况，一段丢失两个还是三个可以通过数每段总数的奇偶来判断
难的是怎么样区分两段中一段缺2个一段缺3个，还是两段中一段缺一个还是一段缺四个
这个通过分情况讨论，还是可以搞定的

【在 m*****f 的大作中提到】

: 三个数也可以吧，以n/3为界，必有一个或者两个小与n/3
: 因为现在有求和和xor两种方法求一个missing number, 如果这两种方法在1-n/3 结果
: 是一样的，那么就求得一个数，否则说明这段有两个数，再重复使用上面求两个数
: 的方法就可以了
: 四个数的话，先分成两半，确定每段是不是>1个数，然后再重复以上阶段
: 五个好象就不灵了，因为没法判断是一段中丢失的是两个数还是三个数..

p*72009-12-07 08:12

18 楼

sum up有个问题是越界，如果N 很大，这个办法没用。

;
a
char.
section,

【在 H*M 的大作中提到】

: 1. if one number is missing, we can sum them up and compute the difference;
: if more is missing, maybe we need hash table?
: 2.keep an array of bool for all ASCII chars
: We loop from the beginning, if we see a new element, check if it already a
: ppeared, if not mark the array; if yes, delete it.
: I think the key is do it in O(n) time. We can not simply delete each char.
: We need to keep two pointers, one for one element past the clean section,
: one pointer to the current index.
:
: wha

m*g2009-12-07 08:12

19 楼

1. programming pearls: binary search
use N/2 as pivot, then N/4 and N*3/4
discard those full sections, narrow on to the ones with less than full
numbers.
this way u get O(n), and works for any missing numbers.
2. int cnt[256], register and remove
3. just try a few examples to figure out how

wha
more

【在 l**a 的大作中提到】

t*52009-12-07 08:12

20 楼

怎么没人回答这个问题

【在 H*****L 的大作中提到】

: 2. find the repetative chars in a string and delete them
: does it mean:
: input: abcbda
: output: abcd or cd?
:
: wha
: more

p*72009-12-07 08:12

21 楼

bit sort。能不能详细点

【在 h*********e 的大作中提到】

: 1. IMHO, if the array is sorted, then binary search O(lgN). If it's not,
: then bit sort O(N). 0 bits are the missing numbers.

p*72009-12-07 08:12

22 楼

必然是删除重复的，你也可以找面试官确认下

【在 t********5 的大作中提到】

: 怎么没人回答这个问题

p*72009-12-07 08:12

23 楼

一个题，数组未必是sorted啊

【在 m*****g 的大作中提到】

: 1. programming pearls: binary search
: use N/2 as pivot, then N/4 and N*3/4
: discard those full sections, narrow on to the ones with less than full
: numbers.
: this way u get O(n), and works for any missing numbers.
: 2. int cnt[256], register and remove
: 3. just try a few examples to figure out how
:
: wha
: more

f*g2009-12-07 08:12

24 楼

也是可以的，就是check每一个数字2进制的最高位，但是在这里有一个问题。PP上说的
是全集是所有的int，也就是说最高位为1或者0的个数是一样的。这里的N是任意数。如
果一定要用Binary Search,是不是可以找到一个小于N的最大的为2的几次方的正整数。
比如N=1500,则选择1024，1024之内的做Binary Search，多出的做线性，或者求和。

f*g2009-12-07 08:12

25 楼

Bit Sort也行，可能更快，可以测试下。

m*g2009-12-07 08:12

26 楼

if array not sorted, binary search is O(n).
the good thing it also apply to missing k numbers.

【在 p********7 的大作中提到】

: 一个题，数组未必是sorted啊