发了一个中国的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或者循环列表?谁给我讲讲?