g*y
2 楼
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了
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了
k*k
3 楼
我现在只有一张discover信用卡,想申请第2张信用卡,不知道大牛们是否可以指点下
申请哪一张比较好,我的信用分数是710分
申请哪一张比较好,我的信用分数是710分
t*h
4 楼
如果不是以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),但是要求什么
: 随机输入的生么数学证明,类似于那个递归式子那样的。牛逼,我不会。然后没事见了
如果是 转化为少一位数字的复杂度 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),但是要求什么
: 随机输入的生么数学证明,类似于那个递归式子那样的。牛逼,我不会。然后没事见了
b*s
5 楼
BOA 123, chase freedom.
P*y
6 楼
你这个list是array还是linkedlist?
f*e
7 楼
信用历史多长
z*p
8 楼
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),但是要求什么
: 随机输入的生么数学证明,类似于那个递归式子那样的。牛逼,我不会。然后没事见了
z*p
14 楼
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
16 楼
嗯,明白了。
感觉严谨的写出应该是高富帅说的
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
感觉严谨的写出应该是高富帅说的
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
18 楼
刚才重想了觉得可以这么解,有错请指点:
比如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
: 吧。
比如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
20 楼
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
G*A
24 楼
能贴一下你的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),但是要求什么
: 随机输入的生么数学证明,类似于那个递归式子那样的。牛逼,我不会。然后没事见了
我怎么觉得除非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),但是要求什么
: 随机输入的生么数学证明,类似于那个递归式子那样的。牛逼,我不会。然后没事见了
g*0
25 楼
我第一张卡才开了3个月,信用分数也是700出头, 前天申请capital one venture, 批
了。 double里程, 送4万分, 还不错
了。 double里程, 送4万分, 还不错
q*8
26 楼
lz怎么写的N的算法?是你每次都move指针吗?
h*2
27 楼
我觉得第二张卡很难,以后就简单了。
如果你信用半年以上了,最好一年,没有不良记录,hp很少话。
建议看自己和银行关系--在哪家有checking就去哪集申请。
Chase-freedom
Citi-学生话考虑forward
Boa-基本返现那个。忘了叫什么了。
如果你信用半年以上了,最好一年,没有不良记录,hp很少话。
建议看自己和银行关系--在哪家有checking就去哪集申请。
Chase-freedom
Citi-学生话考虑forward
Boa-基本返现那个。忘了叫什么了。
g*y
28 楼
不好意思,我没说清楚,耽误大家时间了。
他让我用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
他让我用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
29 楼
跟风加一个吧,懒的开新贴了:
排好序的数组(每个数唯一,没有负数,有0),找漏掉的那个数。比如
[0,1,2,3,5] 返回4
要求O(logN)
排好序的数组(每个数唯一,没有负数,有0),找漏掉的那个数。比如
[0,1,2,3,5] 返回4
要求O(logN)
c*s
31 楼
呵呵,这道题我也碰到了, 也是我的第一道面试题。
我当时直接写的就是如果进位是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),但是要求什么
: 随机输入的生么数学证明,类似于那个递归式子那样的。牛逼,我不会。然后没事见了
我当时直接写的就是如果进位是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
32 楼
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?
operation, then we don't have to assume the list is very very long.
why?
z*p
34 楼
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?
相关阅读
没人讨论下Best Western 64k的offer,感觉还不错呀蓝宝石淘宝买东西 350人民币 convert to 58.96美元Chase Ink bold plus现在开卡是5W点,这个DEAL好吗?staples有kindle gift card吗?american express pending 有电话打吗?STAPLE的$25 offer 返了两次请问现在什么账户最值得转到Aeroplan?southwest 快速搞到100点citi发行的visa gift card 过期了,怎么办?为什么visa gc手续费还不一样?staple mastercard 怎么不可以set pin number?收到BoA Travel Rewards信用卡15000点的offerchase季度5%是否包括may's等店里的化妆品专柜?Grocery Store 的visa gift card (500元的)值得买吗?买delta的美国国内机票怎么能省点儿?旅行卡申请难度 谁给排个序?蓝宝石AAUA酒店staples买的mastercard load不了bluebirdBOA cash rewards卡只能用boa checking帐户还钱吗?用别人收到的citi promotion code申请citi aadvantage,需要打电话recon吗BOA的Keep the change是终生只能拿一次吗?