index calls up - 未名空间MITBBS历史存档

index calls up# Stock

g*t2010-05-21 07:05

1 楼

不知道版上有没有人清楚，请问facebook的末位淘汰是怎么样的哦？有内部的人知道身
边management out之类的例子，还有原因不哦？
我拿到了facebook的offer，但是很害怕是因为自己做面试类的问题太在行了（感觉我
做算法题比自己工作中写普通code还要快）。所以比较担心想问一下...
我是5~8年exp那种。但是害怕自己做（面试题以外）事情的速度达不到fb的速度。
多谢了。

i*t2010-05-21 07:05

2 楼

手上太多有年费的卡了。大牛们帮我看看。把哪张卡取消了。一年快1000的年费
Chase Marriott，撸的80K，好像是一年要发个免费券。$85
CSP 一年95
UA,现在UA的1k会员，据说有这张卡可以看到更多的awards票。85一年
AMEX PRG 275
AMEX benz Platium 475，这张卡主要用来去lounge，吃一次饭30美金要的。UA的club
太挤了，吃的也差

f*u2010-05-21 07:05

3 楼

rt
今天去加油直接在pump上刷的油卡，看价格是按照credit的价格算的啊
去店里让小二刷回事cash的价格么

T*s2010-05-21 07:05

4 楼

with price flat

g*t2010-05-21 07:05

5 楼

忘了分享面试题目了
1. Manager聊经历半小时然后半小时coding: 给你一个read_buffer(char*buffer,
int len)，用这个实现read_line()，完全设计这个interface.
2. 给个数组，找出所有的三个数字trio, 加起来等于目标数字
3. 设计tinyurl
4. 给一个dict，然后一个长字符串，和长度len，找出所有长字符串里长度为len的在
字典内的子串。

v*r2010-05-21 07:05

6 楼

1k会员已经看到额外的票

T*s2010-05-21 07:05

7 楼

tricky ah

g*r2010-05-21 07:05

8 楼

want to know as well

r*52010-05-21 07:05

9 楼

马里奥524可以留着，否则回头要不到了
CSP可以降级到CFU/CF，保留点数无年费
UA也可以降级到免费版，保留MPX优势
PRG可以要retention
Plantium可以留着如果你用的多，高端卡还是留一张比较好

n*a2010-05-21 07:05

10 楼

都有5-8经验了，问题不大，应该比只靠刷题进去的干活速度快多了。

d*h2010-05-21 07:05

11 楼

好奇你1k的升舱概率如何
我不多的几次升舱都是银卡的时候的
变了金铂以后反而升级不到了....
离1k还有挺远不知道值不值得折腾一下

club

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

: 手上太多有年费的卡了。大牛们帮我看看。把哪张卡取消了。一年快1000的年费
: Chase Marriott，撸的80K，好像是一年要发个免费券。$85
: CSP 一年95
: UA,现在UA的1k会员，据说有这张卡可以看到更多的awards票。85一年
: AMEX PRG 275
: AMEX benz Platium 475，这张卡主要用来去lounge，吃一次饭30美金要的。UA的club
: 太挤了，吃的也差

g*t2010-05-21 07:05

12 楼

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

: 都有5-8经验了，问题不大，应该比只靠刷题进去的干活速度快多了。

a*g2010-05-21 07:05

13 楼

请问银卡升舱是自己升还是同伴一块升，是在登机口还是提前通知？

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

: 好奇你1k的升舱概率如何
: 我不多的几次升舱都是银卡的时候的
: 变了金铂以后反而升级不到了....
: 离1k还有挺远不知道值不值得折腾一下
:
: club

S*12010-05-21 07:05

14 楼

问题是5-8年的expectation是totally不一样的

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

: 都有5-8经验了，问题不大，应该比只靠刷题进去的干活速度快多了。

k*u2010-05-21 07:05

15 楼

申请一张CSR，上面的卡可以全关了。

club

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

: 手上太多有年费的卡了。大牛们帮我看看。把哪张卡取消了。一年快1000的年费
: Chase Marriott，撸的80K，好像是一年要发个免费券。$85
: CSP 一年95
: UA,现在UA的1k会员，据说有这张卡可以看到更多的awards票。85一年
: AMEX PRG 275
: AMEX benz Platium 475，这张卡主要用来去lounge，吃一次饭30美金要的。UA的club
: 太挤了，吃的也差

y*n2010-05-21 07:05

16 楼

我觉得担心多余了。如果从小到大都没有末位的话。
顺便跑题问一下这个题的思路。
read_buffer(char*buffer, int len)，用这个实现read_line()，完全设计这个
interface.

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

: 不知道版上有没有人清楚，请问facebook的末位淘汰是怎么样的哦？有内部的人知道身
: 边management out之类的例子，还有原因不哦？
: 我拿到了facebook的offer，但是很害怕是因为自己做面试类的问题太在行了（感觉我
: 做算法题比自己工作中写普通code还要快）。所以比较担心想问一下...
: 我是5~8年exp那种。但是害怕自己做（面试题以外）事情的速度达不到fb的速度。
: 多谢了。

f*y2010-05-21 07:05

17 楼

chase ua 是95吧...prg作什麼用途?

club

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

: 手上太多有年费的卡了。大牛们帮我看看。把哪张卡取消了。一年快1000的年费
: Chase Marriott，撸的80K，好像是一年要发个免费券。$85
: CSP 一年95
: UA,现在UA的1k会员，据说有这张卡可以看到更多的awards票。85一年
: AMEX PRG 275
: AMEX benz Platium 475，这张卡主要用来去lounge，吃一次饭30美金要的。UA的club
: 太挤了，吃的也差

B*12010-05-21 07:05

18 楼

怕啥 flgt 被雷的互相跳，爽得狠。
不雷都没决心没动力跳槽了。

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

: 不知道版上有没有人清楚，请问facebook的末位淘汰是怎么样的哦？有内部的人知道身
: 边management out之类的例子，还有原因不哦？
: 我拿到了facebook的offer，但是很害怕是因为自己做面试类的问题太在行了（感觉我
: 做算法题比自己工作中写普通code还要快）。所以比较担心想问一下...
: 我是5~8年exp那种。但是害怕自己做（面试题以外）事情的速度达不到fb的速度。
: 多谢了。

d*h2010-05-21 07:05

19 楼

登机口升
我当时就自己一人

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

: 请问银卡升舱是自己升还是同伴一块升，是在登机口还是提前通知？

p*22010-05-21 07:05

20 楼

大牛说说 lowball 进去的好跳吗？

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

: 怕啥 flgt 被雷的互相跳，爽得狠。
: 不雷都没决心没动力跳槽了。

w*32010-05-21 07:05

21 楼

ua和prg先关掉再说

v*k2010-05-21 07:05

22 楼

第四个怎么做啊。

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

: 忘了分享面试题目了
: 1. Manager聊经历半小时然后半小时coding: 给你一个read_buffer(char*buffer,
: int len)，用这个实现read_line()，完全设计这个interface.
: 2. 给个数组，找出所有的三个数字trio, 加起来等于目标数字
: 3. 设计tinyurl
: 4. 给一个dict，然后一个长字符串，和长度len，找出所有长字符串里长度为len的在
: 字典内的子串。

l*42010-05-21 07:05

23 楼

标准dfs

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

: 第四个怎么做啊。

g*s2010-05-21 07:05

24 楼

别怕了。进去在慢慢提高，谁不是一般做，一边提高呢。
实在害怕末位淘汰，快淘汰的时候，自己出来就完事了。
真要混的那么惨，真的从自己身上找问题了。总之要相信自己。

x*62010-05-21 07:05

25 楼

第四题是有啥玄机么？怎么感觉扫一遍看长度为len的substring在不在dict里就行了

g*t2010-05-21 07:05

26 楼

额那道题目的话，完整是给你int read_buffer(char*buffer, int len)，返回值是-1
或者填好的buffer的大小。如果不是-1需要可能再次调用，再取下一段。
我讨论了这些内容:
1. read_line()的返回值怎么传: 在read_line()里面分配好，还是api调用者分配好把
大小传进来? 如果用c++既有的string类，跨函数体的时候复制是怎么做的，内部内存
表示是怎样的？这些实现在这个scenario里面会有哪些缺陷？在这个scenario里会产生
内存fragmentation吗？有没有办法用一个自己管理的内存池减少fragmentation？当然
，难的设计只是提一下，也没有时间写出来。
2. 然后我用了一个read_line()自己的可以复用的固定大小buffer，一个指针指到上次
自己的内部buffer用了多少了，再遇到read_line就找下一个'n',如果用完了就把
buffer刷新。还有一些边界判定，比如上次取下来的buffer没有取满之类的。
3. 最后简化解是，最后写代码就用了unique_ptr, 里面分配好传出去。说了
一下string内部的implementation会造成的影响，如果resize会怎样，然后口头说如果
自己专门为这个设计一个结构会怎么做。

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

: 我觉得担心多余了。如果从小到大都没有末位的话。
: 顺便跑题问一下这个题的思路。
: read_buffer(char*buffer, int len)，用这个实现read_line()，完全设计这个
: interface.

g*t2010-05-21 07:05

27 楼

我说的用rolling hash来做。
比如ABCD里面:
ABC hash成 1 * 26 ^2 + 2 * 26 + 3
那么ABC变成BCD的时候，直接减1*26^2，乘26，加4，就可以了。
否则的话，最暴力的办法是，ABCD要先首指针指到A，然后另一边循环dict所有词条，
同时满足了第一个字母了还要再比较第二个字母... 然后首字母再移到B... 最坏情况
是 O(input_len * fixed_len * size_of_dict)
如果Dict用Trie的话，似乎需要track fixed_len那么多的iterator在trie里面寻路。
我已开始说Trie感觉就被打回来了。

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

: 第四题是有啥玄机么？怎么感觉扫一遍看长度为len的substring在不在dict里就行了

g*t2010-05-21 07:05

28 楼

我以前搞ACM之类的感觉面试算法题基本都可以秒... 但是感觉一到严格开发沟通流程
里面不太能stand out，很心虚啊

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

: 别怕了。进去在慢慢提高，谁不是一般做，一边提高呢。
: 实在害怕末位淘汰，快淘汰的时候，自己出来就完事了。
: 真要混的那么惨，真的从自己身上找问题了。总之要相信自己。

g*s2010-05-21 07:05

29 楼

沟通困难？每天总结，突破自己。不要怕。

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

: 我以前搞ACM之类的感觉面试算法题基本都可以秒... 但是感觉一到严格开发沟通流程
: 里面不太能stand out，很心虚啊

h*e2010-05-21 07:05

30 楼

这都是借口，真牛人不会这么想问题。

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

: 我以前搞ACM之类的感觉面试算法题基本都可以秒... 但是感觉一到严格开发沟通流程
: 里面不太能stand out，很心虚啊

g*t2010-05-21 07:05

31 楼

不是很懂... 请问可以展开说一下吗

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

: 这都是借口，真牛人不会这么想问题。

h*e2010-05-21 07:05

32 楼

任何问题只要肯下功夫都可以取得长足进步，说自己某方面不行其实就是懒惰不愿意努
力进步。真牛人都是努力用能力驾驭性格缺陷，同时再提高自身能力。

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

: 不是很懂... 请问可以展开说一下吗

m*u2010-05-21 07:05

33 楼

其实有个现象，真害怕被末尾淘汰的人一般都被淘汰不了，反而是无所谓的人会被淘汰
，道理大家应该都懂

b*t2010-05-21 07:05

34 楼

trio 是指和吗
在学hash
如果两个数子的话查表 n 就搞定了
三个的话就想到要先暴力 n^2 然后查表 ....... 有啥更好的办法吗

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

: 忘了分享面试题目了
: 1. Manager聊经历半小时然后半小时coding: 给你一个read_buffer(char*buffer,
: int len)，用这个实现read_line()，完全设计这个interface.
: 2. 给个数组，找出所有的三个数字trio, 加起来等于目标数字
: 3. 设计tinyurl
: 4. 给一个dict，然后一个长字符串，和长度len，找出所有长字符串里长度为len的在
: 字典内的子串。

g*t2010-05-21 07:05

35 楼

N^2似乎免不了
我曾经想过自己做一个很smart的pair的iterator，让一对pair可以变成按和的大小顺
序遍历那种，再加上一些加减取负数操作，把这个问题转成一个排序好的pair list和
一个integer list的集合求交的问题。
然后发现那个pair list的遍历，光是数量级上还是会有N^2，所以没有带来量级的优化
，那么就建跟(sum->pair_list)的hash差不多。（可能hash的空间是节省了）。
最后我的答案还是建sum->pair_list的hash.然后中间有一些小细节还可以优化。有的
细节没有想到是面试官提醒出来的。估计也还是比较看push到了你的knowledge
boundary之后，你怎么通过沟通继续优化吧...

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

: trio 是指和吗
: 在学hash
: 如果两个数子的话查表 n 就搞定了
: 三个的话就想到要先暴力 n^2 然后查表 ....... 有啥更好的办法吗

l*a2010-05-21 07:05

36 楼

太麻烦
先sort,然后固定一个，用双指针找另外俩

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

: N^2似乎免不了
: 我曾经想过自己做一个很smart的pair的iterator，让一对pair可以变成按和的大小顺
: 序遍历那种，再加上一些加减取负数操作，把这个问题转成一个排序好的pair list和
: 一个integer list的集合求交的问题。
: 然后发现那个pair list的遍历，光是数量级上还是会有N^2，所以没有带来量级的优化
: ，那么就建跟(sum->pair_list)的hash差不多。（可能hash的空间是节省了）。
: 最后我的答案还是建sum->pair_list的hash.然后中间有一些小细节还可以优化。有的
: 细节没有想到是面试官提醒出来的。估计也还是比较看push到了你的knowledge
: boundary之后，你怎么通过沟通继续优化吧...

i*e2010-05-21 07:05

37 楼

老Bay，你很幽默嘛 :)

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

: 怕啥 flgt 被雷的互相跳，爽得狠。
: 不雷都没决心没动力跳槽了。

g*t2010-05-21 07:05

38 楼

不是号称互相hr系统看得到吗...

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

: 怕啥 flgt 被雷的互相跳，爽得狠。
: 不雷都没决心没动力跳槽了。

g*t2010-05-21 07:05

39 楼

真相到底是什么啊...

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

: 老Bay，你很幽默嘛 :)

i*e2010-05-21 07:05

40 楼

老Bay 在G 很老年，专门忽悠新人跳槽。 lol

g*t2010-05-21 07:05

41 楼

不知道版上有没有人清楚，请问facebook的末位淘汰是怎么样的哦？有内部的人知道身
边management out之类的例子，还有原因不哦？
我拿到了facebook的offer，但是很害怕是因为自己做面试类的问题太在行了（感觉我
做算法题比自己工作中写普通code还要快）。所以比较担心想问一下...
我是5~8年exp那种。但是害怕自己做（面试题以外）事情的速度达不到fb的速度。
多谢了。

g*t2010-05-21 07:05

42 楼

忘了分享面试题目了
1. Manager聊经历半小时然后半小时coding: 给你一个read_buffer(char*buffer,
int len)，用这个实现read_line()，完全设计这个interface.
2. 给个数组，找出所有的三个数字trio, 加起来等于目标数字
3. 设计tinyurl
4. 给一个dict，然后一个长字符串，和长度len，找出所有长字符串里长度为len的在
字典内的子串。

g*r2010-05-21 07:05

43 楼

want to know as well

n*a2010-05-21 07:05

44 楼

都有5-8经验了，问题不大，应该比只靠刷题进去的干活速度快多了。

g*t2010-05-21 07:05

45 楼

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

: 都有5-8经验了，问题不大，应该比只靠刷题进去的干活速度快多了。

S*12010-05-21 07:05

46 楼

问题是5-8年的expectation是totally不一样的

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

: 都有5-8经验了，问题不大，应该比只靠刷题进去的干活速度快多了。

y*n2010-05-21 07:05

47 楼

我觉得担心多余了。如果从小到大都没有末位的话。
顺便跑题问一下这个题的思路。
read_buffer(char*buffer, int len)，用这个实现read_line()，完全设计这个
interface.

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

: 不知道版上有没有人清楚，请问facebook的末位淘汰是怎么样的哦？有内部的人知道身
: 边management out之类的例子，还有原因不哦？
: 我拿到了facebook的offer，但是很害怕是因为自己做面试类的问题太在行了（感觉我
: 做算法题比自己工作中写普通code还要快）。所以比较担心想问一下...
: 我是5~8年exp那种。但是害怕自己做（面试题以外）事情的速度达不到fb的速度。
: 多谢了。

B*12010-05-21 07:05

48 楼

怕啥 flgt 被雷的互相跳，爽得狠。
不雷都没决心没动力跳槽了。

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

: 不知道版上有没有人清楚，请问facebook的末位淘汰是怎么样的哦？有内部的人知道身
: 边management out之类的例子，还有原因不哦？
: 我拿到了facebook的offer，但是很害怕是因为自己做面试类的问题太在行了（感觉我
: 做算法题比自己工作中写普通code还要快）。所以比较担心想问一下...
: 我是5~8年exp那种。但是害怕自己做（面试题以外）事情的速度达不到fb的速度。
: 多谢了。

p*22010-05-21 07:05

49 楼

大牛说说 lowball 进去的好跳吗？

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

: 怕啥 flgt 被雷的互相跳，爽得狠。
: 不雷都没决心没动力跳槽了。

v*k2010-05-21 07:05

50 楼

第四个怎么做啊。

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

: 忘了分享面试题目了
: 1. Manager聊经历半小时然后半小时coding: 给你一个read_buffer(char*buffer,
: int len)，用这个实现read_line()，完全设计这个interface.
: 2. 给个数组，找出所有的三个数字trio, 加起来等于目标数字
: 3. 设计tinyurl
: 4. 给一个dict，然后一个长字符串，和长度len，找出所有长字符串里长度为len的在
: 字典内的子串。

l*42010-05-21 07:05

51 楼

标准dfs

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

: 第四个怎么做啊。

g*s2010-05-21 07:05

52 楼

别怕了。进去在慢慢提高，谁不是一般做，一边提高呢。
实在害怕末位淘汰，快淘汰的时候，自己出来就完事了。
真要混的那么惨，真的从自己身上找问题了。总之要相信自己。

x*62010-05-21 07:05

53 楼

第四题是有啥玄机么？怎么感觉扫一遍看长度为len的substring在不在dict里就行了

g*t2010-05-21 07:05

54 楼

额那道题目的话，完整是给你int read_buffer(char*buffer, int len)，返回值是-1
或者填好的buffer的大小。如果不是-1需要可能再次调用，再取下一段。
我讨论了这些内容:
1. read_line()的返回值怎么传: 在read_line()里面分配好，还是api调用者分配好把
大小传进来? 如果用c++既有的string类，跨函数体的时候复制是怎么做的，内部内存
表示是怎样的？这些实现在这个scenario里面会有哪些缺陷？在这个scenario里会产生
内存fragmentation吗？有没有办法用一个自己管理的内存池减少fragmentation？当然
，难的设计只是提一下，也没有时间写出来。
2. 然后我用了一个read_line()自己的可以复用的固定大小buffer，一个指针指到上次
自己的内部buffer用了多少了，再遇到read_line就找下一个'n',如果用完了就把
buffer刷新。还有一些边界判定，比如上次取下来的buffer没有取满之类的。
3. 最后简化解是，最后写代码就用了unique_ptr, 里面分配好传出去。说了
一下string内部的implementation会造成的影响，如果resize会怎样，然后口头说如果
自己专门为这个设计一个结构会怎么做。

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

: 我觉得担心多余了。如果从小到大都没有末位的话。
: 顺便跑题问一下这个题的思路。
: read_buffer(char*buffer, int len)，用这个实现read_line()，完全设计这个
: interface.

g*t2010-05-21 07:05

55 楼

我说的用rolling hash来做。
比如ABCD里面:
ABC hash成 1 * 26 ^2 + 2 * 26 + 3
那么ABC变成BCD的时候，直接减1*26^2，乘26，加4，就可以了。
否则的话，最暴力的办法是，ABCD要先首指针指到A，然后另一边循环dict所有词条，
同时满足了第一个字母了还要再比较第二个字母... 然后首字母再移到B... 最坏情况
是 O(input_len * fixed_len * size_of_dict)
如果Dict用Trie的话，似乎需要track fixed_len那么多的iterator在trie里面寻路。
我已开始说Trie感觉就被打回来了。

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

: 第四题是有啥玄机么？怎么感觉扫一遍看长度为len的substring在不在dict里就行了

g*t2010-05-21 07:05

56 楼

我以前搞ACM之类的感觉面试算法题基本都可以秒... 但是感觉一到严格开发沟通流程
里面不太能stand out，很心虚啊

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

: 别怕了。进去在慢慢提高，谁不是一般做，一边提高呢。
: 实在害怕末位淘汰，快淘汰的时候，自己出来就完事了。
: 真要混的那么惨，真的从自己身上找问题了。总之要相信自己。

g*s2010-05-21 07:05

57 楼

沟通困难？每天总结，突破自己。不要怕。

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

: 我以前搞ACM之类的感觉面试算法题基本都可以秒... 但是感觉一到严格开发沟通流程
: 里面不太能stand out，很心虚啊

h*e2010-05-21 07:05

58 楼

这都是借口，真牛人不会这么想问题。

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

: 我以前搞ACM之类的感觉面试算法题基本都可以秒... 但是感觉一到严格开发沟通流程
: 里面不太能stand out，很心虚啊

g*t2010-05-21 07:05

59 楼

不是很懂... 请问可以展开说一下吗

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

: 这都是借口，真牛人不会这么想问题。

h*e2010-05-21 07:05

60 楼

任何问题只要肯下功夫都可以取得长足进步，说自己某方面不行其实就是懒惰不愿意努
力进步。真牛人都是努力用能力驾驭性格缺陷，同时再提高自身能力。

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

: 不是很懂... 请问可以展开说一下吗

m*u2010-05-21 07:05

61 楼

其实有个现象，真害怕被末尾淘汰的人一般都被淘汰不了，反而是无所谓的人会被淘汰
，道理大家应该都懂

b*t2010-05-21 07:05

62 楼

trio 是指和吗
在学hash
如果两个数子的话查表 n 就搞定了
三个的话就想到要先暴力 n^2 然后查表 ....... 有啥更好的办法吗

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

: 忘了分享面试题目了
: 1. Manager聊经历半小时然后半小时coding: 给你一个read_buffer(char*buffer,
: int len)，用这个实现read_line()，完全设计这个interface.
: 2. 给个数组，找出所有的三个数字trio, 加起来等于目标数字
: 3. 设计tinyurl
: 4. 给一个dict，然后一个长字符串，和长度len，找出所有长字符串里长度为len的在
: 字典内的子串。

g*t2010-05-21 07:05

63 楼

N^2似乎免不了
我曾经想过自己做一个很smart的pair的iterator，让一对pair可以变成按和的大小顺
序遍历那种，再加上一些加减取负数操作，把这个问题转成一个排序好的pair list和
一个integer list的集合求交的问题。
然后发现那个pair list的遍历，光是数量级上还是会有N^2，所以没有带来量级的优化
，那么就建跟(sum->pair_list)的hash差不多。（可能hash的空间是节省了）。
最后我的答案还是建sum->pair_list的hash.然后中间有一些小细节还可以优化。有的
细节没有想到是面试官提醒出来的。估计也还是比较看push到了你的knowledge
boundary之后，你怎么通过沟通继续优化吧...

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

: trio 是指和吗
: 在学hash
: 如果两个数子的话查表 n 就搞定了
: 三个的话就想到要先暴力 n^2 然后查表 ....... 有啥更好的办法吗

l*a2010-05-21 07:05

64 楼

太麻烦
先sort,然后固定一个，用双指针找另外俩

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

: N^2似乎免不了
: 我曾经想过自己做一个很smart的pair的iterator，让一对pair可以变成按和的大小顺
: 序遍历那种，再加上一些加减取负数操作，把这个问题转成一个排序好的pair list和
: 一个integer list的集合求交的问题。
: 然后发现那个pair list的遍历，光是数量级上还是会有N^2，所以没有带来量级的优化
: ，那么就建跟(sum->pair_list)的hash差不多。（可能hash的空间是节省了）。
: 最后我的答案还是建sum->pair_list的hash.然后中间有一些小细节还可以优化。有的
: 细节没有想到是面试官提醒出来的。估计也还是比较看push到了你的knowledge
: boundary之后，你怎么通过沟通继续优化吧...

i*e2010-05-21 07:05

65 楼

老Bay，你很幽默嘛 :)

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

: 怕啥 flgt 被雷的互相跳，爽得狠。
: 不雷都没决心没动力跳槽了。

g*t2010-05-21 07:05

66 楼

不是号称互相hr系统看得到吗...

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

: 怕啥 flgt 被雷的互相跳，爽得狠。
: 不雷都没决心没动力跳槽了。

g*t2010-05-21 07:05

67 楼

真相到底是什么啊...

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

: 老Bay，你很幽默嘛 :)

i*e2010-05-21 07:05

68 楼

老Bay 在G 很老年，专门忽悠新人跳槽。 lol

H*h2010-05-21 07:05

69 楼

为啥不能把dict放进hash table, 然后scan一遍input_string, 然后查看每个pos到pos
+len之间的词在不在hash里？因为dict太大了？

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

: 我说的用rolling hash来做。
: 比如ABCD里面:
: ABC hash成 1 * 26 ^2 + 2 * 26 + 3
: 那么ABC变成BCD的时候，直接减1*26^2，乘26，加4，就可以了。
: 否则的话，最暴力的办法是，ABCD要先首指针指到A，然后另一边循环dict所有词条，
: 同时满足了第一个字母了还要再比较第二个字母... 然后首字母再移到B... 最坏情况
: 是 O(input_len * fixed_len * size_of_dict)
: 如果Dict用Trie的话，似乎需要track fixed_len那么多的iterator在trie里面寻路。
: 我已开始说Trie感觉就被打回来了。

f*n2010-05-21 07:05

70 楼

re

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

: 任何问题只要肯下功夫都可以取得长足进步，说自己某方面不行其实就是懒惰不愿意努
: 力进步。真牛人都是努力用能力驾驭性格缺陷，同时再提高自身能力。

m*a2010-05-21 07:05

71 楼

对呀，同问，这个方法不是很简单吗？
为什么用dfs？

pos

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

: 为啥不能把dict放进hash table, 然后scan一遍input_string, 然后查看每个pos到pos
: +len之间的词在不在hash里？因为dict太大了？

g*r2010-05-21 07:05

72 楼

ACMdo7能搞定，还怕码code这种没技术含量的事

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

: 我以前搞ACM之类的感觉面试算法题基本都可以秒... 但是感觉一到严格开发沟通流程
: 里面不太能stand out，很心虚啊

H*h2010-05-21 07:05

73 楼

看了看Rolling hash, 的确比这个方法好。复杂度从O(n*L)降到O(n)

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

: 对呀，同问，这个方法不是很简单吗？
: 为什么用dfs？
:
: pos

f*c2010-05-21 07:05

74 楼

请问read4k如果用java的话怎么解啊？

z*g2010-05-21 07:05

75 楼

可以把dic pre-process成 trie 然后对input stream dfs，如果dictionary很大并且
多次call这个function的话，感觉这个效率更好一些

pos

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

: 为啥不能把dict放进hash table, 然后scan一遍input_string, 然后查看每个pos到pos
: +len之间的词在不在hash里？因为dict太大了？