由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 狗狗家fail的面经
相关主题
问一道Google的题Google intern 面经,回馈版面
G家最新电面问一个CareerCup上的Google题
这题咋做, 有点像Run Length encoding, 但又不全是?facebook programming challenge难度如何?
G的一道Onesite题前段时间的面试
SnapChat 面經 + 彙總请教一道G家面试题
最优合并及证明F/L/A/G/T/Groupon/Box 贴面经 报offer 回报本版
An immediate intern position in central new jerseyG家电题
问一道题啥叫encode/decode binary tree啊?
相关话题的讨论汇总
话题: string话题: 使得话题: 设计话题: 字符串话题: sum
进入JobHunting版参与讨论
1 (共1页)
g*********e
发帖数: 14401
1
今天HR打电话来说HC没过,记下来参考
电面1:
第一个问题记不得了
第二个,给一系列string,要求找两个string,使得它们没有共同字符,并且长度乘积
最大。好像给了个暴力解
电面2:
给两个string array A,B,要求返回三个array,第一个只包含只出现在A中的字符串,
第二个只包含只出现在B中的字符串,第三个只包含common字符串
然后海量数据下该怎么code。貌似这个电面反馈很好
onsite:
1. 先寒暄介绍,稍稍问现在工作。题目是run length encoding的变种,decoder的规
则是: a3x1bc -> a111bc (用x来表示重复)
该怎么设计encoder。写代码。开头想了很久,才写了代码,写得比较罗嗦。再跑了几
个测试。这轮发挥不好,HR开头也迟到了一会儿,导致时间稍稍不够,没时间再做一题
了,问了几个问题结束。
2. 稍稍介绍下google的工作。题目是常见题二维平面上过最多点的直线。问清后写了
个n^2logn的解法,然后在提示下讲了n^2的方法。扩展问海量数据下的做法,这里纠结
了,给了个比较复杂的方法。时间到。这轮应该还OK。
3. 简单题,给定一个char array,删除里面某个char。
第二题是二维平面有若干个点,找一个点使得到他们的曼哈顿距离最短。就是找median
。分析后讲了quick select找median。
给定一个二维矩阵,有update(x,y) 和 sum(x1,y1, x2, y2)两个方法。
怎么设计使得update()比较快?
怎么设计使得sum()比较快?
怎么设计使得两者都reasonable得快?好像最后讨论到n,log(n)的设计
这轮还不错
4. 简单题。给定一个二叉树,找到最深的leaf,返回深度和节点本身。写code。
找到最浅的leaf,返回深度和节点本身。
给定一系列电影开始和结束时间,怎么选择电影能看最多场次。(greedy O(n))
怎么选择能看最长时间?
返回最长时间,和需要看的电影(写了个dp的方法,nlogn,这轮也还不错)
5. 给定一个数列。返回一个最大的数,使得数列中大于它的数数量也大于它,这个数
不需要在数列里,写代码。(这题真够拗口,当时三哥把题目写在黑板上,读了好几遍
才理解,就是先sort然后一个一个找)代码最后返回处有bug,在提示下修改。然后跑
了几个test,没问题。
然后问如果数列里有很多重复数字该怎么弄比较快,三哥说不需要sort。想了很久,答
bucket sort,再讨论了下具体的bucket细节/数量。这轮也就答了一题就到时间了。
总结:面完感觉整体也就凑合,结果果然悲剧。也不知具体feedback。
面试前HR很强调跟面试官的交流,交流过头了也不行,没时间写代码。写代码越快越好
,最好一口气就写下来。而且有好的solution就应该一步到位,这样有时间做下一题。
g*********e
发帖数: 14401
2
另外求湾区各大软件/互联网公司refer! 主要是C++方向
搞了几个月就狗狗一家给面试,感觉有点划不来。
P*****f
发帖数: 2272
3
试过 PSDUA这些没?直接网投就应该有面试

【在 g*********e 的大作中提到】
: 另外求湾区各大软件/互联网公司refer! 主要是C++方向
: 搞了几个月就狗狗一家给面试,感觉有点划不来。

g*********e
发帖数: 14401
4

简历上写什么比较容易拿到面试?光C++ LINUX之类的貌似不管用

【在 P*****f 的大作中提到】
: 试过 PSDUA这些没?直接网投就应该有面试
d******k
发帖数: 32
5
a23x1bc,中的23x1是输出23个1,还是1个2和3个1?

【在 g*********e 的大作中提到】
: 今天HR打电话来说HC没过,记下来参考
: 电面1:
: 第一个问题记不得了
: 第二个,给一系列string,要求找两个string,使得它们没有共同字符,并且长度乘积
: 最大。好像给了个暴力解
: 电面2:
: 给两个string array A,B,要求返回三个array,第一个只包含只出现在A中的字符串,
: 第二个只包含只出现在B中的字符串,第三个只包含common字符串
: 然后海量数据下该怎么code。貌似这个电面反馈很好
: onsite:

b******t
发帖数: 965
6
好难啊

【在 g*********e 的大作中提到】
: 今天HR打电话来说HC没过,记下来参考
: 电面1:
: 第一个问题记不得了
: 第二个,给一系列string,要求找两个string,使得它们没有共同字符,并且长度乘积
: 最大。好像给了个暴力解
: 电面2:
: 给两个string array A,B,要求返回三个array,第一个只包含只出现在A中的字符串,
: 第二个只包含只出现在B中的字符串,第三个只包含common字符串
: 然后海量数据下该怎么code。貌似这个电面反馈很好
: onsite:

j**********3
发帖数: 3211
7
有g面说明你很牛了!

【在 g*********e 的大作中提到】
: 另外求湾区各大软件/互联网公司refer! 主要是C++方向
: 搞了几个月就狗狗一家给面试,感觉有点划不来。

j**********3
发帖数: 3211
8
PSDUA都是哪些啊?
j**********3
发帖数: 3211
9
请问店面2,海量数据下怎么code啊?谢谢lz
c********r
发帖数: 107
10
mark
相关主题
最优合并及证明Google intern 面经,回馈版面
An immediate intern position in central new jersey问一个CareerCup上的Google题
问一道题facebook programming challenge难度如何?
进入JobHunting版参与讨论
j**********3
发帖数: 3211
11
onsite 直线最多点那个海量数据怎么做?谢谢lz
g*********e
发帖数: 14401
12

23个x

【在 d******k 的大作中提到】
: a23x1bc,中的23x1是输出23个1,还是1个2和3个1?
g*********e
发帖数: 14401
13

还好吧,没遇到那种npc的题目。还是实力不济啊

【在 b******t 的大作中提到】
: 好难啊
w********s
发帖数: 1570
14
店面第一题有不暴力揭发么?

【在 g*********e 的大作中提到】
: 今天HR打电话来说HC没过,记下来参考
: 电面1:
: 第一个问题记不得了
: 第二个,给一系列string,要求找两个string,使得它们没有共同字符,并且长度乘积
: 最大。好像给了个暴力解
: 电面2:
: 给两个string array A,B,要求返回三个array,第一个只包含只出现在A中的字符串,
: 第二个只包含只出现在B中的字符串,第三个只包含common字符串
: 然后海量数据下该怎么code。貌似这个电面反馈很好
: onsite:

p*****2
发帖数: 21240
15
are you sure? 我没做leetcode之前每次g的店面都能过

【在 j**********3 的大作中提到】
: 有g面说明你很牛了!
j**********3
发帖数: 3211
16
请问这个设计题怎么设计?
完全没头绪,只看到o(1)。。。
给定一个二维矩阵,有update(x,y) 和 sum(x1,y1, x2, y2)两个方法。
怎么设计使得update()比较快?
怎么设计使得sum()比较快?
怎么设计使得两者都reasonable得快?好像最后讨论到n,log(n)的设计
j**********3
发帖数: 3211
17
您是大牛,不能跟您比啊。。

【在 p*****2 的大作中提到】
: are you sure? 我没做leetcode之前每次g的店面都能过
R******9
发帖数: 267
18
PSDUA 是什么啊,跟不上形势了。。

【在 P*****f 的大作中提到】
: 试过 PSDUA这些没?直接网投就应该有面试
R******9
发帖数: 267
19
第三种情况用二维线段树吧

【在 j**********3 的大作中提到】
: 请问这个设计题怎么设计?
: 完全没头绪,只看到o(1)。。。
: 给定一个二维矩阵,有update(x,y) 和 sum(x1,y1, x2, y2)两个方法。
: 怎么设计使得update()比较快?
: 怎么设计使得sum()比较快?
: 怎么设计使得两者都reasonable得快?好像最后讨论到n,log(n)的设计

q****m
发帖数: 177
20
binary index tree

【在 j**********3 的大作中提到】
: 请问这个设计题怎么设计?
: 完全没头绪,只看到o(1)。。。
: 给定一个二维矩阵,有update(x,y) 和 sum(x1,y1, x2, y2)两个方法。
: 怎么设计使得update()比较快?
: 怎么设计使得sum()比较快?
: 怎么设计使得两者都reasonable得快?好像最后讨论到n,log(n)的设计

相关主题
前段时间的面试G家电题
请教一道G家面试题啥叫encode/decode binary tree啊?
F/L/A/G/T/Groupon/Box 贴面经 报offer 回报本版说说自己最近的Microsoft的面试经历+面经
进入JobHunting版参与讨论
t**********h
发帖数: 2273
21
好难,给跪了

【在 g*********e 的大作中提到】
: 今天HR打电话来说HC没过,记下来参考
: 电面1:
: 第一个问题记不得了
: 第二个,给一系列string,要求找两个string,使得它们没有共同字符,并且长度乘积
: 最大。好像给了个暴力解
: 电面2:
: 给两个string array A,B,要求返回三个array,第一个只包含只出现在A中的字符串,
: 第二个只包含只出现在B中的字符串,第三个只包含common字符串
: 然后海量数据下该怎么code。貌似这个电面反馈很好
: onsite:

l*********8
发帖数: 4642
22
请问什么是PSDUA?

【在 P*****f 的大作中提到】
: 试过 PSDUA这些没?直接网投就应该有面试
l*********8
发帖数: 4642
23
mark.
lz继续加油。 其他公司的offer应该不远了。

【在 g*********e 的大作中提到】
: 今天HR打电话来说HC没过,记下来参考
: 电面1:
: 第一个问题记不得了
: 第二个,给一系列string,要求找两个string,使得它们没有共同字符,并且长度乘积
: 最大。好像给了个暴力解
: 电面2:
: 给两个string array A,B,要求返回三个array,第一个只包含只出现在A中的字符串,
: 第二个只包含只出现在B中的字符串,第三个只包含common字符串
: 然后海量数据下该怎么code。貌似这个电面反馈很好
: onsite:

x******1
发帖数: 155
24
谢谢lz面经,下周也要电面G家,希望lz好运!!
R******9
发帖数: 267
25
2xaxxxx 怎么encoder呢?

【在 g*********e 的大作中提到】
: 今天HR打电话来说HC没过,记下来参考
: 电面1:
: 第一个问题记不得了
: 第二个,给一系列string,要求找两个string,使得它们没有共同字符,并且长度乘积
: 最大。好像给了个暴力解
: 电面2:
: 给两个string array A,B,要求返回三个array,第一个只包含只出现在A中的字符串,
: 第二个只包含只出现在B中的字符串,第三个只包含common字符串
: 然后海量数据下该怎么code。貌似这个电面反馈很好
: onsite:

f******n
发帖数: 279
26
mark
S******1
发帖数: 216
27
最后一题难道不是partition吗?
那个decoding有其他规则吗? 输入能包含x吗,12223encoding成13x23不就错了...
g*********e
发帖数: 14401
28

1x2xaxxxx
decoder的规则是遇到数字+x就重复x后面的字符
其实这题那哥们出题时给了一个例子,就是类似“1x2"这种。算是hint了,结果我反问
他为何单个字符也用x,然后自己站在那里呆想。估计留下了不好印象。

【在 R******9 的大作中提到】
: 2xaxxxx 怎么encoder呢?
d******s
发帖数: 274
29
我猜他指 pinterest square dropbox uber airbnb
lol

【在 l*********8 的大作中提到】
: 请问什么是PSDUA?
l*********8
发帖数: 4642
30
2xaxxxx 能不能encode为:
1x2xa4xx

【在 g*********e 的大作中提到】
:
: 1x2xaxxxx
: decoder的规则是遇到数字+x就重复x后面的字符
: 其实这题那哥们出题时给了一个例子,就是类似“1x2"这种。算是hint了,结果我反问
: 他为何单个字符也用x,然后自己站在那里呆想。估计留下了不好印象。

相关主题
g电面G家最新电面
F店面这题咋做, 有点像Run Length encoding, 但又不全是?
问一道Google的题G的一道Onesite题
进入JobHunting版参与讨论
g*********e
发帖数: 14401
31

你对的 我写错了

【在 l*********8 的大作中提到】
: 2xaxxxx 能不能encode为:
: 1x2xa4xx

t*********7
发帖数: 255
32
mark.
l*****a
发帖数: 14598
33
Bless
先顶后看

【在 g*********e 的大作中提到】
: 今天HR打电话来说HC没过,记下来参考
: 电面1:
: 第一个问题记不得了
: 第二个,给一系列string,要求找两个string,使得它们没有共同字符,并且长度乘积
: 最大。好像给了个暴力解
: 电面2:
: 给两个string array A,B,要求返回三个array,第一个只包含只出现在A中的字符串,
: 第二个只包含只出现在B中的字符串,第三个只包含common字符串
: 然后海量数据下该怎么code。貌似这个电面反馈很好
: onsite:

R********e
发帖数: 165
34
给定一个二维矩阵,有update(x,y) 和 sum(x1,y1, x2, y2)两个方法。
怎么设计使得update()比较快?
怎么设计使得sum()比较快?
怎么设计使得两者都reasonable得快?好像最后讨论到n,log(n)的设计
这道题怎么做?
s*****G
发帖数: 1535
35
倒 我怎么记得楼主就是G家的。。
f*******r
发帖数: 976
36
mark
x******0
发帖数: 178
37
1x2 怎么encode?
1x1x2? decoding后面的string会用前面decoded的结果么
1x1x2->1x2->2?
S********e
发帖数: 74
38
我一个朋友也面了第五轮那个题,对的,好像用类似quick select的方法可以解出来

【在 S******1 的大作中提到】
: 最后一题难道不是partition吗?
: 那个decoding有其他规则吗? 输入能包含x吗,12223encoding成13x23不就错了...

Z**n
发帖数: 55
39
mark 楼主加油
m*****n
发帖数: 2152
40
给每个string(最大长度m)用hash,然后对array(长度n)用trie,时间复杂度应该
是O(n*m),比纯暴力O(n*n*m*m)要快不少了。

【在 w********s 的大作中提到】
: 店面第一题有不暴力揭发么?
相关主题
G的一道Onesite题An immediate intern position in central new jersey
SnapChat 面經 + 彙總问一道题
最优合并及证明Google intern 面经,回馈版面
进入JobHunting版参与讨论
p*****2
发帖数: 21240
41

大牛真是out了呀。

【在 l*********8 的大作中提到】
: 请问什么是PSDUA?
c**y
发帖数: 172
42
Can you elaborate?

【在 m*****n 的大作中提到】
: 给每个string(最大长度m)用hash,然后对array(长度n)用trie,时间复杂度应该
: 是O(n*m),比纯暴力O(n*n*m*m)要快不少了。

b*****c
发帖数: 1103
43
留名
l*********8
发帖数: 4642
44
谢谢:)

【在 d******s 的大作中提到】
: 我猜他指 pinterest square dropbox uber airbnb
: lol

l*********8
发帖数: 4642
45
写出来一看,都听说过。 合起来真反应不出来:)

【在 p*****2 的大作中提到】
:
: 大牛真是out了呀。

m*****n
发帖数: 2152
46
所有题都要求写代码吗?
还是只要写算法就行了。

【在 g*********e 的大作中提到】
: 今天HR打电话来说HC没过,记下来参考
: 电面1:
: 第一个问题记不得了
: 第二个,给一系列string,要求找两个string,使得它们没有共同字符,并且长度乘积
: 最大。好像给了个暴力解
: 电面2:
: 给两个string array A,B,要求返回三个array,第一个只包含只出现在A中的字符串,
: 第二个只包含只出现在B中的字符串,第三个只包含common字符串
: 然后海量数据下该怎么code。貌似这个电面反馈很好
: onsite:

m*****n
发帖数: 2152
47
"第二题是二维平面有若干个点,找一个点使得到他们的曼哈顿距离最短。就是找
median
。分析后讲了quick select找median。"
楼主分析的不对吧,这个怎么可能是找median呢?
应该是找离average最近的点,这个点不一定是median。

【在 g*********e 的大作中提到】
: 今天HR打电话来说HC没过,记下来参考
: 电面1:
: 第一个问题记不得了
: 第二个,给一系列string,要求找两个string,使得它们没有共同字符,并且长度乘积
: 最大。好像给了个暴力解
: 电面2:
: 给两个string array A,B,要求返回三个array,第一个只包含只出现在A中的字符串,
: 第二个只包含只出现在B中的字符串,第三个只包含common字符串
: 然后海量数据下该怎么code。貌似这个电面反馈很好
: onsite:

m*****n
发帖数: 2152
48
同问,什么意思啊?update(x,y)是更新x y的位置的element?sum是求和?
matrix本身用什么container,vector >还是array[][]?

【在 j**********3 的大作中提到】
: 请问这个设计题怎么设计?
: 完全没头绪,只看到o(1)。。。
: 给定一个二维矩阵,有update(x,y) 和 sum(x1,y1, x2, y2)两个方法。
: 怎么设计使得update()比较快?
: 怎么设计使得sum()比较快?
: 怎么设计使得两者都reasonable得快?好像最后讨论到n,log(n)的设计

m*****n
发帖数: 2152
49
这个方法不对,只有排序+暴力。

【在 c**y 的大作中提到】
: Can you elaborate?
l*********8
发帖数: 4642
50
是median, 你想想一维的情况

【在 m*****n 的大作中提到】
: "第二题是二维平面有若干个点,找一个点使得到他们的曼哈顿距离最短。就是找
: median
: 。分析后讲了quick select找median。"
: 楼主分析的不对吧,这个怎么可能是找median呢?
: 应该是找离average最近的点,这个点不一定是median。

相关主题
问一个CareerCup上的Google题请教一道G家面试题
facebook programming challenge难度如何?F/L/A/G/T/Groupon/Box 贴面经 报offer 回报本版
前段时间的面试G家电题
进入JobHunting版参与讨论
c****d
发帖数: 116
51
我觉得应该从字符串的尾部开始encoding.所以应该是
2xa4x。
encoding没有歧义, 但是如果想decoding的话, 要
注意处理 'x' 和 #x的情况。

【在 l*********8 的大作中提到】
: 2xaxxxx 能不能encode为:
: 1x2xa4xx

b****f
发帖数: 138
52
Mark
l*********8
发帖数: 4642
53
2xa4x, 如果从头decode的话,就得到aa4x了

【在 c****d 的大作中提到】
: 我觉得应该从字符串的尾部开始encoding.所以应该是
: 2xa4x。
: encoding没有歧义, 但是如果想decoding的话, 要
: 注意处理 'x' 和 #x的情况。

c**y
发帖数: 172
54
For the question below, what is the complexity of the brutal force solution?

【在 g*********e 的大作中提到】
:
: 你对的 我写错了

c****d
发帖数: 116
55
我觉得可以这样做
假定string里面只有0-9, a-z, A-Z这些字符ch.
对字符串i, 建立一个a[ch][i]数组, 比如有
a[0][i] = 1; // if char '0' in string i
a[0][i] = 0; // otherwise
...
a[61][i] = 1; // if char 'Z' in string i
a[61][i] = 0; // otherise
然后都a[62][n]进行处理
for (i = 0; i < n - 1; i++)
{
for (j = i + 1; j < n; j++)
{
for (k = 0; k < 62; k++ )
{
val = val && (a[k][i] ^ a[k][j])
}
if (val)
{
if (max < i * j)
{
max = i * j
and remember i, j
}
}
}
}

【在 c**y 的大作中提到】
: Can you elaborate?
c****d
发帖数: 116
56
所以必须假定原串里面没有x和数字,就像
“abc"abc",没有escape \, 这个是非法的

【在 l*********8 的大作中提到】
: 2xa4x, 如果从头decode的话,就得到aa4x了
h********e
发帖数: 1036
57
好难啊,请问这是本科刚毕业的还是什么其它级别的

【在 g*********e 的大作中提到】
: 今天HR打电话来说HC没过,记下来参考
: 电面1:
: 第一个问题记不得了
: 第二个,给一系列string,要求找两个string,使得它们没有共同字符,并且长度乘积
: 最大。好像给了个暴力解
: 电面2:
: 给两个string array A,B,要求返回三个array,第一个只包含只出现在A中的字符串,
: 第二个只包含只出现在B中的字符串,第三个只包含common字符串
: 然后海量数据下该怎么code。貌似这个电面反馈很好
: onsite:

c**y
发帖数: 172
58
What is the definition of 字符串i? Is it array[0,...,i - 1]?
What is the complexity of building a[62][n]?

【在 c****d 的大作中提到】
: 我觉得可以这样做
: 假定string里面只有0-9, a-z, A-Z这些字符ch.
: 对字符串i, 建立一个a[ch][i]数组, 比如有
: a[0][i] = 1; // if char '0' in string i
: a[0][i] = 0; // otherwise
: ...
: a[61][i] = 1; // if char 'Z' in string i
: a[61][i] = 0; // otherise
: 然后都a[62][n]进行处理
: for (i = 0; i < n - 1; i++)

k**8
发帖数: 186
59
.....好难
LZ你申请的啥level的啊
c****d
发帖数: 116
60
for example:
char * string[] = {
"abcdef",
"cdefg",
"zvsm123"
"Zxy"
};
string[0]: "abcdef"
string[1]: "cdefg"
The complexity of building a[62][n] is O(nm), assuming n strings
, and maximum length of string is m, because you need scan all
elements.
Note: in code that I pasted in earlier, internal loop(62) can
exit earlier if find zero.

【在 c**y 的大作中提到】
: What is the definition of 字符串i? Is it array[0,...,i - 1]?
: What is the complexity of building a[62][n]?

相关主题
啥叫encode/decode binary tree啊?F店面
说说自己最近的Microsoft的面试经历+面经问一道Google的题
g电面G家最新电面
进入JobHunting版参与讨论
c**y
发帖数: 172
61
多谢说明!

【在 c****d 的大作中提到】
: for example:
: char * string[] = {
: "abcdef",
: "cdefg",
: "zvsm123"
: "Zxy"
: };
: string[0]: "abcdef"
: string[1]: "cdefg"
: The complexity of building a[62][n] is O(nm), assuming n strings

t*********l
发帖数: 844
62
还是不知道什么是PSDUA

【在 p*****2 的大作中提到】
:
: 大牛真是out了呀。

m*****n
发帖数: 2152
63
你这个还是brute force啊。
用bitset<62> key 更好一点吧,或者干脆用unsigned long key,存hash。
用unsigned int value存字长,然后按value排序,从最大开始loop。
如果字长小于sqrt(max),loop就可以停了。
这样的话,最差也是O(n*n*m),最好的话O(n*log(n)*m)。

【在 c****d 的大作中提到】
: 我觉得可以这样做
: 假定string里面只有0-9, a-z, A-Z这些字符ch.
: 对字符串i, 建立一个a[ch][i]数组, 比如有
: a[0][i] = 1; // if char '0' in string i
: a[0][i] = 0; // otherwise
: ...
: a[61][i] = 1; // if char 'Z' in string i
: a[61][i] = 0; // otherise
: 然后都a[62][n]进行处理
: for (i = 0; i < n - 1; i++)

t*********l
发帖数: 844
64
给两个string array A,B,要求返回三个array,第一个只包含只出现在A中的字符串,
第二个只包含只出现在B中的字符串,第三个只包含common字符串
然后海量数据下该怎么code。貌似这个电面反馈很好
这个海量数据是指单机有很多数据,还是要用很多机器并行处理?
当有很多数据时,是每两两字符串都要返回三个数组吗,还是所有数据只跟同一个数组
B比较?
返回的字符串可以去掉重复字符吗?还是必须按原串出现次序全部输出,包括重复字符?

【在 g*********e 的大作中提到】
: 今天HR打电话来说HC没过,记下来参考
: 电面1:
: 第一个问题记不得了
: 第二个,给一系列string,要求找两个string,使得它们没有共同字符,并且长度乘积
: 最大。好像给了个暴力解
: 电面2:
: 给两个string array A,B,要求返回三个array,第一个只包含只出现在A中的字符串,
: 第二个只包含只出现在B中的字符串,第三个只包含common字符串
: 然后海量数据下该怎么code。貌似这个电面反馈很好
: onsite:

m*****n
发帖数: 2152
65
"第二题是二维平面有若干个点,找一个点使得到他们的曼哈顿距离最短。就是找
median
。分析后讲了quick select找median。
给定一个二维矩阵,有update(x,y) 和 sum(x1,y1, x2, y2)两个方法。
怎么设计使得update()比较快?
怎么设计使得sum()比较快?
怎么设计使得两者都reasonable得快?好像最后讨论到n,log(n)的设计"
1.怎么设计使得update()比较快?
就是普通的matrix最快O(1)。
2. 怎么设计使得sum()比较快?
1D Binary Index tree, O(1)?
3. 怎么设计使得两者都reasonable得快?
2D Binary Index Tree?
这个好像是m log(n) * log(n)吧。
o***g
发帖数: 2784
66
这个sum()是啥意思?输入是两个点,要得到什么?

【在 m*****n 的大作中提到】
: "第二题是二维平面有若干个点,找一个点使得到他们的曼哈顿距离最短。就是找
: median
: 。分析后讲了quick select找median。
: 给定一个二维矩阵,有update(x,y) 和 sum(x1,y1, x2, y2)两个方法。
: 怎么设计使得update()比较快?
: 怎么设计使得sum()比较快?
: 怎么设计使得两者都reasonable得快?好像最后讨论到n,log(n)的设计"
: 1.怎么设计使得update()比较快?
: 就是普通的matrix最快O(1)。
: 2. 怎么设计使得sum()比较快?

m*****n
发帖数: 2152
67
矩阵内所有element的和。

【在 o***g 的大作中提到】
: 这个sum()是啥意思?输入是两个点,要得到什么?
l*****a
发帖数: 14598
68
那update(x,y)的意思是更新一个点,还是其他含义

【在 m*****n 的大作中提到】
: 矩阵内所有element的和。
1 (共1页)
进入JobHunting版参与讨论
相关主题
啥叫encode/decode binary tree啊?SnapChat 面經 + 彙總
说说自己最近的Microsoft的面试经历+面经最优合并及证明
g电面An immediate intern position in central new jersey
F店面问一道题
问一道Google的题Google intern 面经,回馈版面
G家最新电面问一个CareerCup上的Google题
这题咋做, 有点像Run Length encoding, 但又不全是?facebook programming challenge难度如何?
G的一道Onesite题前段时间的面试
相关话题的讨论汇总
话题: string话题: 使得话题: 设计话题: 字符串话题: sum