Linkedin八月onsite面经 - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - Linkedin八月onsite面经

相关主题
● one amazon interview problem
● 有人同看Longest Palindromic Substring 这道题么？
● 求FB 面试　leetcode题目列表
● python搞不定Longest Palindromic Substring啊
● Longest subarray with equal number of 1 and 0
● 热腾腾的twitter电面经
● leetcode online judge Longest Palindromic Substring memory limit exceeded
● 问一道题(7)
● 大家幫我看看longest palindrome為什麽有錯，檢查半天也沒看出
● 这个怎么弄？

相关话题的讨论汇总
话题: dp话题: subset话题: maxlen话题: longest话题: int

进入JobHunting版参与讨论

(共1页)

h*********8
发帖数: 73

面的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*******g
发帖数: 7600

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

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*****a
发帖数: 14598

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

works
subset
2,

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

h*********8
发帖数: 73

应该是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*********8
发帖数: 73

没有答出来吗？

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

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

l*****a
发帖数: 14598

search for range
什么三pass,两pass?

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

: 没有答出来吗？

h*********8
发帖数: 73

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

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

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

l*****a
发帖数: 14598

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

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

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

h*********8
发帖数: 73

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

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

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

l*****a
发帖数: 14598

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

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

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

相关主题
● python搞不定Longest Palindromic Substring啊
● Longest subarray with equal number of 1 and 0
● 热腾腾的twitter电面经
● leetcode online judge Longest Palindromic Substring memory limit exceeded
进入JobHunting版参与讨论

a********5
发帖数: 1631

回文SUBSET那个是DP吧？

a********5
发帖数: 1631

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*****4
发帖数: 13

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

h*********8
发帖数: 73

没错

【在 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*********8
发帖数: 73

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

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

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

p****6
发帖数: 724

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

h*********8
发帖数: 73

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*********8
发帖数: 73

用recursive的话timing complexity太高了

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

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

a********5
发帖数: 1631

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

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

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

h*********8
发帖数: 73

后来回去以后想了一下，第二题比较好的解答应该是建立一个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

相关主题
● 问一道题(7)
● 大家幫我看看longest palindrome為什麽有錯，檢查半天也沒看出
● 这个怎么弄？
● Amazon Summer Intern Offer, 发面经
进入JobHunting版参与讨论

a********5
发帖数: 1631

不用那样麻烦吧，我感觉像我那样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*********8
发帖数: 73

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*****a
发帖数: 14598

你这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*********8
发帖数: 73

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

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

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

a********5
发帖数: 1631

不是吧？直接一遍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*********8
发帖数: 73

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

【在 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****g
发帖数: 355

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

T****U
发帖数: 3344

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

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

N*****i
发帖数: 74

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

j**7
发帖数: 143

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];
}

相关主题
● Bloomberg面试题
● DP通项公式
● g公司面试问Longest increasing subsequence，意义在哪里？
● 贡献两道Bloomberg面试题
进入JobHunting版参与讨论

g*****y
发帖数: 94

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

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

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

J*******o
发帖数: 741

学习了，感谢分享

s*********t
发帖数: 36

怎么下面觉得下面的不对？不是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***e
发帖数: 209

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

s*********t
发帖数: 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*********t
发帖数: 36

: 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*********t
发帖数: 36

: 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*********t
发帖数: 36

: 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*********t
发帖数: 36

: 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*********t
发帖数: 36

: 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
: 直觉上感觉是这样，不知道对不对

(共1页)

进入JobHunting版参与讨论

相关主题
● 这个怎么弄？
● Amazon Summer Intern Offer, 发面经
● Bloomberg面试题
● DP通项公式
● g公司面试问Longest increasing subsequence，意义在哪里？
● 贡献两道Bloomberg面试题
● 问一道题(1)
● Subset of size m Problem
● 面试被拒，百思不得其解，求指点
● 做题了，看看有没有比我更好的解法（20个包子）

相关话题的讨论汇总
话题: dp话题: subset话题: maxlen话题: longest话题: int

boards