10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 2807|回复: 26
收起左侧

Qumulo Phone Interview

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

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

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

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

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

比方说:
.鏈枃鍘熷垱鑷1point3acres璁哄潧[4, 2, 1, 9, 8]
[1, 3, 5, 8, 7]
返回.鏈枃鍘熷垱鑷1point3acres璁哄潧
[1, 8]

我一开始只接丢进了unordered_set里然后,写了个O(n)的。然后小哥follow up说如果两个list都非常大,有trillion数量级的,会怎么样。
答无法塞进memory里,问怎么办。我有点慌了,支支吾吾说了一些paging之类的,然后小哥最后提醒说可以先sort完,然后保持两个pointer,
一直向前移动。
. From 1point 3acres bbs. 1point 3acres 璁哄潧
最后小哥又出了一道题,说给了这两个list的iterator,实现一个iterator能够iterate这两个list的intersection。比方说:
. Waral 鍗氬鏈夋洿澶氭枃绔,
IntersectionIterator it = new IntersectionIterator();
while (it.hasNext()) System.out.println(it.next());. more info on 1point3acres.com


就会依次输出: 1, 8
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我手忙脚乱写了一个buggy版本。。。最后时间不够了. more info on 1point3acres.com

评分

1

查看全部评分

hotinherre 发表于 2016-2-17 13:49:19 | 显示全部楼层
  1. public class IntersectionIterator{
  2.         int nextNum;   // record the number of the next iterator. 1point 3acres 璁哄潧
  3.         boolean callHasNext; // check if call hasNext function before calling next function. Waral 鍗氬鏈夋洿澶氭枃绔,
  4.         Iterator itr1;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  5.         Iterator itr2;
  6.        
    . more info on 1point3acres.com
  7.         public IntersectionIterator(Iterator itr1, Iterator itr2){
  8.                 this.itr1 = itr1;  //Iterator itr = list.Iterator();
  9.                 this.itr2 = itr2;
  10.         }

  11.         // check if hasNext, and update the nextNum
  12.         public boolean hasNext(){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  13.                 if(!itr1.hasNext() || !itr2.hasNext()) return false;
  14.                 int num1 = itr1.next();
  15.                 int num2 = itr2.next();
  16.                 // keep move two iterator, until two numers are same or one of the iterator doesn't have next number.
  17.                 while(true){
  18.                         if(num1 == num2){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  19.                                 nextNum = num1;
  20.                                 return true;
  21.                         }
  22.                         // move the iterator of the smaller number forward
  23.                         else if(num1 < num2){
  24.                                 if(!itr1.hasNext()) return false;
  25.                                 num1 = itr1.next();
  26.                         }
  27.                         else{
  28.                                 if(!itr2.hasNext()) return false;
  29.                                 num2 = itr2.next();. more info on 1point3acres.com
  30.                         }
  31.                 }. more info on 1point3acres.com
  32.         }

  33.         public int next(){
  34.                 if(!callHasNext){
  35.                         // if user call next funtion but no more intersection number
  36.                         if(!hasNext()){
  37.                                 System.out.println("No more intersection number!");
  38.                                 return Integer.MIN_VALUE;
  39.                         }
  40.                         else{
  41.                                 callHasNext = false; //reset the callHasNext.鐣欏璁哄潧-涓浜-涓夊垎鍦
  42.                                 return nextNum;
  43.                         }
  44.                 }
  45.                 else{. from: 1point3acres.com/bbs
  46.                         callHasNext = false; // reset 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  47.                         return nextNum;. 1point3acres.com/bbs
  48.                 }
  49.         }-google 1point3acres
  50. }
复制代码
Iterator 的代码我写了一下, 大家看看对不对

回复 支持 2 反对 0

使用道具 举报

aifer 发表于 2016-2-22 06:49:33 | 显示全部楼层
给一个我写的例子吧。
  1. public class IntersectionIterator implements Iterator<Integer>{. from: 1point3acres.com/bbs
  2. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  3.         private Iterator<Integer> iter1;
  4.         private Iterator<Integer> iter2;
  5.         private Integer item;        // cache the number appeared in both lists
  6.        
  7.         public IntersectionIterator(Iterator<Integer> a, Iterator<Integer> b){
  8.                 iter1 = a;
  9.                 iter2 = b;
  10.                 item = null;
  11.                 cacheNext();. From 1point 3acres bbs
  12.         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  13.         @Override
  14.         public boolean hasNext() {
  15.                 return item != null;
  16.         }

  17.         @Override
  18.         public Integer next() {. 1point 3acres 璁哄潧
  19.                 Integer cur = item;
  20.                 item = null;
  21.                 cacheNext();
  22.                 return cur;
  23.         }
  24.         .1point3acres缃
  25.         /*
  26.          * cache number appeared in both lists.
  27.          */
  28.         private void cacheNext(){
  29.                 if(iter1.hasNext() && iter2.hasNext()){
  30.                         Integer x = iter1.next();
  31.                         Integer y = iter2.next();
  32.                         while(x!= null && y != null && x != y) {
  33.                                 if(x < y && iter1.hasNext()) x = iter1.next();
  34.                                 else if(x < y) x = null;. Waral 鍗氬鏈夋洿澶氭枃绔,
  35.                                 else if(x > y && iter2.hasNext()) y = iter2.next();
  36.                                 else if( x> y) y = null;
  37.                         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  38.                         // find the first repeated number and cache it.
  39.                         if(x != null && y != null && x.equals(y)) item = x;
  40.                 }
  41.         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  42. }
复制代码
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

 楼主| hercule24 发表于 2016-2-5 13:45:15 | 显示全部楼层
hotinherre 发表于 2016-2-5 13:32. Waral 鍗氬鏈夋洿澶氭枃绔,
看来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. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第二题也是sorted的,所以也是按照当前两个iterator指向的值比较,向前移动小的那个的iterator

楼主 请问一下 第二问的意思是. 1point 3acres 璁哄潧
public IntersectionIterator findIntersection(Iterator i1,Iretator i2){
}
这样子么?
我不太懂 多谢多谢
回复 支持 反对

使用道具 举报

 楼主| 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.1point3acres缃
感觉题目很常规啊

唔 。。。那么 可否指导一下 iterator 那个。。。
irisleaving@gmail.com. 鍥磋鎴戜滑@1point 3 acres

跪谢!
回复 支持 反对

使用道具 举报

JamesJi 发表于 2016-2-17 05:06:38 | 显示全部楼层
丢丢棠线 发表于 2016-2-16 16:03.鏈枃鍘熷垱鑷1point3acres璁哄潧
唔 。。。那么 可否指导一下 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-9-20 08:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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