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)，但是要求什么
: 随机输入的生么数学证明，类似于那个递归式子那样的。牛逼，我不会。然后没事见了
a*9
9 楼
你如果已经用了信用卡一年了 大部分主流的免年费的卡都可以申了
【在 k*********k 的大作中提到】
: 我现在只有一张discover信用卡，想申请第2张信用卡，不知道大牛们是否可以指点下
: 申请哪一张比较好，我的信用分数是710分
【在 k*********k 的大作中提到】
: 我现在只有一张discover信用卡，想申请第2张信用卡，不知道大牛们是否可以指点下
: 申请哪一张比较好，我的信用分数是710分
c*t
10 楼
感觉不太对， 最后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)
吧。
【在 z****p 的大作中提到】
:
: return
: C = 9/10*1 + 1/10*(1+C)
: --> C = 10/9 = 1.1111111 --> O(1)
k*k
11 楼
boa 123是什么？
【在 b*****s 的大作中提到】
: BOA 123, chase freedom.
【在 b*****s 的大作中提到】
: BOA 123, chase freedom.
g*y
12 楼
linkedlist. 我直接java List。 他原意估计是想让我python，直接写出[1,2,3].不过
这仅是我的猜测。
【在 P*******y 的大作中提到】
: 你这个list是array还是linkedlist?
这仅是我的猜测。
【在 P*******y 的大作中提到】
: 你这个list是array还是linkedlist?
z*8
13 楼
BankAmericard Cash Rewards
1% cash back on purchases everywhere, every time
2% at grocery stores and 3% on gas for the first $1,500 in combined grocery
store and gas purchases each quarter
1% 2% 3% 所以叫123
【在 k*********k 的大作中提到】
: boa 123是什么？
1% cash back on purchases everywhere, every time
2% at grocery stores and 3% on gas for the first $1,500 in combined grocery
store and gas purchases each quarter
1% 2% 3% 所以叫123
【在 k*********k 的大作中提到】
: boa 123是什么？
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
: 吧。
k*k
15 楼
我来美国四年，但是第一张信用卡今年3月份才有
【在 f********e 的大作中提到】
: 信用历史多长
【在 f********e 的大作中提到】
: 信用历史多长
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
k*k
17 楼
第一张信用卡今年3月份才有
【在 a******9 的大作中提到】
: 你如果已经用了信用卡一年了 大部分主流的免年费的卡都可以申了
【在 a******9 的大作中提到】
: 你如果已经用了信用卡一年了 大部分主流的免年费的卡都可以申了
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
: 吧。
f*e
19 楼
如果你有chase checking, 多存点钱让banker给你开freedom
可以试试AMEX的无年费卡，Blue cash everyday之类
【在 k*********k 的大作中提到】
: 我来美国四年，但是第一张信用卡今年3月份才有
可以试试AMEX的无年费卡，Blue cash everyday之类
【在 k*********k 的大作中提到】
: 我来美国四年，但是第一张信用卡今年3月份才有
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
k*k
21 楼
存多少钱呢？需要存多长时间才能找banker开freedom呢？
谢谢
【在 f********e 的大作中提到】
: 如果你有chase checking, 多存点钱让banker给你开freedom
: 可以试试AMEX的无年费卡，Blue cash everyday之类
谢谢
【在 f********e 的大作中提到】
: 如果你有chase checking, 多存点钱让banker给你开freedom
: 可以试试AMEX的无年费卡，Blue cash everyday之类
c*t
22 楼
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).
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).
f*e
23 楼
最好有个几千一万的，而且chase checking常年有coupon送200刀
不用存多长时间，去开个户存上钱当场就能让banker帮你申
【在 k*********k 的大作中提到】
: 存多少钱呢？需要存多长时间才能找banker开freedom呢？
: 谢谢
不用存多长时间，去开个户存上钱当场就能让banker帮你申
【在 k*********k 的大作中提到】
: 存多少钱呢？需要存多长时间才能找banker开freedom呢？
: 谢谢
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)
e*o
30 楼
cc150原题，binary search
【在 i*******6 的大作中提到】
: 跟风加一个吧，懒的开新贴了：
: 排好序的数组（每个数唯一，没有负数，有0），找漏掉的那个数。比如
: [0,1,2,3,5] 返回4
: 要求O(logN)
【在 i*******6 的大作中提到】
: 跟风加一个吧，懒的开新贴了：
: 排好序的数组（每个数唯一，没有负数，有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?
j*y
33 楼
只有一个数漏掉吗？
【在 i*******6 的大作中提到】
: 跟风加一个吧，懒的开新贴了：
: 排好序的数组（每个数唯一，没有负数，有0），找漏掉的那个数。比如
: [0,1,2,3,5] 返回4
: 要求O(logN)
【在 i*******6 的大作中提到】
: 跟风加一个吧，懒的开新贴了：
: 排好序的数组（每个数唯一，没有负数，有0），找漏掉的那个数。比如
: [0,1,2,3,5] 返回4
: 要求O(logN)
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?
相关阅读
Chase Saving $175 bonus一样的航班Citi thank you比航空公司贵一两百？BOA deal申请CHASE 蓝宝石给多少点?换工作401K怎么办？ (转载)Ebay 8折 L&T GCchase marriott申卡得时候，系统给了个新号，还能用earn free night得promo么？serve卡申请被要求上传证件American express的platinum card 值得搞吗最近要买近5000刀的机票，大家推荐个返点或者bonus多的卡来申请barclay arrival 有人成功从有年费转化为无年费版本吗求建议：discover offer连续5个月花500给100刀，转卡的话还能虚心请教mint和check哪家好一点?请问discover 用于amazonpayments有1% back吗关于chase信用卡的两个问题？寄两万美元回国怎么寄手续费最低？Slate的0% APR balance transferfreedom 的点转不了 ink了么？AMEX Business Platinum VS Business GOLD【求助】如何正确使用T-Mobile Visa Prepaid Card？