i********m
发帖数: 332 | 1 昨天电面BB，今天一大早收到onsite通知，真是有效率。
下面是昨天的题，
1。用什么数据结构存(key,value) pair? 如果你只知道这个key的前几个字母，比如
cat，只要是以cat开始的你都想存，用什么数据结构。
2。6位数的彩票，如果前三位和后三位的sum相同，则为中奖彩票，问有多少种中将可
能。
3。 100盏灯，刚开始是灭的，以后第一次全部flip，第二次每隔一个flip，第三次每
隔两个flip，。。。。 问最后亮着的灯是哪几盏。
4。 有很多URL，用什么数据结构存最近访问的100个。 要想访问最近访问的100个 in
order，用什么数据结构。NlgN 他说不太好。有没有其他的？
5。我有什么问题要问他的。
题不难，bless onsite。 |
j*****y
发帖数: 1071 | 2 cong!
1. 没太弄明白，只知道前几个字母，那么整个 key是不知道的还是知道的？ 感觉
用 prefix tree ?
4, 用 queque 就可以了吧，最近访问了一个就 enqueue, 然后把第一个 dequeue
in
【在 i********m 的大作中提到】
: 昨天电面BB，今天一大早收到onsite通知，真是有效率。
: 下面是昨天的题，
: 1。用什么数据结构存(key,value) pair? 如果你只知道这个key的前几个字母，比如
: cat，只要是以cat开始的你都想存，用什么数据结构。
: 2。6位数的彩票，如果前三位和后三位的sum相同，则为中奖彩票，问有多少种中将可
: 能。
: 3。 100盏灯，刚开始是灭的，以后第一次全部flip，第二次每隔一个flip，第三次每
: 隔两个flip，。。。。 问最后亮着的灯是哪几盏。
: 4。 有很多URL，用什么数据结构存最近访问的100个。 要想访问最近访问的100个 in
: order，用什么数据结构。NlgN 他说不太好。有没有其他的？
|
i********m
发帖数: 332 | 3 1。 Prefix Tree 就是他想要的
4。用queue不行 这样你每次要shift 不是他想要的
【在 j*****y 的大作中提到】
: cong!
: 1. 没太弄明白，只知道前几个字母，那么整个 key是不知道的还是知道的？ 感觉
: 用 prefix tree ?
: 4, 用 queque 就可以了吧，最近访问了一个就 enqueue, 然后把第一个 dequeue
:
: in
|
t*********h
发帖数: 941 | 4 linkedhashmap?
【在 i********m 的大作中提到】
: 1。 Prefix Tree 就是他想要的
: 4。用queue不行 这样你每次要shift 不是他想要的
|
j*****y
发帖数: 1071 | 5 4. 可以自己设计一个 cyclic array 的 queue, 提供 random access 可以吗？
呵呵
【在 i********m 的大作中提到】
: 1。 Prefix Tree 就是他想要的
: 4。用queue不行 这样你每次要shift 不是他想要的
|
t*********n
发帖数: 89 | 6 第二题写个程序出来是55252种号码中奖，求分析思路... |
f*****e
发帖数: 2992 | 7 可以。
【在 j*****y 的大作中提到】
: 4. 可以自己设计一个 cyclic array 的 queue, 提供 random access 可以吗？
: 呵呵
|
i********m
发帖数: 332 | 8 对 就是linkedList + Hashmap 就是他想要的
【在 t*********h 的大作中提到】
: linkedhashmap?
|
j*****y
发帖数: 1071 | 9 感觉可以分三种大情况
abcdef
1. a, b, c 这组数字和 d , e, f这组数字没有相同的
2. 两组中有一个相同的
3. 两组中 三个数字都相同
【在 t*********n 的大作中提到】
: 第二题写个程序出来是55252种号码中奖，求分析思路...
|
i********m
发帖数: 332 | 10 中奖和可以是0-27之间的任意一个。
写一个helper function ：
public int helper (int sum) {
return how many combination for this given sum
}
【在 t*********n 的大作中提到】
: 第二题写个程序出来是55252种号码中奖，求分析思路...
|
|
|
j*****y
发帖数: 1071 | 11 这道题是写 code？
【在 i********m 的大作中提到】
: 中奖和可以是0-27之间的任意一个。
: 写一个helper function ：
: public int helper (int sum) {
: return how many combination for this given sum
: }
|
i********m
发帖数: 332 | 12 没有写code 我就是这么写给他的
【在 j*****y 的大作中提到】
: 这道题是写 code？
|
j*****y
发帖数: 1071 | 13 那当时是要给计算方法还是要那个数字结果阿？
thanks.
【在 i********m 的大作中提到】
: 没有写code 我就是这么写给他的
|
i********m
发帖数: 332 | 14 只要是思路出来 然后写了seudo code 没有最后要结果
【在 j*****y 的大作中提到】
: 那当时是要给计算方法还是要那个数字结果阿？
: thanks.
|
j*****y
发帖数: 1071 | 15 thanks :)
【在 i********m 的大作中提到】
: 只要是思路出来 然后写了seudo code 没有最后要结果
|
s*******a
发帖数: 4166 | 16 I found a really good way to solve #2 on the bus today.
consider the polynomial:
f(x)=(1+x+x^2 + ....+ x^9)^3 = a_0 + a_1 x + a_2 x^2 + ....+ a_27 x^27
The coefficient of x^r will give us the number of combinations to give a sum
of r. Then the total number of possible combination to win the lottery will
be
S= a_0^2 + a_1^2 + .....+ a_27^2
Now the thing is how to compute these coefficients, this can be done as
follows:
f(x) = (1-x^10)^3/(1-x)^3, so basically we just need to do this simple
division operation to get these coefficients. This can be done in seconds if
we have a calculator on hand. Also, if they don't allow to use calculator/
pc, notice that the coefficients are symmetric. So we only need to find a_0,
a_1,.....a_13. This also can be done in a couple of minutes.
【在 i********m 的大作中提到】
: 只要是思路出来 然后写了seudo code 没有最后要结果
|
s*******a
发帖数: 4166 | 17 check my post on 16 floor
【在 t*********n 的大作中提到】
: 第二题写个程序出来是55252种号码中奖，求分析思路...
|
m******s
发帖数: 165 | 18 这是生成函数。如果朴素算乘积的话，会得到与迭代式动态规划相同的效果。如果利用
各种乘方来优化的话，也相当于对原动态规划进行了例行优化。
sum
will
【在 s*******a 的大作中提到】
: I found a really good way to solve #2 on the bus today.
: consider the polynomial:
: f(x)=(1+x+x^2 + ....+ x^9)^3 = a_0 + a_1 x + a_2 x^2 + ....+ a_27 x^27
: The coefficient of x^r will give us the number of combinations to give a sum
: of r. Then the total number of possible combination to win the lottery will
: be
: S= a_0^2 + a_1^2 + .....+ a_27^2
: Now the thing is how to compute these coefficients, this can be done as
: follows:
: f(x) = (1-x^10)^3/(1-x)^3, so basically we just need to do this simple
|
l*******2
发帖数: 114 | 19 welcome to NYC! 这公司福利不错，很稳定，工资和奖金一般，没有股票 |
i****a
发帖数: 36252 | 20 BB = best buy?
[发表自未名空间手机版 - m.mitbbs.com] |
|
|
m****t
发帖数: 2329 | 21 bloomberg
【在 i****a 的大作中提到】
: BB = best buy?
: [发表自未名空间手机版 - m.mitbbs.com]
|
G****A
发帖数: 4160 | 22 how about a queue using doubly-linked list?
push --> O(1)
pop --> O(1)
traverse --> O(n)
【在 i********m 的大作中提到】
: 只要是思路出来 然后写了seudo code 没有最后要结果
|
i********m
发帖数: 332 | 23 traverse 他不想要O(n) lookup他想要O(1)
【在 G****A 的大作中提到】
: how about a queue using doubly-linked list?
: push --> O(1)
: pop --> O(1)
: traverse --> O(n)
|
j*****y
发帖数: 1071 | 24 我觉得实现一下queue, 提供 O(1) 的 access也不难， 因为我们知道 queue里面其实
也是一个 array.
【在 i********m 的大作中提到】
: traverse 他不想要O(n) lookup他想要O(1)
|
i********m
发帖数: 332 | 25 可以
【在 j*****y 的大作中提到】
: 我觉得实现一下queue, 提供 O(1) 的 access也不难， 因为我们知道 queue里面其实
: 也是一个 array.
|
U***5
发帖数: 2796 | 26 第3题咋整？
弄100个bitmap,
1： 000000000....
2： 101010101....
3: 1001001001...
100: 1000...001
然后XOR?
in
【在 i********m 的大作中提到】
: 昨天电面BB，今天一大早收到onsite通知，真是有效率。
: 下面是昨天的题，
: 1。用什么数据结构存(key,value) pair? 如果你只知道这个key的前几个字母，比如
: cat，只要是以cat开始的你都想存，用什么数据结构。
: 2。6位数的彩票，如果前三位和后三位的sum相同，则为中奖彩票，问有多少种中将可
: 能。
: 3。 100盏灯，刚开始是灭的，以后第一次全部flip，第二次每隔一个flip，第三次每
: 隔两个flip，。。。。 问最后亮着的灯是哪几盏。
: 4。 有很多URL，用什么数据结构存最近访问的100个。 要想访问最近访问的100个 in
: order，用什么数据结构。NlgN 他说不太好。有没有其他的？
|
U***5
发帖数: 2796 | 27 祝贺！
每道题大概给你多少时间想啊？
in
【在 i********m 的大作中提到】
: 昨天电面BB，今天一大早收到onsite通知，真是有效率。
: 下面是昨天的题，
: 1。用什么数据结构存(key,value) pair? 如果你只知道这个key的前几个字母，比如
: cat，只要是以cat开始的你都想存，用什么数据结构。
: 2。6位数的彩票，如果前三位和后三位的sum相同，则为中奖彩票，问有多少种中将可
: 能。
: 3。 100盏灯，刚开始是灭的，以后第一次全部flip，第二次每隔一个flip，第三次每
: 隔两个flip，。。。。 问最后亮着的灯是哪几盏。
: 4。 有很多URL，用什么数据结构存最近访问的100个。 要想访问最近访问的100个 in
: order，用什么数据结构。NlgN 他说不太好。有没有其他的？
|
i********m
发帖数: 332 | 28 考虑一个数有多少个factor, 如果有奇数个factor那么最后就是亮着的，所以只能是1-
100的square number
【在 U***5 的大作中提到】
: 第3题咋整？
: 弄100个bitmap,
: 1： 000000000....
: 2： 101010101....
: 3: 1001001001...
: 100: 1000...001
: 然后XOR?
:
: in
|
j*****y
发帖数: 1071 | 29 这道题感觉是一道高频题
1-
【在 i********m 的大作中提到】
: 考虑一个数有多少个factor, 如果有奇数个factor那么最后就是亮着的，所以只能是1-
: 100的square number
|
i********m
发帖数: 332 | 30 大概差不多十几秒吧 我一边把题重复一遍 一遍想 重复玩了就基本想的差不多了
【在 U***5 的大作中提到】
: 祝贺！
: 每道题大概给你多少时间想啊？
:
: in
|
|
|
U***5
发帖数: 2796 | 31 很强大啊，onsite肯定没问题。
【在 i********m 的大作中提到】
: 大概差不多十几秒吧 我一边把题重复一遍 一遍想 重复玩了就基本想的差不多了
|
b*******n
发帖数: 847 | 32 interview exposed 和career cup上都有啊
【在 j*****y 的大作中提到】
: 这道题感觉是一道高频题
:
: 1-
|
j*********e
发帖数: 811 | 33 could u specify the random access part?thanks
【在 j*****y 的大作中提到】
: 4. 可以自己设计一个 cyclic array 的 queue, 提供 random access 可以吗？
: 呵呵
|
b****g
发帖数: 192 | 34 自己手写：
第1盏灯编号0，第2盏灯编号1，第3盏灯编号2。。。一直写到编号9
然后你自己从第一轮到第10轮自己用手写出灯的状况
然后就发现编号是完全平方数的灯和其他灯状况不一样
比如平方数9的约数有1、3、9，所以9号灯只被改变了3次，是奇数次
非平方数8=1、2、4、8，所以9号灯只被改变了4次，是偶数次
这是因为平方数只有奇数个约束，非平方数有偶数个约数
用上面的方法写几行就发现规律了。
【在 U***5 的大作中提到】
: 第3题咋整？
: 弄100个bitmap,
: 1： 000000000....
: 2： 101010101....
: 3: 1001001001...
: 100: 1000...001
: 然后XOR?
:
: in
|
b****g
发帖数: 192 | 35 第二题则么做啊？
“6位数的彩票，如果前三位和后三位的sum相同，则为中奖彩票，问有多少种中将可能”
brute force从000000检查到999999也太笨了，是O(lg n)吧。
in
【在 i********m 的大作中提到】
: 昨天电面BB，今天一大早收到onsite通知，真是有效率。
: 下面是昨天的题，
: 1。用什么数据结构存(key,value) pair? 如果你只知道这个key的前几个字母，比如
: cat，只要是以cat开始的你都想存，用什么数据结构。
: 2。6位数的彩票，如果前三位和后三位的sum相同，则为中奖彩票，问有多少种中将可
: 能。
: 3。 100盏灯，刚开始是灭的，以后第一次全部flip，第二次每隔一个flip，第三次每
: 隔两个flip，。。。。 问最后亮着的灯是哪几盏。
: 4。 有很多URL，用什么数据结构存最近访问的100个。 要想访问最近访问的100个 in
: order，用什么数据结构。NlgN 他说不太好。有没有其他的？
|
b****g
发帖数: 192 | 36 第二题则么做啊？
“6位数的彩票，如果前三位和后三位的sum相同，则为中奖彩票，问有多少种中将可能”
brute force从000000检查到999999也太笨了，是O(n)吧。
in
【在 i********m 的大作中提到】
: 昨天电面BB，今天一大早收到onsite通知，真是有效率。
: 下面是昨天的题，
: 1。用什么数据结构存(key,value) pair? 如果你只知道这个key的前几个字母，比如
: cat，只要是以cat开始的你都想存，用什么数据结构。
: 2。6位数的彩票，如果前三位和后三位的sum相同，则为中奖彩票，问有多少种中将可
: 能。
: 3。 100盏灯，刚开始是灭的，以后第一次全部flip，第二次每隔一个flip，第三次每
: 隔两个flip，。。。。 问最后亮着的灯是哪几盏。
: 4。 有很多URL，用什么数据结构存最近访问的100个。 要想访问最近访问的100个 in
: order，用什么数据结构。NlgN 他说不太好。有没有其他的？
|
i********m
发帖数: 332 | 37 10楼有解释！
能”
【在 b****g 的大作中提到】
: 第二题则么做啊？
: “6位数的彩票，如果前三位和后三位的sum相同，则为中奖彩票，问有多少种中将可能”
: brute force从000000检查到999999也太笨了，是O(n)吧。
:
: in
|
a****r
发帖数: 330 | |
y****n
发帖数: 743 | 39 关于第二题，我能想到的最快的方法。
时间空间都是O(10N)=〉O(N)，此题N=3。
当然如果利用对称性，时间空间还可以再减半。
为了保留一点点可读性，就不继续优化了。
public int[] Apply0to9(int[] inArr)
{
int[] outArr = new int[inArr.Length + 9];
int inst = 0;
for (int i = 0; i < inArr.Length + 9; i++)
{
if (i < inArr.Length)
inst += inArr[i];
outArr[i] = inst;
if (i - 9 >= 0)
inst -= inArr[i - 9];
}
return outArr;
}
public int CountCase(int n)
{
int[] arr = {1};
for(int i = 0; i < n; i ++)
arr = Apply0to9(arr);
int total = 0;
for (int i = 0; i < arr.Length; i++)
total += arr[i] * arr[i];
return total;
} |
i********m
发帖数: 332 | 40 这都一周过去了 给了onsite后就再也没消息了 给recruiter发信问也不回 什么情况！？
in
【在 i********m 的大作中提到】
: 昨天电面BB，今天一大早收到onsite通知，真是有效率。
: 下面是昨天的题，
: 1。用什么数据结构存(key,value) pair? 如果你只知道这个key的前几个字母，比如
: cat，只要是以cat开始的你都想存，用什么数据结构。
: 2。6位数的彩票，如果前三位和后三位的sum相同，则为中奖彩票，问有多少种中将可
: 能。
: 3。 100盏灯，刚开始是灭的，以后第一次全部flip，第二次每隔一个flip，第三次每
: 隔两个flip，。。。。 问最后亮着的灯是哪几盏。
: 4。 有很多URL，用什么数据结构存最近访问的100个。 要想访问最近访问的100个 in
: order，用什么数据结构。NlgN 他说不太好。有没有其他的？
|
