再等等99的rt就来了 - 未名空间MITBBS历史存档

i*m2013-08-30 07:08

1 楼

刚刚结束和IXL的第一轮电面。
一上来问我从哪儿听说到IXL的，我说从LinkedIn的Job Search版面，然后我简单的介
绍了一下自己的背景，他说good，然后接下来就做题了。
第一题：如果n-1 和 n+1 都是 prime number, 证明 n 能够被6 整除。
这题没见过，当时有点慌，说了一堆废话，然后说给个提示吧。他说能够被6整出说明
什么，我说说明能够被2 和 3 整除。然后一下就恍然大悟了，做出来了就。没有写代
码。
第二题：给一个N个元素的unsorted array，每个元素是between 0 到 N-1，让我找
出里面有没有duplicate。同样不用写代码只用给算法。
我问他有没有space 和 time complexity的限制，他说你先做吧。我就先说了一个
naive的，用一个hashmap 搞定。然后我说这样子我没用那个0到N-1的条件，我说应该
可以O（1）space搞定，他补充道说，你可以modify original array。那么就很简单
了，直接swap，例子如下：
original ：2 4 6 3 1 0 4
第一次： 6 4 2 3 1 0 4
第二次： 4 4 2 3 1 0 6
第三次： 1 4 2 3 4 0 6
第四次： 4 1 2 3 4 0 6
第五次：因为发现4 和 4 相同，所以有重复的 return false；
第三题：问我24小时内时针和分针重复多少次。如果开始时间是12：00am好多次，如
果开始时间是12：01am是好多次。
分别是23 和 22 次
最后问我有没有什么问题，我问了几个，最后他问我的deadline是什么？不知道问这个
的意思是什么，我说还没有deadline，（这个回答是不是太嫩了）然后他说 will get
back to me in the next week.
希望这个能过吧。

v*g2013-08-30 07:08

2 楼

恩

i*m2013-08-30 07:08

3 楼

第二题的其实是如何sort 一个 array in plcae的变形。

l*52013-08-30 07:08

4 楼

在等待就9 了。。
洗洗撸一管子去吧

f*e2013-08-30 07:08

5 楼

看起来答得不错。

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

: 刚刚结束和IXL的第一轮电面。
: 一上来问我从哪儿听说到IXL的，我说从LinkedIn的Job Search版面，然后我简单的介
: 绍了一下自己的背景，他说good，然后接下来就做题了。
: 第一题：如果n-1 和 n+1 都是 prime number, 证明 n 能够被6 整除。
: 这题没见过，当时有点慌，说了一堆废话，然后说给个提示吧。他说能够被6整出说明
: 什么，我说说明能够被2 和 3 整除。然后一下就恍然大悟了，做出来了就。没有写代
: 码。
: 第二题：给一个N个元素的unsorted array，每个元素是between 0 到 N-1，让我找
: 出里面有没有duplicate。同样不用写代码只用给算法。
: 我问他有没有space 和 time complexity的限制，他说你先做吧。我就先说了一个

a*y2013-08-30 07:08

6 楼

$49 is a reasonable price

h*n2013-08-30 07:08

7 楼

bless
第二个你是用冒泡还是选择排序呢？不过照样子也没用到题目中的那个1到n的条件啊

s*e2013-08-30 07:08

8 楼

co wait

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

: 恩

i*m2013-08-30 07:08

9 楼

每一次swap都有一个元素在自己该在的位子上，比如第一次交换玩 2 就在 index 2 的
位置，这样只用交换最多N次，这样那个1到n的条件就用了。

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

: bless
: 第二个你是用冒泡还是选择排序呢？不过照样子也没用到题目中的那个1到n的条件啊

p*f2013-08-30 07:08

10 楼

$99的RT比得上100块的nook hd+没？
后者屏幕好，快，APP多。。
结论是：$99的RT也不是什么deal....

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

: 恩

h*n2013-08-30 07:08

11 楼

Got it 学习了

d*g2013-08-30 07:08

12 楼

我就不买refurb的，不知道掉进马桶多少次

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

: $99的RT比得上100块的nook hd+没？
: 后者屏幕好，快，APP多。。
: 结论是：$99的RT也不是什么deal....

f*a2013-08-30 07:08

13 楼

第二题太难了，我不信除了搞竞赛的以外，有人能当场想出来。估计没指望你用O(n)，
hash就可以了。

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

: 刚刚结束和IXL的第一轮电面。
: 一上来问我从哪儿听说到IXL的，我说从LinkedIn的Job Search版面，然后我简单的介
: 绍了一下自己的背景，他说good，然后接下来就做题了。
: 第一题：如果n-1 和 n+1 都是 prime number, 证明 n 能够被6 整除。
: 这题没见过，当时有点慌，说了一堆废话，然后说给个提示吧。他说能够被6整出说明
: 什么，我说说明能够被2 和 3 整除。然后一下就恍然大悟了，做出来了就。没有写代
: 码。
: 第二题：给一个N个元素的unsorted array，每个元素是between 0 到 N-1，让我找
: 出里面有没有duplicate。同样不用写代码只用给算法。
: 我问他有没有space 和 time complexity的限制，他说你先做吧。我就先说了一个

x*02013-08-30 07:08

14 楼

等wsn撸完射到$199的RT上后，退还厂家再refurbish,然后以99卖出来。

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

: 恩

D*32013-08-30 07:08

15 楼

不至于吧。我就当场给出了。。。。。。。。。
IXL过一阵子会联系你做coding exercise.

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

: 第二题太难了，我不信除了搞竞赛的以外，有人能当场想出来。估计没指望你用O(n)，
: hash就可以了。

I*92013-08-30 07:08

16 楼

no format painter no deal

f*a2013-08-30 07:08

17 楼

联系我？
那我觉得你牛啊……

【在 D****3 的大作中提到】

:
: 不至于吧。我就当场给出了。。。。。。。。。
: IXL过一阵子会联系你做coding exercise.

z*g2013-08-30 07:08

18 楼

don't buy even for 99 !

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

: 恩

d*g2013-08-30 07:08

19 楼

第二题：如果没有duplicate而且N个元素都在0到N-1之间，那么只可能0到N-1之间的每
个数都出现且仅出现一次把。那么只需要看array所有元素的和是不是等于0+1+...+N-1
，如果不等于，那就一定有duplicate。
这样做不就可以了么？Or am I missing something？

l*z2013-08-30 07:08

20 楼

我看还是等赠送吧, 到时候买份windows正版,送一个RT

i*m2013-08-30 07:08

21 楼

Did you mean that they will contact me to do a coding exercis?

【在 D****3 的大作中提到】

:
: 不至于吧。我就当场给出了。。。。。。。。。
: IXL过一阵子会联系你做coding exercise.

l*82013-08-30 07:08

22 楼

99 + free office might consider it.

i*m2013-08-30 07:08

23 楼

明显不对啊比如2 2 3 3 和 0 1 2 3 4 加起来都一样
你说的情况是告诉你只有一个数missing掉了其他都出现exactly一次的情况

-1

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

: 第二题：如果没有duplicate而且N个元素都在0到N-1之间，那么只可能0到N-1之间的每
: 个数都出现且仅出现一次把。那么只需要看array所有元素的和是不是等于0+1+...+N-1
: ，如果不等于，那就一定有duplicate。
: 这样做不就可以了么？Or am I missing something？

p*m2013-08-30 07:08

24 楼

19$ is ok price

K*n2013-08-30 07:08

25 楼

不对，给你举个例子：比如有三个4，没有3，没有5，加起来的和看起来是对的，没有d
uplicate的，但实际上有。

-1

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

: 第二题：如果没有duplicate而且N个元素都在0到N-1之间，那么只可能0到N-1之间的每
: 个数都出现且仅出现一次把。那么只需要看array所有元素的和是不是等于0+1+...+N-1
: ，如果不等于，那就一定有duplicate。
: 这样做不就可以了么？Or am I missing something？

s*e2013-08-30 07:08

26 楼

...

【在 x******0 的大作中提到】

: 等wsn撸完射到$199的RT上后，退还厂家再refurbish,然后以99卖出来。

K*n2013-08-30 07:08

27 楼

小宝你太严谨了

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

: 明显不对啊比如2 2 3 3 和 0 1 2 3 4 加起来都一样
: 你说的情况是告诉你只有一个数missing掉了其他都出现exactly一次的情况
:
: -1

E*12013-08-30 07:08

28 楼

看不下去了，可不可以不要这么屌丝啊，好歹让人家软软赚点钱。

d*g2013-08-30 07:08

29 楼

有道理~~~

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

: 明显不对啊比如2 2 3 3 和 0 1 2 3 4 加起来都一样
: 你说的情况是告诉你只有一个数missing掉了其他都出现exactly一次的情况
:
: -1

I*92013-08-30 07:08

30 楼

ballmer内牛满面

【在 E***1 的大作中提到】

: 看不下去了，可不可以不要这么屌丝啊，好歹让人家软软赚点钱。

a*n2013-08-30 07:08

31 楼

第一题是不是反推啊，，显然N应该能被2整除，，现在看能不能被3除，，假定不能的
话，，反推出N+1或N-1不是PRIME。。。
第二题我在CITI BANK的面试碰到过，，原因是他出了一道题，我说做过，，他就出了
这倒题，，要求O(N)时间和O(1)SPACE，，费了我半天劲，，结果给我做出来了。。。
。

L*n2013-08-30 07:08

32 楼

IXL是哪？是我家娃用的数学学习网站吗？

i*m2013-08-30 07:08

33 楼

能够被6整出说明能够被2和3整出
被2整出很显然
被3整出因为连续3个数的和必定能被3整出，而且这三个数必定有一个也能被3整出，
因为n-1和n+1不能被3整出，所以只有n能被3整出

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

: 第一题是不是反推啊，，显然N应该能被2整除，，现在看能不能被3除，，假定不能的
: 话，，反推出N+1或N-1不是PRIME。。。
: 第二题我在CITI BANK的面试碰到过，，原因是他出了一道题，我说做过，，他就出了
: 这倒题，，要求O(N)时间和O(1)SPACE，，费了我半天劲，，结果给我做出来了。。。
: 。

i*m2013-08-30 07:08

34 楼

对的没错

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

: IXL是哪？是我家娃用的数学学习网站吗？

B*i2013-08-30 07:08

35 楼

应该不对把。如果n = 4, 那么n -1 = 3, n + 1 = 5 都是prime number。但是 4 显
然不能被6整除。
是不是你把题目记错了。

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

: 能够被6整出说明能够被2和3整出
: 被2整出很显然
: 被3整出因为连续3个数的和必定能被3整出，而且这三个数必定有一个也能被3整出，
: 因为n-1和n+1不能被3整出，所以只有n能被3整出

i*m2013-08-30 07:08

36 楼

前提条件 n>6 这个忘说了

f*t2013-08-30 07:08

37 楼

第一题不明白怎么证明啊。楼主能说下思路吗

i*m2013-08-30 07:08

38 楼

看18楼的回复

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

: 第一题不明白怎么证明啊。楼主能说下思路吗

S*w2013-08-30 07:08

39 楼

1. n 必为偶数否则 n+1就被2整除 n+1就不是prime
2. n 被3整除，否则 n/3 余2或者1，若余1 n-1被3整除，n-1不是prime；
若余2，n+1被3整除，n+1不是prime。

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

: 第一题不明白怎么证明啊。楼主能说下思路吗

y*e2013-08-30 07:08

40 楼

再整一个N元素数组, 初始化为0，把第一个数组的数字作为第二个数组的index, 如果
所在处不是0，就说明有重复，如果是零，就把这个值放入第二个数组那里。
O(N)

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

: 刚刚结束和IXL的第一轮电面。
: 一上来问我从哪儿听说到IXL的，我说从LinkedIn的Job Search版面，然后我简单的介
: 绍了一下自己的背景，他说good，然后接下来就做题了。
: 第一题：如果n-1 和 n+1 都是 prime number, 证明 n 能够被6 整除。
: 这题没见过，当时有点慌，说了一堆废话，然后说给个提示吧。他说能够被6整出说明
: 什么，我说说明能够被2 和 3 整除。然后一下就恍然大悟了，做出来了就。没有写代
: 码。
: 第二题：给一个N个元素的unsorted array，每个元素是between 0 到 N-1，让我找
: 出里面有没有duplicate。同样不用写代码只用给算法。
: 我问他有没有space 和 time complexity的限制，他说你先做吧。我就先说了一个

j*e2013-08-30 07:08

41 楼

ixl很牛的公司么？

i*m2013-08-30 07:08

42 楼

刚刚结束和IXL的第一轮电面。
一上来问我从哪儿听说到IXL的，我说从LinkedIn的Job Search版面，然后我简单的介
绍了一下自己的背景，他说good，然后接下来就做题了。
第一题：如果n-1 和 n+1 都是 prime number, 证明 n 能够被6 整除。
这题没见过，当时有点慌，说了一堆废话，然后说给个提示吧。他说能够被6整出说明
什么，我说说明能够被2 和 3 整除。然后一下就恍然大悟了，做出来了就。没有写代
码。
第二题：给一个N个元素的unsorted array，每个元素是between 0 到 N-1，让我找
出里面有没有duplicate。同样不用写代码只用给算法。
我问他有没有space 和 time complexity的限制，他说你先做吧。我就先说了一个
naive的，用一个hashmap 搞定。然后我说这样子我没用那个0到N-1的条件，我说应该
可以O（1）space搞定，他补充道说，你可以modify original array。那么就很简单
了，直接swap，例子如下：
original ：2 4 6 3 1 0 4
第一次： 6 4 2 3 1 0 4
第二次： 4 4 2 3 1 0 6
第三次： 1 4 2 3 4 0 6
第四次： 4 1 2 3 4 0 6
第五次：因为发现4 和 4 相同，所以有重复的 return false；
第三题：问我24小时内时针和分针重复多少次。如果开始时间是12：00am好多次，如
果开始时间是12：01am是好多次。
分别是23 和 22 次
最后问我有没有什么问题，我问了几个，最后他问我的deadline是什么？不知道问这个
的意思是什么，我说还没有deadline，（这个回答是不是太嫩了）然后他说 will get
back to me in the next week.
希望这个能过吧。

i*m2013-08-30 07:08

43 楼

第二题的其实是如何sort 一个 array in plcae的变形。

f*e2013-08-30 07:08

44 楼

看起来答得不错。

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

: 刚刚结束和IXL的第一轮电面。
: 一上来问我从哪儿听说到IXL的，我说从LinkedIn的Job Search版面，然后我简单的介
: 绍了一下自己的背景，他说good，然后接下来就做题了。
: 第一题：如果n-1 和 n+1 都是 prime number, 证明 n 能够被6 整除。
: 这题没见过，当时有点慌，说了一堆废话，然后说给个提示吧。他说能够被6整出说明
: 什么，我说说明能够被2 和 3 整除。然后一下就恍然大悟了，做出来了就。没有写代
: 码。
: 第二题：给一个N个元素的unsorted array，每个元素是between 0 到 N-1，让我找
: 出里面有没有duplicate。同样不用写代码只用给算法。
: 我问他有没有space 和 time complexity的限制，他说你先做吧。我就先说了一个

h*n2013-08-30 07:08

45 楼

bless
第二个你是用冒泡还是选择排序呢？不过照样子也没用到题目中的那个1到n的条件啊

i*m2013-08-30 07:08

46 楼

每一次swap都有一个元素在自己该在的位子上，比如第一次交换玩 2 就在 index 2 的
位置，这样只用交换最多N次，这样那个1到n的条件就用了。

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

: bless
: 第二个你是用冒泡还是选择排序呢？不过照样子也没用到题目中的那个1到n的条件啊

h*n2013-08-30 07:08

47 楼

Got it 学习了

f*a2013-08-30 07:08

48 楼

第二题太难了，我不信除了搞竞赛的以外，有人能当场想出来。估计没指望你用O(n)，
hash就可以了。

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

: 刚刚结束和IXL的第一轮电面。
: 一上来问我从哪儿听说到IXL的，我说从LinkedIn的Job Search版面，然后我简单的介
: 绍了一下自己的背景，他说good，然后接下来就做题了。
: 第一题：如果n-1 和 n+1 都是 prime number, 证明 n 能够被6 整除。
: 这题没见过，当时有点慌，说了一堆废话，然后说给个提示吧。他说能够被6整出说明
: 什么，我说说明能够被2 和 3 整除。然后一下就恍然大悟了，做出来了就。没有写代
: 码。
: 第二题：给一个N个元素的unsorted array，每个元素是between 0 到 N-1，让我找
: 出里面有没有duplicate。同样不用写代码只用给算法。
: 我问他有没有space 和 time complexity的限制，他说你先做吧。我就先说了一个

D*32013-08-30 07:08

49 楼

不至于吧。我就当场给出了。。。。。。。。。
IXL过一阵子会联系你做coding exercise.

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

: 第二题太难了，我不信除了搞竞赛的以外，有人能当场想出来。估计没指望你用O(n)，
: hash就可以了。

f*a2013-08-30 07:08

50 楼

联系我？
那我觉得你牛啊……

【在 D****3 的大作中提到】

:
: 不至于吧。我就当场给出了。。。。。。。。。
: IXL过一阵子会联系你做coding exercise.

d*g2013-08-30 07:08

51 楼

第二题：如果没有duplicate而且N个元素都在0到N-1之间，那么只可能0到N-1之间的每
个数都出现且仅出现一次把。那么只需要看array所有元素的和是不是等于0+1+...+N-1
，如果不等于，那就一定有duplicate。
这样做不就可以了么？Or am I missing something？

i*m2013-08-30 07:08

52 楼

Did you mean that they will contact me to do a coding exercis?

【在 D****3 的大作中提到】

:
: 不至于吧。我就当场给出了。。。。。。。。。
: IXL过一阵子会联系你做coding exercise.

i*m2013-08-30 07:08

53 楼

明显不对啊比如2 2 3 3 和 0 1 2 3 4 加起来都一样
你说的情况是告诉你只有一个数missing掉了其他都出现exactly一次的情况

-1

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

: 第二题：如果没有duplicate而且N个元素都在0到N-1之间，那么只可能0到N-1之间的每
: 个数都出现且仅出现一次把。那么只需要看array所有元素的和是不是等于0+1+...+N-1
: ，如果不等于，那就一定有duplicate。
: 这样做不就可以了么？Or am I missing something？

K*n2013-08-30 07:08

54 楼

不对，给你举个例子：比如有三个4，没有3，没有5，加起来的和看起来是对的，没有d
uplicate的，但实际上有。

-1

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

: 第二题：如果没有duplicate而且N个元素都在0到N-1之间，那么只可能0到N-1之间的每
: 个数都出现且仅出现一次把。那么只需要看array所有元素的和是不是等于0+1+...+N-1
: ，如果不等于，那就一定有duplicate。
: 这样做不就可以了么？Or am I missing something？

K*n2013-08-30 07:08

55 楼

小宝你太严谨了

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

: 明显不对啊比如2 2 3 3 和 0 1 2 3 4 加起来都一样
: 你说的情况是告诉你只有一个数missing掉了其他都出现exactly一次的情况
:
: -1

d*g2013-08-30 07:08

56 楼

有道理~~~

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

: 明显不对啊比如2 2 3 3 和 0 1 2 3 4 加起来都一样
: 你说的情况是告诉你只有一个数missing掉了其他都出现exactly一次的情况
:
: -1

a*n2013-08-30 07:08

57 楼

第一题是不是反推啊，，显然N应该能被2整除，，现在看能不能被3除，，假定不能的
话，，反推出N+1或N-1不是PRIME。。。
第二题我在CITI BANK的面试碰到过，，原因是他出了一道题，我说做过，，他就出了
这倒题，，要求O(N)时间和O(1)SPACE，，费了我半天劲，，结果给我做出来了。。。
。

L*n2013-08-30 07:08

58 楼

IXL是哪？是我家娃用的数学学习网站吗？

i*m2013-08-30 07:08

59 楼

能够被6整出说明能够被2和3整出
被2整出很显然
被3整出因为连续3个数的和必定能被3整出，而且这三个数必定有一个也能被3整出，
因为n-1和n+1不能被3整出，所以只有n能被3整出

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

: 第一题是不是反推啊，，显然N应该能被2整除，，现在看能不能被3除，，假定不能的
: 话，，反推出N+1或N-1不是PRIME。。。
: 第二题我在CITI BANK的面试碰到过，，原因是他出了一道题，我说做过，，他就出了
: 这倒题，，要求O(N)时间和O(1)SPACE，，费了我半天劲，，结果给我做出来了。。。
: 。

i*m2013-08-30 07:08

60 楼

对的没错

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

: IXL是哪？是我家娃用的数学学习网站吗？

B*i2013-08-30 07:08

61 楼

应该不对把。如果n = 4, 那么n -1 = 3, n + 1 = 5 都是prime number。但是 4 显
然不能被6整除。
是不是你把题目记错了。

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

: 能够被6整出说明能够被2和3整出
: 被2整出很显然
: 被3整出因为连续3个数的和必定能被3整出，而且这三个数必定有一个也能被3整出，
: 因为n-1和n+1不能被3整出，所以只有n能被3整出

i*m2013-08-30 07:08

62 楼

前提条件 n>6 这个忘说了

f*t2013-08-30 07:08

63 楼

第一题不明白怎么证明啊。楼主能说下思路吗

i*m2013-08-30 07:08

64 楼

看18楼的回复

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

: 第一题不明白怎么证明啊。楼主能说下思路吗

S*w2013-08-30 07:08

65 楼

1. n 必为偶数否则 n+1就被2整除 n+1就不是prime
2. n 被3整除，否则 n/3 余2或者1，若余1 n-1被3整除，n-1不是prime；
若余2，n+1被3整除，n+1不是prime。

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

: 第一题不明白怎么证明啊。楼主能说下思路吗

y*e2013-08-30 07:08

66 楼

再整一个N元素数组, 初始化为0，把第一个数组的数字作为第二个数组的index, 如果
所在处不是0，就说明有重复，如果是零，就把这个值放入第二个数组那里。
O(N)

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

: 刚刚结束和IXL的第一轮电面。
: 一上来问我从哪儿听说到IXL的，我说从LinkedIn的Job Search版面，然后我简单的介
: 绍了一下自己的背景，他说good，然后接下来就做题了。
: 第一题：如果n-1 和 n+1 都是 prime number, 证明 n 能够被6 整除。
: 这题没见过，当时有点慌，说了一堆废话，然后说给个提示吧。他说能够被6整出说明
: 什么，我说说明能够被2 和 3 整除。然后一下就恍然大悟了，做出来了就。没有写代
: 码。
: 第二题：给一个N个元素的unsorted array，每个元素是between 0 到 N-1，让我找
: 出里面有没有duplicate。同样不用写代码只用给算法。
: 我问他有没有space 和 time complexity的限制，他说你先做吧。我就先说了一个

j*e2013-08-30 07:08

67 楼

ixl很牛的公司么？

h*u2013-08-30 07:08

68 楼

mark

N*62013-08-30 07:08

69 楼

第三题为什么是23和22？
我怎么感觉从0点开始24小时是22次？
00:00:00是一次
1点多有一次
2点多有一次
...
11点多的那次应该在12:00整
然后13点多有一次
14点多
...
23点多那次在第二天的00:00:00，不应该计算在内
总共是22次啊？为什么是23次？

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

: 刚刚结束和IXL的第一轮电面。
: 一上来问我从哪儿听说到IXL的，我说从LinkedIn的Job Search版面，然后我简单的介
: 绍了一下自己的背景，他说good，然后接下来就做题了。
: 第一题：如果n-1 和 n+1 都是 prime number, 证明 n 能够被6 整除。
: 这题没见过，当时有点慌，说了一堆废话，然后说给个提示吧。他说能够被6整出说明
: 什么，我说说明能够被2 和 3 整除。然后一下就恍然大悟了，做出来了就。没有写代
: 码。
: 第二题：给一个N个元素的unsorted array，每个元素是between 0 到 N-1，让我找
: 出里面有没有duplicate。同样不用写代码只用给算法。
: 我问他有没有space 和 time complexity的限制，他说你先做吧。我就先说了一个

F*y2013-08-30 07:08

70 楼

不用吧? n=6的时候也成立, 5和7都是prime number

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

: 前提条件 n>6 这个忘说了

r*n2013-08-30 07:08

71 楼

repeat very 12/11 hours
24/(12/11) = 22
22 + the starting point = 23

【在 N*********6 的大作中提到】

: 第三题为什么是23和22？
: 我怎么感觉从0点开始24小时是22次？
: 00:00:00是一次
: 1点多有一次
: 2点多有一次
: ...
: 11点多的那次应该在12:00整
: 然后13点多有一次
: 14点多
: ...

y*12013-08-30 07:08

72 楼

Hash isn't as good as the solution lz provided, but theoretically it is O(n)
too, I think.

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

: 第二题太难了，我不信除了搞竞赛的以外，有人能当场想出来。估计没指望你用O(n)，
: hash就可以了。

y*r2013-08-30 07:08

73 楼

楼主是partition吧. 但是每个数都在0，k之间有啥意义？我觉得counting sort可以
。不过空间是n+k.

r*m2013-08-30 07:08

74 楼

第二题不就是find first missing positive number 的变形么；和LZ思路差不多，顺
序把每个元素扔到该在的位置上，如果发现位置被占了，就是dup了

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

: 第二题太难了，我不信除了搞竞赛的以外，有人能当场想出来。估计没指望你用O(n)，
: hash就可以了。

w*x2013-08-30 07:08

75 楼

彩虹mm~~~~~

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

: 第二题不就是find first missing positive number 的变形么；和LZ思路差不多，顺
: 序把每个元素扔到该在的位置上，如果发现位置被占了，就是dup了

l*h2013-08-30 07:08

76 楼

第一题不是很严谨啊，是不是应该申明n>4?
否则n= 4 的话，题目条件满足，但n不能被6整除

i*m2013-08-30 07:08

77 楼

you are right.

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

: 第一题不是很严谨啊，是不是应该申明n>4?
: 否则n= 4 的话，题目条件满足，但n不能被6整除

d*y2013-08-30 07:08

78 楼

第一题：假设n>6
N-1=6x+d, n+1=6x+d+2
Because both are prime, d cannot be 0,1,2,3,4,so d can only be 5, which
means n=6x+6

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

: 刚刚结束和IXL的第一轮电面。
: 一上来问我从哪儿听说到IXL的，我说从LinkedIn的Job Search版面，然后我简单的介
: 绍了一下自己的背景，他说good，然后接下来就做题了。
: 第一题：如果n-1 和 n+1 都是 prime number, 证明 n 能够被6 整除。
: 这题没见过，当时有点慌，说了一堆废话，然后说给个提示吧。他说能够被6整出说明
: 什么，我说说明能够被2 和 3 整除。然后一下就恍然大悟了，做出来了就。没有写代
: 码。
: 第二题：给一个N个元素的unsorted array，每个元素是between 0 到 N-1，让我找
: 出里面有没有duplicate。同样不用写代码只用给算法。
: 我问他有没有space 和 time complexity的限制，他说你先做吧。我就先说了一个