May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3571|回复: 17
收起左侧

Pocket Gems 两轮电面面经(有新题)

[复制链接] |试试Instant~ |关注本帖
lithui 发表于 2015-5-20 01:11:26 | 显示全部楼层 |阅读模式

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

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

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

x
第一轮是一个美国小哥,问了behavior question和两道经常在面经中出现的题目。
strStr() 和 find k most repeating elements. 1point 3acres 璁哄潧

第二轮是一个阿三小哥,迟到了十五分钟,一度以为被放鸽子了,没有behavior直接问了两个题目。-google 1point3acres
1. max product subsequence
2. 给一个array,找到其中三个index依次增加的数,并且数值也是依次增加。要求O(n) time O(1) extra space。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第二题他看我做不出来曾放宽到O(n) space,虽然最后也没做出来。.1point3acres缃
和阿三小哥交流不多。问他要hint也不给,只是一个劲地说you're in the right direction。面试结束后第二天收到拒信。


补充内容 (2015-5-23 12:46):
第二题只要输出一组即可. 求米啊~

评分

4

查看全部评分

贪睡之萨满 发表于 2015-5-21 06:48:15 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地

O(1) space的思路,想到就写了,如果有不对请指出:. From 1point 3acres bbs

这个题目要求输出的int数量是3个,如果是2个的话就会非常trivial:
你需要1个长度是2的int Array,叫这个array "result";. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
initialization state: reslut[0] = num[0]; // num 是那个input array
for (i = 1 to num.length -1){
        if (num > result[0]){
                      result[1]  = num;
                return result;
        } else {
                result[0] = num;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        }
}
//for loop 没有提前terminate说明无解. 1point 3acres 璁哄潧
//这段code输出的2个数,原题是3个数,同理,不过要多一个array记录
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
code挺烦的我举个例子吧

input 是 [1, 2, 0, 1, 2]
result0 = new int[3]//[0,0,0]
result1 = new int[3]//[0,0,0]. Waral 鍗氬鏈夋洿澶氭枃绔,
需要2个pointer记录每个array填写到哪了,请自行脑补,开始当然是2个index = 0;

i = 0;
result0 = [1,0,0] //我update了这个array
result1 = [0,0,0]. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
-google 1point3acres
i = 1;. From 1point 3acres bbs
result0 = [1,2,0] //我update了这个array
result1 = [0,0,0]

i = 2;// i = 2的时候,num[2] 是0,比result0[0],result0[1]都要小,我们把它update到result1中,注意这个时候result0仍然可能是最后的解,因为他的element比result1多,虽然他最后一个element更大. 1point3acres.com/bbs
result0 = [1,2,0]
result1 = [0,0,0]//我update了这个array,第一个0是update出来的,后面2个0是空的,例子不好,见谅

i = 3;
result0 = [1,2,0]
result1 = [0,1,0] //我update了这个array.鐣欏璁哄潧-涓浜-涓夊垎鍦

result0 = result1//[0,1,0],这个时候已经没有必要保留result0了,因为result1中间的element比result0多,最后一个数也比他小
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴result1 = new int[3];. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

i = 4;
result0 = [0,1,2]  //我update了这个array
result1 = [0,0,0]

return result0;

举的是最tricky的例子(result0中有2个element,result1为空,这个时候我们看到的数 n满足n <= result0[0] ),其他情况update第一个array就好了,写的乱七八糟的,也不知道大家有没有看懂,之前这个公司有个类似的题目,题目很简单,不过要求space O(1)就难了,也是这个思路,不过一个array就够了那题。
. 1point3acres.com/bbs
. more info on 1point3acres.com
补充内容 (2015-5-21 06:50):. from: 1point3acres.com/bbs
输出的数是k个,那么space就是O(k^2),这里k=3,就是constant space了。话说O(n) space的做法是什么思路。。。怎么大家都知道
回复 支持 1 反对 0

使用道具 举报

frankrenyu 发表于 2015-5-21 06:52:29 | 显示全部楼层
关注一亩三分地微博:
Warald
根据上面大神未完成的思路,大概想到是不是这个样子?-google 1point3acres
result[2] = new int[] {num[0], Integer>max};
for (int i = 1; i < num.length; i++) {
     if (num[i] < result[0]) {. 1point 3acres 璁哄潧
      // 不可能是答案,但要更新最小值
      result[0]  = num[i];
      } else if (num[i] <= result[1]) {
        //也不可能是答案,因为中间那个大的index < i, 更新result[[i] 的值
         result[1] = num[i];
      } else {
        // 右边找到比左边大的那个数还大的,是答案
          return true;
     }
.鏈枃鍘熷垱鑷1point3acres璁哄潧}
     return false;
回复 支持 1 反对 0

使用道具 举报

frankrenyu 发表于 2015-5-21 06:53:18 | 显示全部楼层
frankrenyu 发表于 2015-5-21 06:52
根据上面大神未完成的思路,大概想到是不是这个样子?
result[2] = new int[] {num[0], Integer>max};
fo ...

初始化写错了, 应该是Integer.MAX_VALUE
回复 支持 1 反对 0

使用道具 举报

jobchaser 发表于 2015-5-20 03:37:56 | 显示全部楼层
赞LZ

请问strStr()用了KMP没?

三哥第二题不是扫一遍就行了??还是我理解有问题?
回复 支持 反对

使用道具 举报

 楼主| lithui 发表于 2015-5-20 05:37:14 | 显示全部楼层
jobchaser 发表于 2015-5-20 03:37
赞LZ

请问strStr()用了KMP没?

没有用, 直接暴力搜索的.

第二题的话这是原题的描述:
. 1point 3acres 璁哄潧
[8,7,6,12,14]
.鏈枃鍘熷垱鑷1point3acres璁哄潧
you need to find 3 numbers such that a<b<c
  and i<j<k
  a,b,c are the values of the numbers. 1point3acres.com/bbs
    i,j,k are the indices of the numbers
      
      for this case the answer could be . 1point3acres.com/bbs
      8,12,14   or
        7,12,14 or . From 1point 3acres bbs
          6,12,14. 鍥磋鎴戜滑@1point 3 acres
                        
i want O(n) time. O(1) extra memory

如果有好的解法求指点.
回复 支持 反对

使用道具 举报

frankrenyu 发表于 2015-5-21 05:26:38 | 显示全部楼层
jobchaser 发表于 2015-5-20 03:37. 鍥磋鎴戜滑@1point 3 acres
赞LZ

请问strStr()用了KMP没?
-google 1point3acres
扫一遍如何用O(N)时间复杂度啊?
回复 支持 反对

使用道具 举报

frankrenyu 发表于 2015-5-21 05:41:12 | 显示全部楼层
第二轮第二题,我能想到的就是o(n) 时间 O(n)空间,用两个array纪录,当前index的最小值和右边最大值,最后比较这个值是否比左边最小值大比右边最大值小就可以了,但是o(1)的空间不太能想出来。。。
回复 支持 反对

使用道具 举报

57656929bb 发表于 2015-5-21 06:03:57 | 显示全部楼层
第二题挺经典的两个数组存min和max,但是就O(n) space了,不明白O(1)怎么做,个人觉得不可能
回复 支持 反对

使用道具 举报

贪睡之萨满 发表于 2015-5-21 06:25:33 | 显示全部楼层
O(1) space的思路,想到就写了,如果有不对请指出:
为了
这个题目要求输出的int数量是3个,如果是2个的话就会非常trivial:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
你需要1个长度是2的int Array,叫这个array "result";
initialization state: reslut[0] = num[0]; // num 是那个input array. from: 1point3acres.com/bbs
for (i = 1 to num.length -1){
if (num > result[0]){. From 1point 3acres bbs
}
}


补充内容 (2015-5-21 06:26):
按错了。。没写完
回复 支持 反对

使用道具 举报

frankrenyu 发表于 2015-5-21 06:36:21 | 显示全部楼层
贪睡之萨满 发表于 2015-5-21 06:25
O(1) space的思路,想到就写了,如果有不对请指出:
为了
这个题目要求输出的int数量是3个,如果是2个的 ...

坐等指教!
回复 支持 反对

使用道具 举报

57656929bb 发表于 2015-5-21 08:58:30 | 显示全部楼层
啊哦卧槽,楼主这题原来是LIS的方法做,LIS里是维持一个递增数组,这题同理,然后因为k=3,就是constant space
回复 支持 反对

使用道具 举报

57656929bb 发表于 2015-5-21 09:04:40 | 显示全部楼层
感觉有点傻逼,因为k=3所以是const space以及O(n)时间,但其实是O(nlogk)时间以及O(k**2)空间
回复 支持 反对

使用道具 举报

calvinq 发表于 2015-5-23 05:35:07 | 显示全部楼层
我想问个问题...第二题是要返回所有符合这个条件的数...还是只要找到一组就好了?
就像例子中的..只要返回其中一组3个数.就好了么?
回复 支持 反对

使用道具 举报

 楼主| lithui 发表于 2015-5-23 12:47:49 | 显示全部楼层
calvinq 发表于 2015-5-23 05:35
我想问个问题...第二题是要返回所有符合这个条件的数...还是只要找到一组就好了?
就像例子中的..只要返回 ...

是的若干组中的一组就好.
回复 支持 反对

使用道具 举报

lig113 发表于 2015-6-5 13:46:19 | 显示全部楼层
第二题用O(nlogn)的LIS的方法做,但是只要做到证明原数组存在长度为3的递增子序列就可以了。虽然LIS的复杂度是O(nlogn)但是如果只要证明存在长度为3的子序列的话,时间复杂度只有O(n)。而且你只需要一个长度为3的array空间,所以空间复杂度是O(1)。

假设你使用的array名称为a,当你证明子序列存在的时候,a[2], a[1]就已经存放好了正确的数值,这个时候你只要把给你的数组从头再扫一遍,找到第一个数小于a[1]的数,把他放到a[0]里去就行了。时间复杂度也是O(n)
回复 支持 反对

使用道具 举报

combatant 发表于 2015-6-19 09:54:02 | 显示全部楼层
用LIS做, 由于K=3, 所以是O(1), LIS本身的时间为O(NlogK), 由于k = 3, 所以是O(N) 不知道这么理解对不对
回复 支持 反对

使用道具 举报

songyuanyoung 发表于 2017-2-7 04:43:17 | 显示全部楼层
为啥没有人用两根指针?就跟color sorting一样的方法不行吗?我还没试,试好了贴代码。。。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-25 09:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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