一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1309|回复: 26
收起左侧

Qumulo Phone Interview

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

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

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

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

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

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

我一开始只接丢进了unordered_set里然后,写了个O(n)的。然后小哥follow up说如果两个list都非常大,有trillion数量级的,会怎么样。
答无法塞进memory里,问怎么办。我有点慌了,支支吾吾说了一些paging之类的,然后小哥最后提醒说可以先sort完,然后保持两个pointer,
一直向前移动。

最后小哥又出了一道题,说给了这两个list的iterator,实现一个iterator能够iterate这两个list的intersection。比方说:
. more info on 1point3acres.com
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;. From 1point 3acres bbs
  6.        
  7.         public IntersectionIterator(Iterator itr1, Iterator itr2){
  8.                 this.itr1 = itr1;  //Iterator itr = list.Iterator();
  9.                 this.itr2 = itr2;. Waral 鍗氬鏈夋洿澶氭枃绔,
  10.         }

  11.         // check if hasNext, and update the nextNum
  12.         public boolean hasNext(){
  13.                 if(!itr1.hasNext() || !itr2.hasNext()) return false;. From 1point 3acres bbs
  14.                 int num1 = itr1.next();
  15.                 int num2 = itr2.next();. visit 1point3acres.com for more.
  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();
  30.                         }
  31.                 }
  32.         }.1point3acres缃

  33.         public int next(){
  34.                 if(!callHasNext){
  35.                         // if user call next funtion but no more intersection number
  36.                         if(!hasNext()){
    . visit 1point3acres.com for more.
  37.                                 System.out.println("No more intersection number!");
  38.                                 return Integer.MIN_VALUE;
  39.                         }
  40.                         else{. from: 1point3acres.com/bbs
  41.                                 callHasNext = false; //reset the callHasNext
  42.                                 return nextNum;
  43.                         }
  44.                 } . more info on 1point3acres.com
  45.                 else{
  46.                         callHasNext = false; // reset
  47.                         return nextNum;
  48.                 }
  49.         }
  50. }
复制代码
Iterator 的代码我写了一下, 大家看看对不对

.1point3acres缃
回复 支持 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.         }. 1point3acres.com/bbs

  12.         @Override
  13.         public boolean hasNext() {
  14.                 return item != null;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  15.         }

  16.         @Override
  17.         public Integer next() {
  18.                 Integer cur = item;
  19.                 item = null;
  20.                 cacheNext();. 1point3acres.com/bbs
  21.                 return cur;
  22.         }
  23.        
  24.         /*
  25.          * cache number appeared in both lists.
  26.          */
  27.         private void cacheNext(){
  28.                 if(iter1.hasNext() && iter2.hasNext()){. 1point3acres.com/bbs
  29.                         Integer x = iter1.next();. visit 1point3acres.com for more.
  30.                         Integer y = iter2.next();
  31.                         while(x!= null && y != null && x != y) {
  32.                                 if(x < y && iter1.hasNext()) x = iter1.next();
  33.                                 else if(x < y) x = null;
  34.                                 else if(x > y && iter2.hasNext()) y = iter2.next(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  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;
  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.1point3acres缃
第二题也是sorted的,所以也是按照当前两个iterator指向的值比较,向前移动小的那个的iterator

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

使用道具 举报

 楼主| hercule24 发表于 2016-2-17 02:49:13 | 显示全部楼层
丢丢棠线 发表于 2016-2-17 02:36
楼主 请问一下 第二问的意思是. visit 1point3acres.com for more.
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 的代码我写了一下, 大家看看对不对
.1point3acres缃
你的这个有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 姐加油啊
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 11:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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