一亩三分地论坛

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

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

10月8日Google Onsite面经+附上求职总结回报各位 已签offer 真心感谢地里

    [复制链接] |试试Instant~ |关注本帖
thebestsarah 发表于 2015-10-18 14:59:19 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Pass在职跳槽

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

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

x
首先真心感谢各位直接或间接帮助过我的所有人. 尤其是妈妈,在我找工作期间不知道为我操了多少心,无以回报,只能快乐的好好生活不再让她担心,这一定是妈妈最想看到的. 在职找工作的艰辛相信很多人都懂, 今年硅谷就业形势多差大家都有体会, 最后真的近乎绝望了. 谢谢妈妈不断给我力量,让我坚持了下来. 这个offer是我的,更是你的.

先写下Google onsite面经回报地里~ 后面附上我的
求职学习刷题总结,希望能对每一个正在流汗奋斗的你起到一些帮助. . more info on 1point3acres.com

我面的职位是Softwre Engineer, Tools and Infrastracture, 所以开发和测试的问题都会问到.

Phone interview 1:.鏈枃鍘熷垱鑷1point3acres璁哄潧
白人小哥.给一个Interval的class, 就是一个区间,左闭右开,比如 [1, 3) 意思是从1到3除了3的所有interger. 让我在这个class里implement一个method, 判断与另一个Interval是否有overlapping.
第二问是写一个method, 返回在Interval 1而不在Interval 2的区域..鏈枃鍘熷垱鑷1point3acres璁哄潧
一道如此简单的题...因为我前面实在太紧张了全身是汗面的吭吭哧哧...面完以后我都准备move on了, 看来小哥最后还是放了我一码让我有了二面.


Phone interview 2:
白人小哥.更简单了... Leetcode原题Plus One
如果现在Google要release全新版本的Chrome, 我要怎么保证这个新的Chrome全方位的work? 意思就是测试些什么,怎么测试这个新版本的Chrome,才能放心的release出去.
最后他还开心的问了我的名字到底怎么念,我就知道大概有个底儿了~


Onsite:.鐣欏璁哄潧-涓浜-涓夊垎鍦

第一轮: 印度哥哥. 大早上的堵了一个多小时开过去腿都麻了,上来就开始coding,直接蒙圈儿..鐣欏璁哄潧-涓浜-涓夊垎鍦
第一题, 给一个array比如[4,2,1,3,5],根据这个array现在我们能有了一个新的array => 每个数是在原array里, 在它左边的所有比它大的number的个数,就是[0,1,2,1,0]. 题目是现在给了这个[0,1,2,1,0]要求原array, 原来array的range是1~n
第二题, 知不知道binary search? 但是现在array是unsorted的可是依然看做sorted array来做binary search, 返回在array里面所有可以在这种情况下binary search出来的数.


第二轮: 韩国哥哥.. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
经典的地里出现过的String压缩编码解码类似题, 后悔当时看到没有好好写过一遍.给一个String比如"abcdfffffffxyz", 写两个methods, encode和decode. encode就是比如"fffffff"变成"7xf",decode就是要变为原字符串.我说"ff"怎么办,他说变成"2xf"你不觉得更长了吗? 我才明白了,应该是encoded后的String要比原来的短,不然为啥要encode,的亏我问了这个问题...然后又问他,如果原String本来就是"5xt"这种结构, decode不就无法辨认了吗?他说很高兴你提出了这个问题,但是不用管它,一会再讨论,先写吧.. 鍥磋鎴戜滑@1point 3 acres
写完以后他就问我如果原String本来就是"5xt"这种结构,我encode应该怎么处理? 我就傻了... 因为一直觉得encode后的字符串长度一定要比原来的短,所以根本想不出来他要的解法. 说了四五种方法他都不满意, 最后给我hint说,要是有个"1xt"这样的你怎么处理? 当时脑洞大开想出来了... 其实是要变成三个"1xt"这种结构, 比如原String就是"5xq", 就encode成为"1x51xx1xq"就好了. 但是这种方法违背了encode后要变短的rule,所以我是真没想出来...... 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
还讨论了好多种情况, 最后一种是"1aaaaa"这种情况怎么变, 我说"1x15xa". 他说这是6个字符,能不能只用5个? 实在想不出来,这时候第三个小哥进来了,韩国哥哥就过来告诉我说,其实看做1a和aaaa两部分encode就好.... 鍥磋鎴戜滑@1point 3 acres
面完我就觉得跪了....


第三轮: 中国小哥.
第一个问题是测试的,比较简单. 测试Calculator,input就是比如俩数一个operator, 都有什么case, 怎么测,应该有什么预期结果或错误.-google 1point3acres
第二题, 一个array,rearrange成为另一个array, 现在给了这两个array, 求是怎么变化成第二个array的. 挺简单的就用了Hashmap秒了...
然后问我,那现在给你原array,也知道了是怎么变化的了,所以我们现在可以用原array求出变化后的array对吗? 但是我要run这个method好多次比如k次, 怎么最快能求出array被rearrange了k次以后的结果? 最后我就推倒出求LCM.
面完他亲切的用中文跟我说,我是他见过面的最好的,时间复杂度最低trade off也说的好. 谢谢小哥给了我信心~么么哒~

. Waral 鍗氬鏈夋洿澶氭枃绔,
第四轮: 印度姐姐.
假装没有准备的样子现场想题目... 谢谢姐姐没有对我下死手T T
. visit 1point3acres.com for more.海上有一片岛, 每个岛就是一个node, 岛和岛之间有的连着有的没连着. 所有连着的岛是一个Group. 求在这片海上, 包含岛屿个数最小的group的岛的个数,和最大的group的岛的个数. 就是返回两个个数值, 肯定就是int[2]嘛. 先讨论了用什么数据结构存储, 跟她说了trade off. 然后开始写..鏈枃鍘熷垱鑷1point3acres璁哄潧
全程想给我挑错, 不断质疑我的代码... 还好我这一轮在高压下还是写的极其顺畅, 一个bug没有出现, 对她也是笑脸相迎, 躲过一劫...

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第五轮: 中国大哥. 竟然中文给我面试, 也是感动哭...
第一题, 一个二维数组代表了一个岛. 周围都是海, 岛的左侧和上侧通向Pacific, 右侧和下侧通向Atlantic. 每个数字都代表了那个位置的海拔高度. 现在下雨了, 雨只有从海拔高的地儿能流向海拔低或者一样的地儿. 返回岛上的分水岭的点, 就是在某个/某些点上, 雨水既能流进Pacific, 又能流向Atlantic. 大哥可能也知道白板写不下,让我写纸上. 足足写了4页A4纸,当然字也写的大...手都写疼了.... 鍥磋鎴戜滑@1point 3 acres
第二题, 给个Google map, 你就测吧...
-google 1point3acres

我的offer效率很高我完全没想到, 5个工作日从onsite到签offer, 真心感谢hr姐姐. 因为我有个WalmartLabs的competing offer正好是那天截止, hr的意思也是我的feedback很好,所以HC没有犹豫,也马上有组想要我, 所以hr加班加点在进HC当天就跟offer team合作把offer弄出来了. 这里再次感谢各位面试官对我高抬贵手, 以及WalmartLabs..... Waral 鍗氬鏈夋洿澶氭枃绔,
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~. 1point3acres.com/bbs
. visit 1point3acres.com for more.
下面是求职总结.

自我介绍一下. 毕业快两年了. Master读的是普通学校的水专业Information Science. 我是极其水,几乎零基础,项目都抱别人大腿, 当时没有好好学习知识, 现在别提多后悔了... 去年开始找工作的时候, 连HashMap是什么都不知道... Leetcode就刷了七十道, 总
拿女生不要太累了要不就这样吧这种谎言安慰自己... 找到了现在的SDET工作,公司和待遇自然也是好不了. 今年三月开始奋发图强, 八月初开始投简历, 十月十五日当天拿到Google和WalmartLabs的两个offer (对没错,WalmartLabs真的不给考虑时间,当天deadline). 总之是零基础, 靠努力学习和坚持不懈活了下来. 如果你跟我的情况类似,希望我的经验可以帮到你~

CC150. 看了一遍version 5. 据说新版本v6页数多了一倍... 还是希望大家坚持把每一章都看了,对新手帮助很大.

Leetcode. (没有做过Lintcode等等, 我觉得选一个刷题网站全弄会了其实就可以...) 三月到十月共刷5遍,订了subscription,每遍仔细做了每一道题. 过程确实相当痛苦,每天还要上班,一有空就得刷题,周末也不得停歇. 尤其前两遍,基本都是看完答案背着写一遍的,可能也是因为我比较笨... 但是幸亏坚持下来了~ 当我做到第四遍的时候, 有一种通了的感觉, 即使拿到一道新题, 也能比较快的有思路. 这里还是希望我们找工作的朋友们好好刷Leetcode, 弄通弄懂算法精髓, 举一反三. 不要有侥幸思想, 非牛人刷了一遍就想找到非常满意工作的真的少之又少.

Geeksforgeeks. 讲解非常清楚明白易懂, 尤其在学习数据结构和算法上面帮助很大. 它对于很多算法都会有一系列的问题的讲解, 看过之后基本对于某一部分的题目都没什么问题了. 比如Trie,BST的讲解, longest common subsequence一个系列,KMP算法等等,我都是得益于它. 一个算法想不明白,可以先去搜搜geeksforgeeks有没有讲解~

Data structure & Algorithms. 最基础也是最重要的部分, 千万别小瞧基础.
为什么一再强调数据结构与算法基础? 就算刷了十遍leetcode/lintcde等等刷题网站,面试还是会有没见过的题的. 遇到完全没见过的题该怎么办,没有强大的基础知识储备,怎么看穿这道题的本质,怎么很快有思路? 一切都要靠基础, 甚至比刷题本身更重要.
每个数据结构一定要做到彻底明白概念, 结构, 功能, 怎么用. 一定要亲自在IDE里面至少implement一遍!! 推荐书目: 我精读了Data Structures and Algorithms in JAVA. 非常适合初学者, 每个数据结构的实现和用法都写的极其详细. 精读了每一章, 并且implement了两遍里面所有数据结构. 我也听有的人说精读Introductions to Algorithms, 但是这本书感觉不是很适合我这种初学者... 如果你有基础或者是科班出身,面试之前详读Intro to Algo我觉得会很受用的.

刷题的过程中,会遇到很多没见过的算法和数据结构的用法. 比如说graph, 在leetcode里面会有用到dfs, bfs, topology, dijkstra等等算法, 每当遇到一种没见过的, 就脱离这道题, 去网上搜索这究竟是什么, 怎么实现的,
怎么用, 在IDE里面自己亲自实现算法本身, 很生疏的算法要多实现几遍. 这个过程是让我提高最大最快的一步.

Java Conception. 内推我Google的大牛朋友让我看Thinking in Java和Effective Java这两本书. 虽然没有看完,但是确实是非常棒的两本书, 尤其是
Thinking in Java. 据说每看一遍都会对Java有全新的认识, 非常值得一看. 如果实在没有时间,只是为了面试紧急补课, 至少看会这个网站的Java面试题 http://www.programmerinterview.com/-google 1point3acres

Big Data. 今年以来,我发现几乎所有公司的面试都不约而同的添加了大数据相关的问题,就连Walmartlabs的SDET职位的面试中都遇到了,不得不说大数据真是现在一个很猛的trend... 在面Bloomberg的时候就是因为大数据的问题不会而吃了亏挂了,回家以后恶补了很久...
这里推荐这个blog,很多朋友都应该看过: http://blog.csdn.net/v_july_v/article/details/7382693. 1point3acres.com/bbs
我很想知道写这个blog的是个怎样的人,真心膜拜... 他的总结几乎囊括了所有大数据方面的知识背景,实在赞叹. 对于这个帖子里面提到的知识点,他都有专门介绍的链接,全面又方便. 如果想面试无敌的话,每个知识点都要自己多查资料弄懂,每道题都自己过一遍. 对于里面提到的不同方法要多比较, 每种方法什么时候适用, trade off是什么都要清楚. 重中之重是Map Reduce和External sort.. from: 1point3acres.com/bbs
. from: 1point3acres.com/bbs
Thread & Locks. 考得不多但是面ebay碰到了. 主要知识点: thread和process区别, multithread, lock, semaphore, 对resource分配, deadlock, 怎么解决/预防deadlock. 还有BlockingQueue 和 Producer-Consumer经典题要会implement.
这里有几个经典问题:. more info on 1point3acres.com
http://www.careercup.com/question?id=4783236498587648.鐣欏璁哄潧-涓浜-涓夊垎鍦
http://www.careercup.com/question?id=5652784707796992
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
OOD. 老老实实实现了两遍Singleton, Factory, 还有MVC pattern. 设计一个class应该也算在OOD范围里: 写过无数遍LRU, Trie, Iterator, BST以及变种, BlockingQueue等等, 生怕被问到...

System Design. 这个对不住大家,我最后没面到过系统设计,所以不太知道自己这点准备到底充不充分... 如果你要面Facebook几乎肯定是要考系统设计的,还是得好好准备. 一定要看FB的engineering blog, 看的越多越好. 基础的概念至少要会: load balancer, cache, memcache, consistent hashing, round robin, master slave, sharding, pre-computed, map reduce, difference with SQL/NoSQL.... 有很多牛人总结的系统设计帖,我就不多置喙了,这里推荐几个帖子.
http://massivetechinterview.blogspot.com/2015/06/itint5.html
http://www.mitbbs.com/article_t/JobHunting/32777529.html. Waral 鍗氬鏈夋洿澶氭枃绔,
http://blog.csdn.net/sigh1988/article/details/9790337
还有这个公开课,太棒了,新手入门必备,谢谢成哥推荐~
https://www.udacity.com/course/viewer#!/c-cs253/l-48737165.鐣欏璁哄潧-涓浜-涓夊垎鍦

Resume. 就一点,要把自己简历上每个项目都弄熟, 写下项目介绍背下来, 这样被问到的时候可以张口就来. 也要把你要面试的单位的简介自己总结一遍背下来, 还有你为什么想来我们单位, 如果你有工作你为什么想跳槽, 你觉得为什么适合这个职位等等. 其实这些都是标答, 只要好好准备过一次就能适用于各个公司...


这里有一个我总结的软加分项. 尤其对妹子, 说实话妹子是可以很占优势的, 特别如果你是个漂亮妹子~ 你的性别,说话的态度,眼神,都可以成为你的加分项, 一定要利用这一点. 为什么我突然说这个,不是说这只是个锦上添花的事情,而是因为这个点非常重要,其实男生也一样. 一个面试官想要找的不仅仅是能够做出题的人,更需要的是找到一个合适的teammate. 你是不是好说话,是不是能聆听而不是一味反驳别人坚持自己,是不是能马上接纳别人,接受别人的idea并且有接受新知识的能力,从某些方面来说,比仅仅能做出来这道题重要得多. 所以面试的时候, 那天早上就告诉自己今天是去跪舔的,别耍态度,如果你是大神可以除外... 最好全程微笑,遇到不会的题的时候更要微笑. 把想题的过程全部说出来, 不能成为心理活动, 让对方知道你在非常努力的思考, 而且态度很好, 所以就算你没有完全想出来, 他是非常愿意给你hint的. 态度决定很多事,甚至人生.

好啦,我啰啰嗦嗦了那么多真是不好意思T T.... 但愿这篇总结能给任何人一点点的帮助我就没白写~多努力就有多幸运.希望大家都能坚持到底,不倒在黎明前,最终拿到很多大offer,进入自己梦想中的公司,开启人生新的篇章!
. From 1point 3acres bbs


最后. 妈妈 我爱你



. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
.1point3acres缃


补充内容 (2015-10-19 01:25):

不好意思各位~ onsite 第一轮第二题漏了一个点. 除了array是unsorted以外, pivot也是随机的. 也就是说不是严格的binary search每次的pivot就是中间点, 这个binary search的pivot是在array里面每次随机给你找个点...

补充内容 (2015-10-19 01:26):
当然pivot每次都是valid的, 不会出现在已经删除的部分里. 举个例子, 比如[4,2,1,3,5], target是4, 第一次的随机pivot是位置3也就是3. 此时target>3, 所以删除左边部分[4,2,1,3]只剩下了[5].
-google 1point3acres
补充内容 (2015-10-19 01:27):. 鍥磋鎴戜滑@1point 3 acres
由此看出4是不能够被这种方法binary search出来的. 其实这里面能被binary search出来的只有[5]
.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2015-10-21 01:28):
哈哈~很多朋友都在问我是不是真的去年都不会hashmap啥的,是真的~ 昨天一个学长还回忆起了我刚来美国时候的场景, 说发现我当时真的是啥都不会, 就差说我智商捉急了...~

评分

62

查看全部评分

本帖被以下淘专辑推荐:

 楼主| thebestsarah 发表于 2015-10-19 01:31:14 | 显示全部楼层
又见紫风铃 发表于 2015-10-19 01:19. visit 1point3acres.com for more.
哦~那是不是可以理解成只有这个数左边的都小于它右边的都大于它才是能够binary search到的咯?这样只想到 ...

对~ 其实用一个boolean[]或者hashset来记录每个数是不是符合要求就行. . visit 1point3acres.com for more.
从左往右扫一次,记录全程最大值,如果当前值小于左侧最大值,就不符合要求-google 1point3acres
同理再从右往左扫一次,记录全程最小值,如果当前值大于右侧最小值,就不符合要求. 所以扫两次O(n)就可以了~

评分

1

查看全部评分

回复 支持 3 反对 1

使用道具 举报

 楼主| thebestsarah 发表于 2015-10-19 03:12:23 | 显示全部楼层
codermax 发表于 2015-10-19 03:06
恭喜楼主!预祝在G顺风顺水!

楼主能提点以下第一题怎么做的吗?
. 1point3acres.com/bbs
public static int[] reorder(int[] a){-google 1point3acres
                if(a==null||a.length==0) return new int[0];
                int n = a.length;
                int[] b = new int[n]; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                List<Integer> list = new ArrayList<>();
                for(int i=1; i<=n; i++){
                        list.add(i);//1,2,3,4,5
                }. from: 1point3acres.com/bbs
                for(int i=n-1; i>=0; i--){
                        b = list.remove(i-a);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                }
               
                return b;
        }

补充内容 (2015-10-19 03:15):
for循环里应该是. From 1point 3acres bbs
b = list.remove(i-a);
不知道为啥copy paste之后变了...

补充内容 (2015-10-19 03:16):
我去...为啥还是这样...
应该是 b [ i ] 和 a [ i ] ....
回复 支持 2 反对 0

使用道具 举报

 楼主| thebestsarah 发表于 2015-10-19 00:19:40 | 显示全部楼层
又见紫风铃 发表于 2015-10-18 21:36
onsite第二轮的encode decode还是好晕。。为什么说一定encode要比原来短,还能够5xq这种1x51xx1xq呢。。楼 ...

我觉得韩国哥哥的意思是, 基本rule是encode要比原来短,但是他也没明说, 有的地方也不一定要遵守这个rule... 所以具体是长是短还是要具体分析...我当时就是死守一定要变短这一点, 所以就没往别的地儿想T T
他就对我说了一句1xt怎么办? 我理解的意思是遇到原本就是"5xt"这种pattern的原String的时候, 在encode时为了能够将来decode回来, 对每一个char都进行encode. 也就是"5xt"拆成三个char分别都encode => "1x5", "1xx", "1xt"
.鐣欏璁哄潧-涓浜-涓夊垎鍦
LCM和GCD是Google常考的数学知识, 很高兴你问到~
. from: 1point3acres.com/bbs
        public static int getLCM(int a, int b){
                return (a*b)/getGCD(a, b);
        }. 1point 3acres 璁哄潧
        public static int getGCD(int a, int b){
                if(a==b) return a;
                if(a>b) return getGCD(a-b, b);
                else return getGCD(a, b-a);
        }
       
回复 支持 2 反对 0

使用道具 举报

will_ym 发表于 2015-10-18 22:43:45 | 显示全部楼层
第五轮第一题 我的想法是建立两个二维矩阵然后DP,然后两个二维矩阵取AND就得到结果了。不过楼主写了四页,感觉我这个不太对啊,求问楼主思路啊
回复 支持 0 反对 1

使用道具 举报

 楼主| thebestsarah 发表于 2015-10-20 11:51:47 | 显示全部楼层
queeniejing 发表于 2015-10-20 04:46
LzMM, 我看了你的文章非常非常感同身受也很受鼓励,我跟你情况差不多一模一样,在职找工作,而且也是非CS ...

问题比较多啊~ 我来慢慢回答
首先电面一般要简单些, 你leetcode才刷完一遍的话, 最好在这一周里多刷几道题, easy和medium为主, 不是说要背答案啥的,而是把这个手感维持下去,大脑处于勤思考的状态, 对面试帮助比较大.
最重要的是千万别紧张,就当做今天只是跟一个人一起做道题的这种心态就对了. 千万别学我,那么简单的题就是因为紧张,啥都不会了...
面试的时候遇到新题,首先肯定是不会的...但是我的话一般会重复一遍这个问题, 问他这个问题和return值我的理解对吗? 这个过程就是找思路的过程,需要你对数据结构很熟悉(这里又要强调数据结构了咳咳...),题目无非就是用相关的数据结构解决. 你要看这道题给了你什么条件, 要求得到什么, 这时候你在脑子里就过一遍所有数据结构的特性, 哪种数据结构有一样的特点能用于这道题. 心里想了一遍之后, 一定要跟他说出来你刚才的思想过程, 即使不对他也会知道你在积极思考,而不是傻等着什么也不会. g家面试官是水平最高的, 看的就是你聪不聪明基础扎不扎实, 所以多说话总没错.
等你LC刷到第四遍你就懂了~ 在一次次因为小bug而run不过case以后,很多bug自己就都能发现了... bug free我觉得基本谁都做不到,但是自己快速发现并且解决它是很关键的.. more info on 1point3acres.com
刷到第四遍开始投简历. 因为是在职找工作所以只能准备的非常充分了才开始面的. 这样我保证了每一个phone interview都有onsite, 不会错过机会. 后来发现以赛代练效果也很好, 建议先拿一两个小公司练手, 因为第一次面试还不适应,很大可能会比较糟糕...
不客气哈. 另外谢谢你~~
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
回复 支持 1 反对 0

使用道具 举报

will_ym 发表于 2015-10-18 21:24:38 | 显示全部楼层
恭喜楼主拿到offer 想请问一下onsite第一轮第二题是什么意思啊 没太看懂啊 search什么呢?
回复 支持 反对

使用道具 举报

又见紫风铃 发表于 2015-10-18 21:28:49 | 显示全部楼层
will_ym 发表于 2015-10-18 21:24. 鍥磋鎴戜滑@1point 3 acres
恭喜楼主拿到offer 想请问一下onsite第一轮第二题是什么意思啊 没太看懂啊 search什么呢?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
就是search array里的target吧我觉得,比如[4,2,1,3,5]能用binary search找到的就是[1,3,5]。感觉只能想到O(nlogn)的brute force的办法。求大神们指点
回复 支持 反对

使用道具 举报

又见紫风铃 发表于 2015-10-18 21:36:38 | 显示全部楼层
onsite第二轮的encode decode还是好晕。。为什么说一定encode要比原来短,还能够5xq这种1x51xx1xq呢。。楼主脑洞大开在Hint 1xt那儿想出来的是什么方法呢。。

补充内容 (2015-10-18 21:50):
另外楼主能讲一下Onsite第三轮的LCM具体怎么做的么
回复 支持 反对

使用道具 举报

will_ym 发表于 2015-10-18 22:59:25 | 显示全部楼层
又见紫风铃 发表于 2015-10-18 21:28
就是search array里的target吧我觉得,比如[4,2,1,3,5]能用binary search找到的就是[1,3,5]。感觉只能想 ...

多谢指点 同求更快的方法
回复 支持 反对

使用道具 举报

grandture 发表于 2015-10-18 23:52:56 | 显示全部楼层
求问LZ, Softwre Engineer, Tools and Infrastracture 和 一般的Software Engineer 有什么区别吗?
回复 支持 反对

使用道具 举报

 楼主| thebestsarah 发表于 2015-10-19 00:06:16 | 显示全部楼层
不好意思各位~ onsite 第一轮第二题漏了一个点. 除了array是unsorted以外, pivot也是随机的. 也就是说不是严格的binary search每次的pivot就是中间点, 这个binary search的pivot是在array里面每次随机给你找个点. 当然pivot每次都是valid的, 不会出现在已经删除的部分里. 举个例子, 比如[4,2,1,3,5], target是4, 第一次的随机pivot是位置3也就是3. 此时target>3, 所以删除左边部分[4,2,1,3]只剩下了[5]. 由此看出4是不能够被这种方法binary search出来的. 其实这里面能被binary search出来的只有[5]
回复 支持 反对

使用道具 举报

 楼主| thebestsarah 发表于 2015-10-19 00:07:48 | 显示全部楼层
又见紫风铃 发表于 2015-10-18 21:28
就是search array里的target吧我觉得,比如[4,2,1,3,5]能用binary search找到的就是[1,3,5]。感觉只能想 ...
. visit 1point3acres.com for more.
不好意思这道题我漏了一点信息~ 在上边这层楼回复了~
回复 支持 反对

使用道具 举报

 楼主| thebestsarah 发表于 2015-10-19 00:08:08 | 显示全部楼层
will_ym 发表于 2015-10-18 22:59
多谢指点 同求更快的方法
.1point3acres缃
不好意思请看回复~~
回复 支持 反对

使用道具 举报

 楼主| thebestsarah 发表于 2015-10-19 00:32:53 | 显示全部楼层
will_ym 发表于 2015-10-18 22:43
第五轮第一题 我的想法是建立两个二维矩阵然后DP,然后两个二维矩阵取AND就得到结果了。不过楼主写了四页, ...

你的方法我觉得可以~ 两个二维矩阵空间是2n^2, 分别取结果最后取AND一共是扫三次?

我的方法也是DP+DFS,只扫一次. 我用了两个HashSet分别用于存放能够流入Pacific或Atlantic的点的坐标. Pacific和Atlantic两个情况在DFS里同时做.
在DFS的时候, 先分别recursion上下左右四个方向, 如果hashset里面记录过就直接返回结果(当然如果用boolean[] visited去记录当前点有没有被扫过肯定更好, 这题元素太多, 当时时间实在不够了...). 然后判断当前点是否能流入Pacific或Atlantic, 如果能, 分别记录在Hashset里.. visit 1point3acres.com for more.
最后只要看有哪些点在两个HashSet里面都出现就好了.
所以每个点只用扫一次, 空间复杂度就是符合分别能够流入Pacific或Atlantic的坐标个数.
. more info on 1point3acres.com
表达的如此不清楚,不知道能不能大家理解...

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| thebestsarah 发表于 2015-10-19 00:34:04 | 显示全部楼层
grandture 发表于 2015-10-18 23:52
求问LZ, Softwre Engineer, Tools and Infrastracture 和 一般的Software Engineer 有什么区别吗?

都是developer, 不过是做内部软件或者工具
回复 支持 反对

使用道具 举报

storm_hair 发表于 2015-10-19 00:59:24 | 显示全部楼层
原来是女生……
回复 支持 反对

使用道具 举报

oliverhao 发表于 2015-10-19 01:07:24 | 显示全部楼层
最近接到Google家电话面试,还有两个星期,可是hashmap都不会,请问短时间内能准备些什么?
回复 支持 反对

使用道具 举报

storm_hair 发表于 2015-10-19 01:09:56 | 显示全部楼层
oliverhao 发表于 2015-10-19 01:07. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
最近接到Google家电话面试,还有两个星期,可是hashmap都不会,请问短时间内能准备些什么?

可以投PM职位
回复 支持 反对

使用道具 举报

 楼主| thebestsarah 发表于 2015-10-19 01:10:46 | 显示全部楼层

是不是看到这混乱的文风,觉得一定是个汉子~~
回复 支持 反对

使用道具 举报

 楼主| thebestsarah 发表于 2015-10-19 01:12:39 | 显示全部楼层
oliverhao 发表于 2015-10-19 01:07
最近接到Google家电话面试,还有两个星期,可是hashmap都不会,请问短时间内能准备些什么?

是说完全零基础吗? 那...至少把leecode的easy题写一遍吧,数据结构抓紧时间能看多少看多少,争取把phone interview骗过去~
回复 支持 反对

使用道具 举报

又见紫风铃 发表于 2015-10-19 01:19:58 | 显示全部楼层
thebestsarah 发表于 2015-10-19 00:07
不好意思这道题我漏了一点信息~ 在上边这层楼回复了~

哦~那是不是可以理解成只有这个数左边的都小于它右边的都大于它才是能够binary search到的咯?这样只想到O(n^2)找到这样的点了。。楼主当时怎么做的呢?
回复 支持 反对

使用道具 举报

又见紫风铃 发表于 2015-10-19 01:21:04 | 显示全部楼层
thebestsarah 发表于 2015-10-19 00:19
我觉得韩国哥哥的意思是, 基本rule是encode要比原来短,但是他也没明说, 有的地方也不一定要遵守这个rule. ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
赞!不过我想问的是LCM和这个array rearrange多少次是什么关系呢?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 00:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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