logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
T家一面
avatar
T家一面# JobHunting - 待字闺中
c*5
1 楼
一个美国小伙给电面的，问了点数据库的知识，解释下什么是Normalization。
编程题是merge k个长度均为n的sorted的数组，觉得写得不是特别好，后来上网查了下
，比较好
的方法好像有两种，一种是用一个min-heap，还有一种是分成k/2个组，两两归并，然
后再把结果两两归并，直到得到最终结果，时间复杂度应该是O(knlog(k))不过还是给
过了。二面约在了下周一，求bless~~
avatar
h*n
2 楼
数组是sort的吗，另外对时间和内存有要求么？
avatar
c*5
3 楼
数组的sorted的，对时间和内存没有要求。

【在 h****n 的大作中提到】
: 数组是sort的吗，另外对时间和内存有要求么？
avatar
c*5
4 楼
一个美国小伙给电面的，问了点数据库的知识，解释下什么是Normalization。
编程题是merge k个长度均为n的sorted的数组，觉得写得不是特别好，后来上网查了下
，比较好
的方法好像有两种，一种是用一个min-heap，还有一种是分成k/2个组，两两归并，然
后再把结果两两归并，直到得到最终结果，时间复杂度应该是O(knlog(k))不过还是给
过了。二面约在了下周一，求bless~~
avatar
h*n
5 楼
数组是sort的吗，另外对时间和内存有要求么？
avatar
c*5
6 楼
数组的sorted的，对时间和内存没有要求。

【在 h****n 的大作中提到】
: 数组是sort的吗，另外对时间和内存有要求么？
avatar
j*2
7 楼
我怎么觉得这个两两归并有点荒谬，k个数列还不是要比k-1次，哪会省？

【在 c******5 的大作中提到】
: 一个美国小伙给电面的，问了点数据库的知识，解释下什么是Normalization。
: 编程题是merge k个长度均为n的sorted的数组，觉得写得不是特别好，后来上网查了下
: ，比较好
: 的方法好像有两种，一种是用一个min-heap，还有一种是分成k/2个组，两两归并，然
: 后再把结果两两归并，直到得到最终结果，时间复杂度应该是O(knlog(k))不过还是给
: 过了。二面约在了下周一，求bless~~
avatar
r*h
8 楼
两两归并的思路更方便使用多线程吧？

【在 j******2 的大作中提到】
: 我怎么觉得这个两两归并有点荒谬，k个数列还不是要比k-1次，哪会省？
avatar
e*s
9 楼
两两归并是不是可以MapReduce?
avatar
j*g
10 楼
请问LZ T家是指哪家？Bless~
avatar
c*t
11 楼
比较lg(k)次，和用heap一样的时间复杂度O(nklog(k))
天晴说的多线程有道理

【在 j******2 的大作中提到】
: 我怎么觉得这个两两归并有点荒谬，k个数列还不是要比k-1次，哪会省？
avatar
z*o
12 楼
tmobile ?

【在 j********g 的大作中提到】
: 请问LZ T家是指哪家？Bless~
avatar
n*w
13 楼
如果两两归并
比较总次数是 k*n*lg（k）（每层都是kn次比较，lgk层）
一次接一个的归并
比较总次数是 2n + 3n +... + kn = O(k^2*n) > k*n*lg（k）
当k很大的时候lgk比k小得多

【在 j******2 的大作中提到】
: 我怎么觉得这个两两归并有点荒谬，k个数列还不是要比k-1次，哪会省？
avatar
s*n
14 楼
两两归并还是 O(k*n*ｋ)，lgk 层没错，但是每层从 n, 2n, 4n...递增..所以比较次
数没有减少，两两归并用recursive代码比较好写，但是空间复杂度就不好说了

【在 n*******w 的大作中提到】
: 如果两两归并
: 比较总次数是 k*n*lg（k）（每层都是kn次比较，lgk层）
: 一次接一个的归并
: 比较总次数是 2n + 3n +... + kn = O(k^2*n) > k*n*lg（k）
: 当k很大的时候lgk比k小得多
avatar
s*5
15 楼
这道题可以看出，很多人的基本算术都不行。
avatar
n*w
16 楼
你这样的话归并排序变成k^2了，应该不是。n=1退化成基本的归并排序。
具体的计算式应该是
sum {(2^i*n) * (k/2^i)}
i=[1, lgk]

【在 s*******n 的大作中提到】
: 两两归并还是 O(k*n*ｋ)，lgk 层没错，但是每层从 n, 2n, 4n...递增..所以比较次
: 数没有减少，两两归并用recursive代码比较好写，但是空间复杂度就不好说了
avatar
t*h
17 楼
你这个2^i不就抵消了吗 和上面的什么区别？ 貌似结果和heap是一样的

【在 n*******w 的大作中提到】
: 你这样的话归并排序变成k^2了，应该不是。n=1退化成基本的归并排序。
: 具体的计算式应该是
: sum {(2^i*n) * (k/2^i)}
: i=[1, lgk]
avatar
j*2
18 楼
编程题就是基本算术，没啥别的

【在 s***5 的大作中提到】
: 这道题可以看出，很多人的基本算术都不行。
avatar
n*w
19 楼
对的。是和sumperman 解释为什么是nklgk

【在 t*********h 的大作中提到】
: 你这个2^i不就抵消了吗 和上面的什么区别？ 貌似结果和heap是一样的
相关阅读
【收费的technical test习题的网站叫什么？】报道：在美国，移民比本国人容易找工作How long does VSC process H1B file?有没有了解morgan stanley的？？运车时大家都在车里放东西么？Resume 问题请教加州contract的software engineer工资一般是多少？Offer bargin求bloomberg onsite 面试时间选择建议EE/CS大牛们帮忙看看: Intel Lab 怎么样公司律师说给我现在办H1B申请，starting date是四月中旬，这个保险嘛？Wireless Test Engineer at Denver电面怎么coding？问个碰到的c语言面试题C++ 面试题请问从F1直接申请H1如何 serialization 和deserialization hash table ？有一个透平机械方向（最好是压缩机）的工作机会 (转载)关于遍历二叉树的复杂度bay area jobs for software engineer
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。