一亩三分地论坛

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

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

狗狗11/2店面

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

2016(10-12月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
请告诉我 问这么容易的题是正常的……. 1point 3acres 璁哄潧

1. 给一个数组,找到比左右邻居都大的element。比如[1,2,3,4,3,5,6,7],返回4
看到这道题,内心无数黑人问号脸……. 鍥磋鎴戜滑@1point 3 acres

2. 设计一个Iterator类,构造器input是一个Integer的Iterator,  next()返回里面的下一个负数,hasNext()返回是否还有负数……
这道题也很简单,但我当时过于紧张,把剩余的时间都花在了这道题上……

这种难度的题是不是至少要做3道才算合格,好机会没太把握好



补充内容 (2016-11-10 10:58):
刚收到二面通知,森森滴感觉被放水

本帖被以下淘专辑推荐:

Owenli20 发表于 2016-11-5 09:28:10 | 显示全部楼层
第一题binary search3分钟写出来
第二题怎么做……参数的Iterator有没有peek()之类的东西?
回复 支持 反对

使用道具 举报

 楼主| sqrl 发表于 2016-11-5 09:52:21 | 显示全部楼层
Owenli20 发表于 2016-11-4 19:28
第一题binary search3分钟写出来
第二题怎么做……参数的Iterator有没有peek()之类的东西?
-google 1point3acres
第一题我当时也想到binary search, 但他说不是sorted, 那怎么判断从mid往左走还是往右走?感觉都是O(n)

第二题在类里定义一个iterator存储input, 定义一个int存储下一个负数,hasNext()用来更新这个int
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-5 10:51:18 | 显示全部楼层
希望也可以遇到到和LZ类似的题。估计这样的题就是考察细节和一定要bug free吧。
第一题我觉得最优不可能少于O(N),因为数组中任何元素都各自独立并都有可能影响最终结果。第二题我用vector::iterator比较方便。-google 1point3acres
  1. int firstLocalMax(vector<int>& a) { // O(N). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  2.   int i = 0;
  3.   while (i < a.size()-2) {
  4.     if (a[i] < a[i+1]) {
  5.       if (a[i+1] > a[i+2]) return a[i+1];
  6.       else if (a[i+1] == a[i+2]) { i+=2; continue; }. 1point3acres.com/bbs
  7.     }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  8.     i++;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  9.   }
  10.   return INT_MIN;
  11. }

  12. class NegativeItr {
  13. private:
  14.   vector<int>::iterator itr, end;
  15. public:
  16.   NegativeItr(vector<int>& a):itr(a.begin()),end(a.end()) { // worst O(N)
  17.     while (itr != end && *itr >= 0) ++itr;  . from: 1point3acres.com/bbs
  18.   }
  19.   
  20.   bool hasNext() { return itr != end; } // O(1)-google 1point3acres
  21.   int next() { // worst O(N)
  22.     if (!hasNext()) return INT_MAX;
  23.     int res = *itr++;
  24.     while (itr != end && *itr >= 0) ++itr;
  25.     return res;
  26.   }. visit 1point3acres.com for more.
  27. };
复制代码
回复 支持 反对

使用道具 举报

zhan1612 发表于 2016-11-5 11:30:03 | 显示全部楼层
第一题是lc原题, 条件是无重复数, 然后两边无限小。
思路是:
if(mid < mid+1)
     left = mid+1;
else
     if(mid > mid+1)
         return  mid;
     else
         right = mid-1;
回复 支持 反对

使用道具 举报

jpeng7 发表于 2016-11-5 11:47:04 | 显示全部楼层
这两道貌似都是leetcode原题,第一道162,第二道341?
回复 支持 反对

使用道具 举报

33847682 发表于 2016-11-5 11:59:45 | 显示全部楼层
我也是大概这么容易的题 然后挂了
回复 支持 反对

使用道具 举报

 楼主| sqrl 发表于 2016-11-5 17:14:56 | 显示全部楼层
33847682 发表于 2016-11-4 21:59
我也是大概这么容易的题 然后挂了
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
那我也得做好心理准备了……你是几号面的?
回复 支持 反对

使用道具 举报

 楼主| sqrl 发表于 2016-11-5 17:22:51 | 显示全部楼层
jpeng7 发表于 2016-11-4 21:47
这两道貌似都是leetcode原题,第一道162,第二道341?
. 1point 3acres 璁哄潧
第二题跟284差不多,唉,就感觉做过,好久以前做的都忘了
回复 支持 反对

使用道具 举报

 楼主| sqrl 发表于 2016-11-5 17:24:03 | 显示全部楼层
zhan1612 发表于 2016-11-4 21:30
第一题是lc原题, 条件是无重复数, 然后两边无限小。
思路是:
if(mid < mid+1)

两边怎么处理我都没问,目测挂定了
回复 支持 反对

使用道具 举报

33847682 发表于 2016-11-5 17:37:20 | 显示全部楼层
sqrl 发表于 2016-11-5 17:14
那我也得做好心理准备了……你是几号面的?

1号面的
回复 支持 反对

使用道具 举报

jpeng7 发表于 2016-11-5 22:05:42 | 显示全部楼层
sqrl 发表于 2016-11-5 17:22
第二题跟284差不多,唉,就感觉做过,好久以前做的都忘了

摸摸楼主,没事,继续加油!另外想问一下狗家的questionnaire是不是要写得很细?那个是用来在pool里面匹配的吗?我之前不知道,写得很简单,能不能重新提交呀?
回复 支持 反对

使用道具 举报

 楼主| sqrl 发表于 2016-11-6 03:37:18 | 显示全部楼层
jpeng7 发表于 2016-11-5 08:05
摸摸楼主,没事,继续加油!另外想问一下狗家的questionnaire是不是要写得很细?那个是用来在pool里面匹 ...

我也没写很细,就写了prefer西海岸之类的
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-6 06:30:11 | 显示全部楼层
zhan1612 发表于 2016-11-5 11:30. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一题是lc原题, 条件是无重复数, 然后两边无限小。
思路是:
if(mid < mid+1)
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
多谢!我说怎么能O(logN)时间解决呢,原来Leetcode 162原题里还有两个限制条件。。。.1point3acres缃


PS(纯娱乐):我想了想为什么加上那两个条件就可以O(logN)时间解决(即使不是sorted),这其实就是一个微积分关于连续函数局部极大值证明题的离散版本啊!
根据离散条件,我可以对等的出这么一道题:(这个题就是用闭区间套定理证明的,相当于binary search)
.1point3acres缃给定一个定义在闭区间[a, b]上的连续函数f(x), 满足:
1. f(x) > f(a), f(x) > f(b), 对任意 x in (a, b);. from: 1point3acres.com/bbs
2. 对任意 x in [a, b], 存在小邻域(x-d, x+d) 使得f(x)在(x-d, x]和[x, x+d)上分别严格单调 (若x=a or b的话只需满足一边)。
.鐣欏璁哄潧-涓浜-涓夊垎鍦求建立一个[a, b]中的一个序列{x_n}使其收敛到一个严格局部极大值。
回复 支持 反对

使用道具 举报

Owenli20 发表于 2016-11-6 09:27:14 | 显示全部楼层
zzgzzm 发表于 2016-11-6 06:30
多谢!我说怎么能O(logN)时间解决呢,原来Leetcode 162原题里还有两个限制条件。。。

我觉得这个题的考点肯定就是binary search,不然没任何意义。
”两边无限小“这个并不算关键,甚至算是隐含在题目描述里的(当然要和面试官确认)。
问题的关键是他只需要你随便找一个peak element,而不是所有peak element。随便找就是O(logn),所有就是O(n)
回复 支持 反对

使用道具 举报

krystal1115 发表于 2016-11-6 10:16:02 | 显示全部楼层
zzgzzm 发表于 2016-11-6 06:30
多谢!我说怎么能O(logN)时间解决呢,原来Leetcode 162原题里还有两个限制条件。。。

就是loule定理啊,如果函数f(x)满足:
在闭区间[a,b]上连续;
在开区间(a,b)内可导;
在区间端点处的函数值相等,即f(a)=f(b),
那么在(a,b)内至少有一点ξ(a<ξ<b),使得 f'(ξ)=0.
回复 支持 反对

使用道具 举报

krystal1115 发表于 2016-11-6 10:19:45 | 显示全部楼层
Owenli20 发表于 2016-11-6 09:27
我觉得这个题的考点肯定就是binary search,不然没任何意义。
”两边无限小“这个并不算关键,甚至算是 ...
. visit 1point3acres.com for more.
两边无限小这个条件很关键,这样会保证element一定有先递增再递减的过程。否则binary search用不了,最简单的例子[1,3,2,4,5,6,7]二分查找是找不出来3的
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-6 11:16:08 | 显示全部楼层
你给f(x)的假设条件太强了,因为可能它就不是可导的。而且为什么要求f(a)=f(b)呢?而且即使找到f'(x)=0的点也不能说明它就一定是严格局部极大值点。
这个关键是要把a[i]!=a[i+1]翻译成等价的连续形式。在离散系统中1就是最小的delta, 而在连续系统中就只能用存在邻域的形式表述了。而这个题是要构造找出严格极大值点,光证明存在性还是不够的。我在Leetcode 162的discussion 中写了证明离散(就是本题)和连续两个版本的证明。得用到实数域的比区间套定理。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 09:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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