walmartlab面经 - 未名空间MITBBS历史存档

p*f2012-12-20 08:12

1 楼

一共两次电面（没让签保密协议）
一面：1. Fabonacci number，给了三种解法，最快lgn
2. 从1加到100，不让用循环，不让用递归
二面：排好序的矩阵，从左到右升序，从上到下升序，要求判断给定的元素是否在矩阵
里，给了三种解法，最快lgn （跟面试官说了可以用master定理，但是忘了细节）
两次面试都完成了题目，做了boundary check和test cases
电面结果：被拒。
号外：本人已有工作（OPT），在linkedin上被recruiter联系，因为听说了“天价
offer”，就投了。因为当时比较忙，就跟recruiter把面试推到半个月后，recruiter
后来没有联系我。我打电话过去，被告知如果学位不是未来三个月之内拿到，就不能面
试。
可是不到一周，对方打电话过来问我第二天能不能面试。之后两次面试，自我感觉不错
，没有出现重大失误，按以往经历，GF之类的公司都会给onsite，结果被W告知被拒。
两次面试官都是老印，我都礼貌代之，据说也都给我了正面评价（第二个口音太重，很
多地方让重复了几遍，不知道是否这个有影响）。recruiter说team的bar很高，但是没
有在面试题目上体现。不知道他们到底想考察什么。
有朋友半月前拿到W的offer，据说一般，已经没有之前传说的那么高，朋友就从了别家。
不清楚明年是否还会有天价offer或者明显扩招的趋势，祝大家好运！

j*y2012-12-20 08:12

2 楼

bless.
二面的题目能做到 log N ? 对于 m by n的 array, 这是 Young table, 只能
做到 O(m + n)吧？

recruiter

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

: 一共两次电面（没让签保密协议）
: 一面：1. Fabonacci number，给了三种解法，最快lgn
: 2. 从1加到100，不让用循环，不让用递归
: 二面：排好序的矩阵，从左到右升序，从上到下升序，要求判断给定的元素是否在矩阵
: 里，给了三种解法，最快lgn （跟面试官说了可以用master定理，但是忘了细节）
: 两次面试都完成了题目，做了boundary check和test cases
: 电面结果：被拒。
: 号外：本人已有工作（OPT），在linkedin上被recruiter联系，因为听说了“天价
: offer”，就投了。因为当时比较忙，就跟recruiter把面试推到半个月后，recruiter
: 后来没有联系我。我打电话过去，被告知如果学位不是未来三个月之内拿到，就不能面

s*22012-12-20 08:12

3 楼

Walmart的面经比较少呀，LZ的三种解法是面试官要求的，还是自己主要提供的?

t*h2012-12-20 08:12

4 楼

zan

recruiter

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

: 一共两次电面（没让签保密协议）
: 一面：1. Fabonacci number，给了三种解法，最快lgn
: 2. 从1加到100，不让用循环，不让用递归
: 二面：排好序的矩阵，从左到右升序，从上到下升序，要求判断给定的元素是否在矩阵
: 里，给了三种解法，最快lgn （跟面试官说了可以用master定理，但是忘了细节）
: 两次面试都完成了题目，做了boundary check和test cases
: 电面结果：被拒。
: 号外：本人已有工作（OPT），在linkedin上被recruiter联系，因为听说了“天价
: offer”，就投了。因为当时比较忙，就跟recruiter把面试推到半个月后，recruiter
: 后来没有联系我。我打电话过去，被告知如果学位不是未来三个月之内拿到，就不能面

l*a2012-12-20 08:12

5 楼

第二题leetcode上只给出了nlgn的解法。lgn的解法是如何得到的？
第一题有lgn的解法，不过嫌复杂被放弃掉了。

i*s2012-12-20 08:12

6 楼

报你朋友的package吧, 好奇有多少? 我一直怀疑W天价OFFER. 一个零售商, PROFIT
MARGIN 也不大, 怎么能PAY $30W?!

recruiter

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

: 一共两次电面（没让签保密协议）
: 一面：1. Fabonacci number，给了三种解法，最快lgn
: 2. 从1加到100，不让用循环，不让用递归
: 二面：排好序的矩阵，从左到右升序，从上到下升序，要求判断给定的元素是否在矩阵
: 里，给了三种解法，最快lgn （跟面试官说了可以用master定理，但是忘了细节）
: 两次面试都完成了题目，做了boundary check和test cases
: 电面结果：被拒。
: 号外：本人已有工作（OPT），在linkedin上被recruiter联系，因为听说了“天价
: offer”，就投了。因为当时比较忙，就跟recruiter把面试推到半个月后，recruiter
: 后来没有联系我。我打电话过去，被告知如果学位不是未来三个月之内拿到，就不能面

p*f2012-12-20 08:12

7 楼

好像应该是O(n^(lg_4^3)),比O（n）小点点。
那个O（m+n）的算法我也给了。

【在 j*****y 的大作中提到】

: bless.
: 二面的题目能做到 log N ? 对于 m by n的 array, 这是 Young table, 只能
: 做到 O(m + n)吧？
:
: recruiter

p*f2012-12-20 08:12

8 楼

没问，估计不会超过140K。
另外一个进去的，据说就这么多。
也听说过应届拿到十六七万的，可惜都只是听说而已。

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

: 报你朋友的package吧, 好奇有多少? 我一直怀疑W天价OFFER. 一个零售商, PROFIT
: MARGIN 也不大, 怎么能PAY $30W?!
:
: recruiter

h*e2012-12-20 08:12

9 楼

收藏 fibonacci log n 算法。。。

p*f2012-12-20 08:12

10 楼

O（n^2）和O(n)是我主动给的。他让提高，我就又给了O（lgn）。

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

: Walmart的面经比较少呀，LZ的三种解法是面试官要求的，还是自己主要提供的?

j*y2012-12-20 08:12

11 楼

原来有个 O(n^(lg_4^3)) 的 Young table search. 多谢。

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

: 好像应该是O(n^(lg_4^3)),比O（n）小点点。
: 那个O（m+n）的算法我也给了。

p*f2012-12-20 08:12

12 楼

如果我没有搞错，用master定理应该是
T(n)=3T(n/4)+O(1)
所以有 O(n^(lg_4^3))

【在 j*****y 的大作中提到】

: 原来有个 O(n^(lg_4^3)) 的 Young table search. 多谢。

i*s2012-12-20 08:12

13 楼

哈,我说嘛，Ｗ不象能那么财大气粗.　ＬＺ无所谓了,　Ａ３砸堆/统治的地方不去也罢.

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

: 没问，估计不会超过140K。
: 另外一个进去的，据说就这么多。
: 也听说过应届拿到十六七万的，可惜都只是听说而已。

p*f2012-12-20 08:12

14 楼

嗯，被反复折腾的过程中就已经对他家有疑虑了。不让去onsite，也算少浪费点时间。
我也等着最后拿到天价offer的大牛出现，好好膜拜一下

罢.

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

: 哈,我说嘛，Ｗ不象能那么财大气粗.　ＬＺ无所谓了,　Ａ３砸堆/统治的地方不去也罢.

c*t2012-12-20 08:12

15 楼

虽然不知道package是多少，但知道能进去的都是超级大牛！
问一问大家，碰上题是给三种解好，还是直接给最优解好？

recruiter

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

: 一共两次电面（没让签保密协议）
: 一面：1. Fabonacci number，给了三种解法，最快lgn
: 2. 从1加到100，不让用循环，不让用递归
: 二面：排好序的矩阵，从左到右升序，从上到下升序，要求判断给定的元素是否在矩阵
: 里，给了三种解法，最快lgn （跟面试官说了可以用master定理，但是忘了细节）
: 两次面试都完成了题目，做了boundary check和test cases
: 电面结果：被拒。
: 号外：本人已有工作（OPT），在linkedin上被recruiter联系，因为听说了“天价
: offer”，就投了。因为当时比较忙，就跟recruiter把面试推到半个月后，recruiter
: 后来没有联系我。我打电话过去，被告知如果学位不是未来三个月之内拿到，就不能面

j*y2012-12-20 08:12

16 楼

感觉如果给出多种解法的话，45分钟内只有时间让你做一道题。
直接给最优解的话，面试官会有时间给你做两道题。
不知道面试官希望得到过程还是得到答案。

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

: 虽然不知道package是多少，但知道能进去的都是超级大牛！
: 问一问大家，碰上题是给三种解好，还是直接给最优解好？
:
: recruiter

i*s2012-12-20 08:12

17 楼

linkedin 上显示不一定都是大牛吧．．．

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

: 虽然不知道package是多少，但知道能进去的都是超级大牛！
: 问一问大家，碰上题是给三种解好，还是直接给最优解好？
:
: recruiter

s*l2012-12-20 08:12

18 楼

能给个O(n^(lg_4^3))的解法吗？
学些学习

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

: 好像应该是O(n^(lg_4^3)),比O（n）小点点。
: 那个O（m+n）的算法我也给了。

O*i2012-12-20 08:12

19 楼

我就是慢条斯理型，做题慢，经常被鄙视。

【在 j*****y 的大作中提到】

: 感觉如果给出多种解法的话，45分钟内只有时间让你做一道题。
: 直接给最优解的话，面试官会有时间给你做两道题。
: 不知道面试官希望得到过程还是得到答案。

p*f2012-12-20 08:12

20 楼

有点类似二分，每次取matrix中间的值跟要查找的值比较，如果不相等，要么舍弃左上
部分，要么舍弃右下部分,剩下的三个部分继续查找
这样T(n)=3T(n/4)+O(1)

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

: 能给个O(n^(lg_4^3))的解法吗？
: 学些学习

p*f2012-12-20 08:12

21 楼

这个我同意，面试运气成分挺大的，天时地利人和

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

: linkedin 上显示不一定都是大牛吧．．．

j*y2012-12-20 08:12

22 楼

这个对吗？里面的 n是什么 ? n x n的 table 的 size ?

有点类似二分，每次取matrix中间的值跟要查找的值比较，如果不相等，要么舍弃左上
部分，要么舍弃右下部分,剩下的三个部分继续查找
这样T(n)=3T(n/4)+O(1)

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

: 有点类似二分，每次取matrix中间的值跟要查找的值比较，如果不相等，要么舍弃左上
: 部分，要么舍弃右下部分,剩下的三个部分继续查找
: 这样T(n)=3T(n/4)+O(1)

g*g2012-12-20 08:12

23 楼

walmartlab是walmart收购的一个小startup，至于offer，我听说过google转过去给25
的。大约看人吧。fresh拿这个显然不现实。

x*02012-12-20 08:12

24 楼

mark

e*s2012-12-20 08:12

25 楼

这家的HR感觉很不怎么样。在linkedin上多次骚扰我，后来约好了聊一下给我打电话也
没打，最后再找我就不理他了。

recruiter

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

: 一共两次电面（没让签保密协议）
: 一面：1. Fabonacci number，给了三种解法，最快lgn
: 2. 从1加到100，不让用循环，不让用递归
: 二面：排好序的矩阵，从左到右升序，从上到下升序，要求判断给定的元素是否在矩阵
: 里，给了三种解法，最快lgn （跟面试官说了可以用master定理，但是忘了细节）
: 两次面试都完成了题目，做了boundary check和test cases
: 电面结果：被拒。
: 号外：本人已有工作（OPT），在linkedin上被recruiter联系，因为听说了“天价
: offer”，就投了。因为当时比较忙，就跟recruiter把面试推到半个月后，recruiter
: 后来没有联系我。我打电话过去，被告知如果学位不是未来三个月之内拿到，就不能面

w*p2012-12-20 08:12

26 楼

2. 从1加到100，不让用循环，不让用递归
请教最后用啥呢？ bit 运算吗？总不会是数学公式吧。

recruiter

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

: 一共两次电面（没让签保密协议）
: 一面：1. Fabonacci number，给了三种解法，最快lgn
: 2. 从1加到100，不让用循环，不让用递归
: 二面：排好序的矩阵，从左到右升序，从上到下升序，要求判断给定的元素是否在矩阵
: 里，给了三种解法，最快lgn （跟面试官说了可以用master定理，但是忘了细节）
: 两次面试都完成了题目，做了boundary check和test cases
: 电面结果：被拒。
: 号外：本人已有工作（OPT），在linkedin上被recruiter联系，因为听说了“天价
: offer”，就投了。因为当时比较忙，就跟recruiter把面试推到半个月后，recruiter
: 后来没有联系我。我打电话过去，被告知如果学位不是未来三个月之内拿到，就不能面

l*n2012-12-20 08:12

27 楼

my guess:
(1+100)*100/2

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

: 2. 从1加到100，不让用循环，不让用递归
: 请教最后用啥呢？ bit 运算吗？总不会是数学公式吧。
:
: recruiter

w*p2012-12-20 08:12

28 楼

可是这个没有考的点啊？就是会就会，不会就不会，
不知道有没有其他的解法呀

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

: my guess:
: (1+100)*100/2

l*d2012-12-20 08:12

29 楼

这题就属于脑筋急转弯...

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

: 可是这个没有考的点啊？就是会就会，不会就不会，
: 不知道有没有其他的解法呀

I*72012-12-20 08:12

30 楼

第二题不让循环不让递归该怎么写啊。。
不是考察用公式吧？
求思路

r*l2012-12-20 08:12

31 楼

(1+100)*100/2?

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

: 第二题不让循环不让递归该怎么写啊。。
: 不是考察用公式吧？
: 求思路

i*h2012-12-20 08:12

32 楼

等差数列公式？

i*h2012-12-20 08:12

33 楼

顺便问一下W什么题都是问几种解法？直接给最优的不行吗？

I*72012-12-20 08:12

34 楼

考公式没意义吧。。。
我知道C/C++里面可以用类的静态变量+构造函数可以算出来
JAVA里面不知道怎么弄。

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

: (1+100)*100/2?

y*92012-12-20 08:12

35 楼

“不让用循环，不让用递归”这里提供C#解法
Enumerable.Range(1, 100).Sum();
不考算法，不用递归循环，还不考公式，那就考语法糖

t*l2012-12-20 08:12

36 楼

lz二面复杂度算错了，最快也要O(m+n)的，没有O(log n)算法

recruiter

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

: 一共两次电面（没让签保密协议）
: 一面：1. Fabonacci number，给了三种解法，最快lgn
: 2. 从1加到100，不让用循环，不让用递归
: 二面：排好序的矩阵，从左到右升序，从上到下升序，要求判断给定的元素是否在矩阵
: 里，给了三种解法，最快lgn （跟面试官说了可以用master定理，但是忘了细节）
: 两次面试都完成了题目，做了boundary check和test cases
: 电面结果：被拒。
: 号外：本人已有工作（OPT），在linkedin上被recruiter联系，因为听说了“天价
: offer”，就投了。因为当时比较忙，就跟recruiter把面试推到半个月后，recruiter
: 后来没有联系我。我打电话过去，被告知如果学位不是未来三个月之内拿到，就不能面

t*l2012-12-20 08:12

37 楼

内部实现还是得用循环吧，不知道考官什么意思

【在 y****9 的大作中提到】

: “不让用循环，不让用递归”这里提供C#解法
: Enumerable.Range(1, 100).Sum();
: 不考算法，不用递归循环，还不考公式，那就考语法糖

a*32012-12-20 08:12

38 楼

log(m)+log(n) = log(m*n)
m 列数，n 行数更确切些吧。

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

: lz二面复杂度算错了，最快也要O(m+n)的，没有O(log n)算法
:
: recruiter

t*l2012-12-20 08:12

39 楼

先二分选定一行，再在行里二分？这个方法是不对的

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

: log(m)+log(n) = log(m*n)
: m 列数，n 行数更确切些吧。

a*m2012-12-20 08:12

40 楼

恩。lgn肯定不行。不过m+n能搞定吗？俺咋脚着至少要nlgn （简化成m=n）？

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

: 先二分选定一行，再在行里二分？这个方法是不对的

a*m2012-12-20 08:12

41 楼

俺错了。

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

: 恩。lgn肯定不行。不过m+n能搞定吗？俺咋脚着至少要nlgn （简化成m=n）？

w*a2012-12-20 08:12

42 楼

从1加到100，不让用循环，不让用递归
这个用模板元做？

a*32012-12-20 08:12

43 楼

为啥不对呢，能否详细说说哈。

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

: 先二分选定一行，再在行里二分？这个方法是不对的

x*62012-12-20 08:12

44 楼

没记错的话是用二分法，left＝0，right＝m＊n－1， mid＝（left＋right）／2，转
化为index是matrix［mid／n］［mid％n］， O（log（m＊n））

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

: 为啥不对呢，能否详细说说哈。

b*e2012-12-20 08:12

45 楼

楼上说二分法可以能达到log(m+n)的应该是考虑的这种情况：
i-1行的行尾小于第i行的行头，比如
1 2 3 4
5 6 7 8
9 10 11 12
而说只能（m+n）的考虑的是这种情况
1 10 20 30
2 20 30 40
5 50 100 120
这种情况下，同样存在楼主所说的“从左到右升序，从上到下升序”
但是只能m+n

a*32012-12-20 08:12

46 楼

如果先找到所在的行（log（m）），然后再在那行里用二分法查询目标（log（n））应
该也是没问题的。时间复杂度是log（m）+log（n）=log（m*n）。比起用一次二分法来
，就免去了每次计算index的麻烦。

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

:
: 没记错的话是用二分法，left＝0，right＝m＊n－1， mid＝（left＋right）／2，转
: 化为index是matrix［mid／n］［mid％n］， O（log（m＊n））

b*e2012-12-20 08:12

47 楼

不是的，比如
1 10 20 30
4 40 50 70
8 90 100 110
target=40

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

: 如果先找到所在的行（log（m）），然后再在那行里用二分法查询目标（log（n））应
: 该也是没问题的。时间复杂度是log（m）+log（n）=log（m*n）。比起用一次二分法来
: ，就免去了每次计算index的麻烦。

a*32012-12-20 08:12

48 楼

多谢提醒，我粗心啦。
可能用两个index来实现二分法比较快。算法复杂度差不多是 max（log（m），log（n
））。

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

: 不是的，比如
: 1 10 20 30
: 4 40 50 70
: 8 90 100 110
: target=40

a*32012-12-20 08:12

49 楼

多谢提醒，我粗心啦。
可能用两个index来实现二分法比较快。算法复杂度差不多是 max（log（m），log（n
））。

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

: 不是的，比如
: 1 10 20 30
: 4 40 50 70
: 8 90 100 110
: target=40

t*l2012-12-20 08:12

50 楼

这是个被讨论过很多次的题目了，只要第二行首元素可以小于首行末元素，就需要O(m+
n)，具体分析复杂一些，网上有讨论的

n

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

: 多谢提醒，我粗心啦。
: 可能用两个index来实现二分法比较快。算法复杂度差不多是 max（log（m），log（n
: ））。