Linkedin八月onsite面经 - 未名空间MITBBS历史存档

h*r2015-08-12 07:08

1 楼

夏季天气湿热，稍微运动就是一身的汗，有些地区是没有空调的，并且即使有空调也阻
挡不不了那些不速之客来侵占你的房间。
日前就有报道称，某女子下班后十分疲惫，放水准备洗澡的时候，发现水池里有一坨什
么东西，仔细一看，瞬间全身发麻。只见是一只通体红色的大蜈蚣，幸好自己刚刚没有
进去，否则这么大的蜈蚣一定是有毒的吧。
那夏季如何有效的避免虫子呢，一般的虫子都是比较喜欢潮湿阴暗的环境，那我们就要
保证房间通风，要有阳光，紫外线可以杀灭部分细菌，同时虫子一般是畏光的，所以上
班前吧窗帘拉开房间通风。
另外，虫子一般喜欢脏乱的地方，我们时刻保持房间整洁，吃过的东西不过夜，不存放
垃圾，一般蟑螂什么的是不会生的，有虫子的话可以用杀虫剂喷一下，杀虫剂使用时对
人体是有害的，建议使用时，尽量出去待一段时间，差不多半小时回家通风等味道全部
散尽，在回家，尽量不要使用杀虫剂，因为我之前有用过，后来觉得呼吸到有感染，嗓
子痛了好几天。
夏天在美美的同时，我们也要注意身边的生物，不要让它们打破宁静的生活。

h*82015-08-12 07:08

2 楼

面的application组
1.Design tinyurl
面试的是一个台湾人加一个烙印，面完自我感觉不错，面试官也说这个solution works
。但是最后feedback不好。
2.Coding
面试官是一男一女两个中国人
Leetcode Search for a Range原题，先写了3pass的solution，面试官问能不能用
2pass解决，答可以，于是说了2pass的solution。
第二题是Find the size of longest palindrome subset of an array，注意是subset
而不是subarray。不能改变order。所以[1, 2, 2, 0, 1]的longest palindrome
subset是[1, 2, 2, 1]，应该返回4。
当时想到可以选定array中的某一点，把array分成左右两个subarray，就是取一个中点
把[1, 2, 2, 0, 1]分成[1, 2]和[2, 0, 1]两个subarray，然后把[2, 0, 1]reverse
order变成[1, 0, 2]
然后用Leetcode里Edit Distance的Solution，也就是用2D auxiliary array和dynamic
programming找出[1, 2]和[1, 0, 2]的longest matched elements。
http://www.programcreek.com/2013/12/edit-distance-in-java/
当时感觉这题还挺难的，比leetcode里hard的题目还再深了一层。面试的时候能想出都
觉得自己挺不容易的。最后面试官说这个solution和他原本想的solution不一样，但是
good enough。
但是这一轮最后feedback也不太好。
3.Coding
两个韩国人
检查两个binary tree是否identical
Leetcode combination sum
都轻松答出
面试完满心欢喜以为稳了，结果悲剧

I*g2015-08-12 07:08

3 楼

结果正常啊，
你基本都没有答出来。

works
subset
2,

【在 h*********8 的大作中提到】

: 面的application组
: 1.Design tinyurl
: 面试的是一个台湾人加一个烙印，面完自我感觉不错，面试官也说这个solution works
: 。但是最后feedback不好。
: 2.Coding
: 面试官是一男一女两个中国人
: Leetcode Search for a Range原题，先写了3pass的solution，面试官问能不能用
: 2pass解决，答可以，于是说了2pass的solution。
: 第二题是Find the size of longest palindrome subset of an array，注意是subset
: 而不是subarray。不能改变order。所以[1, 2, 2, 0, 1]的longest palindrome

l*a2015-08-12 07:08

4 楼

这句话怎么解释? ==>注意是subset而不是subsequence
如果是subset 的话,跟顺序有关系吗?
另外不看你怎么答的,判断不出来悲剧原因啊

works
subset
2,

【在 h*********8 的大作中提到】

: 面的application组
: 1.Design tinyurl
: 面试的是一个台湾人加一个烙印，面完自我感觉不错，面试官也说这个solution works
: 。但是最后feedback不好。
: 2.Coding
: 面试官是一男一女两个中国人
: Leetcode Search for a Range原题，先写了3pass的solution，面试官问能不能用
: 2pass解决，答可以，于是说了2pass的solution。
: 第二题是Find the size of longest palindrome subset of an array，注意是subset
: 而不是subarray。不能改变order。所以[1, 2, 2, 0, 1]的longest palindrome

h*82015-08-12 07:08

5 楼

应该是subset而不是subarray。
和顺序有关，答案有点复杂
就是取一个中点把[1, 2, 2, 0, 1]分成[1, 2]和[2, 0, 1]两个subarray
然后把[2, 0, 1]reverse order变成[1, 0, 2]，然后用
http://www.programcreek.com/2013/12/edit-distance-in-java/
这个方法找[1, 2]和[1, 0, 2]之间有多少
elements是match的

【在 l*****a 的大作中提到】

: 这句话怎么解释? ==>注意是subset而不是subsequence
: 如果是subset 的话,跟顺序有关系吗?
: 另外不看你怎么答的,判断不出来悲剧原因啊
:
: works
: subset
: 2,

h*82015-08-12 07:08

6 楼

没有答出来吗？

【在 I*******g 的大作中提到】

: 结果正常啊，
: 你基本都没有答出来。
:
: works
: subset
: 2,

l*a2015-08-12 07:08

7 楼

search for range
什么三pass,两pass?

【在 h*********8 的大作中提到】

: 没有答出来吗？

h*82015-08-12 07:08

8 楼

3pass就是三次binary search
第一次找target是hit还是miss，第二次找左边界，第三次找右边界
2pass就是两次binary search
第一次找左边界，第二次找右边界

【在 l*****a 的大作中提到】

: search for range
: 什么三pass,两pass?

l*a2015-08-12 07:08

9 楼

找左边界时就知道是不是hit ah

【在 h*********8 的大作中提到】

: 3pass就是三次binary search
: 第一次找target是hit还是miss，第二次找左边界，第三次找右边界
: 2pass就是两次binary search
: 第一次找左边界，第二次找右边界

h*82015-08-12 07:08

10 楼

是的当时没有意识到，然后面试官问能不能只用两次binary search的时候意识到了

【在 l*****a 的大作中提到】

: 找左边界时就知道是不是hit ah

l*a2015-08-12 07:08

11 楼

看看你code怎么写的,还有其他题

【在 h*********8 的大作中提到】

: 是的当时没有意识到，然后面试官问能不能只用两次binary search的时候意识到了

a*52015-08-12 07:08

12 楼

回文SUBSET那个是DP吧？

a*52015-08-12 07:08

13 楼

D(i, j) = max{
D(i, j-1)
D(i+1, j)
D(i+1, j-1) + 2 if s(i) == s(j)
}
D(i,i) = 1
D(i, i+1) = s(i) == s(i+1) ? 2 : 1
直觉上感觉是这样，不知道对不对

b*42015-08-12 07:08

14 楼

楼主辛苦了, 请问manager和technical communication怎么样

h*82015-08-12 07:08

15 楼

没错

【在 a********5 的大作中提到】

: D(i, j) = max{
: D(i, j-1)
: D(i+1, j)
: D(i+1, j-1) + 2 if s(i) == s(j)
: }
: D(i,i) = 1
: D(i, i+1) = s(i) == s(i+1) ? 2 : 1
: 直觉上感觉是这样，不知道对不对

h*82015-08-12 07:08

16 楼

这两个就随便聊聊，没有什么特别的

【在 b*****4 的大作中提到】

: 楼主辛苦了, 请问manager和technical communication怎么样

p*62015-08-12 07:08

17 楼

第二题的标准答案是recusive
你只要不写标准答案，L的interviewer基本不放你过。

h*82015-08-12 07:08

18 楼

public int[] findRange(int[] arr, int target) {
int[] res = new int[2];
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int m = (l+r)/2;
if (arr[m] < target) l = m + 1;
else r = m - 1;
}
if (l >= arr.length) return new int[] {-1, -1};
res[0] = l;
l = 0;
r = arr.length - 1;
while (l <= r) {
int m = (l+r)/2;
if (arr[m] > target) r = m - 1;
else l = m + 1;
}
res[1] = r;
return res;
}

【在 l*****a 的大作中提到】

: 看看你code怎么写的,还有其他题

h*82015-08-12 07:08

19 楼

用recursive的话timing complexity太高了

【在 p****6 的大作中提到】

: 第二题的标准答案是recusive
: 你只要不写标准答案，L的interviewer基本不放你过。

a*52015-08-12 07:08

20 楼

我那时候没发现题库里有这题，给的解答是暴力递归？OMG

【在 p****6 的大作中提到】

: 第二题的标准答案是recusive
: 你只要不写标准答案，L的interviewer基本不放你过。

h*82015-08-12 07:08

21 楼

后来回去以后想了一下，第二题比较好的解答应该是建立一个n*n的2D auxiliary
array（n是input array的size）。
aux[i][j]代表在input array里，从第0个到i个这个subarray，和从n个到n-j个这个
subarray有多少match的element。然后用dp求出所有的aux[i][j]的组合。
最后求最大值
for (int i = 0; i < n; i++)
max = Math.max(max, aux[i][n-i]);

【在 a********5 的大作中提到】

: 我那时候没发现题库里有这题，给的解答是暴力递归？OMG

a*52015-08-12 07:08

22 楼

不用那样麻烦吧，我感觉像我那样DP应该是WORK的

【在 h*********8 的大作中提到】

: 后来回去以后想了一下，第二题比较好的解答应该是建立一个n*n的2D auxiliary
: array（n是input array的size）。
: aux[i][j]代表在input array里，从第0个到i个这个subarray，和从n个到n-j个这个
: subarray有多少match的element。然后用dp求出所有的aux[i][j]的组合。
: 最后求最大值
: for (int i = 0; i < n; i++)
: max = Math.max(max, aux[i][n-i]);

h*82015-08-12 07:08

23 楼

dp是work啊，可是dp只是其中一个步骤
同样重要的是你怎样设2d auxiliary array呢？
你的aux[i][j]代表什么？如果代表从中心向左i个element和向右j个element的话，中
心就要遍历所有的点，每一个中心要花n^2，最终timing complexity就是n^3。
但是用我刚才说的方法timing complexity是n^2。

【在 a********5 的大作中提到】

: 不用那样麻烦吧，我感觉像我那样DP应该是WORK的

l*a2015-08-12 07:08

24 楼

你这code work吗?
please find 3 in [2,4]

【在 h*********8 的大作中提到】

: public int[] findRange(int[] arr, int target) {
: int[] res = new int[2];
: int l = 0;
: int r = arr.length - 1;
: while (l <= r) {
: int m = (l+r)/2;
: if (arr[m] < target) l = m + 1;
: else r = m - 1;
: }
: if (l >= arr.length) return new int[] {-1, -1};

h*82015-08-12 07:08

25 楼

不work，谢谢指正
应该是
if (l >= arr.length || arr[l] != target)
return new int[] {-1, -1};
面试的时候写的是这个正确的版本

【在 l*****a 的大作中提到】

: 你这code work吗?
: please find 3 in [2,4]

a*52015-08-12 07:08

26 楼

不是吧？直接一遍DP就出结果了啊，N^2.
我说的是SUBSET最长回文那道题。。
我那个回帖里D(i,j)的意思是[i,j]的区间里，最长回文子串的长度。现在考虑：只包
括下一个字符(d(i, j-1)), 只包括前一个字符(d(i+1, j)) 以及如果两边新的字符相
等，扩充长度(d(i+1, j-1) + 2)

【在 h*********8 的大作中提到】

: dp是work啊，可是dp只是其中一个步骤
: 同样重要的是你怎样设2d auxiliary array呢？
: 你的aux[i][j]代表什么？如果代表从中心向左i个element和向右j个element的话，中
: 心就要遍历所有的点，每一个中心要花n^2，最终timing complexity就是n^3。
: 但是用我刚才说的方法timing complexity是n^2。

h*82015-08-12 07:08

27 楼

不好意思误解了。
是的应该是这样

【在 a********5 的大作中提到】

: 不是吧？直接一遍DP就出结果了啊，N^2.
: 我说的是SUBSET最长回文那道题。。
: 我那个回帖里D(i,j)的意思是[i,j]的区间里，最长回文子串的长度。现在考虑：只包
: 括下一个字符(d(i, j-1)), 只包括前一个字符(d(i+1, j)) 以及如果两边新的字符相
: 等，扩充长度(d(i+1, j-1) + 2)

p*g2015-08-12 07:08

28 楼

SUBSET最长回文那道题就是和翻转的数组求longest common subsequence

T*U2015-08-12 07:08

29 楼

为什么要循环两次？
难道不是找到下边界，上边界就是相邻，或者隔一位的那个数吗？

【在 h*********8 的大作中提到】

: public int[] findRange(int[] arr, int target) {
: int[] res = new int[2];
: int l = 0;
: int r = arr.length - 1;
: while (l <= r) {
: int m = (l+r)/2;
: if (arr[m] < target) l = m + 1;
: else r = m - 1;
: }
: if (l >= arr.length) return new int[] {-1, -1};

N*i2015-08-12 07:08

30 楼

palindrome 那题不就是Reverse这个array再和原来array找longest common
subsequence ?
这个是CRLS例题啊。假设存在最长palindrome,那么在reverse order中它的顺序不变，
直接找最长subsequence就好了啊。

j*72015-08-12 07:08

31 楼

Longest palindrome sub-sequence
public int longest(int[] A) {
int[][] DP = new int[A.length][A.length];
for (int i = A.length - 1; i >= 0; i--) {
for (int j = i; j < A.length; j++) {
if (A[i] == A[j]) {
DP[i][j] = (i == j) ? 1 : 2;
if (i + 1 <= j - 1) {
DP[i][j] += DP[i + 1][j - 1];
}
} else {
DP[i][j] = Math.max(DP[i + 1][j], DP[i][j - 1]);
}
}
}
return DP[0][A.length - 1];
}

g*y2015-08-12 07:08

32 楼

你们都在哪找题库？求教。

【在 a********5 的大作中提到】

: 我那时候没发现题库里有这题，给的解答是暴力递归？OMG

J*o2015-08-12 07:08

33 楼

学习了，感谢分享

s*t2015-08-12 07:08

34 楼

怎么下面觉得下面的不对？不是subset啊。 subset of longest palindrome subset
至少第一个和最后一个要一样, 然后只要中间有palindrome 就是一个subset，我觉得
应该是：
bool D[][]
len = [3, array.size()-3]
if s(i) == s(j) &&(D(i+1, j-1)| D(i, j-1) | D(i+1, j)
maxLen = len
是这样吗？

z*e2015-08-12 07:08

35 楼

第一题design short URL,网上好像有很多解释.
请问你当时是怎么回答的?
系统设计,细节要到什么程度?比如有没有估计一些统计量,估计机器数目,要求怎么算
Hash之类的?

s*t2015-08-12 07:08

36 楼

觉得下面的解法不对啊。longest palindrome subset of an array，我理解subset 至
少应是第一和最后一个字母相同，然后字串之间包含palindrome ：
bool D[][]
D(i,i) = true (maxLen = 1)
D(i, i+1) = s(i) == s(i+1) ? true : false (true -> maxLen = 2)
len = [3, size()]
D(i, j) = (D(i+1, j-1) || D(i, j-1)|| D(i+1, j)) && s(i) == s(j)
maxLen = whatever longest above
不知是不是这样

【在 a********5 的大作中提到】

: D(i, j) = max{
: D(i, j-1)
: D(i+1, j)
: D(i+1, j-1) + 2 if s(i) == s(j)
: }
: D(i,i) = 1
: D(i, i+1) = s(i) == s(i+1) ? 2 : 1
: 直觉上感觉是这样，不知道对不对

s*t2015-08-12 07:08

37 楼

觉得下面的解法不对啊。longest palindrome subset of an array，我理解subset 至
少应是第一和最后一个字母相同，然后字串之间包含palindrome ：
bool D[][]
D(i,i) = true (maxLen = 1)
D(i, i+1) = s(i) == s(i+1) ? true : false (true -> maxLen = 2)
len = [3, size()]
D(i, j) = (D(i+1, j-1) || D(i, j-1)|| D(i+1, j)) && s(i) == s(j)
maxLen = whatever longest above
不知是不是这样

【在 a********5 的大作中提到】

: D(i, j) = max{
: D(i, j-1)
: D(i+1, j)
: D(i+1, j-1) + 2 if s(i) == s(j)
: }
: D(i,i) = 1
: D(i, i+1) = s(i) == s(i+1) ? 2 : 1
: 直觉上感觉是这样，不知道对不对

s*t2015-08-12 07:08

38 楼

觉得下面的解法不对啊。longest palindrome subset of an array，我理解subset 至
少应是第一和最后一个字母相同，然后字串之间包含palindrome ：
bool D[][]
D(i,i) = true (maxLen = 1)
D(i, i+1) = s(i) == s(i+1) ? true : false (true -> maxLen = 2)
len = [3, size()]
D(i, j) = (D(i+1, j-1) || D(i, j-1)|| D(i+1, j)) && s(i) == s(j)
maxLen = whatever longest above
不知是不是这样

【在 a********5 的大作中提到】

: D(i, j) = max{
: D(i, j-1)
: D(i+1, j)
: D(i+1, j-1) + 2 if s(i) == s(j)
: }
: D(i,i) = 1
: D(i, i+1) = s(i) == s(i+1) ? 2 : 1
: 直觉上感觉是这样，不知道对不对

s*t2015-08-12 07:08

39 楼

觉得下面的解法不对啊。longest palindrome subset of an array，我理解subset 至
少应是第一和最后一个字母相同，然后字串之间包含palindrome ：
bool D[][]
D(i,i) = true (maxLen = 1)
D(i, i+1) = s(i) == s(i+1) ? true : false (true -> maxLen = 2)
len = [3, size()]
D(i, j) = (D(i+1, j-1) || D(i, j-1)|| D(i+1, j)) && s(i) == s(j)
maxLen = whatever longest above
不知是不是这样

【在 a********5 的大作中提到】

: D(i, j) = max{
: D(i, j-1)
: D(i+1, j)
: D(i+1, j-1) + 2 if s(i) == s(j)
: }
: D(i,i) = 1
: D(i, i+1) = s(i) == s(i+1) ? 2 : 1
: 直觉上感觉是这样，不知道对不对

s*t2015-08-12 07:08

40 楼

觉得下面的解法不对啊。longest palindrome subset of an array，我理解subset 至
少应是第一和最后一个字母相同，然后字串之间包含palindrome ：
bool D[][]
D(i,i) = true (maxLen = 1)
D(i, i+1) = s(i) == s(i+1) ? true : false (true -> maxLen = 2)
len = [3, size()]
D(i, j) = (D(i+1, j-1) || D(i, j-1)|| D(i+1, j)) && s(i) == s(j)
maxLen = whatever longest above
不知是不是这样

【在 a********5 的大作中提到】

: D(i, j) = max{
: D(i, j-1)
: D(i+1, j)
: D(i+1, j-1) + 2 if s(i) == s(j)
: }
: D(i,i) = 1
: D(i, i+1) = s(i) == s(i+1) ? 2 : 1
: 直觉上感觉是这样，不知道对不对

s*t2015-08-12 07:08

41 楼

觉得下面的解法不对啊。longest palindrome subset of an array，我理解subset 至
少应是第一和最后一个字母相同，然后字串之间包含palindrome ：
bool D[][]
D(i,i) = true (maxLen = 1)
D(i, i+1) = s(i) == s(i+1) ? true : false (true -> maxLen = 2)
len = [3, size()]
D(i, j) = (D(i+1, j-1) || D(i, j-1)|| D(i+1, j)) && s(i) == s(j)
maxLen = whatever longest above
不知是不是这样

【在 a********5 的大作中提到】

: D(i, j) = max{
: D(i, j-1)
: D(i+1, j)
: D(i+1, j-1) + 2 if s(i) == s(j)
: }
: D(i,i) = 1
: D(i, i+1) = s(i) == s(i+1) ? 2 : 1
: 直觉上感觉是这样，不知道对不对