一亩三分地论坛

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

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

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

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

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

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

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

x
第一轮是一个美国小哥,问了behavior question和两道经常在面经中出现的题目。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
strStr() 和 find k most repeating elements. Waral 鍗氬鏈夋洿澶氭枃绔,

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


补充内容 (2015-5-23 12:46):. Waral 鍗氬鏈夋洿澶氭枃绔,
第二题只要输出一组即可. 求米啊~

评分

4

查看全部评分

贪睡之萨满 发表于 2015-5-21 06:48:15 | 显示全部楼层

O(1) space的思路,想到就写了,如果有不对请指出:
.1point3acres缃
这个题目要求输出的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;. 1point3acres.com/bbs
        } else {
                result[0] = num;
        }
}
//for loop 没有提前terminate说明无解
//这段code输出的2个数,原题是3个数,同理,不过要多一个array记录

code挺烦的我举个例子吧

input 是 [1, 2, 0, 1, 2]. From 1point 3acres bbs
result0 = new int[3]//[0,0,0]
result1 = new int[3]//[0,0,0]
需要2个pointer记录每个array填写到哪了,请自行脑补,开始当然是2个index = 0;

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

i = 1;
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更大. 1point 3acres 璁哄潧
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]. 鍥磋鎴戜滑@1point 3 acres
. more info on 1point3acres.com
return result0;

举的是最tricky的例子(result0中有2个element,result1为空,这个时候我们看到的数 n满足n <= result0[0] ),其他情况update第一个array就好了,写的乱七八糟的,也不知道大家有没有看懂,之前这个公司有个类似的题目,题目很简单,不过要求space O(1)就难了,也是这个思路,不过一个array就够了那题。
. 鍥磋鎴戜滑@1point 3 acres

补充内容 (2015-5-21 06:50):
输出的数是k个,那么space就是O(k^2),这里k=3,就是constant space了。话说O(n) space的做法是什么思路。。。怎么大家都知道
回复 支持 1 反对 0

使用道具 举报

frankrenyu 发表于 2015-5-21 06:52:29 | 显示全部楼层
根据上面大神未完成的思路,大概想到是不是这个样子?
result[2] = new int[] {num[0], Integer>max};
for (int i = 1; i < num.length; i++) {
     if (num[i] < result[0]) {
      // 不可能是答案,但要更新最小值
      result[0]  = num[i];
      } else if (num[i] <= result[1]) {
        //也不可能是答案,因为中间那个大的index < i, 更新result[[i] 的值
         result[1] = num[i];. from: 1point3acres.com/bbs
      } else {
        // 右边找到比左边大的那个数还大的,是答案.鐣欏璁哄潧-涓浜-涓夊垎鍦
          return true;
     }
}
     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.1point3acres缃

请问strStr()用了KMP没?
. Waral 鍗氬鏈夋洿澶氭枃绔,
没有用, 直接暴力搜索的.

第二题的话这是原题的描述:

[8,7,6,12,14]

you need to find 3 numbers such that a<b<c
  and i<j<k
  a,b,c are the values of the numbers
    i,j,k are the indices of the numbers
      . 鍥磋鎴戜滑@1point 3 acres
      for this case the answer could be
      8,12,14   or
        7,12,14 or
          6,12,14
                        
i want O(n) time. O(1) extra memory

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

使用道具 举报

frankrenyu 发表于 2015-5-21 05:26:38 | 显示全部楼层
jobchaser 发表于 2015-5-20 03:37
赞LZ.鐣欏璁哄潧-涓浜-涓夊垎鍦

请问strStr()用了KMP没?

扫一遍如何用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的思路,想到就写了,如果有不对请指出:. From 1point 3acres bbs
为了
这个题目要求输出的int数量是3个,如果是2个的话就会非常trivial:
你需要1个长度是2的int Array,叫这个array "result";. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
initialization state: reslut[0] = num[0]; // num 是那个input array. more info on 1point3acres.com
for (i = 1 to num.length -1){
if (num > result[0]){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
}. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
}


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

使用道具 举报

frankrenyu 发表于 2015-5-21 06:36:21 | 显示全部楼层
贪睡之萨满 发表于 2015-5-21 06:25. from: 1point3acres.com/bbs
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
我想问个问题...第二题是要返回所有符合这个条件的数...还是只要找到一组就好了?
就像例子中的..只要返回 ...
-google 1point3acres
是的若干组中的一组就好.
回复 支持 反对

使用道具 举报

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) 不知道这么理解对不对
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 12:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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