发了一个中国的petition, 大家快来签名！看看中国和印度，哪个# EB23 - 劳工卡
w*g
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或者循环列表？谁给我讲讲？
实现某一功能时用了哪些系统调用、函数名是什么、参数怎么设置、某些用到的系统文
件的具体路径，总之就是要确定我真的做过这些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或者循环列表？谁给我讲讲？
