传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

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

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


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

评分

4

查看全部评分

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

O(1) space的思路,想到就写了,如果有不对请指出:-google 1point3acres
.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]){. from: 1point3acres.com/bbs
                      result[1]  = num;
                return result;. visit 1point3acres.com for more.
        } else {
                result[0] = num;
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷        }
}
//for loop 没有提前terminate说明无解
//这段code输出的2个数,原题是3个数,同理,不过要多一个array记录

code挺烦的我举个例子吧
-google 1point3acres
input 是 [1, 2, 0, 1, 2]
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]

. 1point3acres.com/bbsi = 1;. From 1point 3acres bbs
result0 = [1,2,0] //我update了这个array. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
result1 = [0,0,0]. more info on 1point3acres.com

i = 2;// i = 2的时候,num[2] 是0,比result0[0],result0[1]都要小,我们把它update到result1中,注意这个时候result0仍然可能是最后的解,因为他的element比result1多,虽然他最后一个element更大
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就够了那题。

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (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]) {
      // 不可能是答案,但要更新最小值.鏈枃鍘熷垱鑷1point3acres璁哄潧
      result[0]  = num[i];-google 1point3acres
      } else if (num[i] <= result[1]) {
        //也不可能是答案,因为中间那个大的index < i, 更新result[[i] 的值
.1point3acres缃         result[1] = num[i];
      } else {. from: 1point3acres.com/bbs
        // 右边找到比左边大的那个数还大的,是答案
          return true;
     }
}. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
     return false;
回复 支持 1 反对 0

使用道具 举报

frankrenyu 发表于 2015-5-21 06:53:18 | 显示全部楼层
frankrenyu 发表于 2015-5-21 06:52. visit 1point3acres.com for more.
根据上面大神未完成的思路,大概想到是不是这个样子?
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. 1point 3acres 璁哄潧
赞LZ

请问strStr()用了KMP没?

没有用, 直接暴力搜索的. . from: 1point3acres.com/bbs

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

[8,7,6,12,14]

you need to find 3 numbers such that a<b<c
  and i<j<k.鏈枃鍘熷垱鑷1point3acres璁哄潧
  a,b,c are the values of the numbers
    i,j,k are the indices of the numbers
      
      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的思路,想到就写了,如果有不对请指出:.鐣欏璁哄潧-涓浜-涓夊垎鍦
为了
这个题目要求输出的int数量是3个,如果是2个的话就会非常trivial:. from: 1point3acres.com/bbs
你需要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]){
}
}


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

使用道具 举报

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

使用道具 举报

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一样的方法不行吗?我还没试,试好了贴代码。。。
回复 支持 反对

使用道具 举报

milanow 发表于 2017-7-28 05:36:19 | 显示全部楼层
  1. void findIndices(vector<int>& nums, int& a, int& b, int& c){
  2.         int cache1[2] = {0}, cache2[2] = {0};
  3.         int p1 = 0, p2 = 0;
  4.         for(int i = 0; i < nums.size(); ++i){
  5.                 // found sol in cache2;
    . 1point3acres.com/bbs
  6.                 if(p2 != 0 && nums[i] > cache2[1]){
  7.                         a = cache2[0];
  8.                         b = cache2[1];.鏈枃鍘熷垱鑷1point3acres璁哄潧
  9.                         c = nums[i];
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  10.                         return;
  11.                 }

  12. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  13.                 // compare nums[i] with cache1 elements
  14.                 if(p1 == 0){
  15.                         cache1[p1++] = nums[i];
  16.                 }else if(p1 == 1){. 1point 3acres 璁哄潧
  17.                         if(nums[i] < cache1[0]) cache1[0] = nums[i];
  18.                         else if(nums[i] > cache1[0]){
  19.                                 cache1[p1++] = nums[i];
  20.                         }
  21.                 }else if(p1 == 2){
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  22.                         if(nums[i] < cache1[0]){
  23.                                 // find a better candicates, cache2 must be the worst, replace cache2 with cache1, and assign cache1[0] = nums[i]
  24.                                 cache2[0] = cache1[0];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  25.                                 cache2[1] = cache1[1];
  26.                                 p2 = 2;. Waral 鍗氬鏈夋洿澶氭枃绔,

  27.                                 cache1[0] = nums[i];
  28.                                 p1 = 1;
  29.                         }else if(nums[i] < cache1[1]){. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  30.                                 cache1[1] = nums[i];
  31.                         }else if(nums[i] > cache1[1]){
  32.                                 a = cache1[0];
  33.                                 b = cache1[1];
  34.                                 c = nums[i];
  35.                                 return;
  36.                         }
  37.                 }
  38.         }. from: 1point3acres.com/bbs
  39.         cout << "Cannot find a pair" << endl;
  40. }
复制代码


这个算是O(1) Space的解法吧,用了两个array长度为2的cache, cache2保存最好的两个数(第二个数最小), cache1保存最好的一个数(最小),p1,p2分别是两个cache中的元素个数,目前我还没发现什么test case错误。如果有求指正。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-21 22:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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