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
|
