walmartLab面经 phone interview - 未名空间MITBBS历史存档

walmartLab面经 phone interview# JobHunting - 待字闺中

s*r2013-02-26 08:02

1 楼

两轮 phone interview
第一轮
亚裔面试官，很nice，很详细问了当前project，问到许多细节的处理
算法题 reverse words in a string.
"It is good"--------->"good is It"
很简单，写完的时候有个bug，让我检查发现了改了
然后又提示把reverse string的函数单独提出来
follow question问能不能处理 string 前后中许多空白
我说可以他觉得不可以我们一块走了一遍code 可以
结束了
第二轮
面试官烙印，交流有问题，至少两处都要求重复了两三遍才听懂
先一个一个的让介绍自己的project 大概20分钟基本都是我在说
然后开始算法题
Q1
find longest palindrome in a string leetcode原题
解释思路，对每个character 从中间向两边扫找最长的他说ok
开始写写到一半考虑到偶数的情况，说还要考虑从中间两个character往两边扫
code，然后继续写还没写完就被烙印打断说u r on the right track 就下一题了
Q2 Let say you are given all pairwise distances between n points, points in
3d, compute a coordinate representation of the points such that the euclid
distance matches the input distance
x = sqrt(2)
eg) 1 2 3 4
1 0 1 1 1
2 1 0 x x
3 1 x 0 x
4 1 x x 0
output
1: (0,0,0)
2: (1,0,0)
3: (0,1,0)
4: (0,0,-1)
心想这code也太难了吧有点懵不知道他是什么意思想了一会儿还是没思路
试着问只给距离不给坐标系解并不唯一可以选择坐标系有很多解啊？他说是的就
沉默了
还是没思路只好任意发挥，说可以先选两点确定一线作为x轴，然后再选一个不在一条
线上的第三点确定以平面然后确定y轴后面还没说怎么确定z轴就又被打断了 ok let'
s move on next
Q3 given 2 distance matrices M1, M2 that represent distances bw points in 2d
, check if the point sets are equivalent (same upto translation + rotation)
这时候还没从上一题中回复过来脑子已经不转了，就brute force吧
说两matrix里的每行对比，看M1中的一行是不是可以通过M2中某一行交换顺序得到如
果不能返回false，如果可以，对M1所有列做相同的顺序变换看能不能对M1中的每一行
都在M2中找到对应的
还没说完又被打断了让问个问题就结束了
和烙印交流不太顺利肯定是挂了
move on了题目还是分享一下吧万一后面有面的兄弟可以有点心理准备

z*22013-02-26 08:02

2 楼

感謝分享， Q2 很難
leetcode 沒有 reverse words in a string

s*r2013-02-26 08:02

3 楼

那是我记错了 oj里确实没有
可能是在leetcode的blog entry里或者别处看到的
嗯 Q2我只能当数学题目来想想
下次再有这样问的烙印我就直接投降主动让他move on next...

【在 z***2 的大作中提到】

: 感謝分享， Q2 很難
: leetcode 沒有 reverse words in a string

l*b2013-02-26 08:02

4 楼

Q3:
1. each point has a key: sorted distances to other points
2. sort all points according to this key
3. the matrix is re-arranged accordingly by row + col permutation
4. verify if the matrices are equal to each other
Not very efficient though... actually slow and hard to write

f*e2013-02-26 08:02

5 楼

Q2只想到了N^4的解法，Q3 isomophism，先coarse filter，再finer filter。

【在 s*******r 的大作中提到】

: 两轮 phone interview
: 第一轮
: 亚裔面试官，很nice，很详细问了当前project，问到许多细节的处理
: 算法题 reverse words in a string.
: "It is good"--------->"good is It"
: 很简单，写完的时候有个bug，让我检查发现了改了
: 然后又提示把reverse string的函数单独提出来
: follow question问能不能处理 string 前后中许多空白
: 我说可以他觉得不可以我们一块走了一遍code 可以
: 结束了

l*b2013-02-26 08:02

6 楼

Q2: three points that satisfy a triangle inequality will form a triangle,
pick a 4-th point not on the same plane, it will decide the orintation of
the space. They can be fit into the space in arbitrary orientation.
Coordinates of all other points can be determined by their distance to these
four points.
But it's still hard to figure out their exact coordinates. You will need to
dervive some formulas using some area, volumn, distance to get their
coordinates more efficiently. I guess.
Edit: with coordinate of 4 points given and distance to them, coordinate of
another point is given by (x,y,z), you can reduce it to a 3 variable 3
equation linear system. So it will be solve in linear time. :)

【在 s*******r 的大作中提到】

: 那是我记错了 oj里确实没有
: 可能是在leetcode的blog entry里或者别处看到的
: 嗯 Q2我只能当数学题目来想想
: 下次再有这样问的烙印我就直接投降主动让他move on next...

s*r2013-02-26 08:02

7 楼

果然大牛说的名词我都不认识
说说N^4的解法?

【在 f*****e 的大作中提到】

: Q2只想到了N^4的解法，Q3 isomophism，先coarse filter，再finer filter。

f*e2013-02-26 08:02

8 楼

每加入一个点i+1，用1至i中的3个点可以确定i+1只有两个位置，这个耗费常数时间c，
然后确定它与已经加入的所有点1至i的距离是否满足矩阵。所以是
sum(1+2+...+N)=O(N^2)

【在 s*******r 的大作中提到】

: 果然大牛说的名词我都不认识
: 说说N^4的解法?

f*e2013-02-26 08:02

9 楼

Q3用凸包比较好做，记录polar angle和distance。也只要O(N^2)

【在 f*****e 的大作中提到】

: 每加入一个点i+1，用1至i中的3个点可以确定i+1只有两个位置，这个耗费常数时间c，
: 然后确定它与已经加入的所有点1至i的距离是否满足矩阵。所以是
: sum(1+2+...+N)=O(N^2)

p*22013-02-26 08:02

10 楼

LZ是ACMer吗？怎么电面这么难呢？

A*o2013-02-26 08:02

11 楼

luckynoob gave an answer to Q2, not repeating ,,,

s*r2013-02-26 08:02

12 楼

不是
面试的时候一直让我说自己很少说话
会做的不让做完换个偏题给我做也不给提示看我做不出接着再来一道类似的
我不负责任的胡乱推测一下安慰自己: 是被烙印给黑了

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

: LZ是ACMer吗？怎么电面这么难呢？

s*r2013-02-26 08:02

13 楼

差距啊极坐标我现在也只记得一个名词了回去复习去!

【在 f*****e 的大作中提到】

: Q3用凸包比较好做，记录polar angle和distance。也只要O(N^2)

s*r2013-02-26 08:02

14 楼

嗯我的思路也是这样不过没有你想的这么细
可能口语不行吧烙印都没耐心听我把坐标系建立完

these
to
of

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

: Q2: three points that satisfy a triangle inequality will form a triangle,
: pick a 4-th point not on the same plane, it will decide the orintation of
: the space. They can be fit into the space in arbitrary orientation.
: Coordinates of all other points can be determined by their distance to these
: four points.
: But it's still hard to figure out their exact coordinates. You will need to
: dervive some formulas using some area, volumn, distance to get their
: coordinates more efficiently. I guess.
: Edit: with coordinate of 4 points given and distance to them, coordinate of
: another point is given by (x,y,z), you can reduce it to a 3 variable 3

l*b2013-02-26 08:02

15 楼

电面时间不多呀, 这个坐下来自己想肯定能搞清楚的, 面起来就不好说了, 感觉.

【在 s*******r 的大作中提到】

: 嗯我的思路也是这样不过没有你想的这么细
: 可能口语不行吧烙印都没耐心听我把坐标系建立完
:
: these
: to
: of

x*02013-02-26 08:02

16 楼

mark

r*n2013-02-26 08:02

17 楼

Q2 idea
显然坐标系不是唯一的，
让第一个点是原点（0,0,0）
让第二个点在x axis上面，这样第二个点的坐标是(d12,0,0)，同时确立了x axis的方向
让第三个点在x-y平面上面，这样第三个点的坐标可以表示为(x3,y3,0)，通过d13,d23
解一个2元2次方程，并让y3取正值，这样相当于确立了y-axis方向（如果y3取负值，y-
axis就反向而已）（这里有个细节，如果1，2，3三个点在同一线上，那么是无法确立y
axis，这个时候就要找下面一个点了）
有了x axis和y axis，z axis就自动确立了。
剩下来的点的坐标假设为(a,b,c)，通过列方程求解。

p*e2013-02-26 08:02

18 楼

Q2估计老印也觉得不适合作为面试题，就move on了

r*n2013-02-26 08:02

19 楼

Q3 idea
通过Q2，我们可以从M1，M2算出每个点在两个坐标系的坐标。通过M1算出来的坐标是ui
，i = 1, ..., n，同理通过M2算出来的坐标是vi。Q3实际上等同于问有没有线性变换
把一个坐标系换成另外一个坐标系，or equivalently does there exist a matrix A
such that
A*ui = vj for some i,j = 1,...,n
A represents rotation and the translation (means swap of indices?) is
captured by the the fact i,j could be different.
但是这个怎么解，还没想出来。
LZ面的职位不是纯码工吧

A*o2013-02-26 08:02

20 楼

Q2的结果可以用来解Q3，O(n^2)

s*l2013-02-26 08:02

21 楼

Q3:
求和，平方求和，三次方求和，...
或者每项d_(ij)换成exp(-d_(ij)*d_(ij)/sigma), 任取sigma, 再求和，
如果对两个矩阵用以上的运算得到的和都一样的话，可以肯定两个点集是isometry(旋
转平移)
Keywords: euclidean distance matrix, isometry-invariant

s*l2013-02-26 08:02

22 楼

或者检查两组特征值是否一致，不过复杂度(N^3)应该比上面的求和复杂度(N^2)高。

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

: Q3:
: 求和，平方求和，三次方求和，...
: 或者每项d_(ij)换成exp(-d_(ij)*d_(ij)/sigma), 任取sigma, 再求和，
: 如果对两个矩阵用以上的运算得到的和都一样的话，可以肯定两个点集是isometry(旋
: 转平移)
: Keywords: euclidean distance matrix, isometry-invariant

a*g2013-02-26 08:02

23 楼

请问面的是什么职位，是SE吗？还是他家data scientist也是这么面？谢谢了

c*t2013-02-26 08:02

24 楼

弱问一下Q3，就算所有distance都一样，也不一定是相同点集合啊
极端一点
矩阵M 0 1
矩阵N 0 1
M和N能代表相同两个点吗？

【在 s*******r 的大作中提到】

: 两轮 phone interview
: 第一轮
: 亚裔面试官，很nice，很详细问了当前project，问到许多细节的处理
: 算法题 reverse words in a string.
: "It is good"--------->"good is It"
: 很简单，写完的时候有个bug，让我检查发现了改了
: 然后又提示把reverse string的函数单独提出来
: follow question问能不能处理 string 前后中许多空白
: 我说可以他觉得不可以我们一块走了一遍code 可以
: 结束了

s*r2013-02-26 08:02

25 楼

两轮 phone interview
第一轮
亚裔面试官，很nice，很详细问了当前project，问到许多细节的处理
算法题 reverse words in a sentence.
"It is good"--------->"good is It"
很简单，写完的时候有个bug，让我检查发现了改了
然后又提示把reverse string的函数单独提出来
follow question问能不能处理 string 前后中许多空白
我说可以他觉得不可以我们一块走了一遍code 可以
结束了
第二轮
面试官烙印，交流有问题，至少两处都要求重复了两三遍才听懂
先一个一个的让介绍自己的project 大概20分钟基本都是我在说
然后开始算法题
Q1
find longest palindrome in a string leetcode原题
解释思路，对每个character 从中间向两边扫找最长的他说ok
开始写写到一半考虑到偶数的情况，说还要考虑从中间两个character往两边扫
code，然后继续写还没写完就被烙印打断说u r on the right track 就下一题了
Q2 Let say you are given all pairwise distances between n points, points in
3d, compute a coordinate representation of the points such that the euclid
distance matches the input distance
x = sqrt(2)
eg) 1 2 3 4
1 0 1 1 1
2 1 0 x x
3 1 x 0 x
4 1 x x 0
output
1: (0,0,0)
2: (1,0,0)
3: (0,1,0)
4: (0,0,-1)
心想这code也太难了吧有点懵不知道他是什么意思想了一会儿还是没思路
试着问只给距离不给坐标系解并不唯一可以选择坐标系有很多解啊？他说是的就
沉默了
还是没思路只好任意发挥，说可以先选两点确定一线作为x轴，然后再选一个不在一条
线上的第三点确定以平面然后确定y轴后面还没说怎么确定z轴就又被打断了 ok let'
s move on next
Q3 given 2 distance matrices M1, M2 that represent distances bw points in 2d
, check if the point sets are equivalent (same upto translation + rotation)
这时候还没从上一题中回复过来脑子已经不转了，就brute force吧
说两matrix里的每行对比，看M1中的一行是不是可以通过M2中某一行交换顺序得到如
果不能返回false，如果可以，对M1所有列做相同的顺序变换看能不能对M1中的每一行
都在M2中找到对应的
还没说完又被打断了让问个问题就结束了
和烙印交流不太顺利肯定是挂了
move on了题目还是分享一下吧万一后面有面的兄弟可以有点心理准备

z*22013-02-26 08:02

26 楼

感謝分享， Q2 很難
leetcode 沒有 reverse words in a string

s*r2013-02-26 08:02

27 楼

那是我记错了 oj里确实没有
可能是在leetcode的blog entry里或者别处看到的
嗯 Q2我只能当数学题目来想想
下次再有这样问的烙印我就直接投降主动让他move on next...

【在 z***2 的大作中提到】

: 感謝分享， Q2 很難
: leetcode 沒有 reverse words in a string

l*b2013-02-26 08:02

28 楼

Q3:
1. each point has a key: sorted distances to other points
2. sort all points according to this key
3. the matrix is re-arranged accordingly by row + col permutation
4. verify if the matrices are equal to each other
Not very efficient though... actually slow and hard to write

f*e2013-02-26 08:02

29 楼

Q2只想到了N^2的解法，Q3 isomophism，先coarse filter，再finer filter。

【在 s*******r 的大作中提到】

: 两轮 phone interview
: 第一轮
: 亚裔面试官，很nice，很详细问了当前project，问到许多细节的处理
: 算法题 reverse words in a sentence.
: "It is good"--------->"good is It"
: 很简单，写完的时候有个bug，让我检查发现了改了
: 然后又提示把reverse string的函数单独提出来
: follow question问能不能处理 string 前后中许多空白
: 我说可以他觉得不可以我们一块走了一遍code 可以
: 结束了

l*b2013-02-26 08:02

30 楼

Q2: three points that satisfy a triangle inequality will form a triangle,
pick a 4-th point not on the same plane, it will decide the orintation of
the space. They can be fit into the space in arbitrary orientation.
Coordinates of all other points can be determined by their distance to these
four points.
But it's still hard to figure out their exact coordinates. You will need to
dervive some formulas using some area, volumn, distance to get their
coordinates more efficiently. I guess.
Edit: with coordinate of 4 points given and distance to them, coordinate of
another point is given by (x,y,z), you can reduce it to a 3 variable 3
equation linear system. So it will be solve in linear time. :)

【在 s*******r 的大作中提到】

: 那是我记错了 oj里确实没有
: 可能是在leetcode的blog entry里或者别处看到的
: 嗯 Q2我只能当数学题目来想想
: 下次再有这样问的烙印我就直接投降主动让他move on next...

s*r2013-02-26 08:02

31 楼

果然大牛说的名词我都不认识
说说N^4的解法?

【在 f*****e 的大作中提到】

: Q2只想到了N^4的解法，Q3 isomophism，先coarse filter，再finer filter。

f*e2013-02-26 08:02

32 楼

每加入一个点i+1，用1至i中的3个点可以确定i+1只有两个位置，这个耗费常数时间c，
然后确定它与已经加入的所有点1至i的距离是否满足矩阵。所以是
sum(1+2+...+N)=O(N^2)

【在 s*******r 的大作中提到】

: 果然大牛说的名词我都不认识
: 说说N^4的解法?

f*e2013-02-26 08:02

33 楼

Q3用凸包比较好做，记录polar angle和distance。也只要O(N^2)

【在 f*****e 的大作中提到】

: 每加入一个点i+1，用1至i中的3个点可以确定i+1只有两个位置，这个耗费常数时间c，
: 然后确定它与已经加入的所有点1至i的距离是否满足矩阵。所以是
: sum(1+2+...+N)=O(N^2)

p*22013-02-26 08:02

34 楼

LZ是ACMer吗？怎么电面这么难呢？

A*o2013-02-26 08:02

35 楼

luckynoob gave an answer to Q2, not repeating ,,,

s*r2013-02-26 08:02

36 楼

差距啊极坐标我现在也只记得一个名词了回去复习去!

【在 f*****e 的大作中提到】

: Q3用凸包比较好做，记录polar angle和distance。也只要O(N^2)

s*r2013-02-26 08:02

37 楼

嗯我的思路也是这样不过没有你想的这么细
可能口语不行吧烙印都没耐心听我把坐标系建立完

these
to
of

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

: Q2: three points that satisfy a triangle inequality will form a triangle,
: pick a 4-th point not on the same plane, it will decide the orintation of
: the space. They can be fit into the space in arbitrary orientation.
: Coordinates of all other points can be determined by their distance to these
: four points.
: But it's still hard to figure out their exact coordinates. You will need to
: dervive some formulas using some area, volumn, distance to get their
: coordinates more efficiently. I guess.
: Edit: with coordinate of 4 points given and distance to them, coordinate of
: another point is given by (x,y,z), you can reduce it to a 3 variable 3

l*b2013-02-26 08:02

38 楼

电面时间不多呀, 这个坐下来自己想肯定能搞清楚的, 面起来就不好说了, 感觉.

【在 s*******r 的大作中提到】

: 嗯我的思路也是这样不过没有你想的这么细
: 可能口语不行吧烙印都没耐心听我把坐标系建立完
:
: these
: to
: of

x*02013-02-26 08:02

39 楼

mark

r*n2013-02-26 08:02

40 楼

Q2 idea
显然坐标系不是唯一的，
让第一个点是原点（0,0,0）
让第二个点在x axis上面，这样第二个点的坐标是(d12,0,0)，同时确立了x axis的方向
让第三个点在x-y平面上面，这样第三个点的坐标可以表示为(x3,y3,0)，通过d13,d23
解一个2元2次方程，并让y3取正值，这样相当于确立了y-axis方向（如果y3取负值，y-
axis就反向而已）（这里有个细节，如果1，2，3三个点在同一线上，那么是无法确立y
axis，这个时候就要找下面一个点了）
有了x axis和y axis，z axis就自动确立了。
剩下来的点的坐标假设为(a,b,c)，通过列方程求解。

p*e2013-02-26 08:02

41 楼

Q2估计老印也觉得不适合作为面试题，就move on了

r*n2013-02-26 08:02

42 楼

Q3 idea
通过Q2，我们可以从M1，M2算出每个点在两个坐标系的坐标。通过M1算出来的坐标是ui
，i = 1, ..., n，同理通过M2算出来的坐标是vi。Q3实际上等同于问有没有线性变换
把一个坐标系换成另外一个坐标系，or equivalently does there exist a matrix A
such that
A*ui = vj for some i,j = 1,...,n
A represents rotation and the translation (means swap of indices?) is
captured by the the fact i,j could be different.
但是这个怎么解，还没想出来。
LZ面的职位不是纯码工吧

A*o2013-02-26 08:02

43 楼

Q2的结果可以用来解Q3，O(n^2)

s*l2013-02-26 08:02

44 楼

Q3:
求和，平方求和，三次方求和，...
或者每项d_(ij)换成exp(-d_(ij)*d_(ij)/sigma), 任取sigma, 再求和，
如果对两个矩阵用以上的运算得到的和都一样的话，可以肯定两个点集是isometry(旋
转平移)
Keywords: euclidean distance matrix, isometry-invariant

s*l2013-02-26 08:02

45 楼

或者检查两组特征值是否一致，不过复杂度(N^3)应该比上面的求和复杂度(N^2)高。

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

: Q3:
: 求和，平方求和，三次方求和，...
: 或者每项d_(ij)换成exp(-d_(ij)*d_(ij)/sigma), 任取sigma, 再求和，
: 如果对两个矩阵用以上的运算得到的和都一样的话，可以肯定两个点集是isometry(旋
: 转平移)
: Keywords: euclidean distance matrix, isometry-invariant

a*g2013-02-26 08:02

46 楼

请问面的是什么职位，是SE吗？还是他家data scientist也是这么面？谢谢了

c*t2013-02-26 08:02

47 楼

弱问一下Q3，就算所有distance都一样，也不一定是相同点集合啊
极端一点
矩阵M 0 1
矩阵N 0 1
M和N能代表相同两个点吗？

【在 s*******r 的大作中提到】

: 两轮 phone interview
: 第一轮
: 亚裔面试官，很nice，很详细问了当前project，问到许多细节的处理
: 算法题 reverse words in a sentence.
: "It is good"--------->"good is It"
: 很简单，写完的时候有个bug，让我检查发现了改了
: 然后又提示把reverse string的函数单独提出来
: follow question问能不能处理 string 前后中许多空白
: 我说可以他觉得不可以我们一块走了一遍code 可以
: 结束了

s*r2013-02-26 08:02

48 楼

改个名准备整理下其他的发过来

【在 s*******r 的大作中提到】

: 两轮 phone interview
: 第一轮
: 亚裔面试官，很nice，很详细问了当前project，问到许多细节的处理
: 算法题 reverse words in a sentence.
: "It is good"--------->"good is It"
: 很简单，写完的时候有个bug，让我检查发现了改了
: 然后又提示把reverse string的函数单独提出来
: follow question问能不能处理 string 前后中许多空白
: 我说可以他觉得不可以我们一块走了一遍code 可以
: 结束了

g*r2013-02-26 08:02

49 楼

这也太难了

g*s2013-02-26 08:02

50 楼

Q3我也有同样的疑问。
distance矩阵只包含local信息。就算M1 M2完全一样，也只是说明可能两个set组成的
多边形形状一样。你对这个多边形做任意旋转或平移M都不会变把？

【在 c********t 的大作中提到】

: 弱问一下Q3，就算所有distance都一样，也不一定是相同点集合啊
: 极端一点
: 矩阵M 0 1
: 矩阵N 0 1
: M和N能代表相同两个点吗？

w*m2013-02-26 08:02

51 楼

Q2, multiscaling problems in data mining
Q3, first do Q2, then compute its eigen values, eigen vectors, and new
coordinates projected to the new eigen vectors by SVD.
if sorted eigen values different, different
else if sorted eigen vectors different, different
else if sorted new coordinates different, different
else same

【在 s*******r 的大作中提到】

: 两轮 phone interview
: 第一轮
: 亚裔面试官，很nice，很详细问了当前project，问到许多细节的处理
: 算法题 reverse words in a sentence.
: "It is good"--------->"good is It"
: 很简单，写完的时候有个bug，让我检查发现了改了
: 然后又提示把reverse string的函数单独提出来
: follow question问能不能处理 string 前后中许多空白
: 我说可以他觉得不可以我们一块走了一遍code 可以
: 结束了

x*02013-02-26 08:02

52 楼

mark

H*r2013-02-26 08:02

53 楼

Q1 输入是valid sentence么？ Reverse 后是不是需要改大小写？ “Good is it"?
有标点符号的情况呢？ "Good, is it?" reverse => "It is, good?" or "?It is ,
Good" or "It is good" or "it is Good"?

【在 s*******r 的大作中提到】

: 两轮 phone interview
: 第一轮
: 亚裔面试官，很nice，很详细问了当前project，问到许多细节的处理
: 算法题 reverse words in a sentence.
: "It is good"--------->"good is It"
: 很简单，写完的时候有个bug，让我检查发现了改了
: 然后又提示把reverse string的函数单独提出来
: follow question问能不能处理 string 前后中许多空白
: 我说可以他觉得不可以我们一块走了一遍code 可以
: 结束了