w********g
发帖数: 106 | 1 店面之前首先了online test，所以店面只问了简历上的内容，问得很详细，包括具体
实现某一功能时用了哪些系统调用、函数名是什么、参数怎么设置、某些用到的系统文
件的具体路径，总之就是要确定我真的做过这些project。
店面前要求的online test有三道题，共90分钟，和leetcode类似要求编译运行，但是
不提供test case，只能自己输入，所以真的考验自己是否细心，比如overflow、空输
入之类的。
第一题不难：
给一个整形数组存储的是下一跳的位置，就像指针一样。
比如A[0]=2 A[1]=3 A[2]=1 A[3]=1 A[4]=3
就这么跳：0 2 1 3 1 3...，于是找到了一个长度为2的由1、3这两个元素组成loop。
题目就是输入这样的数组，返回loop长度。
要求O(N) time，O(1) space，其中N是数组长度。
第二题极简单：
给一个表示16进制数的字符串，返回这个数的二进制表示中有几个1.
例如，输入16进制字符串“1E”，它的二进制为“11110”，所以返回4。
要求O(N) time，O(1) space，其中N是字符串长度。
第三题我不会：
找字符串的最长的公共前缀和后缀（不考虑字符串是其本身的前后缀）。
例如abcabca有前缀abca，后缀也是abca，并且是最长的，所以返回abca。
要求O(N) time，O(N) space，其中N是字符串长度。
我想了两种方法都不对：
（1）最naive的方法是每次都比较相等长度的前后缀，那么时间复杂度就是O(N^2)，
因为要扫N遍字符串，每一遍里面还要比较前后缀。
（2）如果用hashtable把所有前缀存起来，再看每一个后缀是不是在hashtable里，
那空间就是O(N^2)，因为hashtable的key是所有的前缀。
或者是用DP或者hash或者循环列表？谁给我讲讲？ |
i******y
发帖数: 191 | 2 第三题可以这样不？
一头一尾两个指针固定不动，另外一头一尾两个指针分别往中间靠近，每次就能截取到
string的前缀和后缀，然后把截取到的sub string放到一个hash_map里面比较有没有重
复，每次更新满足条件string的size，这样一直遍历完一趟，最后得到的就是要找的最
大重复前后缀。
比如：
abcabca
第一趟截取前面的a和后面的a，放进hashmap，value记录为1满足条件然后记录下来
第二趟比较ab和ca，不满足，break
这样第四趟比较abca和abca，满足条件，value记录为4
最后搞完一趟就输出value为4的最大值对应的key
初学者，请轻点拍！~~~ |
b****g
发帖数: 192 | 3 用hashtable存前后缀？那就是O(n^2)space
逐次比较前后缀？那就是O(n^2)time
【在 i******y 的大作中提到】
: 第三题可以这样不？
: 一头一尾两个指针固定不动，另外一头一尾两个指针分别往中间靠近，每次就能截取到
: string的前缀和后缀，然后把截取到的sub string放到一个hash_map里面比较有没有重
: 复，每次更新满足条件string的size，这样一直遍历完一趟，最后得到的就是要找的最
: 大重复前后缀。
: 比如：
: abcabca
: 第一趟截取前面的a和后面的a，放进hashmap，value记录为1满足条件然后记录下来
: 第二趟比较ab和ca，不满足，break
: 这样第四趟比较abca和abca，满足条件，value记录为4
|
g****o
发帖数: 547 | 4 第三题可以用z algorithm
the Z Algorithm produces an array Z where Z[i] is the length of the longest
substring starting from S[i] which is also a prefix of S
在计算Z[i]的过程中，加一步验证Z[i]是不是等于n-i，
Z[i]等于n-i,意味着它也是Suffix
时间o(n)
z algorithm可以看这里：
http://codeforces.com/blog/entry/3107
【在 w********g 的大作中提到】
: 店面之前首先了online test，所以店面只问了简历上的内容，问得很详细，包括具体
: 实现某一功能时用了哪些系统调用、函数名是什么、参数怎么设置、某些用到的系统文
: 件的具体路径，总之就是要确定我真的做过这些project。
: 店面前要求的online test有三道题，共90分钟，和leetcode类似要求编译运行，但是
: 不提供test case，只能自己输入，所以真的考验自己是否细心，比如overflow、空输
: 入之类的。
: 第一题不难：
: 给一个整形数组存储的是下一跳的位置，就像指针一样。
: 比如A[0]=2 A[1]=3 A[2]=1 A[3]=1 A[4]=3
: 就这么跳：0 2 1 3 1 3...，于是找到了一个长度为2的由1、3这两个元素组成loop。
|
z*******o
发帖数: 4773 | |
r*********n
发帖数: 4553 | 6 能展开来说说吗？
【在 z*******o 的大作中提到】
: 第三题, 就是KMP算法的一个变形.
|
s**********r
发帖数: 8153 | |
x*****0
发帖数: 452 | |
s***g
发帖数: 1250 | 9 大牛们，第一题啥思路啊？
【在 w********g 的大作中提到】
: 店面之前首先了online test，所以店面只问了简历上的内容，问得很详细，包括具体
: 实现某一功能时用了哪些系统调用、函数名是什么、参数怎么设置、某些用到的系统文
: 件的具体路径，总之就是要确定我真的做过这些project。
: 店面前要求的online test有三道题，共90分钟，和leetcode类似要求编译运行，但是
: 不提供test case，只能自己输入，所以真的考验自己是否细心，比如overflow、空输
: 入之类的。
: 第一题不难：
: 给一个整形数组存储的是下一跳的位置，就像指针一样。
: 比如A[0]=2 A[1]=3 A[2]=1 A[3]=1 A[4]=3
: 就这么跳：0 2 1 3 1 3...，于是找到了一个长度为2的由1、3这两个元素组成loop。
|
w****y
发帖数: 9 | 10 你是对的。
给定一个string, 用pat = string[:-1] (除去最后一个char) 作为pattern, 在str =
string[1:] (除去第一个char) 中，用kmp搜索。搜索结束后得到的state值即为pat的
prefix（也即string的prefix）长度，同时也是str的suffix.
string = abcabca
str = bcabca
pat = abcabc
搜索结束时,虽然pattern没有找到(除非pat==str)，结束时state的值即为所求长度。
bcabca
abcabc
【在 z*******o 的大作中提到】
: 第三题, 就是KMP算法的一个变形.
|
a****r
发帖数: 330 | |
