a*****n
发帖数: 158 | 1 倒在最后一个INTERVIEW。。对方MD，说话特快，好几次都要重复了我才听懂。。。问
了一算法题，没做好，跟大家请教一下，就是：把数学PI转成字符串，找第一个长度为
４的重复字符串，我的答案是，把每４个串做成HASH，存HASH MAP，然后找重复。然后
问复杂度，我说是O（N）。对方说不对，我只好说，如果重复的串在K个位置出现的话
，在第K个循环后能找到。ASSUME HASH 算法时间固定和插入、查找时间固定。。。结
果好象也不对 。。。。 |
b***u
发帖数: 12010 | 2 pi转了字符串才给你么？无穷长？
【在 a*****n 的大作中提到】
: 倒在最后一个INTERVIEW。。对方MD，说话特快，好几次都要重复了我才听懂。。。问
: 了一算法题，没做好，跟大家请教一下，就是：把数学PI转成字符串，找第一个长度为
: ４的重复字符串，我的答案是，把每４个串做成HASH，存HASH MAP，然后找重复。然后
: 问复杂度，我说是O（N）。对方说不对，我只好说，如果重复的串在K个位置出现的话
: ，在第K个循环后能找到。ASSUME HASH 算法时间固定和插入、查找时间固定。。。结
: 果好象也不对 。。。。
|
b***u
发帖数: 12010 | 3 A是哪个银行？想了一圈没想到A开头的。。
【在 b***u 的大作中提到】
: pi转了字符串才给你么？无穷长？
|
b***u
发帖数: 12010 | 4 我会弄个bitmap，四位digit有10k，用10k/32+1个unsigned int。每读一个digit把后
四位查下出现没。第几位出现就需要多少时间。
【在 a*****n 的大作中提到】
: 倒在最后一个INTERVIEW。。对方MD，说话特快，好几次都要重复了我才听懂。。。问
: 了一算法题，没做好，跟大家请教一下，就是：把数学PI转成字符串，找第一个长度为
: ４的重复字符串，我的答案是，把每４个串做成HASH，存HASH MAP，然后找重复。然后
: 问复杂度，我说是O（N）。对方说不对，我只好说，如果重复的串在K个位置出现的话
: ，在第K个循环后能找到。ASSUME HASH 算法时间固定和插入、查找时间固定。。。结
: 果好象也不对 。。。。
|
l*****a
发帖数: 14598 | 5 AE
【在 b***u 的大作中提到】
: A是哪个银行？想了一圈没想到A开头的。。
|
b***u
发帖数: 12010 | 6 ae不是银行，是payment tech firm..
【在 l*****a 的大作中提到】
: AE
|
a*****n
发帖数: 158 | 7 A是AMAZON，上个星期ONSITE的。银行就是WALL ST那几个哪。。。
>每读一个digit把后
>四位查下出现没。第几位出现就需要多少时间。
我就是这么回答的啊，他说不对。。。。还特别问多少个循环后，我说K个循环啊。。
。。不知道PI是不是有特别的规律,,感觉不是算法不对，而是复杂度不对，，，所以想请教一下大家。。 |
r********9
发帖数: 1116 | 8
是不是还得检查下重复的四位有没有和被重复的四位重合？
也就是:
a1-a2-a3-a4-a5-a6-a7
你发现a4-a5-a6-a7是重复的，还得保证a4-a5-a6-a7!=ai-a(i+1)-a(i+2)-a(i+3), for
i=1,2,3.
【在 b***u 的大作中提到】
: 我会弄个bitmap，四位digit有10k，用10k/32+1个unsigned int。每读一个digit把后
: 四位查下出现没。第几位出现就需要多少时间。
|
i**********e
发帖数: 1145 | 9 你思路应该没错，唯一能想到的一个优化就是如 biggu 所说的，用 bitmap 来储存当
hash使用，稍微节省空间一些，但复杂度基本不变。有可能是你说 O(n)，但是没解释
什么是 n 呢？这题你也不知道到何时才能找到重复那四个decimal？除非你能数学证明
出来。 |
S*****e
发帖数: 229 | 10 是不是可以可以这样理解：10000个4位字符串中必有两个一样的，所以扫描10000个字
符之后一定有重复，复杂度是O(1)?
【在 a*****n 的大作中提到】
: 倒在最后一个INTERVIEW。。对方MD，说话特快，好几次都要重复了我才听懂。。。问
: 了一算法题，没做好，跟大家请教一下，就是：把数学PI转成字符串，找第一个长度为
: ４的重复字符串，我的答案是，把每４个串做成HASH，存HASH MAP，然后找重复。然后
: 问复杂度，我说是O（N）。对方说不对，我只好说，如果重复的串在K个位置出现的话
: ，在第K个循环后能找到。ASSUME HASH 算法时间固定和插入、查找时间固定。。。结
: 果好象也不对 。。。。
|
|
|
i**********e
发帖数: 1145 | 11 Ahh... you are right! Can't believe I missed it.
There's only maximum of 10000 possibilities for 4 digits.
【在 S*****e 的大作中提到】
: 是不是可以可以这样理解：10000个4位字符串中必有两个一样的，所以扫描10000个字
: 符之后一定有重复，复杂度是O(1)?
|
k***g
发帖数: 166 | 12 弱人路过，木有看懂...
第一个长度为４的重复字符串是不是指：“0123412345” 这里面的1234?
那解法说的“每四个做一个hash”的话，上面就要做10个hash值？ |
b***u
发帖数: 12010 | 13 great point!
【在 S*****e 的大作中提到】
: 是不是可以可以这样理解：10000个4位字符串中必有两个一样的，所以扫描10000个字
: 符之后一定有重复，复杂度是O(1)?
|
b***u
发帖数: 12010 | 14 有个相关的问题是11111算不算两个1111？不算的话上面的算法要处理下边界条件。 |
m*****a
发帖数: 636 | 15 。。。别跟我说是抽屉原理
是不是可以可以这样理解：10000个4位字符串中必有两个一样的，所以扫描10000个字
符之后一定有重复，复杂度是O(1)?
【在 S*****e 的大作中提到】
: 是不是可以可以这样理解：10000个4位字符串中必有两个一样的，所以扫描10000个字
: 符之后一定有重复，复杂度是O(1)?
|
a*****n
发帖数: 158 | 16 面食完后，我也想到他是不是想问这个，可是他应该换一种问法。。SIGH，前面都过了
N论了，就倒在这儿。。。。
【在 S*****e 的大作中提到】
: 是不是可以可以这样理解：10000个4位字符串中必有两个一样的，所以扫描10000个字
: 符之后一定有重复，复杂度是O(1)?
|
a*****n
发帖数: 158 | 17 我解释了，说如果重复的数字出现在Kth位置，检查的次数为K。
【在 i**********e 的大作中提到】
: 你思路应该没错，唯一能想到的一个优化就是如 biggu 所说的，用 bitmap 来储存当
: hash使用，稍微节省空间一些，但复杂度基本不变。有可能是你说 O(n)，但是没解释
: 什么是 n 呢？这题你也不知道到何时才能找到重复那四个decimal？除非你能数学证明
: 出来。
|
h********w
发帖数: 221 | 18 这道题的解法，我会用dictionary tree, 在遍历的时候同时建立tree, 最多有10*9*8*
7个4排列，可以到这个级别然后遍历，哪位大虾指点一下我的解法？ |
h********w
发帖数: 221 | 19 还有就是用Hash了，4个一组，直接map到table, 原table为NULL, 每map一个table
increase one, till some collision happen, and then check the value same or
just the key value same, the time complex is O(n) to build up the table, but
the find time should be O(1) |
t**d
发帖数: 352 | 20 in this case, o(n) is not good enough. since Pi is infinite. |
|
|
z****c
发帖数: 602 | 21 这道题可能还要考察其实不需要每次读一个字符都算前四位。假设上个前四位放在int
n里。新的字符是a。这次就算（n%1000）*10+a-'0'。 |
a*****n
发帖数: 158 | |
y*******o
发帖数: 6632 | 23 hashmap
所有四位数0000 to 9999做hash key，value是出现次数
然后遍历， if（occurrence）
++value
if（value>1)
break;
return key;
【在 a*****n 的大作中提到】
: 倒在最后一个INTERVIEW。。对方MD，说话特快，好几次都要重复了我才听懂。。。问
: 了一算法题，没做好，跟大家请教一下，就是：把数学PI转成字符串，找第一个长度为
: ４的重复字符串，我的答案是，把每４个串做成HASH，存HASH MAP，然后找重复。然后
: 问复杂度，我说是O（N）。对方说不对，我只好说，如果重复的串在K个位置出现的话
: ，在第K个循环后能找到。ASSUME HASH 算法时间固定和插入、查找时间固定。。。结
: 果好象也不对 。。。。
|
y*******o
发帖数: 6632 | 24 这个好
就是搞个9999的数组，初始化都是-1
然后根据数字填数，
while(1){
i=index到index+3
if value[i]!=-1
return i
else
value[i]=index;
++index;
}
but
【在 h********w 的大作中提到】
: 还有就是用Hash了，4个一组，直接map到table, 原table为NULL, 每map一个table
: increase one, till some collision happen, and then check the value same or
: just the key value same, the time complex is O(n) to build up the table, but
: the find time should be O(1)
|
