Z**********4
发帖数: 528 | 1 已挂，发了攒人品。
有一个array ["this", "is", "a", "is", "fox", "happy"]
需要返回两个单词的最近距离（用index计算）。
int dist(string word1, string word2)
比如dist("fox", "happy") = 1
dist("is", "fox") = 1 注意“is”是有重复的。
每个单词都是有可能重复的。 |
l*****a
发帖数: 14598 | 2 就一道题？你怎么做的
【在 Z**********4 的大作中提到】
: 已挂，发了攒人品。
: 有一个array ["this", "is", "a", "is", "fox", "happy"]
: 需要返回两个单词的最近距离（用index计算）。
: int dist(string word1, string word2)
: 比如dist("fox", "happy") = 1
: dist("is", "fox") = 1 注意“is”是有重复的。
: 每个单词都是有可能重复的。
|
p*******e
发帖数: 933 | 3 如果面试前在这个版做过功课,这个题太高频了啊
怎么就挂了呢
【在 Z**********4 的大作中提到】
: 已挂，发了攒人品。
: 有一个array ["this", "is", "a", "is", "fox", "happy"]
: 需要返回两个单词的最近距离（用index计算）。
: int dist(string word1, string word2)
: 比如dist("fox", "happy") = 1
: dist("is", "fox") = 1 注意“is”是有重复的。
: 每个单词都是有可能重复的。
|
X*4
发帖数: 101 | 4 求最优解
【在 p*******e 的大作中提到】
: 如果面试前在这个版做过功课,这个题太高频了啊
: 怎么就挂了呢
|
a***n
发帖数: 623 | 5 这题还有扩展，如果你连扩展都没做到，那确实要好好做功课。
扩展是，求一个最小区间，囊括了一个set of words。
这个问题在实际中也有很直接的应用：
比如用户丢了一个query里面有N个term，搜索引擎返回了一堆snippets，如果展现最简
洁的snippets且包括了所有term？
倒排索引应该能想到。
扩展问题解法就是贪心，不需要DP。 |
c*******r
发帖数: 610 | 6 auyin 说得是对的，其实就是inverted index的简单版本吧。
基本思想应该是：对每一个词，记录它的index （从小到大）。然后对于s1, s2，计算
索引
之间的最小值，就是两个词之间的最小距离了。
glassdoor上面原题 |
l*****a
发帖数: 14598 | 7 有必要记录那么多吗？
indexa=-1
indexb=-1
然后找到一个就更新相应index,算Math.min(indexa-indexb)不就可以了?
【在 c*******r 的大作中提到】
: auyin 说得是对的，其实就是inverted index的简单版本吧。
: 基本思想应该是：对每一个词，记录它的index （从小到大）。然后对于s1, s2，计算
: 索引
: 之间的最小值，就是两个词之间的最小距离了。
: glassdoor上面原题
|
g***j
发帖数: 1275 | 8 没明白，展开说说？
【在 l*****a 的大作中提到】
: 有必要记录那么多吗？
: indexa=-1
: indexb=-1
: 然后找到一个就更新相应index,算Math.min(indexa-indexb)不就可以了?
|
c*******r
发帖数: 610 | 9 你这个方法更好，不需要存储位置信息。
【在 l*****a 的大作中提到】
: 有必要记录那么多吗？
: indexa=-1
: indexb=-1
: 然后找到一个就更新相应index,算Math.min(indexa-indexb)不就可以了?
|
c*******r
发帖数: 610 | 10 伪代码：
//assume both words appear at least once in the input
int index1 = -1;
int index2 = -1;
int min_dist = INT_MIN;
for i = 0 to words.size()
if words[i]= word1
index1 = i;
if words[i] = word2
index2 = i;
if (index1 != -1 && index2 !=-1)
min_dist = min(min_dist, abs(index1 -index2);
return min_dist;
lolhaha大牛是这个意思么？
【在 g***j 的大作中提到】
: 没明白，展开说说？
|
|
|
l*****a
发帖数: 14598 | 11 俺是菜鸟 ：）
就这个意思，不知道是不是最优解
【在 c*******r 的大作中提到】
: 伪代码：
: //assume both words appear at least once in the input
: int index1 = -1;
: int index2 = -1;
: int min_dist = INT_MIN;
: for i = 0 to words.size()
: if words[i]= word1
: index1 = i;
: if words[i] = word2
: index2 = i;
|
Z**********4
发帖数: 528 | 12 就是用hash先存所有word可能出现的index序列
然后word1和word2的序列，希望找出其中具有最小绝对值的一对。
这一面试官要求O(n)的算法吧。。没想出来。
【在 l*****a 的大作中提到】
: 就一道题？你怎么做的
|
m******3
发帖数: 346 | 13 应该不用这么麻烦吧，两个变量，记录word1 和 word 2最近出现的位置，然后每次计
算当前的距离，如果这个距离小于当前已知的最小距离，就更新最小距离，O(n)扫一遍
就行
【在 Z**********4 的大作中提到】
: 就是用hash先存所有word可能出现的index序列
: 然后word1和word2的序列，希望找出其中具有最小绝对值的一对。
: 这一面试官要求O(n)的算法吧。。没想出来。
|
s********x
发帖数: 81 | 14 如果这个函数调用一次，我觉得一次扫描，不用hash最好。
如果调用多次，我觉得用构造hash更好。 |
i**********e
发帖数: 1145 | 15 当 word1 = word2 怎么办？
【在 c*******r 的大作中提到】
: 伪代码：
: //assume both words appear at least once in the input
: int index1 = -1;
: int index2 = -1;
: int min_dist = INT_MIN;
: for i = 0 to words.size()
: if words[i]= word1
: index1 = i;
: if words[i] = word2
: index2 = i;
|
g***j
发帖数: 1275 | 16 直接返回0？
【在 i**********e 的大作中提到】
: 当 word1 = word2 怎么办？
|
l*********8
发帖数: 4642 | 17 your code always returns INT_MIN
【在 c*******r 的大作中提到】
: 伪代码：
: //assume both words appear at least once in the input
: int index1 = -1;
: int index2 = -1;
: int min_dist = INT_MIN;
: for i = 0 to words.size()
: if words[i]= word1
: index1 = i;
: if words[i] = word2
: index2 = i;
|
l*********8
发帖数: 4642 | 18 word不在数组中呢？
【在 g***j 的大作中提到】
: 直接返回0？
|
h*******e
发帖数: 1377 | 19 这个set of words 满足什么条件阿。
【在 a***n 的大作中提到】
: 这题还有扩展，如果你连扩展都没做到，那确实要好好做功课。
: 扩展是，求一个最小区间，囊括了一个set of words。
: 这个问题在实际中也有很直接的应用：
: 比如用户丢了一个query里面有N个term，搜索引擎返回了一堆snippets，如果展现最简
: 洁的snippets且包括了所有term？
: 倒排索引应该能想到。
: 扩展问题解法就是贪心，不需要DP。
|
g***j
发帖数: 1275 | 20 为啥？
【在 l*********8 的大作中提到】
: your code always returns INT_MIN
|
|
|
m*****k
发帖数: 731 | |
o***g
发帖数: 2784 | 22 因为初始化min_dist = INT_MIN，应该初始化成最大整数
【在 g***j 的大作中提到】
: 为啥？
|
W*********y
发帖数: 481 | 23 typo了吧，应该是INT_MAX
【在 g***j 的大作中提到】
: 为啥？
|
h*********o
发帖数: 230 | 24 初始化 应该是 max
【在 g***j 的大作中提到】
: 为啥？
|
r*******k
发帖数: 1423 | 25 算出来，存到矩阵里
【在 c*******r 的大作中提到】
: 你这个方法更好，不需要存储位置信息。
|
m*********n
发帖数: 931 | |
y***n
发帖数: 1594 | |
T*****u
发帖数: 7103 | |
T*****u
发帖数: 7103 | 29 python初学者贴个python的
def dist(word1, word2):
wordlist = ['this','this','is']
l1,l2 = -1,-1
dist = len(wordlist)
for p in range(len(wordlist)):
if word1==wordlist[p]:
l1 = p
if word1==word2:
l1,l2 = l2,l1
elif word2 == wordlist[p]:
l2 = p
if l1*l2>-1:
if dist>abs(l2-l1):
dist = abs(l2-l1)
if dist==len(wordlist): return None
else: return dist |
Z**********4
发帖数: 528 | 30 已挂，发了攒人品。
有一个array ["this", "is", "a", "is", "fox", "happy"]
需要返回两个单词的最近距离（用index计算）。
int dist(string word1, string word2)
比如dist("fox", "happy") = 1
dist("is", "fox") = 1 注意“is”是有重复的。
每个单词都是有可能重复的。 |
|
|
l*****a
发帖数: 14598 | 31 就一道题？你怎么做的
【在 Z**********4 的大作中提到】
: 已挂，发了攒人品。
: 有一个array ["this", "is", "a", "is", "fox", "happy"]
: 需要返回两个单词的最近距离（用index计算）。
: int dist(string word1, string word2)
: 比如dist("fox", "happy") = 1
: dist("is", "fox") = 1 注意“is”是有重复的。
: 每个单词都是有可能重复的。
|
p*******e
发帖数: 933 | 32 如果面试前在这个版做过功课,这个题太高频了啊
怎么就挂了呢
【在 Z**********4 的大作中提到】
: 已挂，发了攒人品。
: 有一个array ["this", "is", "a", "is", "fox", "happy"]
: 需要返回两个单词的最近距离（用index计算）。
: int dist(string word1, string word2)
: 比如dist("fox", "happy") = 1
: dist("is", "fox") = 1 注意“is”是有重复的。
: 每个单词都是有可能重复的。
|
X*4
发帖数: 101 | 33 求最优解
【在 p*******e 的大作中提到】
: 如果面试前在这个版做过功课,这个题太高频了啊
: 怎么就挂了呢
|
a***n
发帖数: 623 | 34 这题还有扩展，如果你连扩展都没做到，那确实要好好做功课。
扩展是，求一个最小区间，囊括了一个set of words。
这个问题在实际中也有很直接的应用：
比如用户丢了一个query里面有N个term，搜索引擎返回了一堆snippets，如果展现最简
洁的snippets且包括了所有term？
倒排索引应该能想到。
扩展问题解法就是贪心，不需要DP。 |
c*******r
发帖数: 610 | 35 auyin 说得是对的，其实就是inverted index的简单版本吧。
基本思想应该是：对每一个词，记录它的index （从小到大）。然后对于s1, s2，计算
索引
之间的最小值，就是两个词之间的最小距离了。
glassdoor上面原题 |
l*****a
发帖数: 14598 | 36 有必要记录那么多吗？
indexa=-1
indexb=-1
然后找到一个就更新相应index,算Math.min(indexa-indexb)不就可以了?
【在 c*******r 的大作中提到】
: auyin 说得是对的，其实就是inverted index的简单版本吧。
: 基本思想应该是：对每一个词，记录它的index （从小到大）。然后对于s1, s2，计算
: 索引
: 之间的最小值，就是两个词之间的最小距离了。
: glassdoor上面原题
|
g***j
发帖数: 1275 | 37 没明白，展开说说？
【在 l*****a 的大作中提到】
: 有必要记录那么多吗？
: indexa=-1
: indexb=-1
: 然后找到一个就更新相应index,算Math.min(indexa-indexb)不就可以了?
|
c*******r
发帖数: 610 | 38 你这个方法更好，不需要存储位置信息。
【在 l*****a 的大作中提到】
: 有必要记录那么多吗？
: indexa=-1
: indexb=-1
: 然后找到一个就更新相应index,算Math.min(indexa-indexb)不就可以了?
|
c*******r
发帖数: 610 | 39 伪代码：
//assume both words appear at least once in the input
int index1 = -1;
int index2 = -1;
int min_dist = INT_MAX;
for i = 0 to words.size()
if words[i]= word1
index1 = i;
if words[i] = word2
index2 = i;
if (index1 != -1 && index2 !=-1)
min_dist = min(min_dist, abs(index1 -index2);
return min_dist;
lolhaha大牛是这个意思么？
【在 g***j 的大作中提到】
: 没明白，展开说说？
|
l*****a
发帖数: 14598 | 40 俺是菜鸟 ：）
就这个意思，不知道是不是最优解
【在 c*******r 的大作中提到】
: 伪代码：
: //assume both words appear at least once in the input
: int index1 = -1;
: int index2 = -1;
: int min_dist = INT_MAX;
: for i = 0 to words.size()
: if words[i]= word1
: index1 = i;
: if words[i] = word2
: index2 = i;
|
|
|
Z**********4
发帖数: 528 | 41 就是用hash先存所有word可能出现的index序列
然后word1和word2的序列，希望找出其中具有最小绝对值的一对。
这一面试官要求O(n)的算法吧。。没想出来。
【在 l*****a 的大作中提到】
: 就一道题？你怎么做的
|
m******3
发帖数: 346 | 42 应该不用这么麻烦吧，两个变量，记录word1 和 word 2最近出现的位置，然后每次计
算当前的距离，如果这个距离小于当前已知的最小距离，就更新最小距离，O(n)扫一遍
就行
【在 Z**********4 的大作中提到】
: 就是用hash先存所有word可能出现的index序列
: 然后word1和word2的序列，希望找出其中具有最小绝对值的一对。
: 这一面试官要求O(n)的算法吧。。没想出来。
|
s********x
发帖数: 81 | 43 如果这个函数调用一次，我觉得一次扫描，不用hash最好。
如果调用多次，我觉得用构造hash更好。 |
i**********e
发帖数: 1145 | 44 当 word1 = word2 怎么办？
【在 c*******r 的大作中提到】
: 伪代码：
: //assume both words appear at least once in the input
: int index1 = -1;
: int index2 = -1;
: int min_dist = INT_MAX;
: for i = 0 to words.size()
: if words[i]= word1
: index1 = i;
: if words[i] = word2
: index2 = i;
|
g***j
发帖数: 1275 | 45 直接返回0？
【在 i**********e 的大作中提到】
: 当 word1 = word2 怎么办？
|
l*********8
发帖数: 4642 | 46 your code always returns INT_MIN
【在 c*******r 的大作中提到】
: 伪代码：
: //assume both words appear at least once in the input
: int index1 = -1;
: int index2 = -1;
: int min_dist = INT_MAX;
: for i = 0 to words.size()
: if words[i]= word1
: index1 = i;
: if words[i] = word2
: index2 = i;
|
l*********8
发帖数: 4642 | 47 word不在数组中呢？
【在 g***j 的大作中提到】
: 直接返回0？
|
h*******e
发帖数: 1377 | 48 这个set of words 满足什么条件阿。
【在 a***n 的大作中提到】
: 这题还有扩展，如果你连扩展都没做到，那确实要好好做功课。
: 扩展是，求一个最小区间，囊括了一个set of words。
: 这个问题在实际中也有很直接的应用：
: 比如用户丢了一个query里面有N个term，搜索引擎返回了一堆snippets，如果展现最简
: 洁的snippets且包括了所有term？
: 倒排索引应该能想到。
: 扩展问题解法就是贪心，不需要DP。
|
g***j
发帖数: 1275 | 49 为啥？
【在 l*********8 的大作中提到】
: your code always returns INT_MIN
|
m*****k
发帖数: 731 | |
|
|
o***g
发帖数: 2784 | 51 因为初始化min_dist = INT_MIN，应该初始化成最大整数
【在 g***j 的大作中提到】
: 为啥？
|
W*********y
发帖数: 481 | 52 typo了吧，应该是INT_MAX
【在 g***j 的大作中提到】
: 为啥？
|
h*********o
发帖数: 230 | 53 初始化 应该是 max
【在 g***j 的大作中提到】
: 为啥？
|
r*******k
发帖数: 1423 | 54 算出来，存到矩阵里
【在 c*******r 的大作中提到】
: 你这个方法更好，不需要存储位置信息。
|
m*********n
发帖数: 931 | |
y***n
发帖数: 1594 | |
T*****u
发帖数: 7103 | |
T*****u
发帖数: 7103 | 58 python初学者贴个python的
def dist(word1, word2):
wordlist = ['this','this','is']
l1,l2 = -1,-1
dist = len(wordlist)
for p in range(len(wordlist)):
if word1==wordlist[p]:
l1 = p
if word1==word2:
l1,l2 = l2,l1
elif word2 == wordlist[p]:
l2 = p
if l1*l2>-1:
if dist>abs(l2-l1):
dist = abs(l2-l1)
if dist==len(wordlist): return None
else: return dist |
f**********t
发帖数: 1001 | 59 #include "common.h"
class WordsDistance {
vector _array;
public:
WordsDistance(initializer_list l) : _array(l) {}
int dist(string word1, string word2) {
int res = INT_MAX;
size_t left = 0;
while (left < _array.size() && _array[left] != word1 && _array[left] !=
word2) {
++left;
}
if (left == _array.size()) {
return res;
}
size_t right = left + 1;
while (right < _array.size()) {
if (_array[right] == _array[left]) {
left = right;
} else if (_array[right] == word1 || _array[right] == word2) {
res = min(res, (int)(right - left));
left = right;
}
++right;
}
return res;
}
};
void WordsDistanceTest() {
WordsDistance wd{"this", "is", "a", "is", "fox", "happy"};
cout << wd.dist("is", "a") << ' ' << wd.dist("this", "fox") << endl;
}
【在 Z**********4 的大作中提到】
: 已挂，发了攒人品。
: 有一个array ["this", "is", "a", "is", "fox", "happy"]
: 需要返回两个单词的最近距离（用index计算）。
: int dist(string word1, string word2)
: 比如dist("fox", "happy") = 1
: dist("is", "fox") = 1 注意“is”是有重复的。
: 每个单词都是有可能重复的。
|
c******e
发帖数: 558 | 60 +1
【在 l*****a 的大作中提到】
: 有必要记录那么多吗？
: indexa=-1
: indexb=-1
: 然后找到一个就更新相应index,算Math.min(indexa-indexb)不就可以了?
|
|
|
c*****m
发帖数: 271 | 61 这个followup怎么做啊？好像leecode上有，但是忘记了
【在 a***n 的大作中提到】
: 这题还有扩展，如果你连扩展都没做到，那确实要好好做功课。
: 扩展是，求一个最小区间，囊括了一个set of words。
: 这个问题在实际中也有很直接的应用：
: 比如用户丢了一个query里面有N个term，搜索引擎返回了一堆snippets，如果展现最简
: 洁的snippets且包括了所有term？
: 倒排索引应该能想到。
: 扩展问题解法就是贪心，不需要DP。
|
c*****m
发帖数: 271 | 62 这个followup怎么做啊？好像leecode上有，但是忘记了
【在 a***n 的大作中提到】
: 这题还有扩展，如果你连扩展都没做到，那确实要好好做功课。
: 扩展是，求一个最小区间，囊括了一个set of words。
: 这个问题在实际中也有很直接的应用：
: 比如用户丢了一个query里面有N个term，搜索引擎返回了一堆snippets，如果展现最简
: 洁的snippets且包括了所有term？
: 倒排索引应该能想到。
: 扩展问题解法就是贪心，不需要DP。
|
k******i
发帖数: 11 | 63 我之前也被面了这道题目， 当时面试官要求这个method会被call multiple times，
所以先用hashmap简历索引比较合理。
最小值的lookup可以做到worst case 0（n）。
假设两个word的index 序列是 int[] a, int[] b.
用两个index1， index2表示在各自序列中的位置。
一旦一个a[index1]的值大于b[index2]， 继续增加index1不会得到小于当前最优的解(
consider a = [3,4], b = [1,2])，所以index2++
反之亦然，相互交替直到遍历完两个index数组。
hashmap初始化复杂度O（n）。
lookup复杂度O(a.length + b.length), worst case O（n）。
【在 Z**********4 的大作中提到】
: 就是用hash先存所有word可能出现的index序列
: 然后word1和word2的序列，希望找出其中具有最小绝对值的一对。
: 这一面试官要求O(n)的算法吧。。没想出来。
|
s*****n
发帖数: 102 | 64 用hash应该很方便吧？
key是word，value是word对应的一个或多个index的值
然后两个word的value一对比，找个min的就行了 |
l*****8
发帖数: 1083 | 65 这个one pass就可以了，cc150上就有类似的
【在 Z**********4 的大作中提到】
: 已挂，发了攒人品。
: 有一个array ["this", "is", "a", "is", "fox", "happy"]
: 需要返回两个单词的最近距离（用index计算）。
: int dist(string word1, string word2)
: 比如dist("fox", "happy") = 1
: dist("is", "fox") = 1 注意“is”是有重复的。
: 每个单词都是有可能重复的。
|
y****e
发帖数: 25 | 66 “扩展问题解法就是贪心“ － 能不能展开说说。
【在 a***n 的大作中提到】
: 这题还有扩展，如果你连扩展都没做到，那确实要好好做功课。
: 扩展是，求一个最小区间，囊括了一个set of words。
: 这个问题在实际中也有很直接的应用：
: 比如用户丢了一个query里面有N个term，搜索引擎返回了一堆snippets，如果展现最简
: 洁的snippets且包括了所有term？
: 倒排索引应该能想到。
: 扩展问题解法就是贪心，不需要DP。
|
w*****t
发帖数: 485 | |
