r*****t
发帖数: 68 | 1 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
phone interview
给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
排好序的
onsite
1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
3. 写一个二叉树遍历的iterator
4. design一个middle layer，在客户端跟搜索服务器之间 |
n****t
发帖数: 241 | 2 好难，一个都不会，呵呵
【在 r*****t 的大作中提到】
: 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
: phone interview
: 给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
: 排好序的
: onsite
: 1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
: 2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 3. 写一个二叉树遍历的iterator
: 4. design一个middle layer，在客户端跟搜索服务器之间
|
w*****o
发帖数: 53 | |
c******w
发帖数: 1108 | 4 二次函数先算出对称轴,对左右两边的分别计算好之后merge? |
c*****e
发帖数: 74 | 5 先找到对称轴（或者最小的包含区间）,然后从两个不同的方向扩展，顺序由到对称轴
的距离决定。
【在 c******w 的大作中提到】
: 二次函数先算出对称轴,对左右两边的分别计算好之后merge?
|
j*****u
发帖数: 1133 | 6 看起来挺难的。。
单个文件里没有conflict吧。2 way merge sort?
只想到build一个char->word的inverted index，复杂度可以减到O(n*AVG(#words_
share_no_letter)), worse case还是O(n^2)
有什么更好的方法？
还好这个不难，如果用C#做traversal的时候yield return就行了
middle tier要做什么：requirement是啥？e.g. load balancing? logging?
preprocessing? |
j********x
发帖数: 2330 | |
j********x
发帖数: 2330 | 8 定义一个函数collapse(word) {
return sort(unique(word)); //返回经过排序的独一字符
}
处理每个单词，collapse(word)，同时将返回值插入一个trie，叶子节点记录目前插入
的单词长度的最大值。然后查询吧
对于每个单吃，查询时间是O(24-length(word'))，word'是collapse以后的单词。复杂
度O(n) |
c******w
发帖数: 1108 | 9 二次函数的值先算还是后算没区别.不过你这样要多做几次减法
【在 c*****e 的大作中提到】
: 先找到对称轴（或者最小的包含区间）,然后从两个不同的方向扩展，顺序由到对称轴
: 的距离决定。
|
h***n
发帖数: 276 | 10 do u assume char set is "a" - "z"? why it is 24 instead of 26?
if the char set is unicode, this solution seems incur high cost, right?
aslo, do u know any application of this problem?
【在 j********x 的大作中提到】
: 定义一个函数collapse(word) {
: return sort(unique(word)); //返回经过排序的独一字符
: }
: 处理每个单词，collapse(word)，同时将返回值插入一个trie，叶子节点记录目前插入
: 的单词长度的最大值。然后查询吧
: 对于每个单吃，查询时间是O(24-length(word'))，word'是collapse以后的单词。复杂
: 度O(n)
|
|
|
j********x
发帖数: 2330 | 11 26搞错了，假设'a'-'z'
unicode的不懂
不管怎么说第一步的collapse一定是有用的
of 26?
high cost, right?
【在 h***n 的大作中提到】
: do u assume char set is "a" - "z"? why it is 24 instead of 26?
: if the char set is unicode, this solution seems incur high cost, right?
: aslo, do u know any application of this problem?
|
h***n
发帖数: 276 | 12 it seems I understand your solution correctly
the only concern is that, when the character set is large (say unicode which
has chars more than 109,000), we can no longer take advantage of trie, but
instead, we just have to compare them directly, which lead to O(n^2) solutio
n
【在 j********x 的大作中提到】
: 26搞错了，假设'a'-'z'
: unicode的不懂
: 不管怎么说第一步的collapse一定是有用的
:
: of 26?
: high cost, right?
|
f***g
发帖数: 214 | 13 看了上面的回复，受到启发。
也说一个想法：
Assumption: ASCII
对于每一个单词，利用bitset原理
用一个int就可以表示出其字母出现的模式。
假设用最低位表示z，最高的第7位表示a
预处理
1.建hash，就是一个2^26的数组，每一个单词，预处理，算出相应的int值。
2.在每个数组中的保存符合当前模式的最长的单词。
找最大：
对于每一种模试，也就是每一个数组的index，翻转其index，比如模式是1010 (ac)，
则~1010=0101(bd)，这两个数组元素相乘（也就是长度想乘），保持最大值。然后每次
去掉一个1.(0100)在相乘比较。
这么做虽然数组很大，但对于每一个数组中的元素，需要相乘比较的次数不多，应该不
算慢吧 |
c*****e
发帖数: 74 | 14 No need to compare the function value.
【在 c******w 的大作中提到】
: 二次函数的值先算还是后算没区别.不过你这样要多做几次减法
|
f***g
发帖数: 214 | 15 写了个测试下，用了一个常用字典
结果是：
foresightedness
blackjack
有点意思，就是不知道这个变态的题目有什么实际意义 |
l*****a
发帖数: 14598 | 16 my solution:
1.create hash for each word
2.sort the dictionary by word length.
assume the dictionary become
a[0],a[1]......
find the largest k so that hash(a[0])&hash(a[k])==0,
get max=len(a[0])*len(a[k])
find max i in [2,k-1] so that hash(a[1])&hash(a[i])==0,
compare max and len(a[1])*len(a[i])
next step find max j in [3,i-1]....
【在 f***g 的大作中提到】
: 看了上面的回复，受到启发。
: 也说一个想法：
: Assumption: ASCII
: 对于每一个单词，利用bitset原理
: 用一个int就可以表示出其字母出现的模式。
: 假设用最低位表示z，最高的第7位表示a
: 预处理
: 1.建hash，就是一个2^26的数组，每一个单词，预处理，算出相应的int值。
: 2.在每个数组中的保存符合当前模式的最长的单词。
: 找最大：
|
i********s
发帖数: 133 | |
y******2
发帖数: 46 | |
g*********s
发帖数: 1782 | 19
What's this? Given class bst, design a class iterator to do the following?
for (bst::in_order_iterator it = bst.root(); it != bst.end(); ++ it) {
it->print();
}
【在 r*****t 的大作中提到】
: 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
: phone interview
: 给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
: 排好序的
: onsite
: 1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
: 2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 3. 写一个二叉树遍历的iterator
: 4. design一个middle layer，在客户端跟搜索服务器之间
|
g*********s
发帖数: 1782 | 20
If m words, length of words are L_1, L_2,..., L_m. O(m^2+sum(L_i))?
Is O(mlg(m)) possible?
【在 r*****t 的大作中提到】
: 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
: phone interview
: 给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
: 排好序的
: onsite
: 1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
: 2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 3. 写一个二叉树遍历的iterator
: 4. design一个middle layer，在客户端跟搜索服务器之间
|
|
|
r*****t
发帖数: 68 | 21 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
phone interview
给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
排好序的
onsite
1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
3. 写一个二叉树遍历的iterator
4. design一个middle layer，在客户端跟搜索服务器之间 |
n****t
发帖数: 241 | 22 好难，一个都不会，呵呵
【在 r*****t 的大作中提到】
: 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
: phone interview
: 给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
: 排好序的
: onsite
: 1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
: 2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 3. 写一个二叉树遍历的iterator
: 4. design一个middle layer，在客户端跟搜索服务器之间
|
w*****o
发帖数: 53 | |
c******w
发帖数: 1108 | 24 二次函数先算出对称轴,对左右两边的分别计算好之后merge? |
c*****e
发帖数: 74 | 25 先找到对称轴（或者最小的包含区间）,然后从两个不同的方向扩展，顺序由到对称轴
的距离决定。
【在 c******w 的大作中提到】
: 二次函数先算出对称轴,对左右两边的分别计算好之后merge?
|
j*****u
发帖数: 1133 | 26 看起来挺难的。。
单个文件里没有conflict吧。2 way merge sort?
只想到build一个char->word的inverted index，复杂度可以减到O(n*AVG(#words_
share_no_letter)), worse case还是O(n^2)
有什么更好的方法？
还好这个不难，如果用C#做traversal的时候yield return就行了
middle tier要做什么：requirement是啥？e.g. load balancing? logging?
preprocessing? |
j********x
发帖数: 2330 | |
j********x
发帖数: 2330 | 28 定义一个函数collapse(word) {
return sort(unique(word)); //返回经过排序的独一字符
}
处理每个单词，collapse(word)，同时将返回值插入一个trie，叶子节点记录目前插入
的单词长度的最大值。然后查询吧
对于每个单吃，查询时间是O(24-length(word'))，word'是collapse以后的单词。复杂
度O(n) |
c******w
发帖数: 1108 | 29 二次函数的值先算还是后算没区别.不过你这样要多做几次减法
【在 c*****e 的大作中提到】
: 先找到对称轴（或者最小的包含区间）,然后从两个不同的方向扩展，顺序由到对称轴
: 的距离决定。
|
h***n
发帖数: 276 | 30 do u assume char set is "a" - "z"? why it is 24 instead of 26?
if the char set is unicode, this solution seems incur high cost, right?
aslo, do u know any application of this problem?
【在 j********x 的大作中提到】
: 定义一个函数collapse(word) {
: return sort(unique(word)); //返回经过排序的独一字符
: }
: 处理每个单词，collapse(word)，同时将返回值插入一个trie，叶子节点记录目前插入
: 的单词长度的最大值。然后查询吧
: 对于每个单吃，查询时间是O(24-length(word'))，word'是collapse以后的单词。复杂
: 度O(n)
|
|
|
j********x
发帖数: 2330 | 31 26搞错了，假设'a'-'z'
unicode的不懂
不管怎么说第一步的collapse一定是有用的
of 26?
high cost, right?
【在 h***n 的大作中提到】
: do u assume char set is "a" - "z"? why it is 24 instead of 26?
: if the char set is unicode, this solution seems incur high cost, right?
: aslo, do u know any application of this problem?
|
h***n
发帖数: 276 | 32 it seems I understand your solution correctly
the only concern is that, when the character set is large (say unicode which
has chars more than 109,000), we can no longer take advantage of trie, but
instead, we just have to compare them directly, which lead to O(n^2) solutio
n
【在 j********x 的大作中提到】
: 26搞错了，假设'a'-'z'
: unicode的不懂
: 不管怎么说第一步的collapse一定是有用的
:
: of 26?
: high cost, right?
|
f***g
发帖数: 214 | 33 看了上面的回复，受到启发。
也说一个想法：
Assumption: ASCII
对于每一个单词，利用bitset原理
用一个int就可以表示出其字母出现的模式。
假设用最低位表示z，最高的第7位表示a
预处理
1.建hash，就是一个2^26的数组，每一个单词，预处理，算出相应的int值。
2.在每个数组中的保存符合当前模式的最长的单词。
找最大：
对于每一种模试，也就是每一个数组的index，翻转其index，比如模式是1010 (ac)，
则~1010=0101(bd)，这两个数组元素相乘（也就是长度想乘），保持最大值。然后每次
去掉一个1.(0100)在相乘比较。
这么做虽然数组很大，但对于每一个数组中的元素，需要相乘比较的次数不多，应该不
算慢吧 |
c*****e
发帖数: 74 | 34 No need to compare the function value.
【在 c******w 的大作中提到】
: 二次函数的值先算还是后算没区别.不过你这样要多做几次减法
|
f***g
发帖数: 214 | 35 写了个测试下，用了一个常用字典
结果是：
foresightedness
blackjack
有点意思，就是不知道这个变态的题目有什么实际意义 |
l*****a
发帖数: 14598 | 36 my solution:
1.create hash for each word
2.sort the dictionary by word length.
assume the dictionary become
a[0],a[1]......
find the largest k so that hash(a[0])&hash(a[k])==0,
get max=len(a[0])*len(a[k])
find max i in [2,k-1] so that hash(a[1])&hash(a[i])==0,
compare max and len(a[1])*len(a[i])
next step find max j in [3,i-1]....
【在 f***g 的大作中提到】
: 看了上面的回复，受到启发。
: 也说一个想法：
: Assumption: ASCII
: 对于每一个单词，利用bitset原理
: 用一个int就可以表示出其字母出现的模式。
: 假设用最低位表示z，最高的第7位表示a
: 预处理
: 1.建hash，就是一个2^26的数组，每一个单词，预处理，算出相应的int值。
: 2.在每个数组中的保存符合当前模式的最长的单词。
: 找最大：
|
i********s
发帖数: 133 | |
y******2
发帖数: 46 | |
g*********s
发帖数: 1782 | 39
What's this? Given class bst, design a class iterator to do the following?
for (bst::in_order_iterator it = bst.root(); it != bst.end(); ++ it) {
it->print();
}
【在 r*****t 的大作中提到】
: 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
: phone interview
: 给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
: 排好序的
: onsite
: 1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
: 2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 3. 写一个二叉树遍历的iterator
: 4. design一个middle layer，在客户端跟搜索服务器之间
|
g*********s
发帖数: 1782 | 40
If m words, length of words are L_1, L_2,..., L_m. O(m^2+sum(L_i))?
Is O(mlg(m)) possible?
【在 r*****t 的大作中提到】
: 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
: phone interview
: 给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
: 排好序的
: onsite
: 1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
: 2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 3. 写一个二叉树遍历的iterator
: 4. design一个middle layer，在客户端跟搜索服务器之间
|
|
|
m**q
发帖数: 189 | 41 创建trie没问题，查询怎么查啊，比如 查找和单词hello 没有
共同字母的单词，貌似trie无法有效支持这种类型的查询啊，
感觉只能遍历。
【在 j********x 的大作中提到】
: 定义一个函数collapse(word) {
: return sort(unique(word)); //返回经过排序的独一字符
: }
: 处理每个单词，collapse(word)，同时将返回值插入一个trie，叶子节点记录目前插入
: 的单词长度的最大值。然后查询吧
: 对于每个单吃，查询时间是O(24-length(word'))，word'是collapse以后的单词。复杂
: 度O(n)
|
r*******g
发帖数: 1335 | |
g**********y
发帖数: 14569 | 43 radiochromatogram * suspensefulnesses = 289
public class WordProduct {
private final static String DIR = "src/test/resources/com/practice/
search";
public void search() {
int N = 30;
String content = FileHelper.readFile(DIR + "/WORD.LST");
String[] words = content.split("\n");
HashSet[] set = new HashSet[30];
HashMap map = new HashMap();
for (int i=0; i
set[i] = new HashSet();
}
for (String word : words) {
set[word.length()].add(word);
map.put(word, score(word));
}
ArrayList pairs = new ArrayList();
for (int i=1; i<30; i++) {
for (int j=i; j<30; j++) {
pairs.add(new Pair(j, i));
}
}
Collections.sort(pairs, new Comparator(){
public int compare(Pair a, Pair b) {
return b.x * b.y - a.x * a.y;
}
});
for (Pair p : pairs) {
for (String w1 : set[p.x]) {
for (String w2 : set[p.y]) {
if ((map.get(w1) & map.get(w2)) == 0) {
System.out.println(w1 + " * " + w2 + " = " + p.x*p.y
);
return;
}
}
}
}
}
private int score(String word) {
int score = 0;
for (int i=0; i
score |= 1 << word.charAt(i) - 'a';
}
return score;
}
private class Pair {
int x, y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) {
new WordProduct().search();
}
} |
g**********y
发帖数: 14569 | 44 想法：
1. 把每个单词的score算出来，放在hashmap里。score的定义是：26位，某个字母出现
则该位为1. 判断两个单词是否有共同字母 = score(w1) & score(w2) > 0
2. 把单词长度对按乘积从高到低排序，然后按这个顺序搜单词库，找到的第一组满组
的单词对就是解。
Code在楼上 |
c*****m
发帖数: 315 | 45 2词函数那个可以先算拐点（拐点之间的区间都是单调的），然后几次MERGE SORT 就好
了。 |
a********1
发帖数: 750 | 46 没人讨论一下4 怎么做？
很没头绪，我估计会先问问 search server本身提供哪些功能，
replicate和index update再哪里做啊？
middle layer大概会做load balance 和cache ?
哪位大拿谈谈这一题
【在 r*****t 的大作中提到】
: 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
: phone interview
: 给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
: 排好序的
: onsite
: 1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
: 2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 3. 写一个二叉树遍历的iterator
: 4. design一个middle layer，在客户端跟搜索服务器之间
|
r*****n
发帖数: 20 | 47 不考虑unicode 我觉得trie还是比较可行的做法：
1、用字典所有words来build up a trie, root是NULL 第一层结点是a,b,c,d,e,....
2、对于第二层结点开始的subtrees, 找各自的maxheight
3、选出两个height最大的substree 就是答案
1. O(n), where n is the number of words in the dictionary
2. O(|E|*m), where m is the (average) total number of nodes in each substree
and |E| is the size of the alphabetic set.
3. O(1) |
g**********y
发帖数: 14569 | 48 computer, haul
没有一层字母一样，但是有共同字母u
substree
【在 r*****n 的大作中提到】
: 不考虑unicode 我觉得trie还是比较可行的做法：
: 1、用字典所有words来build up a trie, root是NULL 第一层结点是a,b,c,d,e,....
: 2、对于第二层结点开始的subtrees, 找各自的maxheight
: 3、选出两个height最大的substree 就是答案
: 1. O(n), where n is the number of words in the dictionary
: 2. O(|E|*m), where m is the (average) total number of nodes in each substree
: and |E| is the size of the alphabetic set.
: 3. O(1)
|
r*****n
发帖数: 20 | 49 恩 make sense
题意理解有误
这个题有比O(n^2)好的算法么？
写了一下O(n^2) 测了一下349901词的一个dichttp://www.math.sjsu.edu/~foster/dictionary.txt 要跑5-6分钟
return:
stekelenburg,hohohohohoho
代码如下
int myfunc(string a, string b){
return a.size()>b.size();
}
void foo(vector arr){
if(!arr.size())
return;
//step 1. sort w.r.t. lentgh of each word O(nlogn)
sort(arr.begin(), arr.end(), myfunc);
//step 2. compute signature for each word
vector sig;
for(long i=0; i
int tmp = 0;
for(long j=0; j
if( ((tmp>>(arr[i][j]-'a'))&0x01) == 0 )
tmp |= (1<<(arr[i][j]-'a'));
}
sig.push_back(tmp);
}
//step 2. compare each other O(n^2)
int mymax = 0;
string maxstr1, maxstr2;
for(long i=0; i
for(long j=i+1; j
if( (sig[i]&sig[j]) == 0 ){
int tmp = int(arr[i].size()*arr[j].size());
if(mymax
maxstr1 = arr[i];
maxstr2 = arr[j];
mymax = tmp;
}
}
}
}
//step 3. get the two words
cout<
}
int main(){
vector arr;
//http://www.math.sjsu.edu/~foster/dictionary.txt
ifstream fin;
fin.open("dictionary.txt", ifstream::in);
while(fin.good()){
string sztmp;
getline(fin, sztmp);
arr.push_back(sztmp);
}
cout<
fin.close();
foo(arr);
return 1;
}
【在 g**********y 的大作中提到】
: computer, haul
: 没有一层字母一样，但是有共同字母u
:
: substree
|
g**********y
发帖数: 14569 | 50 不需要O(n^2), 可以用加速的办法，用你的字典，也可以1秒钟内出答案。
1. 我给的code里就用了：从大算到小，可以避免算很多无用的。
2. 对长度L的单词，每个score只留一个，可以减少很多计算。
3. 算等长的两个词时，循环上可以优化。
【在 r*****n 的大作中提到】
: 恩 make sense
: 题意理解有误
: 这个题有比O(n^2)好的算法么？
: 写了一下O(n^2) 测了一下349901词的一个dichttp://www.math.sjsu.edu/~foster/dictionary.txt 要跑5-6分钟
: return:
: stekelenburg,hohohohohoho
: 代码如下
: int myfunc(string a, string b){
: return a.size()>b.size();
: }
|
