会有spring 一波吗？ - 未名空间MITBBS历史存档

会有spring 一波吗？# Living

n*r2013-02-25 08:02

1 楼

很nice的欧洲女马工和我talk.老问题，可我没见到过这个问题。讨论好久。终于在最
后弄出来了。不知她满意不满意。
很奇怪如果大家都没见的题。这种题，大家在面试中多快弄出来？
Given an array of numbers, nums, return an array of numbers products, where
products[i] is the product of all nums[j], j != i.
Input : [1, 2, 3, 4, 5]
Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
= [120, 60, 40, 30, 24]
You must do this in O(N) without using division.

s*82013-02-25 08:02

2 楼

自打元月份开始看房，把市场上所有符合备选要求的都看了一遍，也有十来个房子了。
都不是很满意。这周休息，我的agent打电话来，安慰我说，耐心等等，春天应该有一
波房子上市。大家说说看看？

b*52013-02-25 08:02

3 楼

我面试时，怎么都不见到这种题？？！！！

f*i2013-02-25 08:02

4 楼

会，但是普遍贵15%

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

: 自打元月份开始看房，把市场上所有符合备选要求的都看了一遍，也有十来个房子了。
: 都不是很满意。这周休息，我的agent打电话来，安慰我说，耐心等等，春天应该有一
: 波房子上市。大家说说看看？

n*r2013-02-25 08:02

5 楼

你不用急。我准备的问题人家也不问。你什么题？

L*P2013-02-25 08:02

6 楼

是的,有一波
但是以我有限的2011-2012看房经历, 条件差不多的房子,close在4月之前的比close在
10月前的房子便宜

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

: 自打元月份开始看房，把市场上所有符合备选要求的都看了一遍，也有十来个房子了。
: 都不是很满意。这周休息，我的agent打电话来，安慰我说，耐心等等，春天应该有一
: 波房子上市。大家说说看看？

s*u2013-02-25 08:02

7 楼

这个题，我有一天出去吃饭、逛超市的时候一直在想，没想出来。看了答案，晕倒。突
然觉得自己弱爆了。

t*j2013-02-25 08:02

8 楼

今年不好说啊，inventory这么少。
[发表自未名空间手机版 - m.mitbbs.com]

n*r2013-02-25 08:02

9 楼

刷题刷不到的话，会。总觉的这些大公司出这些题就像靠回字几种写法。

c*o2013-02-25 08:02

10 楼

等两个大波

s*u2013-02-25 08:02

11 楼

这个题，我有一天出去吃饭、逛超市的时候一直在想，没想出来。看了答案，晕倒。突
然觉得自己弱爆了。

t*j2013-02-25 08:02

12 楼

毛

[发表自未名空间手机版 - m.mitbbs.com]

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

: 等两个大波

s*w2013-02-25 08:02

13 楼

这题貌似就是考如何不用　／　实现　／
leetcode 有　　divide two intergers 啊
没记错的话，就是使劲左移除数然后相减，得到结果再使劲左移再相减，结果就是所有
２^(左移的位数)相加
cc150 上有不用　+-做　+- 的：
做＋：　A+B = recursive +(A xor B, carry)
-: A+-B
-B : nagation +1
忘记咋做 * 了，难道是用左移相加？

where

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

: 很nice的欧洲女马工和我talk.老问题，可我没见到过这个问题。讨论好久。终于在最
: 后弄出来了。不知她满意不满意。
: 很奇怪如果大家都没见的题。这种题，大家在面试中多快弄出来？
: Given an array of numbers, nums, return an array of numbers products, where
: products[i] is the product of all nums[j], j != i.
: Input : [1, 2, 3, 4, 5]
: Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
: = [120, 60, 40, 30, 24]
: You must do this in O(N) without using division.

s*82013-02-25 08:02

14 楼

是这样。

【在 L**P 的大作中提到】

: 是的,有一波
: 但是以我有限的2011-2012看房经历, 条件差不多的房子,close在4月之前的比close在
: 10月前的房子便宜

g*42013-02-25 08:02

15 楼

看到O(n)了，我的错
请问LZ面的是intern还是full time？

where

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

: 很nice的欧洲女马工和我talk.老问题，可我没见到过这个问题。讨论好久。终于在最
: 后弄出来了。不知她满意不满意。
: 很奇怪如果大家都没见的题。这种题，大家在面试中多快弄出来？
: Given an array of numbers, nums, return an array of numbers products, where
: products[i] is the product of all nums[j], j != i.
: Input : [1, 2, 3, 4, 5]
: Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
: = [120, 60, 40, 30, 24]
: You must do this in O(N) without using division.

s*82013-02-25 08:02

16 楼

是这样。

【在 L**P 的大作中提到】

: 是的,有一波
: 但是以我有限的2011-2012看房经历, 条件差不多的房子,close在4月之前的比close在
: 10月前的房子便宜

t*n2013-02-25 08:02

17 楼

About 30 seconds

s*82013-02-25 08:02

18 楼

嗯，天娇等到没？

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

: 等两个大波

y*g2013-02-25 08:02

19 楼

http://stackoverflow.com/questions/2680548/given-an-array-of-nu
奇技淫巧，不学也罢

s*82013-02-25 08:02

20 楼

有同感。

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

: 今年不好说啊，inventory这么少。
: [发表自未名空间手机版 - m.mitbbs.com]

d*k2013-02-25 08:02

21 楼

我贡献个方法
idea: 若原数组为A，所求数组为B.对于每个i，令
L[i] = A[0] * A[1] * ... * A[i-1],
R[i] = A[i+1] * A[i+2] * ... * A[n-1]，则B[i] = L[i] * R[i]。
用python Online coding一个哈
def solve(A):
n = len(A)
if n == 0:
return []
L = [0] * n
R = [0] * n
B = [0] * n
L[0] = 1
for i in xrange(1, n):
L[i] = L[i-1] * A[i-1]
R[n-1] = 1
for i in xrange(n-2, -1, -1):
R[i] = R[i+1] * A[i+1]
for i in xrange(1, n):
B[i] = L[i] * R[i]
return B
时间复杂度O(n)，空间复杂度O(n)。
欢迎斧正，，顺便继续求G家在美国和中国以外的team match(因为没有H1b)。

w*r2013-02-25 08:02

22 楼

偶偏爱小波，赫赫

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

: 等两个大波

j*72013-02-25 08:02

23 楼

Evernote的Interview Street有这道题。
public static void multiplyExceptSelf(int [] input)
{
if(input==null)
return;
if(input.length==0)
return;
long [] left=new long[input.length];
long [] right=new long[input.length];
left[0]=1;
for(int i=1;i{
left[i]=left[i-1]*input[i-1];
}
right[input.length-1]=1;
for(int i=input.length-2;i>=0;i--)
{
right[i]=right[i+1]*input[i+1];
}
for(int i=0;i{
long product=left[i]*right[i];
System.out.println(product);
}

}

n*a2013-02-25 08:02

24 楼

波。。。让人浮想联翩。
你想说的是拨儿吧？

l*n2013-02-25 08:02

25 楼

显然不是你这种思路。
正解是计算prefix product & suffix product。

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

: 这题貌似就是考如何不用　／　实现　／
: leetcode 有　　divide two intergers 啊
: 没记错的话，就是使劲左移除数然后相减，得到结果再使劲左移再相减，结果就是所有
: ２^(左移的位数)相加
: cc150 上有不用　+-做　+- 的：
: 做＋：　A+B = recursive +(A xor B, carry)
: -: A+-B
: -B : nagation +1
: 忘记咋做 * 了，难道是用左移相加？
:

j*72013-02-25 08:02

26 楼

Evernote的Interview Street有这道题。
public static void multiplyExceptSelf(int [] input)
{
if(input==null)
return;
if(input.length==0)
return;
long [] left=new long[input.length];
long [] right=new long[input.length];
left[0]=1;
for(int i=1;i{
left[i]=left[i-1]*input[i-1];
}
right[input.length-1]=1;
for(int i=input.length-2;i>=0;i--)
{
right[i]=right[i+1]*input[i+1];
}
for(int i=0;i{
long product=left[i]*right[i];
System.out.println(product);
}

}

n*r2013-02-25 08:02

27 楼

知道了很简单。

n*r2013-02-25 08:02

28 楼

这个对。

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

: Evernote的Interview Street有这道题。
: public static void multiplyExceptSelf(int [] input)
: {
: if(input==null)
: return;
: if(input.length==0)
: return;
: long [] left=new long[input.length];
: long [] right=new long[input.length];
: left[0]=1;

s*w2013-02-25 08:02

29 楼

恩，看了大家的讨论觉得自己巨弱
思维定势太强了，不让／，第一反应就是walk around (因为训练过），没想到还是要
做 *

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

: 显然不是你这种思路。
: 正解是计算prefix product & suffix product。

g*r2013-02-25 08:02

30 楼

LZ怎么遇到这么好的题目。。。我那个也是女的，就一道题 open question : how to
design a maze，要有分岔路，deadend。准备了几百道的算法全没用，就和她说dfs然
后写代码，明显感觉她不满意。。。。

w*r2013-02-25 08:02

31 楼

这个题要是做不出来， LZ你应该检讨。
绝对是你做题不够。经典的不能再经典。

n*r2013-02-25 08:02

32 楼

我只有2周时间。做了20个题。

s*u2013-02-25 08:02

33 楼

额。。不是这个意思。。
那样的话还是用除法了，leetcode原题吧，有人讨论的。

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

: 这题貌似就是考如何不用　／　实现　／
: leetcode 有　　divide two intergers 啊
: 没记错的话，就是使劲左移除数然后相减，得到结果再使劲左移再相减，结果就是所有
: ２^(左移的位数)相加
: cc150 上有不用　+-做　+- 的：
: 做＋：　A+B = recursive +(A xor B, carry)
: -: A+-B
: -B : nagation +1
: 忘记咋做 * 了，难道是用左移相加？
:

s*u2013-02-25 08:02

34 楼

2周时间只做了20个leetcode题？不应该啊。。
我觉得2-3天就能做吧。

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

: 我只有2周时间。做了20个题。

b*52013-02-25 08:02

35 楼

你是全天在做？我就是下班后，晚上边灌水，边看电视，边做做

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

: 2周时间只做了20个leetcode题？不应该啊。。
: 我觉得2-3天就能做吧。

n*r2013-02-25 08:02

36 楼

你不复习概念啊。我早忘了。

n*r2013-02-25 08:02

37 楼

你不上班啊？

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

: 2周时间只做了20个leetcode题？不应该啊。。
: 我觉得2-3天就能做吧。

s*u2013-02-25 08:02

38 楼

哦我fresh graduate。我还以为你说全职复习呢

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

: 你不上班啊？

A*o2013-02-25 08:02

39 楼

<1 min, 思路参照leetcode stock III

where

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

: 很nice的欧洲女马工和我talk.老问题，可我没见到过这个问题。讨论好久。终于在最
: 后弄出来了。不知她满意不满意。
: 很奇怪如果大家都没见的题。这种题，大家在面试中多快弄出来？
: Given an array of numbers, nums, return an array of numbers products, where
: products[i] is the product of all nums[j], j != i.
: Input : [1, 2, 3, 4, 5]
: Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
: = [120, 60, 40, 30, 24]
: You must do this in O(N) without using division.

i*s2013-02-25 08:02

40 楼

这个题目预期的是system design吧，而不是algorithm solution

to

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

: LZ怎么遇到这么好的题目。。。我那个也是女的，就一道题 open question : how to
: design a maze，要有分岔路，deadend。准备了几百道的算法全没用，就和她说dfs然
: 后写代码，明显感觉她不满意。。。。

g*r2013-02-25 08:02

41 楼

是啊，满心以为店面只会有datastructure和算法题，结果碰到这题我就是跪了。完全
没法shine啊。看来没缘分

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

: 这个题目预期的是system design吧，而不是algorithm solution
:
: to

m*n2013-02-25 08:02

42 楼

我觉得是algorithm，应该就是个dfs。

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

: 这个题目预期的是system design吧，而不是algorithm solution
:
: to

g*e2013-02-25 08:02

43 楼

教你设计不是教你解迷宫

to

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

: LZ怎么遇到这么好的题目。。。我那个也是女的，就一道题 open question : how to
: design a maze，要有分岔路，deadend。准备了几百道的算法全没用，就和她说dfs然
: 后写代码，明显感觉她不满意。。。。

a*e2013-02-25 08:02

44 楼

这种问题面试官不会给提示么？

where

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

: 很nice的欧洲女马工和我talk.老问题，可我没见到过这个问题。讨论好久。终于在最
: 后弄出来了。不知她满意不满意。
: 很奇怪如果大家都没见的题。这种题，大家在面试中多快弄出来？
: Given an array of numbers, nums, return an array of numbers products, where
: products[i] is the product of all nums[j], j != i.
: Input : [1, 2, 3, 4, 5]
: Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
: = [120, 60, 40, 30, 24]
: You must do this in O(N) without using division.

g*r2013-02-25 08:02

45 楼

是设计，不是解maze。但是我是用dfs去设计，感觉设计的不太好。 visit一个节点以
后随机选择一个没有被visit的邻居来继续，如果发现到不了exit就返回false，然后
重新再来一遍。然后可以随机生成一些branch（用的random)，每个branch地方对两个
邻居visit
反正我觉得我的设计很水就是了，没技术含量。 dfs是其中一种方法但是据说应该还
有其他设计的方法

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

: 教你设计不是教你解迷宫
:
: to

a*e2013-02-25 08:02

46 楼

请问为啥和stock III思路类似？

【在 A***o 的大作中提到】

: <1 min, 思路参照leetcode stock III
:
: where

b*e2013-02-25 08:02

47 楼

这种题说白了就一脑筋急转弯。

where

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

: 很nice的欧洲女马工和我talk.老问题，可我没见到过这个问题。讨论好久。终于在最
: 后弄出来了。不知她满意不满意。
: 很奇怪如果大家都没见的题。这种题，大家在面试中多快弄出来？
: Given an array of numbers, nums, return an array of numbers products, where
: products[i] is the product of all nums[j], j != i.
: Input : [1, 2, 3, 4, 5]
: Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
: = [120, 60, 40, 30, 24]
: You must do this in O(N) without using division.

x*92013-02-25 08:02

48 楼

果然有这种感觉，一种难以名状的愤怒

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

: 这个题，我有一天出去吃饭、逛超市的时候一直在想，没想出来。看了答案，晕倒。突
: 然觉得自己弱爆了。

n*r2013-02-25 08:02

49 楼

愤怒! haha

x*m2013-02-25 08:02

50 楼

哈哈，就是哎，难怪都说面试是个运气活，有灵感就很简单……

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

: 这种题说白了就一脑筋急转弯。
:
: where

B*l2013-02-25 08:02

51 楼

从左到右走一遍生成array L，L[i]=num[0]*num[1]*...*num[i]
从右到左走一遍生成array R，R[i]=num[i]*num[i+1]*...*num[n-1]
output[i]=L[i-1]*R[i+1]

where

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

: 很nice的欧洲女马工和我talk.老问题，可我没见到过这个问题。讨论好久。终于在最
: 后弄出来了。不知她满意不满意。
: 很奇怪如果大家都没见的题。这种题，大家在面试中多快弄出来？
: Given an array of numbers, nums, return an array of numbers products, where
: products[i] is the product of all nums[j], j != i.
: Input : [1, 2, 3, 4, 5]
: Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
: = [120, 60, 40, 30, 24]
: You must do this in O(N) without using division.