《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 2896|回复: 26
收起左侧

Qumulo Phone Interview

[复制链接] |试试Instant~ |关注本帖
hercule24 发表于 2016-2-5 09:25:07 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Qumulo - 网上海投 - 技术电面 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
今天结束了Qumulo,地里好像没有出现过这题,来贡献一下跪经。。。
给两个list of integers,求这两个list的intersection。

比方说:
[4, 2, 1, 9, 8]
[1, 3, 5, 8, 7]
返回
[1, 8]
. visit 1point3acres.com for more.
我一开始只接丢进了unordered_set里然后,写了个O(n)的。然后小哥follow up说如果两个list都非常大,有trillion数量级的,会怎么样。
答无法塞进memory里,问怎么办。我有点慌了,支支吾吾说了一些paging之类的,然后小哥最后提醒说可以先sort完,然后保持两个pointer, 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
一直向前移动。

最后小哥又出了一道题,说给了这两个list的iterator,实现一个iterator能够iterate这两个list的intersection。比方说:

IntersectionIterator it = new IntersectionIterator();
while (it.hasNext()) System.out.println(it.next());


就会依次输出: 1, 8

我手忙脚乱写了一个buggy版本。。。最后时间不够了
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

评分

1

查看全部评分

hotinherre 发表于 2016-2-17 13:49:19 | 显示全部楼层
  1. public class IntersectionIterator{
  2.         int nextNum;   // record the number of the next iterator. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  3.         boolean callHasNext; // check if call hasNext function before calling next function
  4.         Iterator itr1;
  5.         Iterator itr2;
  6.        
  7.         public IntersectionIterator(Iterator itr1, Iterator itr2){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  8.                 this.itr1 = itr1;  //Iterator itr = list.Iterator();
  9.                 this.itr2 = itr2;
  10.         }
  11. . 1point3acres.com/bbs
  12.         // check if hasNext, and update the nextNum. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  13.         public boolean hasNext(){
  14.                 if(!itr1.hasNext() || !itr2.hasNext()) return false;
  15.                 int num1 = itr1.next();
  16.                 int num2 = itr2.next();
  17.                 // keep move two iterator, until two numers are same or one of the iterator doesn't have next number.
  18.                 while(true){
  19.                         if(num1 == num2){
  20.                                 nextNum = num1;
  21.                                 return true;. 1point3acres.com/bbs
  22.                         }
  23.                         // move the iterator of the smaller number forward
  24.                         else if(num1 < num2){
  25.                                 if(!itr1.hasNext()) return false;
  26.                                 num1 = itr1.next();. 1point3acres.com/bbs
  27.                         }
  28.                         else{
  29.                                 if(!itr2.hasNext()) return false;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  30.                                 num2 = itr2.next();
  31.                         }
  32.                 }
  33.         }
  34. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  35.         public int next(){
  36.                 if(!callHasNext){
  37.                         // if user call next funtion but no more intersection number. 1point3acres.com/bbs
  38.                         if(!hasNext()){
  39.                                 System.out.println("No more intersection number!");
  40.                                 return Integer.MIN_VALUE;.1point3acres缃
  41.                         }
  42.                         else{. more info on 1point3acres.com
  43.                                 callHasNext = false; //reset the callHasNext
  44.                                 return nextNum;
  45.                         }
  46.                 }
  47.                 else{
  48.                         callHasNext = false; // reset
  49.                         return nextNum;
  50.                 }. From 1point 3acres bbs
  51.         }. 鍥磋鎴戜滑@1point 3 acres
  52. }
复制代码
Iterator 的代码我写了一下, 大家看看对不对. from: 1point3acres.com/bbs

回复 支持 2 反对 0

使用道具 举报

aifer 发表于 2016-2-22 06:49:33 | 显示全部楼层
给一个我写的例子吧。
  1. public class IntersectionIterator implements Iterator<Integer>{

  2.         private Iterator<Integer> iter1;
  3.         private Iterator<Integer> iter2;
  4.         private Integer item;        // cache the number appeared in both lists
  5.        
  6.         public IntersectionIterator(Iterator<Integer> a, Iterator<Integer> b){
  7.                 iter1 = a;
  8.                 iter2 = b;
  9.                 item = null;
  10.                 cacheNext();
  11.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  12.         @Override.鏈枃鍘熷垱鑷1point3acres璁哄潧
  13.         public boolean hasNext() {. 1point 3acres 璁哄潧
  14.                 return item != null;
  15.         }

  16.         @Override
  17.         public Integer next() {
  18.                 Integer cur = item;
  19.                 item = null;
  20.                 cacheNext();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  21.                 return cur;
  22.         }
  23.        
  24.         /*
  25.          * cache number appeared in both lists.
  26.          */. From 1point 3acres bbs
  27.         private void cacheNext(){
  28.                 if(iter1.hasNext() && iter2.hasNext()){
  29.                         Integer x = iter1.next();
  30.                         Integer y = iter2.next();
  31.                         while(x!= null && y != null && x != y) {. 1point 3acres 璁哄潧
  32.                                 if(x < y && iter1.hasNext()) x = iter1.next();. visit 1point3acres.com for more.
  33.                                 else if(x < y) x = null;
  34.                                 else if(x > y && iter2.hasNext()) y = iter2.next();. From 1point 3acres bbs
  35.                                 else if( x> y) y = null;
  36.                         }
  37.                         // find the first repeated number and cache it.. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  38.                         if(x != null && y != null && x.equals(y)) item = x;. 1point3acres.com/bbs
  39.                 }
  40.         }
  41. }
复制代码
回复 支持 1 反对 0

使用道具 举报

hotinherre 发表于 2016-2-5 13:32:43 | 显示全部楼层
看来qumolo面试真的 不简单啊。。。 谢谢楼主分享了! 我是投实习的 但是给的我也是全职的oa 说实习全职一样对待。。  对了 你是直接开始做题么? 多久的面试?
回复 支持 反对

使用道具 举报

 楼主| hercule24 发表于 2016-2-5 13:45:15 | 显示全部楼层
hotinherre 发表于 2016-2-5 13:32
看来qumolo面试真的 不简单啊。。。 谢谢楼主分享了! 我是投实习的 但是给的我也是全职的oa 说实习全职一 ...

我提前把网上那四道OA题做了再去的 都有快一个月了吧
回复 支持 反对

使用道具 举报

starfalling 发表于 2016-2-5 13:51:05 | 显示全部楼层
这是家神奇的小公司,看到glassdoor上面一排跪经https://www.glassdoor.com/Interview/Qumulo-Interview-Questions-E678884.htm。package挺给力的貌似。
回复 支持 反对

使用道具 举报

 楼主| hercule24 发表于 2016-2-6 00:17:34 | 显示全部楼层
starfalling 发表于 2016-2-5 13:51
这是家神奇的小公司,看到glassdoor上面一排跪经https://www.glassdoor.com/Interview/Qumulo-Int ...

所以进去应该很难吧
回复 支持 反对

使用道具 举报

starfalling 发表于 2016-2-6 04:39:30 | 显示全部楼层
hercule24 发表于 2016-2-6 00:17
所以进去应该很难吧
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
感觉应该挺难的,主要是规模小不怎么招人。然后package又给力,就更难进了。
回复 支持 反对

使用道具 举报

blactangeri 发表于 2016-2-7 10:46:12 | 显示全部楼层
请问lz
第二问怎么做的谢谢
回复 支持 反对

使用道具 举报

 楼主| hercule24 发表于 2016-2-7 12:35:38 | 显示全部楼层
blactangeri 发表于 2016-2-7 10:46
请问lz
第二问怎么做的谢谢

第二题也是sorted的,所以也是按照当前两个iterator指向的值比较,向前移动小的那个的iterator
回复 支持 反对

使用道具 举报

丢丢棠线 发表于 2016-2-17 02:36:36 | 显示全部楼层
hercule24 发表于 2016-2-7 12:35. more info on 1point3acres.com
第二题也是sorted的,所以也是按照当前两个iterator指向的值比较,向前移动小的那个的iterator
.1point3acres缃
楼主 请问一下 第二问的意思是
public IntersectionIterator findIntersection(Iterator i1,Iretator i2){
}. 鍥磋鎴戜滑@1point 3 acres
这样子么?.1point3acres缃
我不太懂 多谢多谢
回复 支持 反对

使用道具 举报

 楼主| hercule24 发表于 2016-2-17 02:49:13 | 显示全部楼层
丢丢棠线 发表于 2016-2-17 02:36
楼主 请问一下 第二问的意思是
public IntersectionIterator findIntersection(Iterator i1,Iretator i2 ...

应该是 IntersectionIterator (Iterator i1,Iretator i2) {
}
这样子的吧,这样子就是实现一个类了
回复 支持 反对

使用道具 举报

丢丢棠线 发表于 2016-2-17 04:45:26 | 显示全部楼层
hercule24 发表于 2016-2-17 02:49
应该是 IntersectionIterator (Iterator i1,Iretator i2) {
}
这样子的吧,这样子就是实现一个类了

多谢楼主! 那个请问能给个邮箱么 我觉得我写的还是感觉有点问题 能跟你交流一下么 马上就要电面了 有点捉急!谢谢!!
回复 支持 反对

使用道具 举报

JamesJi 发表于 2016-2-17 04:59:58 | 显示全部楼层
感觉题目很常规啊
回复 支持 反对

使用道具 举报

丢丢棠线 发表于 2016-2-17 05:03:56 | 显示全部楼层
JamesJi 发表于 2016-2-17 04:59
感觉题目很常规啊

唔 。。。那么 可否指导一下 iterator 那个。。。
irisleaving@gmail.com

跪谢!
回复 支持 反对

使用道具 举报

JamesJi 发表于 2016-2-17 05:06:38 | 显示全部楼层
丢丢棠线 发表于 2016-2-16 16:03
唔 。。。那么 可否指导一下 iterator 那个。。。

楼主不是说了做法了吗
回复 支持 反对

使用道具 举报

hotinherre 发表于 2016-2-17 13:15:39 | 显示全部楼层
qumulo 好喜欢问两个list找相同呀, 你们怎么都那么喜欢map...  我看到另外一个帖子小哥做的找string也是上来就map..
回复 支持 反对

使用道具 举报

aifer 发表于 2016-2-22 06:41:50 | 显示全部楼层
hotinherre 发表于 2016-2-17 13:49
Iterator 的代码我写了一下, 大家看看对不对

你的这个有Bug吧。如果连续调用hasNext()函数的话,而不调用next(),你的写法会刷新nextNum的值。
比如楼主的例子。调用两次hasNext()之后,在next() 你这个返回的就是8不是1了。而且你的callHasNext变量也没有设置过true??
回复 支持 反对

使用道具 举报

shiloh00 发表于 2016-2-23 13:18:47 | 显示全部楼层
谢唐神!马上面qumulo
回复 支持 反对

使用道具 举报

benjaminxu 发表于 2016-2-24 03:04:26 | 显示全部楼层
shiloh00 发表于 2016-2-23 13:18
谢唐神!马上面qumulo

can 姐加油啊
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-22 22:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表