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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 另外求湾区各大软件/互联网公司refer! 主要是C++方向 : 搞了几个月就狗狗一家给面试,感觉有点划不来。
|
g*********e 发帖数: 14401 | 4
简历上写什么比较容易拿到面试?光C++ LINUX之类的貌似不管用
【在 P*****f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 试过 PSDUA这些没?直接网投就应该有面试
|
d******k 发帖数: 32 | 5 a23x1bc,中的23x1是输出23个1,还是1个2和3个1?
【在 g*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 今天HR打电话来说HC没过,记下来参考 : 电面1: : 第一个问题记不得了 : 第二个,给一系列string,要求找两个string,使得它们没有共同字符,并且长度乘积 : 最大。好像给了个暴力解 : 电面2: : 给两个string array A,B,要求返回三个array,第一个只包含只出现在A中的字符串, : 第二个只包含只出现在B中的字符串,第三个只包含common字符串 : 然后海量数据下该怎么code。貌似这个电面反馈很好 : onsite:
|
b******t 发帖数: 965 | 6 好难啊
【在 g*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 今天HR打电话来说HC没过,记下来参考 : 电面1: : 第一个问题记不得了 : 第二个,给一系列string,要求找两个string,使得它们没有共同字符,并且长度乘积 : 最大。好像给了个暴力解 : 电面2: : 给两个string array A,B,要求返回三个array,第一个只包含只出现在A中的字符串, : 第二个只包含只出现在B中的字符串,第三个只包含common字符串 : 然后海量数据下该怎么code。貌似这个电面反馈很好 : onsite:
|
j**********3 发帖数: 3211 | 7 有g面说明你很牛了!
【在 g*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 另外求湾区各大软件/互联网公司refer! 主要是C++方向 : 搞了几个月就狗狗一家给面试,感觉有点划不来。
|
j**********3 发帖数: 3211 | |
j**********3 发帖数: 3211 | |
c********r 发帖数: 107 | |
|
|
j**********3 发帖数: 3211 | 11 onsite 直线最多点那个海量数据怎么做?谢谢lz |
g*********e 发帖数: 14401 | 12
23个x
【在 d******k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : a23x1bc,中的23x1是输出23个1,还是1个2和3个1?
|
g*********e 发帖数: 14401 | 13
还好吧,没遇到那种npc的题目。还是实力不济啊
【在 b******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好难啊
|
w********s 发帖数: 1570 | 14 店面第一题有不暴力揭发么?
【在 g*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 今天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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : are you sure? 我没做leetcode之前每次g的店面都能过
|
R******9 发帖数: 267 | 18 PSDUA 是什么啊,跟不上形势了。。
【在 P*****f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 试过 PSDUA这些没?直接网投就应该有面试
|
R******9 发帖数: 267 | 19 第三种情况用二维线段树吧
【在 j**********3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请问这个设计题怎么设计? : 完全没头绪,只看到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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请问这个设计题怎么设计? : 完全没头绪,只看到o(1)。。。 : 给定一个二维矩阵,有update(x,y) 和 sum(x1,y1, x2, y2)两个方法。 : 怎么设计使得update()比较快? : 怎么设计使得sum()比较快? : 怎么设计使得两者都reasonable得快?好像最后讨论到n,log(n)的设计
|
|
|
t**********h 发帖数: 2273 | 21 好难,给跪了
【在 g*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 今天HR打电话来说HC没过,记下来参考 : 电面1: : 第一个问题记不得了 : 第二个,给一系列string,要求找两个string,使得它们没有共同字符,并且长度乘积 : 最大。好像给了个暴力解 : 电面2: : 给两个string array A,B,要求返回三个array,第一个只包含只出现在A中的字符串, : 第二个只包含只出现在B中的字符串,第三个只包含common字符串 : 然后海量数据下该怎么code。貌似这个电面反馈很好 : onsite:
|
l*********8 发帖数: 4642 | 22 请问什么是PSDUA?
【在 P*****f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 试过 PSDUA这些没?直接网投就应该有面试
|
l*********8 发帖数: 4642 | 23 mark.
lz继续加油。 其他公司的offer应该不远了。
【在 g*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 今天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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 今天HR打电话来说HC没过,记下来参考 : 电面1: : 第一个问题记不得了 : 第二个,给一系列string,要求找两个string,使得它们没有共同字符,并且长度乘积 : 最大。好像给了个暴力解 : 电面2: : 给两个string array A,B,要求返回三个array,第一个只包含只出现在A中的字符串, : 第二个只包含只出现在B中的字符串,第三个只包含common字符串 : 然后海量数据下该怎么code。貌似这个电面反馈很好 : onsite:
|
f******n 发帖数: 279 | |
S******1 发帖数: 216 | 27 最后一题难道不是partition吗?
那个decoding有其他规则吗? 输入能包含x吗,12223encoding成13x23不就错了... |
g*********e 发帖数: 14401 | 28
1x2xaxxxx
decoder的规则是遇到数字+x就重复x后面的字符
其实这题那哥们出题时给了一个例子,就是类似“1x2"这种。算是hint了,结果我反问
他为何单个字符也用x,然后自己站在那里呆想。估计留下了不好印象。
【在 R******9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 2xaxxxx 怎么encoder呢?
|
d******s 发帖数: 274 | 29 我猜他指 pinterest square dropbox uber airbnb
lol
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请问什么是PSDUA?
|
l*********8 发帖数: 4642 | 30 2xaxxxx 能不能encode为:
1x2xa4xx
【在 g*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 1x2xaxxxx : decoder的规则是遇到数字+x就重复x后面的字符 : 其实这题那哥们出题时给了一个例子,就是类似“1x2"这种。算是hint了,结果我反问 : 他为何单个字符也用x,然后自己站在那里呆想。估计留下了不好印象。
|
|
|
g*********e 发帖数: 14401 | 31
你对的 我写错了
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 2xaxxxx 能不能encode为: : 1x2xa4xx
|
t*********7 发帖数: 255 | |
l*****a 发帖数: 14598 | 33 Bless
先顶后看
【在 g*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 今天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 | |
f*******r 发帖数: 976 | |
x******0 发帖数: 178 | 37 1x2 怎么encode?
1x1x2? decoding后面的string会用前面decoded的结果么
1x1x2->1x2->2? |
S********e 发帖数: 74 | 38 我一个朋友也面了第五轮那个题,对的,好像用类似quick select的方法可以解出来
【在 S******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最后一题难道不是partition吗? : 那个decoding有其他规则吗? 输入能包含x吗,12223encoding成13x23不就错了...
|
Z**n 发帖数: 55 | |
m*****n 发帖数: 2152 | 40 给每个string(最大长度m)用hash,然后对array(长度n)用trie,时间复杂度应该
是O(n*m),比纯暴力O(n*n*m*m)要快不少了。
【在 w********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 店面第一题有不暴力揭发么?
|
|
|
p*****2 发帖数: 21240 | 41
大牛真是out了呀。
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请问什么是PSDUA?
|
c**y 发帖数: 172 | 42 Can you elaborate?
【在 m*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给每个string(最大长度m)用hash,然后对array(长度n)用trie,时间复杂度应该 : 是O(n*m),比纯暴力O(n*n*m*m)要快不少了。
|
b*****c 发帖数: 1103 | |
l*********8 发帖数: 4642 | 44 谢谢:)
【在 d******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我猜他指 pinterest square dropbox uber airbnb : lol
|
l*********8 发帖数: 4642 | 45 写出来一看,都听说过。 合起来真反应不出来:)
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 大牛真是out了呀。
|
m*****n 发帖数: 2152 | 46 所有题都要求写代码吗?
还是只要写算法就行了。
【在 g*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 今天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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 今天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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请问这个设计题怎么设计? : 完全没头绪,只看到o(1)。。。 : 给定一个二维矩阵,有update(x,y) 和 sum(x1,y1, x2, y2)两个方法。 : 怎么设计使得update()比较快? : 怎么设计使得sum()比较快? : 怎么设计使得两者都reasonable得快?好像最后讨论到n,log(n)的设计
|
m*****n 发帖数: 2152 | 49 这个方法不对,只有排序+暴力。
【在 c**y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Can you elaborate?
|
l*********8 发帖数: 4642 | 50 是median, 你想想一维的情况
【在 m*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : "第二题是二维平面有若干个点,找一个点使得到他们的曼哈顿距离最短。就是找 : median : 。分析后讲了quick select找median。" : 楼主分析的不对吧,这个怎么可能是找median呢? : 应该是找离average最近的点,这个点不一定是median。
|
|
|
c****d 发帖数: 116 | 51 我觉得应该从字符串的尾部开始encoding.所以应该是
2xa4x。
encoding没有歧义, 但是如果想decoding的话, 要
注意处理 'x' 和 #x的情况。
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 2xaxxxx 能不能encode为: : 1x2xa4xx
|
b****f 发帖数: 138 | |
l*********8 发帖数: 4642 | 53 2xa4x, 如果从头decode的话,就得到aa4x了
【在 c****d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得应该从字符串的尾部开始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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 你对的 我写错了
|
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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Can you elaborate?
|
c****d 发帖数: 116 | 56 所以必须假定原串里面没有x和数字,就像
“abc"abc",没有escape \, 这个是非法的
【在 l*********8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 2xa4x, 如果从头decode的话,就得到aa4x了
|
h********e 发帖数: 1036 | 57 好难啊,请问这是本科刚毕业的还是什么其它级别的
【在 g*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 今天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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得可以这样做 : 假定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 | |
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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : What is the definition of 字符串i? Is it array[0,...,i - 1]? : What is the complexity of building a[62][n]?
|
|
|
c**y 发帖数: 172 | 61 多谢说明!
【在 c****d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 大牛真是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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得可以这样做 : 假定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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 今天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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : "第二题是二维平面有若干个点,找一个点使得到他们的曼哈顿距离最短。就是找 : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个sum()是啥意思?输入是两个点,要得到什么?
|
l*****a 发帖数: 14598 | 68 那update(x,y)的意思是更新一个点,还是其他含义
【在 m*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 矩阵内所有element的和。
|