San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 4851|回复: 18
收起左侧

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

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

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

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

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

x
第一轮是一个美国小哥,问了behavior question和两道经常在面经中出现的题目。.本文原创自1point3acres论坛
strStr() 和 find k most repeating elements

第二轮是一个阿三小哥,迟到了十五分钟,一度以为被放鸽子了,没有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。面试结束后第二天收到拒信。

来源一亩.三分地论坛.
补充内容 (2015-5-23 12:46):. 一亩-三分-地,独家发布
第二题只要输出一组即可. 求米啊~

评分

4

查看全部评分

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

O(1) space的思路,想到就写了,如果有不对请指出:

这个题目要求输出的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){. From 1point 3acres bbs
        if (num > result[0]){
                      result[1]  = num;
                return result;
        } else {
                result[0] = num;
        }
}-google 1point3acres
//for loop 没有提前terminate说明无解
//这段code输出的2个数,原题是3个数,同理,不过要多一个array记录
. Waral 博客有更多文章,
code挺烦的我举个例子吧

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

i = 0;. more info on 1point3acres
result0 = [1,0,0] //我update了这个array
result1 = [0,0,0]

i = 1;. from: 1point3acres
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更大
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];
. Waral 博客有更多文章,
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 | 显示全部楼层
根据上面大神未完成的思路,大概想到是不是这个样子?. 围观我们@1point 3 acres
result[2] = new int[] {num[0], Integer>max};. from: 1point3acres
for (int i = 1; i < num.length; i++) {. 围观我们@1point 3 acres
     if (num[i] < result[0]) {
      // 不可能是答案,但要更新最小值
      result[0]  = num[i];
      } else if (num[i] <= result[1]) {
        //也不可能是答案,因为中间那个大的index < i, 更新result[[i] 的值
         result[1] = num[i];
      } 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. 围观我们@1point 3 acres

请问strStr()用了KMP没?

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

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

[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.本文原创自1point3acres论坛
      
      for this case the answer could be
      8,12,14   or. more info on 1point3acres
        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)的空间不太能想出来。。。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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
for (i = 1 to num.length -1){ 来源一亩.三分地论坛.
if (num > result[0]){
}
}
.本文原创自1point3acres论坛

. 牛人云集,一亩三分地补充内容 (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
我想问个问题...第二题是要返回所有符合这个条件的数...还是只要找到一组就好了?. 1point 3acres 论坛
就像例子中的..只要返回 ...

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

使用道具 举报

lig113 发表于 2015-6-5 13:46:19 | 显示全部楼层
第二题用O(nlogn)的LIS的方法做,但是只要做到证明原数组存在长度为3的递增子序列就可以了。虽然LIS的复杂度是O(nlogn)但是如果只要证明存在长度为3的子序列的话,时间复杂度只有O(n)。而且你只需要一个长度为3的array空间,所以空间复杂度是O(1)。
. From 1point 3acres bbs
假设你使用的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;. visit 1point3acres for more.
  4.         for(int i = 0; i < nums.size(); ++i){
  5.                 // found sol in cache2;
  6.                 if(p2 != 0 && nums[i] > cache2[1]){
  7.                         a = cache2[0];
  8.                         b = cache2[1];
  9.                         c = nums[i];
  10.                         return;. 1point 3acres 论坛
  11.                 }
  12. . Waral 博客有更多文章,
  13.                 // compare nums[i] with cache1 elements
  14.                 if(p1 == 0){
  15.                         cache1[p1++] = nums[i];
  16.                 }else if(p1 == 1){. 围观我们@1point 3 acres
  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];
    . visit 1point3acres for more.
  34.                                 c = nums[i];.1point3acres网
  35.                                 return;
  36.                         }
  37.                 }
  38.         }
  39.         cout << "Cannot find a pair" << endl;
  40. }
复制代码


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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-26 10:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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