logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
linkedin电面题
avatar
linkedin电面题# JobHunting - 待字闺中
Z*4
1 楼
已挂，发了攒人品。
有一个array ["this", "is", "a", "is", "fox", "happy"]
需要返回两个单词的最近距离（用index计算）。
int dist(string word1, string word2)
比如dist("fox", "happy") = 1
dist("is", "fox") = 1 注意“is”是有重复的。
每个单词都是有可能重复的。
avatar
l*a
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”是有重复的。
: 每个单词都是有可能重复的。
avatar
p*e
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”是有重复的。
: 每个单词都是有可能重复的。
avatar
X*4
4 楼
求最优解

【在 p*******e 的大作中提到】
: 如果面试前在这个版做过功课,这个题太高频了啊
: 怎么就挂了呢
avatar
a*n
5 楼
这题还有扩展，如果你连扩展都没做到，那确实要好好做功课。
扩展是，求一个最小区间，囊括了一个set of words。
这个问题在实际中也有很直接的应用：
比如用户丢了一个query里面有N个term，搜索引擎返回了一堆snippets，如果展现最简
洁的snippets且包括了所有term？
倒排索引应该能想到。
扩展问题解法就是贪心，不需要DP。
avatar
c*r
6 楼
auyin 说得是对的，其实就是inverted index的简单版本吧。
基本思想应该是：对每一个词，记录它的index （从小到大）。然后对于s1, s2，计算
索引
之间的最小值，就是两个词之间的最小距离了。
glassdoor上面原题
avatar
l*a
7 楼
有必要记录那么多吗？
indexa=-1
indexb=-1
然后找到一个就更新相应index,算Math.min(indexa-indexb)不就可以了?

【在 c*******r 的大作中提到】
: auyin 说得是对的，其实就是inverted index的简单版本吧。
: 基本思想应该是：对每一个词，记录它的index （从小到大）。然后对于s1, s2，计算
: 索引
: 之间的最小值，就是两个词之间的最小距离了。
: glassdoor上面原题
avatar
g*j
8 楼
没明白，展开说说？

【在 l*****a 的大作中提到】
: 有必要记录那么多吗？
: indexa=-1
: indexb=-1
: 然后找到一个就更新相应index,算Math.min(indexa-indexb)不就可以了?
avatar
c*r
9 楼
你这个方法更好，不需要存储位置信息。

【在 l*****a 的大作中提到】
: 有必要记录那么多吗？
: indexa=-1
: indexb=-1
: 然后找到一个就更新相应index,算Math.min(indexa-indexb)不就可以了?
avatar
c*r
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 的大作中提到】
: 没明白，展开说说？
avatar
l*a
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;
avatar
Z*4
12 楼
就是用hash先存所有word可能出现的index序列
然后word1和word2的序列，希望找出其中具有最小绝对值的一对。
这一面试官要求O(n)的算法吧。。没想出来。

【在 l*****a 的大作中提到】
: 就一道题？你怎么做的
avatar
m*3
13 楼
应该不用这么麻烦吧，两个变量，记录word1 和 word 2最近出现的位置，然后每次计
算当前的距离，如果这个距离小于当前已知的最小距离，就更新最小距离，O(n)扫一遍
就行

【在 Z**********4 的大作中提到】
: 就是用hash先存所有word可能出现的index序列
: 然后word1和word2的序列，希望找出其中具有最小绝对值的一对。
: 这一面试官要求O(n)的算法吧。。没想出来。
avatar
s*x
14 楼
如果这个函数调用一次，我觉得一次扫描，不用hash最好。
如果调用多次，我觉得用构造hash更好。
avatar
i*e
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;
avatar
g*j
16 楼
直接返回0？

【在 i**********e 的大作中提到】
: 当 word1 = word2 怎么办？
avatar
l*8
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;
avatar
l*8
18 楼
word不在数组中呢？

【在 g***j 的大作中提到】
: 直接返回0？
avatar
h*e
19 楼
这个set of words 满足什么条件阿。

【在 a***n 的大作中提到】
: 这题还有扩展，如果你连扩展都没做到，那确实要好好做功课。
: 扩展是，求一个最小区间，囊括了一个set of words。
: 这个问题在实际中也有很直接的应用：
: 比如用户丢了一个query里面有N个term，搜索引擎返回了一堆snippets，如果展现最简
: 洁的snippets且包括了所有term？
: 倒排索引应该能想到。
: 扩展问题解法就是贪心，不需要DP。
avatar
g*j
20 楼
为啥？

【在 l*********8 的大作中提到】
: your code always returns INT_MIN
avatar
m*k
21 楼
avatar
o*g
22 楼
因为初始化min_dist = INT_MIN，应该初始化成最大整数

【在 g***j 的大作中提到】
: 为啥？
avatar
W*y
23 楼
typo了吧，应该是INT_MAX

【在 g***j 的大作中提到】
: 为啥？
avatar
h*o
24 楼
初始化 应该是 max

【在 g***j 的大作中提到】
: 为啥？
avatar
r*k
25 楼
算出来，存到矩阵里

【在 c*******r 的大作中提到】
: 你这个方法更好，不需要存储位置信息。
avatar
m*n
26 楼
好题~ 不用hash应该就ok
avatar
y*n
27 楼
好像CC 150 也有这个题。
avatar
T*u
28 楼
这个能先sort了list吗？
avatar
T*u
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
avatar
Z*4
30 楼
已挂，发了攒人品。
有一个array ["this", "is", "a", "is", "fox", "happy"]
需要返回两个单词的最近距离（用index计算）。
int dist(string word1, string word2)
比如dist("fox", "happy") = 1
dist("is", "fox") = 1 注意“is”是有重复的。
每个单词都是有可能重复的。
avatar
l*a
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”是有重复的。
: 每个单词都是有可能重复的。
avatar
p*e
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”是有重复的。
: 每个单词都是有可能重复的。
avatar
X*4
33 楼
求最优解

【在 p*******e 的大作中提到】
: 如果面试前在这个版做过功课,这个题太高频了啊
: 怎么就挂了呢
avatar
a*n
34 楼
这题还有扩展，如果你连扩展都没做到，那确实要好好做功课。
扩展是，求一个最小区间，囊括了一个set of words。
这个问题在实际中也有很直接的应用：
比如用户丢了一个query里面有N个term，搜索引擎返回了一堆snippets，如果展现最简
洁的snippets且包括了所有term？
倒排索引应该能想到。
扩展问题解法就是贪心，不需要DP。
avatar
c*r
35 楼
auyin 说得是对的，其实就是inverted index的简单版本吧。
基本思想应该是：对每一个词，记录它的index （从小到大）。然后对于s1, s2，计算
索引
之间的最小值，就是两个词之间的最小距离了。
glassdoor上面原题
avatar
l*a
36 楼
有必要记录那么多吗？
indexa=-1
indexb=-1
然后找到一个就更新相应index,算Math.min(indexa-indexb)不就可以了?

【在 c*******r 的大作中提到】
: auyin 说得是对的，其实就是inverted index的简单版本吧。
: 基本思想应该是：对每一个词，记录它的index （从小到大）。然后对于s1, s2，计算
: 索引
: 之间的最小值，就是两个词之间的最小距离了。
: glassdoor上面原题
avatar
g*j
37 楼
没明白，展开说说？

【在 l*****a 的大作中提到】
: 有必要记录那么多吗？
: indexa=-1
: indexb=-1
: 然后找到一个就更新相应index,算Math.min(indexa-indexb)不就可以了?
avatar
c*r
38 楼
你这个方法更好，不需要存储位置信息。

【在 l*****a 的大作中提到】
: 有必要记录那么多吗？
: indexa=-1
: indexb=-1
: 然后找到一个就更新相应index,算Math.min(indexa-indexb)不就可以了?
avatar
c*r
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 的大作中提到】
: 没明白，展开说说？
avatar
l*a
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;
avatar
Z*4
41 楼
就是用hash先存所有word可能出现的index序列
然后word1和word2的序列，希望找出其中具有最小绝对值的一对。
这一面试官要求O(n)的算法吧。。没想出来。

【在 l*****a 的大作中提到】
: 就一道题？你怎么做的
avatar
m*3
42 楼
应该不用这么麻烦吧，两个变量，记录word1 和 word 2最近出现的位置，然后每次计
算当前的距离，如果这个距离小于当前已知的最小距离，就更新最小距离，O(n)扫一遍
就行

【在 Z**********4 的大作中提到】
: 就是用hash先存所有word可能出现的index序列
: 然后word1和word2的序列，希望找出其中具有最小绝对值的一对。
: 这一面试官要求O(n)的算法吧。。没想出来。
avatar
s*x
43 楼
如果这个函数调用一次，我觉得一次扫描，不用hash最好。
如果调用多次，我觉得用构造hash更好。
avatar
i*e
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;
avatar
g*j
45 楼
直接返回0？

【在 i**********e 的大作中提到】
: 当 word1 = word2 怎么办？
avatar
l*8
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;
avatar
l*8
47 楼
word不在数组中呢？

【在 g***j 的大作中提到】
: 直接返回0？
avatar
h*e
48 楼
这个set of words 满足什么条件阿。

【在 a***n 的大作中提到】
: 这题还有扩展，如果你连扩展都没做到，那确实要好好做功课。
: 扩展是，求一个最小区间，囊括了一个set of words。
: 这个问题在实际中也有很直接的应用：
: 比如用户丢了一个query里面有N个term，搜索引擎返回了一堆snippets，如果展现最简
: 洁的snippets且包括了所有term？
: 倒排索引应该能想到。
: 扩展问题解法就是贪心，不需要DP。
avatar
g*j
49 楼
为啥？

【在 l*********8 的大作中提到】
: your code always returns INT_MIN
avatar
m*k
50 楼
avatar
o*g
51 楼
因为初始化min_dist = INT_MIN，应该初始化成最大整数

【在 g***j 的大作中提到】
: 为啥？
avatar
W*y
52 楼
typo了吧，应该是INT_MAX

【在 g***j 的大作中提到】
: 为啥？
avatar
h*o
53 楼
初始化 应该是 max

【在 g***j 的大作中提到】
: 为啥？
avatar
r*k
54 楼
算出来，存到矩阵里

【在 c*******r 的大作中提到】
: 你这个方法更好，不需要存储位置信息。
avatar
m*n
55 楼
好题~ 不用hash应该就ok
avatar
y*n
56 楼
好像CC 150 也有这个题。
avatar
T*u
57 楼
这个能先sort了list吗？
avatar
T*u
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
avatar
f*t
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”是有重复的。
: 每个单词都是有可能重复的。
avatar
c*e
60 楼
+1

【在 l*****a 的大作中提到】
: 有必要记录那么多吗？
: indexa=-1
: indexb=-1
: 然后找到一个就更新相应index,算Math.min(indexa-indexb)不就可以了?
avatar
c*m
61 楼
这个followup怎么做啊？好像leecode上有，但是忘记了

【在 a***n 的大作中提到】
: 这题还有扩展，如果你连扩展都没做到，那确实要好好做功课。
: 扩展是，求一个最小区间，囊括了一个set of words。
: 这个问题在实际中也有很直接的应用：
: 比如用户丢了一个query里面有N个term，搜索引擎返回了一堆snippets，如果展现最简
: 洁的snippets且包括了所有term？
: 倒排索引应该能想到。
: 扩展问题解法就是贪心，不需要DP。
avatar
c*m
62 楼
这个followup怎么做啊？好像leecode上有，但是忘记了

【在 a***n 的大作中提到】
: 这题还有扩展，如果你连扩展都没做到，那确实要好好做功课。
: 扩展是，求一个最小区间，囊括了一个set of words。
: 这个问题在实际中也有很直接的应用：
: 比如用户丢了一个query里面有N个term，搜索引擎返回了一堆snippets，如果展现最简
: 洁的snippets且包括了所有term？
: 倒排索引应该能想到。
: 扩展问题解法就是贪心，不需要DP。
avatar
k*i
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)的算法吧。。没想出来。
avatar
s*n
64 楼
用hash应该很方便吧？
key是word，value是word对应的一个或多个index的值
然后两个word的value一对比，找个min的就行了
avatar
l*8
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”是有重复的。
: 每个单词都是有可能重复的。
avatar
y*e
66 楼
“扩展问题解法就是贪心“ － 能不能展开说说。

【在 a***n 的大作中提到】
: 这题还有扩展，如果你连扩展都没做到，那确实要好好做功课。
: 扩展是，求一个最小区间，囊括了一个set of words。
: 这个问题在实际中也有很直接的应用：
: 比如用户丢了一个query里面有N个term，搜索引擎返回了一堆snippets，如果展现最简
: 洁的snippets且包括了所有term？
: 倒排索引应该能想到。
: 扩展问题解法就是贪心，不需要DP。
相关阅读
人还没开始上班，能办H1b吗？西雅图的Startup寻找前端，后端和网页设计人员opt挂靠 (转载)请问uber电面难度Uber Driver Allegedly Fractured His Passenger's Skull Withbackground check都要国内大学成绩单吗HR来约二面的时间，我回复之后HR没消息？怎么样搜索一段时间内facebook的面经贴pinterest on-site高富帅命好还是vision好？ＥＱ降龙18掌 (转载)leetcode的题目都不提供标准答案了？工作太闲怎么办 (转载)H1B transfer批下来了，还能改上班日期吗？Top K in last minute/hour/day 有什么好的思路吗[面经]YELP家不刷题的惨烈后果急问，关于h1b 被layoff可以只刷 leetcode、cc150,没有工作经验可以吗？大家来刷这个题： 烙印指数增长问个难题
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。