一亩三分地论坛

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

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

Google电面面经

[复制链接] |试试Instant~ |关注本帖
飞翔的小狐狸 发表于 2016-9-1 03:20:32 | 显示全部楼层 |阅读模式

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

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

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

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]祝大家一切顺利。. 1point 3acres 璁哄潧

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

补充内容 (2016-9-1 03:58):
A < A[j] < A[k]. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

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

补充内容 (2016-9-1 03:59):
A < A[j] < A[k]
mnmunknown 发表于 2016-9-1 04:17:54 | 显示全部楼层
大概。。。这样?

  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++){
  7.             if(nums[i] <= num1){
  8.                 num1 = nums[i];
  9.             } else if(nums[i] <= num2){
  10.                 num2 = nums[i];
  11.             } else {. 1point3acres.com/bbs
  12.                 return true;
  13.             }. from: 1point3acres.com/bbs
  14.         }
  15.   
  16.         return false;. 1point3acres.com/bbs
  17.     }
复制代码

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

使用道具 举报

 楼主| 飞翔的小狐狸 发表于 2016-9-1 03:29:58 | 显示全部楼层
youto 发表于 2016-9-1 03:26. Waral 鍗氬鏈夋洿澶氭枃绔,
lc的原题吧

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

使用道具 举报

youto 发表于 2016-9-1 03:26:11 | 显示全部楼层
lc的原题吧
回复 支持 反对

使用道具 举报

ytsr 发表于 2016-9-1 03:39:50 | 显示全部楼层
是 A[i] < A[j] < A[k] 吗?

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

使用道具 举报

 楼主| 飞翔的小狐狸 发表于 2016-9-1 03:56:09 | 显示全部楼层
ytsr 发表于 2016-9-1 03:39. more info on 1point3acres.com
是 A < A[j] < A[k] 吗?

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

不是你说的这个,你们都想多了。最简单的,判断a<a[j] 一个循环,在判断a[j]<a[k].1point3acres缃
一个循环,如果存在这样的i<j<k and a<a[j]<a[k]
返回对的。我不知道我是不是说清楚了。
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| 飞翔的小狐狸 发表于 2016-9-1 04:00:25 | 显示全部楼层
怎么回事儿?A'['i']' 为什么自动被吞了。补充都不充不上~bug :)
回复 支持 反对

使用道具 举报

ytsr 发表于 2016-9-1 04:09:57 | 显示全部楼层
飞翔的小狐狸 发表于 2016-9-1 03:56
不是你说的这个,你们都想多了。最简单的,判断a

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

使用道具 举报

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

使用道具 举报

larry_cn 发表于 2016-9-1 04:16:04 | 显示全部楼层
感觉 这道题的 思路 可以类似 354. Russian Doll Envelopes(这道题 复杂点不过 算法差不多) 做

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

补充内容 (2016-9-1 04:16):.鐣欏璁哄潧-涓浜-涓夊垎鍦
lc 那道复杂 点
回复 支持 反对

使用道具 举报

aangel 发表于 2016-9-1 04:30:19 | 显示全部楼层
ytsr 发表于 2016-9-1 04:09
你这个复杂度是 O(n^2), longest increasing subsequence的解法在你这个最长为3的情况下复杂度是 O(n)

longest increasing subsequence原题的解法是O(N^2),求问这里怎么优化到O(N)
回复 支持 反对

使用道具 举报

christwsy 发表于 2016-9-1 04:41:17 | 显示全部楼层
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上.1point3acres缃
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
就酱w.1point3acres缃

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

使用道具 举报

ytsr 发表于 2016-9-1 04:41:33 | 显示全部楼层
aangel 发表于 2016-9-1 04:30
longest increasing subsequence原题的解法是O(N^2),求问这里怎么优化到O(N)

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

使用道具 举报

 楼主| 飞翔的小狐狸 发表于 2016-9-1 04:41:54 | 显示全部楼层
我的暴力是O(n^3)哈哈,水平不行啊。
我刚在二楼说的是印度小哥让我优化的思路,可能是看我水平实在不行就不要求o(n)了,优化到o(n^2)就可以了??

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

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

使用道具 举报

 楼主| 飞翔的小狐狸 发表于 2016-9-1 04:43:09 | 显示全部楼层
chestnut9919 发表于 2016-9-1 04:36. more info on 1point3acres.com
LC 334~~~
-google 1point3acres
就是这题,谢谢大神:)
回复 支持 反对

使用道具 举报

swly 发表于 2016-9-1 05:11:14 | 显示全部楼层
没太多时间的话,近期的lc公司标签题还是要准备一下,还是挺合算的
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-9-1 05:26:30 | 显示全部楼层
这道题目是fb高频啊? 怎么 g拿来面试了
回复 支持 反对

使用道具 举报

Pony_s 发表于 2016-9-5 23:32:11 | 显示全部楼层
用patient sort O(n)

补充内容 (2016-9-5 23:34):
Patience sorting.
实际上是O(N*lgN),但是最长长度是3,搜索过程变为常数,就是O(N)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 08:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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