i*******6 发帖数: 107 | 1 很好玩的,这个面试的人估计自己都没准备好,打电话说你稍等一下,我找一下面试题
的文档,咦到哪儿去了?...然后敲了1分钟鼠标...
题目很简单,doc上写代码:
1.很大的文件里面若干行,每行一个字符串,去重复,保留第一次出现顺序
2.比如aabbbbccccccdde这么个排好序的字符串,输入c,输出c出现的次数6 |
w****x 发帖数: 2483 | 2 第一题我能想到的是如果不考虑内存空间的限制的话做hash table保存遍历过的字符串
. 如果内存空间有限制的话做hard disk上的hash?? 就是把一定范围内的hash code印
射到一个file上, 每个file都可以单独放进内存?? 太慢了, 有什么合适的解答吗 |
w****x 发帖数: 2483 | 3 第二题作两次binary search来确定左右边界?? |
s*********9 发帖数: 241 | 4 我觉得应该是。第一个能讲下吗,我题没看懂?
【在 w****x 的大作中提到】 : 第二题作两次binary search来确定左右边界??
|
i*******e 发帖数: 240 | |
h****n 发帖数: 1093 | |
g*******n 发帖数: 214 | 7 求解答
★ Sent from iPhone App: iReader Mitbbs Lite 7.39 |
f*******t 发帖数: 7549 | 8 第一题可以用radix tree,比普通trie更节省内存 |
|
w****x 发帖数: 2483 | 9 Trie tree 也不一定可以吧, 要是没那么多公共前缀的话 |
b***u 发帖数: 12010 | 10 trie怎么保留第一次顺序?
【在 i*******e 的大作中提到】 : 第一题用trie
|
|
|
z******d 发帖数: 93 | 11 suffix tree 咯
【在 w****x 的大作中提到】 : Trie tree 也不一定可以吧, 要是没那么多公共前缀的话
|
i*******n 发帖数: 401 | 12 第一个问题很简单吧,逐行便利,每一行的hashcode都记下来,hashcode可以放在某个
bit vector里面以便节省内存,然后遇到新一行,check bit vector, hit就删掉,不
hit就记录 |
l**********1 发帖数: 415 | 13 code prefix tree in the first phone interview? and do you guys think it's
even possible to code prefix tree in an interview? |
i**********e 发帖数: 1145 | 14 trie 这类的题目在 GFMA 这类的公司还是会问到的。面试时写个 trie insert 的代码
一点也不过分。反正我面试时就碰到了trie的问题两次。
不过话说回来,这道题我怎么想也想不到为什么会牵扯到 trie?
【在 l**********1 的大作中提到】 : code prefix tree in the first phone interview? and do you guys think it's : even possible to code prefix tree in an interview?
|
b******c 发帖数: 70 | 15 同意
记得面试F时先定义数据结构,然后写插入,然后查找,然后改查找为针对带“.”的
match,接下来要求做优化
【在 i**********e 的大作中提到】 : trie 这类的题目在 GFMA 这类的公司还是会问到的。面试时写个 trie insert 的代码 : 一点也不过分。反正我面试时就碰到了trie的问题两次。 : 不过话说回来,这道题我怎么想也想不到为什么会牵扯到 trie?
|
i*******e 发帖数: 240 | 16
Foreach line in document
Traverse trie following this line
If this line is closing to the end and isKey == true in the trie
then ignore this line because it must have occurred before
else if this line is closing to the end and isKey == false in the trie
then isKey = true and keep this line in the output (this is the
firs time occurrence)
顺序遍历每一行,当读到第i行结尾处,发现trie中的isKey为true (初始值都是false
)则说明之前有过相同的行出现过,就应该ignore他。如果没有出现过,把isKey设置
为true,保留该行。继续读取下一行直至所有
【在 i**********e 的大作中提到】 : trie 这类的题目在 GFMA 这类的公司还是会问到的。面试时写个 trie insert 的代码 : 一点也不过分。反正我面试时就碰到了trie的问题两次。 : 不过话说回来,这道题我怎么想也想不到为什么会牵扯到 trie?
|
b******b 发帖数: 300 | 17 不太懂 ,求解释
【在 w****x 的大作中提到】 : 第二题作两次binary search来确定左右边界??
|
l*****a 发帖数: 14598 | 18 当成两道题
1)找某字符出现的最大index
2)找某字符出现的最小index
都用BINARY SEARCH
【在 b******b 的大作中提到】 : 不太懂 ,求解释
|
q****x 发帖数: 7404 | 19
stream in stream out? not that easy if file size huge.
equal_range. classical, but not easy either.
【在 i*******6 的大作中提到】 : 很好玩的,这个面试的人估计自己都没准备好,打电话说你稍等一下,我找一下面试题 : 的文档,咦到哪儿去了?...然后敲了1分钟鼠标... : 题目很简单,doc上写代码: : 1.很大的文件里面若干行,每行一个字符串,去重复,保留第一次出现顺序 : 2.比如aabbbbccccccdde这么个排好序的字符串,输入c,输出c出现的次数6
|
p*******o 发帖数: 3564 | 20 2. 找和stl algorithm里面同样定义的lower_bound和upper_bound,次数=upper_bound
-lower_bound
【在 i*******6 的大作中提到】 : 很好玩的,这个面试的人估计自己都没准备好,打电话说你稍等一下,我找一下面试题 : 的文档,咦到哪儿去了?...然后敲了1分钟鼠标... : 题目很简单,doc上写代码: : 1.很大的文件里面若干行,每行一个字符串,去重复,保留第一次出现顺序 : 2.比如aabbbbccccccdde这么个排好序的字符串,输入c,输出c出现的次数6
|
|
|
i*******6 发帖数: 107 | 21 第一题我用的blizzard专利算法3-way hash,取string的hashcode作为index再做3次
hash,不知道的可以查询一下,网上有介绍的。另外用了bit-vector,给他算了下1G内
存最多只能支持多少多少个字符串,他说够了。那我就直接写代码。不过中间脑子昏了
算法复杂度搞错了,我说是 nlogn他提醒我说其实是n,我说哦哦不好意思我搞错了,
不晓得会不会扣分。
第二题嘛直接二分查找,int binarysearch(int[]array, int start, int end, int
target)函数返回值代表的意思是:“这段从start-end的字符串里面 包括了多少个
target”,直接加起来就是了。 |
H***e 发帖数: 476 | 22 没明白第二题说的什么意思 ?
难道不用写两个函数?
【在 i*******6 的大作中提到】 : 第一题我用的blizzard专利算法3-way hash,取string的hashcode作为index再做3次 : hash,不知道的可以查询一下,网上有介绍的。另外用了bit-vector,给他算了下1G内 : 存最多只能支持多少多少个字符串,他说够了。那我就直接写代码。不过中间脑子昏了 : 算法复杂度搞错了,我说是 nlogn他提醒我说其实是n,我说哦哦不好意思我搞错了, : 不晓得会不会扣分。 : 第二题嘛直接二分查找,int binarysearch(int[]array, int start, int end, int : target)函数返回值代表的意思是:“这段从start-end的字符串里面 包括了多少个 : target”,直接加起来就是了。
|
i*******6 发帖数: 107 | 23
不用啊,我没说清楚?给个代码好了:
public static int binarySearch(char[] charset, int start, int end, char target){
if (charset == null) return 0;
if (start == end){
if (charset[start] == target) return 1;
else return 0;
}
int mid = start + (end-start)/2;
if (charset[mid]
else if(charset[mid] > target) return binarySearch(charset, start, mid - 1, target);
else{
int left = 0, right = 0;
if (charset[mid-1]==target && (mid-1)>=start)
left = binarySearch(charset,start,mid-1,target);
if (charset[mid+1]==target && (mid+1)<=end)
right = binarySearch(charset, mid+1, end, target);
return left+right+1;
}
}
public static void main(String[] args) {
// TODO code application logic here
String str = "aaabbbbbcccccccddefgggg";
System.out.println(binarySearch(str.toCharArray(),0,str.length()-1,'c'));
}
【在 H***e 的大作中提到】 : 没明白第二题说的什么意思 ? : 难道不用写两个函数?
|
H***e 发帖数: 476 | 24 这个复杂度是O(n)喔
不比做两次binarysearch,一次左边界一次右边界
target){
);
- 1, target);
【在 i*******6 的大作中提到】 : : 不用啊,我没说清楚?给个代码好了: : public static int binarySearch(char[] charset, int start, int end, char target){ : if (charset == null) return 0; : if (start == end){ : if (charset[start] == target) return 1; : else return 0; : } : int mid = start + (end-start)/2; : if (charset[mid]
|
H***e 发帖数: 476 | 25 我觉得第一道题说的也不是很清楚啊
是不是每个字符串特别长?需要用它的hash(比如md5) 做key来存进hashtable来判断
重复?
能不能把constraints说清楚电啊?
【在 i*******6 的大作中提到】 : 第一题我用的blizzard专利算法3-way hash,取string的hashcode作为index再做3次 : hash,不知道的可以查询一下,网上有介绍的。另外用了bit-vector,给他算了下1G内 : 存最多只能支持多少多少个字符串,他说够了。那我就直接写代码。不过中间脑子昏了 : 算法复杂度搞错了,我说是 nlogn他提醒我说其实是n,我说哦哦不好意思我搞错了, : 不晓得会不会扣分。 : 第二题嘛直接二分查找,int binarysearch(int[]array, int start, int end, int : target)函数返回值代表的意思是:“这段从start-end的字符串里面 包括了多少个 : target”,直接加起来就是了。
|
i*******6 发帖数: 107 | 26
似乎没什么constraints,就那个意思。只是我就是这么解的
倒是第二题还真是o(n)average...悲剧
【在 H***e 的大作中提到】 : 我觉得第一道题说的也不是很清楚啊 : 是不是每个字符串特别长?需要用它的hash(比如md5) 做key来存进hashtable来判断 : 重复? : 能不能把constraints说清楚电啊?
|
h********w 发帖数: 221 | 27 第一题没读明白,
第二题我用count sort 不知道行不行, 很容易就知道任何字母的frequency, array
index 0 stands for A, index 26 stands for a. time complex should be O(n), 求
教各位对我解法的评价。
【在 i*******6 的大作中提到】 : 很好玩的,这个面试的人估计自己都没准备好,打电话说你稍等一下,我找一下面试题 : 的文档,咦到哪儿去了?...然后敲了1分钟鼠标... : 题目很简单,doc上写代码: : 1.很大的文件里面若干行,每行一个字符串,去重复,保留第一次出现顺序 : 2.比如aabbbbccccccdde这么个排好序的字符串,输入c,输出c出现的次数6
|