g***y
发帖数: 166 | 1 1.问project， 说个有coding的，说说感想。
2.coding一下， 给一个list，比如[1,2,3]，表示123, 写个increment的函数，return
[1,2,4],
如果是[9,9]这样的list，就要return[1,0,0]。assume list给的都是0到9的数字。 写
完要我代入几个test case过一下，然后要求写test function来测这个函数。写完问
complexity，俺发现俺的函数是O(N)可以优化到平均O(1)，然后问为什么平均O(1)。要
求证明俺不会，只能给出直觉分析，俺说只有10%的是9结尾的，需要进位，剩下的都是
不要进位的。complexity和输入有关，随机输入就是平均O(1)。 面试大哥不怎么满意
，最后问我有无问题，我说你告诉我这题的答案，他说是average O(1)，但是要求什么
随机输入的生么数学证明，类似于那个递归式子那样的。牛逼，我不会。然后没事见了
，google大哥说got to run。
就这样一小时过去了。
update:
- 我用java 的list，所以我就能直接用 get(),set()和add().这些都assume O(1)
的操作。不是singly linked list。
- 今天回去找code，发现那个电面的google doc没permission了 | t*********h
发帖数: 941 | 2 如果不是以9结尾的话 可以立即停止 cost:1 prob: 9/10
如果是 转化为少一位数字的复杂度 cost:C(L-1)= prob: 1/10
so C(L)=9/10 + 1/10xC(L-1) = 1? 不确定 哪位打牛给分析一下
return
【在 g***y 的大作中提到】
: 1.问project， 说个有coding的，说说感想。
: 2.coding一下， 给一个list，比如[1,2,3]，表示123, 写个increment的函数，return
: [1,2,4],
: 如果是[9,9]这样的list，就要return[1,0,0]。assume list给的都是0到9的数字。 写
: 完要我代入几个test case过一下，然后要求写test function来测这个函数。写完问
: complexity，俺发现俺的函数是O(N)可以优化到平均O(1)，然后问为什么平均O(1)。要
: 求证明俺不会，只能给出直觉分析，俺说只有10%的是9结尾的，需要进位，剩下的都是
: 不要进位的。complexity和输入有关，随机输入就是平均O(1)。 面试大哥不怎么满意
: ，最后问我有无问题，我说你告诉我这题的答案，他说是average O(1)，但是要求什么
: 随机输入的生么数学证明，类似于那个递归式子那样的。牛逼，我不会。然后没事见了
| P*******y
发帖数: 168 | 3 你这个list是array还是linkedlist? | z****p
发帖数: 18 | 4
return
C = 9/10*1 + 1/10*(1+C)
--> C = 10/9 = 1.1111111 --> O(1)
【在 g***y 的大作中提到】
: 1.问project， 说个有coding的，说说感想。
: 2.coding一下， 给一个list，比如[1,2,3]，表示123, 写个increment的函数，return
: [1,2,4],
: 如果是[9,9]这样的list，就要return[1,0,0]。assume list给的都是0到9的数字。 写
: 完要我代入几个test case过一下，然后要求写test function来测这个函数。写完问
: complexity，俺发现俺的函数是O(N)可以优化到平均O(1)，然后问为什么平均O(1)。要
: 求证明俺不会，只能给出直觉分析，俺说只有10%的是9结尾的，需要进位，剩下的都是
: 不要进位的。complexity和输入有关，随机输入就是平均O(1)。 面试大哥不怎么满意
: ，最后问我有无问题，我说你告诉我这题的答案，他说是average O(1)，但是要求什么
: 随机输入的生么数学证明，类似于那个递归式子那样的。牛逼，我不会。然后没事见了
| c********t
发帖数: 5706 | 5 感觉不太对， 最后1位是9，并不代表1+c啊，只能是2吧，只有9999999这样才能算1+c
吧。
【在 z****p 的大作中提到】
:
: return
: C = 9/10*1 + 1/10*(1+C)
: --> C = 10/9 = 1.1111111 --> O(1)
| g***y
发帖数: 166 | 6 linkedlist. 我直接java List。 他原意估计是想让我python，直接写出[1,2,3].不过
这仅是我的猜测。
【在 P*******y 的大作中提到】
: 你这个list是array还是linkedlist?
| z****p
发帖数: 18 | 7
c
1. assuming the list is very very long (almost infinite)
2. when a new call to "increment", we look at the last digit:
--if the last digit is between 0 and 8 (with prob 9/10), we are done with 1
operation (change of the last digit)
--if the last digit is 9, we change it to 0, which takes one operation, and
then recursively call "increment" on the prefix (the sublist with the last
digit removed).
--since the prefix is very very long, incrementing it has the same
complexity as incrementing the original list.
3. here "C" means the expected cost of incrementing the list.
4. if we consider adding a new "1" to the beginning of the list as 1
operation, then we don't have to assume the list is very very long.
【在 c********t 的大作中提到】
: 感觉不太对， 最后1位是9，并不代表1+c啊，只能是2吧，只有9999999这样才能算1+c
: 吧。
| c********t
发帖数: 5706 | 8 嗯，明白了。
感觉严谨的写出应该是高富帅说的
C(L)=9/10 + 1/10 * （1+C(L-1)）
C(1)=11/10
但和你的结果是一样的 1.1111111...
1
and
【在 z****p 的大作中提到】
:
: c
: 1. assuming the list is very very long (almost infinite)
: 2. when a new call to "increment", we look at the last digit:
: --if the last digit is between 0 and 8 (with prob 9/10), we are done with 1
: operation (change of the last digit)
: --if the last digit is 9, we change it to 0, which takes one operation, and
: then recursively call "increment" on the prefix (the sublist with the last
: digit removed).
: --since the prefix is very very long, incrementing it has the same
| g***y
发帖数: 166 | 9 刚才重想了觉得可以这么解，有错请指点：
比如1到1000的数；
以9结尾的是100个，
以99结尾是10个，
以999结尾的是1个，
所以以9结尾的就是:
(100/1000) * 1 + (10/1000）* 2 + （1/1000） * 3
写成通项就是 sum（1/10^k）* k, k from 1 to n , (n = 3 in above case)
不是9结尾的就是 [1-sum（1/10^k）] * 1, k from 1 to n
[1-sum（1/10^k）] * 1 + sum（1/10^k）* k = 1 + sum (（k-1)/10^k) -> 1
c
【在 c********t 的大作中提到】
: 感觉不太对， 最后1位是9，并不代表1+c啊，只能是2吧，只有9999999这样才能算1+c
: 吧。
| z****p
发帖数: 18 | 10
I guess you are right.
However, then the answer should be C(L) = 1.1111... (with L occurrences of 1
's after the decimal point).
Of course, the final answer to the complexity problem is O(1).
【在 c********t 的大作中提到】
: 嗯，明白了。
: 感觉严谨的写出应该是高富帅说的
: C(L)=9/10 + 1/10 * （1+C(L-1)）
: C(1)=11/10
: 但和你的结果是一样的 1.1111111...
:
: 1
: and
| | | c********t
发帖数: 5706 | 11 totally agree!
1
【在 z****p 的大作中提到】
:
: I guess you are right.
: However, then the answer should be C(L) = 1.1111... (with L occurrences of 1
: 's after the decimal point).
: Of course, the final answer to the complexity problem is O(1).
| G****A
发帖数: 4160 | 12 能贴一下你的code么？
我怎么觉得除非double-linked list,否则best case也不可能O(1). 你总要scan from
head to tail吧？这不就O(n)了？
return
【在 g***y 的大作中提到】
: 1.问project， 说个有coding的，说说感想。
: 2.coding一下， 给一个list，比如[1,2,3]，表示123, 写个increment的函数，return
: [1,2,4],
: 如果是[9,9]这样的list，就要return[1,0,0]。assume list给的都是0到9的数字。 写
: 完要我代入几个test case过一下，然后要求写test function来测这个函数。写完问
: complexity，俺发现俺的函数是O(N)可以优化到平均O(1)，然后问为什么平均O(1)。要
: 求证明俺不会，只能给出直觉分析，俺说只有10%的是9结尾的，需要进位，剩下的都是
: 不要进位的。complexity和输入有关，随机输入就是平均O(1)。 面试大哥不怎么满意
: ，最后问我有无问题，我说你告诉我这题的答案，他说是average O(1)，但是要求什么
: 随机输入的生么数学证明，类似于那个递归式子那样的。牛逼，我不会。然后没事见了
| q******8
发帖数: 848 | 13 lz怎么写的N的算法？是你每次都move指针吗？ | g***y
发帖数: 166 | 14 不好意思，我没说清楚，耽误大家时间了。
他让我用java 的list，所以我就能直接用 get(),set()和add().这些都assume O(1)
的操作了。
你说的对，如果是一个singly linked list, 要scan from head to tail, worst case
就是O(N^2), best case也要从头来过一次，是O(N)
from
【在 G****A 的大作中提到】
: 能贴一下你的code么？
: 我怎么觉得除非double-linked list,否则best case也不可能O(1). 你总要scan from
: head to tail吧？这不就O(n)了？
:
: return
| i*******6
发帖数: 107 | 15 跟风加一个吧，懒的开新贴了：
排好序的数组（每个数唯一，没有负数，有0），找漏掉的那个数。比如
[0,1,2,3,5] 返回4
要求O(logN) | e******o
发帖数: 757 | 16 cc150原题，binary search
【在 i*******6 的大作中提到】
: 跟风加一个吧，懒的开新贴了：
: 排好序的数组（每个数唯一，没有负数，有0），找漏掉的那个数。比如
: [0,1,2,3,5] 返回4
: 要求O(logN)
| c***s
发帖数: 192 | 17 呵呵，这道题我也碰到了， 也是我的第一道面试题。
我当时直接写的就是如果进位是0，直接break（我用array做的），所以也就没有问我
复杂度。
复杂度的话应该就是 1 * 0.9 + 2 * 0.1 * 0.9 + 3 * 0.1^2 * 0.9 + 4 * 0.1^3 * 0
.9 + ......
我当时做完这个以后就是两个list 相加，
然后是另外一道稍微复杂点的题目。
return
【在 g***y 的大作中提到】
: 1.问project， 说个有coding的，说说感想。
: 2.coding一下， 给一个list，比如[1,2,3]，表示123, 写个increment的函数，return
: [1,2,4],
: 如果是[9,9]这样的list，就要return[1,0,0]。assume list给的都是0到9的数字。 写
: 完要我代入几个test case过一下，然后要求写test function来测这个函数。写完问
: complexity，俺发现俺的函数是O(N)可以优化到平均O(1)，然后问为什么平均O(1)。要
: 求证明俺不会，只能给出直觉分析，俺说只有10%的是9结尾的，需要进位，剩下的都是
: 不要进位的。complexity和输入有关，随机输入就是平均O(1)。 面试大哥不怎么满意
: ，最后问我有无问题，我说你告诉我这题的答案，他说是average O(1)，但是要求什么
: 随机输入的生么数学证明，类似于那个递归式子那样的。牛逼，我不会。然后没事见了
| s******t
发帖数: 229 | 18 4. if we consider adding a new "1" to the beginning of the list as 1
operation, then we don't have to assume the list is very very long.
why? | j*****y
发帖数: 1071 | 19 只有一个数漏掉吗？
【在 i*******6 的大作中提到】
: 跟风加一个吧，懒的开新贴了：
: 排好序的数组（每个数唯一，没有负数，有0），找漏掉的那个数。比如
: [0,1,2,3,5] 返回4
: 要求O(logN)
| z****p
发帖数: 18 | 20
Sorry about the handwaving. My thought was that in order for the recursive
function to work, the list should be very long. That is, in C = 9/10*1 + 1/
10*(1+C), we put the same C on both sides, which implies that C is
independent of the length of the list. This is of course not true, but only
an approximation.
The boundary case, which behaves different from the general cases, is when
the leftmost digit is 9 and when we need to extend the list length by 1. But
the time complexity for extending the list depends on how the list is
implemented. For example, if the list is reversely stored in a linked list,
then extending the list length by 1 takes constant time (as long as we
maintain a pointer to the last element of the linked list, which stores the
leftmost digit); if the list is stored in an arraylist, which doubles its
size when needed, then on average its contant time; and so on.
Without knowing the detail, it's hard to tell about the boundary case.
However, if we assume it's cheaper than C to extend the list length by 1, e.
g., I assumed it's just 1 operation, then the boundary case is bounded above
by C, which guarantees that the recursive function is still valid.
I know, it's not very rigorous, as coldnight already pointed out.
【在 s******t 的大作中提到】
: 4. if we consider adding a new "1" to the beginning of the list as 1
: operation, then we don't have to assume the list is very very long.
: why?
|
|
