Fall 18 我的 HCI 申请复盘与策略总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 2756|回复: 20
收起左侧

Google电面面经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
飞翔的小狐狸 发表于 2016-9-1 03:20:32 | 显示全部楼层 |阅读模式
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】

2016(7-9月) 码农类General 硕士 全职@Google - 内推 - 技术电面  | Fail | 在职跳槽

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

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

x
年纪大了好长时间没找个工作,深感自己刷题的能力比不上新一代年轻人。
给的题特别简单,特别简单。自己能力不行。没什么别的可说的。

FindIJK

Input: int[] A
Output: boolean, is there i < j < k, such that A < A[j] < A[k]


Eg.
{6, 5, 4, 3, 2} -> False
{1, 2, 3,4, 5} -> True
{1000, -3, 900, 2, 800, 8 } -> True


[size=13.3333px]祝大家一切顺利。



补充内容 (2016-9-1 03:58):
A < A[j] < A[k]

. more info on 1point3acres补充内容 (2016-9-1 03:58):
A < A[j] < A[k]

补充内容 (2016-9-1 03:59):-google 1point3acres
A < A[j] < A[k]

上一篇:新鲜狗狗店面,感觉是跪了啊。。。
下一篇:新鲜coursera OA 换题了orz

本帖被以下淘专辑推荐:

  • · Google|主题: 459, 订阅: 124
我的人缘0
mnmunknown 发表于 2016-9-1 04:17:54 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
大概。。。这样?. from: 1point3acres

  1.     public boolean increasingTriplet(int[] nums) {
  2.         if(nums == null || nums.length < 3) return false;
  3.         int n = nums.length;
  4.         int num1 = Integer.MAX_VALUE;
  5.         int num2 = Integer.MAX_VALUE;
  6.         for(int i = 0; i < n; i++){-google 1point3acres
  7.             if(nums[i] <= num1){
  8.                 num1 = nums[i];
  9.             } else if(nums[i] <= num2){
  10.                 num2 = nums[i];
  11.             } else {
  12.                 return true;
  13.             }. 1point3acres
  14.         }
  15.   
  16.         return false;
  17.     }
复制代码

补充内容 (2016-9-1 04:20):
大概意思就是维护一个 size = 3 的单调栈。。LIS 的常数退化版
回复 支持 2 反对 0

使用道具 举报

我的人缘0
 楼主| 飞翔的小狐狸 发表于 2016-9-1 03:29:58 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】

我感觉是原题,但是刷题刷的不够熟练。没找到,找到的同学告诉一下。就算不是原题也很简单,当时脑袋一下短路了。
回复 支持 0 反对 1

使用道具 举报

我的人缘0
youto 发表于 2016-9-1 03:26:11 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
lc的原题吧
回复 支持 反对

使用道具 举报

我的人缘0
ytsr 发表于 2016-9-1 03:39:50 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (1) 【我投】
是 A[i] < A[j] < A[k] 吗?

那就是longest increasing subsequence, 判断长度是否大于等于3.
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 飞翔的小狐狸 发表于 2016-9-1 03:56:09 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
ytsr 发表于 2016-9-1 03:39
是 A < A[j] < A[k] 吗?

那就是longest increasing subsequence, 判断长度是否大于等于3.

不是你说的这个,你们都想多了。最简单的,判断a<a[j] 一个循环,在判断a[j]<a[k]. 一亩-三分-地,独家发布
一个循环,如果存在这样的i<j<k and a<a[j]<a[k]. Waral 博客有更多文章,
返回对的。我不知道我是不是说清楚了。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 飞翔的小狐狸 发表于 2016-9-1 03:57:26 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
我确实觉得理解题意最重要,不要一开始就自己吭哧吭哧写。这提这么简单,我竟然一下蒙了,想了一堆乱七八糟的。特别懊恼。不过也好,onsite那么难,反正也过不去。翻篇了~
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 飞翔的小狐狸 发表于 2016-9-1 04:00:25 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
怎么回事儿?A'['i']' 为什么自动被吞了。补充都不充不上~bug :)
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
ytsr 发表于 2016-9-1 04:09:57 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (1) 【我投】
飞翔的小狐狸 发表于 2016-9-1 03:56. 围观我们@1point 3 acres
不是你说的这个,你们都想多了。最简单的,判断a

你这个复杂度是 O(n^2), longest increasing subsequence的解法在你这个最长为3的情况下复杂度是 O(n)
回复 支持 反对

使用道具 举报

我的人缘0
aangel 发表于 2016-9-1 04:10:57 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这个题在facebook面试中出现过,楼主你给的是暴力解法吧,时间复杂度O(N^2)的,
可以优化到时间复杂度O(N), 空间复杂度O(1),
估计那才是面试官想要的
回复 支持 反对

使用道具 举报

我的人缘0
larry_cn 发表于 2016-9-1 04:16:04 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
感觉 这道题的 思路 可以类似 354. Russian Doll Envelopes(这道题 复杂点不过 算法差不多) 做

如果 next 比之前保留的 序列最后一个 大 就加进去 长度+1
如果 next 比之前保留的 序列最后一个 小 就找到 序列里的 lower bound 然后 替换

补充内容 (2016-9-1 04:16):
lc 那道复杂 点
回复 支持 反对

使用道具 举报

我的人缘0
aangel 发表于 2016-9-1 04:30:19 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
ytsr 发表于 2016-9-1 04:09. visit 1point3acres for more.
你这个复杂度是 O(n^2), longest increasing subsequence的解法在你这个最长为3的情况下复杂度是 O(n)
. 牛人云集,一亩三分地
longest increasing subsequence原题的解法是O(N^2),求问这里怎么优化到O(N)
回复 支持 反对

使用道具 举报

我的人缘0
christwsy 发表于 2016-9-1 04:41:17 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
aangel 发表于 2016-8-31 15:30
longest increasing subsequence原题的解法是O(N^2),求问这里怎么优化到O(N)

三个变量a b c,一次循环
set a <- nums[0].留学论坛-一亩-三分地
如果找到一个比a 大的就存在b上
如果找到一个比b 大的就存在c上. more info on 1point3acres

就酱w

补充内容 (2016-8-31 15:42):
酱你大爷,写错了6666
回复 支持 反对

使用道具 举报

我的人缘0
ytsr 发表于 2016-9-1 04:41:33 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (1) 【我投】
aangel 发表于 2016-9-1 04:30
longest increasing subsequence原题的解法是O(N^2),求问这里怎么优化到O(N)

这个需要存的序列最长为2,第3个出现就返回true了, 最坏也就O(2N) = O(N)
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 飞翔的小狐狸 发表于 2016-9-1 04:41:54 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
我的暴力是O(n^3)哈哈,水平不行啊。. 留学申请论坛-一亩三分地
我刚在二楼说的是印度小哥让我优化的思路,可能是看我水平实在不行就不要求o(n)了,优化到o(n^2)就可以了??. 1point3acres

我觉得确实有时候要跟着面试官,面试官有自己的一套解法,我们开始是讨论了半天解法,很浪费时间
后来是在说不明白了,他说那你先暴力吧,然后再优化。

是印度小哥,感觉还挺友好的。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 飞翔的小狐狸 发表于 2016-9-1 04:43:09 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
chestnut9919 发表于 2016-9-1 04:36. 牛人云集,一亩三分地
LC 334~~~

就是这题,谢谢大神:)
回复 支持 反对

使用道具 举报

我的人缘0
swly 发表于 2016-9-1 05:11:14 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
没太多时间的话,近期的lc公司标签题还是要准备一下,还是挺合算的
回复 支持 反对

使用道具 举报

我的人缘0
qiuxuxing007 发表于 2016-9-1 05:26:30 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这道题目是fb高频啊? 怎么 g拿来面试了
回复 支持 反对

使用道具 举报

我的人缘0
Pony_s 发表于 2016-9-5 23:32:11 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
用patient sort O(n)
.留学论坛-一亩-三分地
补充内容 (2016-9-5 23:34):
Patience sorting.
实际上是O(N*lgN),但是最长长度是3,搜索过程变为常数,就是O(N)
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-6-20 06:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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