x****1
发帖数: 118 | 1 Google onsite归来，回馈本版，贡献一点面经和体会。记题的能力不是太好，就捡记
得住的说吧。废话不说，直接上题：
Phone screen：
先问了10道左右的小题，都是概念性的。
包括OOP，hashtable，BST，big O问题, 多线程，都是基本知识，没有什么tricky的地方。
有一道程序改错题，程序大概是替换一个字符串里面的pattern，不知道是谁写的，不是很
organized，估计是其他面试的同学的程序，我看了半天虽然觉的code写得很别扭，但也没找出什
么大错，面试官看我卡住了，就说我们继续吧。好在后来的题都答得比较顺利。
接下来又问了问现在做的项目，根据我的项目问了些问题，如server端如何实现session，项目中
有没有多线程，怎么实现。
最后还有5分钟结束的时候，给留了两道coding题，让我明早之前发给他。
一个就是binary search，不用多说了。
另外一个就是如何查找rotated sorted array (这也是很常见的题，因为面试官讲的是
cyclic，所以一开始我理解成{123456456}，后来email问了才明白题意）。
我为了给面试官留下好印象，挂了电话就开始写code，发email询问第二题理解不清的地方。因为是
常见题，很快完成，run了一下没什么问题就发过去了。
当天晚上面试官回信谢谢我给他发题。（这个人的确很nice）
过了两天recruiter电话告诉我可以去local office onsite，有点出乎我的意料，因为觉得改
错那道题答得很不好。之前没有想到会给onsite，既然给了机会就不要放弃，于是我开始玩命复
习。此时距onsite有两周半时间。白天在小公司上班，干不了私活。晚上回家吃完饭就开始看刚买
的cracking the coding interview, 从string ，array看起，周末两天在图书馆泡着练看
过的题目，这两周过的极度崩溃。基本练完了那本书上的题，还练了ihas1337code上面的不少题。
先不说废话，上onsite的题：
第一个人问我的全是design的问题。
先问我懂不懂TDD，我说懂一点，于是胡扯一通。
然后从我做的项目聊起来。我自己多嘴，说我们现在的设计不好，不容易实现TDD，要是改成MVC或
者MVP就好实现TDD。于是他就问我怎么把我的项目改成MVP，其实我没有准备，就根据基本概念胡扯
一番，讲了每一个部分做什么，他把我说的都认真做的笔记，因为他说他只知道MVC不懂MVP，回去
要做做功课。我说其实差不多，因为我也的确说不出什么区别。
讲完项目，就出了一道design题，其实巨简单，就是所有面向对象教材讲继承这一章的例题。给了
circle， oval，cube，square，rectangle/ diameter， perimeter，area，
surface， volum；写abstraction 虽然简单，但是是我发挥最差的一道，因为一直复习
coding，冷不丁来这么一题，有点不知如何下笔。我写了shape，2d， 3d的抽象类，然后准备去
写各个继承类，然后没时间了，就没写完，口头回答了他的几个问题。失误是在动笔之前没有好好想
一下结构，边写边想边改，很乱还没写完。
第二个人是个大牛，言谈举止比较古怪，有点高傲，但还算gentle。
大牛废话特别多，讲题blabla一大堆，都没听明白，不知道重点是什么要让我做什么。交流过后才
大概清楚是一道貌似google题库题（我没见过，但是后面的面试官又提到过这题）题目大概是这样
的：actor和actor之间用同时参演的movie连接，给你两个方法, getActorsByMovie() 和
getMoviesByActor(), 让你去找连接两个actor的movies。上来先问我这两个方法返回值用什
么collection比较好，我说arraylist，然后解释为什么。接下来开始解题，我说可以看成图，
节点是actor，路径是movie，然后用广度或者深度去遍历。我就回忆cracking the coding上
4.2那道题开始写code。写的过程中大牛随时指出我写的有问题的地方，于是我边写边改边交流，最
后时间到了，差一点没写完。讲了我接下来几行的思路给大牛听。大牛对着白板拍了张照片然后带我
吃饭的人就进来了。（每个面试官都会对白板拍照，不知道其他公司是否也这样）
第三个人是个中规中矩的美国中年白人
介绍了自己，以前在微软后来，3年前跳google。他问的全是小题，给了方法的signature，填
code。
第一题是 bool isOverlap(int a, int b, int c, int d)参数取值范围0~6代表星期
几。a 到b是一个区间，c到d是一个区间，查看有没有overlap，要考虑跨周末的情况。我简单画了
个图，给出各种情况。我知道肯定有技巧，但是当时想不出来，于是准备按部就班写code，他说你能
不能不用大于号和小于号，因为有巧妙的解法。于是我就使劲想，还是没想出来。他说我们做下一道
吧。
之后有merge sorted array，bool isPowerOfThree(int n)，我很快完成code。然后出
了一道类似于spell checking的题 void foo(string word, string[] dictionary),
如果改word一个字母，新word出现在dictionary里面，就要改正这个word，比如字典里有
apple，word=appre，你就要改正这个单词。我的方法就是逐位比较，count不match的位，要是
1的话就改正。也不知道有什么更巧妙的方法。然后又问我怎么优化dictionary，我说先按length
分类，他说这就是他想听到的。又问我要是去查漏掉一位的单词如何实现，比如appe 和apple，我
说加一个空格或者特殊字符进appe然后用我之前的方法查，他又说这是他想听到的。后来感觉他的题
也问完了，随便聊了两句，下一个人就来了。
第四个人
最年轻的一个，在google干了三年，以前有没有别的地方做过不知道。这个人说他们的server
crash了，正在trouble shooting，所以晚了几分钟过来。我说你要考我的题不会就是你正在
trouble shooting的问题吧。他笑了笑说不是，然后给我出了第二个面我的大牛的那道题，我说
我刚做过这道题，刚才做的不是很好，现在有了好的思路，要不要我再做一遍。（这个时候我挺放松
的，因为这个人比较年轻，而且感觉上一个面的还不错）他显然没什么其他准备，于是先让我写了一
个binary search，我心想怎么会问这么简单的题。很快写完了。他估计是趁我写binary的时候
想题呢。
第二题问我怎样serialize和deserialize 一个binary tree，目的是在网络中传输。我问他
是不是BST，是不是balanced，他说不是。于是我想起ihas1337code那道preorder和inorder
数组生成tree的题。就说先做preorder和iorder得到两个数组，然后又描述了如何通过他们恢复
原树。我本以为这是标准答案，没想到他说以前没人这么解这道题，不过看我的解法肯定是work的。
我问你有更好的解法？你是希望我去把我的解法写code还是想我继续想其他解法，他说 继续想想其
他解法（正合我意，虽然也能吭哧出来这道题的code，前几天刚练过，但是讲思路聊天总比coding
好）于是就开始讨论各种方法，他说你想一想如何用一个string表示这个tree，我就说插入一些特
殊符号做标记，他说那你要是就想传这些特殊符号怎么办。说着说着我发现这不就是xml嘛，他说
xml肯定能实现，但最终也没说他心中的标准答案是什么。（这个是最轻松的一个）
最后一个人来的时候问我累不累，要不要喝水。我说不用了，一鼓作气吧。
聊了几句他开始出题，给一个吸地毯的irobot，和一个长方形的屋子，四面有墙，四个指令：
Bool moveForward（）//向前走一格，走不了的话返回false
Void Rotate（int degree）//就是左拐右拐
Bool isClean（）//当前单元格是否干净
Void clean（）
把irobot 扔在屋子任意位置，写代码让irobot清理房间，每一格都要走过（单元格没有坐标）。
我一开始想外螺旋，后来经提醒发现行不通；
然后内螺旋，也行不通；
（前几天看本版竟是讨论螺旋矩阵，所以不由自主老想螺旋）
后来尝试贪吃蛇走法，发现行得通，于是开始coding。说实话，这个时候已经很累了，思路也慢
了，题目简单但是coding挺繁琐的，写着写着自己都乱了，一度想放弃。最后还是吭哧出来了。面
试官跟我过了一遍code，看看能不能实现。看来我写的不是标准答案，至少代码不是最简洁的。
总结：
Google面试也不是传说中的那么恐怖，每道题都会有思路，但是临场发挥，白板coding还是挺有挑
战的。我自知功力还不够，没有抱过任何希望，也不求祝福了，发点题只是为了回馈本版。
面完了，终于可以不用每天折磨自己练题了。话说这是我第一个big name的onsite当初
recruiter找我的时候，我都没敢回信，心想自己水平差得远着呢，recruiter又通过linkedin
发了站内信，我不好意思才回信联系了电面。现在回想这前前后后一个月准备面试，的确提高了不少
（只是应对面试而言）。以后继续努力，等实力到了那个份上，去big name就水到渠成的事了。
PS: 问了recruiter最近hiring process 有没有slow down，她说没有特别原因，只是夏天
take vocation的人比较多，所以会比平时慢一点。不管是不是真的，反正自己好好准备，机会来
了去把握就是了，一辈子又不是只有这一次机会。大家都加油吧！ |
h*********n
发帖数: 11319 | 2 bless, 看来很有戏
area
法,
word
preorder
xml
coding
【在 x****1 的大作中提到】
: Google onsite归来，回馈本版，贡献一点面经和体会。记题的能力不是太好，就捡记
: 得住的说吧。废话不说，直接上题：
: Phone screen：
: 先问了10道左右的小题，都是概念性的。
: 包括OOP，hashtable，BST，big O问题, 多线程，都是基本知识，没有什么tricky的地方。
: 有一道程序改错题，程序大概是替换一个字符串里面的pattern，不知道是谁写的，不是很
: organized，估计是其他面试的同学的程序，我看了半天虽然觉的code写得很别扭，但也没找出什
: 么大错，面试官看我卡住了，就说我们继续吧。好在后来的题都答得比较顺利。
: 接下来又问了问现在做的项目，根据我的项目问了些问题，如server端如何实现session，项目中
: 有没有多线程，怎么实现。
|
c******n
发帖数: 710 | |
a*****g
发帖数: 110 | 4 zan & bless!!
的地方。
不是很
但也没找出什
session，项目中
【在 x****1 的大作中提到】
: Google onsite归来，回馈本版，贡献一点面经和体会。记题的能力不是太好，就捡记
: 得住的说吧。废话不说，直接上题：
: Phone screen：
: 先问了10道左右的小题，都是概念性的。
: 包括OOP，hashtable，BST，big O问题, 多线程，都是基本知识，没有什么tricky的地方。
: 有一道程序改错题，程序大概是替换一个字符串里面的pattern，不知道是谁写的，不是很
: organized，估计是其他面试的同学的程序，我看了半天虽然觉的code写得很别扭，但也没找出什
: 么大错，面试官看我卡住了，就说我们继续吧。好在后来的题都答得比较顺利。
: 接下来又问了问现在做的项目，根据我的项目问了些问题，如server端如何实现session，项目中
: 有没有多线程，怎么实现。
|
c****p
发帖数: 6474 | 5 一周7天是不是overlap那个怎么做。。
还有isPowerOf3有O(1)的实现么
的地方。
不是很
但也没找出什
session，项目中
【在 x****1 的大作中提到】
: Google onsite归来，回馈本版，贡献一点面经和体会。记题的能力不是太好，就捡记
: 得住的说吧。废话不说，直接上题：
: Phone screen：
: 先问了10道左右的小题，都是概念性的。
: 包括OOP，hashtable，BST，big O问题, 多线程，都是基本知识，没有什么tricky的地方。
: 有一道程序改错题，程序大概是替换一个字符串里面的pattern，不知道是谁写的，不是很
: organized，估计是其他面试的同学的程序，我看了半天虽然觉的code写得很别扭，但也没找出什
: 么大错，面试官看我卡住了，就说我们继续吧。好在后来的题都答得比较顺利。
: 接下来又问了问现在做的项目，根据我的项目问了些问题，如server端如何实现session，项目中
: 有没有多线程，怎么实现。
|
i**********e
发帖数: 1145 | 6 >>第一题是 bool isOverlap(int a, int b, int c, int d)参数取值范围0~6代表星期
几。a 到b是一个区间，c到d是一个区间，查看有没有overlap，要考虑跨周末的情况。
这题我也被问到了，只不过我的不用考虑跨周末的情况。
如果不用考虑跨周末，直接 return min(b,d) - max(a,c) > 0 就行了，因为如果相交
的话，其中一个终点必须包括在另一个区间。
如果要考虑跨周末的话，也就是当起点大于终点的状况：【2,1】 --> 指的是星期三到
星期二，那么把起点减掉 7，这样就能保证起点永远小于或者等于终点了，然后再用回
之前的方法。
不知道 lz 的方法是不是这样？怎样还有更巧妙的 trick，可以不用 >, < 来做？
另外要加个强 bless！
的地方。
不是很
但也没找出什
session，项目中
【在 x****1 的大作中提到】
: Google onsite归来，回馈本版，贡献一点面经和体会。记题的能力不是太好，就捡记
: 得住的说吧。废话不说，直接上题：
: Phone screen：
: 先问了10道左右的小题，都是概念性的。
: 包括OOP，hashtable，BST，big O问题, 多线程，都是基本知识，没有什么tricky的地方。
: 有一道程序改错题，程序大概是替换一个字符串里面的pattern，不知道是谁写的，不是很
: organized，估计是其他面试的同学的程序，我看了半天虽然觉的code写得很别扭，但也没找出什
: 么大错，面试官看我卡住了，就说我们继续吧。好在后来的题都答得比较顺利。
: 接下来又问了问现在做的项目，根据我的项目问了些问题，如server端如何实现session，项目中
: 有没有多线程，怎么实现。
|
i**********e
发帖数: 1145 | 7 关于第一题，突然想到一个方法：
既然区间里只有7天，那为何不用一个 byte (8 bits）来表示一个区间呢？
这样判断两个区间是否相交，只要两个区间做一个 and operation，0 就代表不相交，
否则相交。
typedef unsigned char u8;
u8 setBits(int i, int j) {
if (i > j) return 0;
assert(j >= 0 && j <= 6);
assert(i >= 0 && i <= j);
u8 x = (1U << (j+1)) - 1;
u8 y = (1U << i ) - 1;
return x ^ y;
}
u8 createInterval(int start, int end) {
if (start <= end)
return setBits(start, end);
else
return ~setBits(end+1, start-1);
}
bool isIntersect(int a, int b, int c, int d) {
u8 interval1 = createInterval(a, b);
u8 interval2 = createInterval(c, d);
return (interval1 & interval2) != 0;
}
这里有个 edge case 要注意：也就是【0，2】 和【2，3】 是否相交？以上代码会判定为相交。如果这个应该是不相交的话，只要稍微改下就行，也就是不把 end time 包括在区间里。 |
a**********2
发帖数: 340 | |
g**********y
发帖数: 14569 | 9 是可以这样做，但是这个也用了 >, <=。这个题从实质上看，就是你前面贴的:
min(end1, end2) >= max(start1, start2)
我觉得面试官问的，就是要一个巧妙的转化，把上面的情况简单表示出来。
没准可以简单到一句, 也不用 >, <=。
我没想出来他期望什么答案。
【在 i**********e 的大作中提到】
: 关于第一题，突然想到一个方法：
: 既然区间里只有7天，那为何不用一个 byte (8 bits）来表示一个区间呢？
: 这样判断两个区间是否相交，只要两个区间做一个 and operation，0 就代表不相交，
: 否则相交。
: typedef unsigned char u8;
: u8 setBits(int i, int j) {
: if (i > j) return 0;
: assert(j >= 0 && j <= 6);
: assert(i >= 0 && i <= j);
: u8 x = (1U << (j+1)) - 1;
|
m****t
发帖数: 555 | 10 不错，很详细。
最后一道题其实就是图的遍历吧，每个格子当成一个节点，clean 就是 visit. |
|
|
z*******y
发帖数: 578 | 11 赞！
这些题目写出来bug free的code都要费一些时间，虽然没出现DP之类的题目，但不算简单 |
f*******t
发帖数: 7549 | |
x****1
发帖数: 118 | 13 感谢大家祝福。
To： ihasleetcode
你就是ihas1337code的作者吧，你的网站做得很好，对面试很有帮助，谢谢！
关于isOverLap（）那道题，我觉得也许我误导大家了。回忆当时面试官的确提到能不
能不用comparison，但也许他指的只是其中的一个步骤有比用好几个比较巧妙的方法，
而不是整个方法不允许出现comparision。遗憾的是我到现在也不知道标准解法。看过
你给的方法，已经很简单了，我觉得没有必要为了不用comparision而不用去解题。如
果我的表述误导了大家，抱歉。 |
a********m
发帖数: 15480 | 14 bless.
不管怎么说，能去onsite也已经不错了。lz要有信心。:) |
x****1
发帖数: 118 | 15
忘记说了，一开始有些格子是脏的，有些是干净的，所以不能用isClean()判断是否has
visited。
我觉得这道题思路很直接，没有什么复杂的算法，主要是程序要写清楚。让机器人知道
遇到什么样的情况该如何处理。在一个大的while（true）loop里面每次moveforward（
）根据返回值，进行各种判断。这题属于想想简单，写起来麻烦。
我当时的解法是两个while loop，用第一个把机器人移到一个corner，第二个loop让机
器人进行贪吃蛇走法，就是撞墙以后左拐->前进->左拐，下次撞墙右拐->前进->右拐,
同时要判断什么时候清理，什么时候停下。走一点重复的路没关系，其实也是无法避免
的。
【在 m****t 的大作中提到】
: 不错，很详细。
: 最后一道题其实就是图的遍历吧，每个格子当成一个节点，clean 就是 visit.
|
b*****p
发帖数: 9649 | 16 可以不用>,<
只用==,abs,+,-就可以了
input(a,b,c,d),a
output:boolean True:crossover, False:otherwise
如果不相交,那末a
检查
abs(d-b)==abs(c-b)+d-c
or
abs(b-d)==abs(a-d)+b-a
利用
distance(b,d) == distance(b,c) + distance(c,d)
distance(d,b) == distance(d,a) + distance(a,b)
可以证明
abs,==,-,+都可以用bit运算,将进一步加快速度. |
g**********y
发帖数: 14569 | 17 这个解法很好了。如果没有房间大小的参数，很难想象有什么办法可以一点不走重复路。而且这种解法，写起来应该算简单的，其它办法写出来会更复杂。试写一下：
public void cleanRoom() {
// Go to top-left corner (this is just imaginary, not matters)
while (moveForward());
rotate(-90);
while (moveForward());
// Snake clean
rotate(-90);
while (true) {
do {
if (!isClean()) clean();
} while (moveForward());
rotate(-90);
if (!moveForward()) break;
rotate(-90);
do {
if (!isClean()) clean();
} while (moveForward());
rotate(90);
if (!moveForward()) break;
rotate(90);
}
}
has
【在 x****1 的大作中提到】
:
: 忘记说了，一开始有些格子是脏的，有些是干净的，所以不能用isClean()判断是否has
: visited。
: 我觉得这道题思路很直接，没有什么复杂的算法，主要是程序要写清楚。让机器人知道
: 遇到什么样的情况该如何处理。在一个大的while（true）loop里面每次moveforward（
: ）根据返回值，进行各种判断。这题属于想想简单，写起来麻烦。
: 我当时的解法是两个while loop，用第一个把机器人移到一个corner，第二个loop让机
: 器人进行贪吃蛇走法，就是撞墙以后左拐->前进->左拐，下次撞墙右拐->前进->右拐,
: 同时要判断什么时候清理，什么时候停下。走一点重复的路没关系，其实也是无法避免
: 的。
|
b*****p
发帖数: 9649 | 18 binary search的trick其实不少,我根据I has 1337 code大侠的指点读了
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binary
非常强烈的推荐.
code海无涯啊! |
i**********e
发帖数: 1145 | 19 恩，我也觉得是。不用感到遗憾，他们面试要看你的整个思路过程，不是看你最后是不
是做出所谓的‘标准’答案。
谢谢，如果网站还有什么不足的地方还请你多多提出意见来 :)
【在 x****1 的大作中提到】
: 感谢大家祝福。
: To： ihasleetcode
: 你就是ihas1337code的作者吧，你的网站做得很好，对面试很有帮助，谢谢！
: 关于isOverLap（）那道题，我觉得也许我误导大家了。回忆当时面试官的确提到能不
: 能不用comparison，但也许他指的只是其中的一个步骤有比用好几个比较巧妙的方法，
: 而不是整个方法不允许出现comparision。遗憾的是我到现在也不知道标准解法。看过
: 你给的方法，已经很简单了，我觉得没有必要为了不用comparision而不用去解题。如
: 果我的表述误导了大家，抱歉。
|
i**********e
发帖数: 1145 | 20 很好，这个可行，学习了。
但是如果跨周末的情况怎么扩展呢？
【在 b*****p 的大作中提到】
: 可以不用>,<
: 只用==,abs,+,-就可以了
: input(a,b,c,d),a: output:boolean True:crossover, False:otherwise
: 如果不相交,那末a: 检查
: abs(d-b)==abs(c-b)+d-c
: or
: abs(b-d)==abs(a-d)+b-a
: 利用
|
|
|
a**********2
发帖数: 340 | 21 不用考虑障碍物吗？
路。而且这种解法，写起来应该算简单的，其它办法写出来会更复杂。试写一下：
【在 g**********y 的大作中提到】
: 这个解法很好了。如果没有房间大小的参数，很难想象有什么办法可以一点不走重复路。而且这种解法，写起来应该算简单的，其它办法写出来会更复杂。试写一下：
: public void cleanRoom() {
: // Go to top-left corner (this is just imaginary, not matters)
: while (moveForward());
: rotate(-90);
: while (moveForward());
: // Snake clean
: rotate(-90);
: while (true) {
: do {
|
g**********y
发帖数: 14569 | 22 题目没看出有障碍物吧？不能moveForward()应该是撞墙了。
【在 a**********2 的大作中提到】
: 不用考虑障碍物吗？
:
: 路。而且这种解法，写起来应该算简单的，其它办法写出来会更复杂。试写一下：
|
g*****k
发帖数: 623 | 23 可以解决跨周末。
I got one solution.
bool isOverlap(int a, int b, int c, int d) {
int distance = (b-c+7) % 7;
int d1 = (b-a+7)%7;
int d2 = (d-c+7)%7;
return (d1+d2)>distance;
}
Proof:
There are two cases for relationship between b and c:
1) b < c
This is obvious that two intervals overlap iff d1+d2 > 7-(c-b)
2) b > c
This is obvious that two intervals overlap iff d1+d2 > b-c
点了，然后再用回
【在 i**********e 的大作中提到】
: 很好，这个可行，学习了。
: 但是如果跨周末的情况怎么扩展呢？
|
x****1
发帖数: 118 | 24
路。而且这种解法，写起来应该算简单的，其它办法写出来会更复杂。试写一下：
大概就是这个意思，你写的比我当时的简洁一些。对，没有障碍物。
【在 g**********y 的大作中提到】
: 这个解法很好了。如果没有房间大小的参数，很难想象有什么办法可以一点不走重复路。而且这种解法，写起来应该算简单的，其它办法写出来会更复杂。试写一下：
: public void cleanRoom() {
: // Go to top-left corner (this is just imaginary, not matters)
: while (moveForward());
: rotate(-90);
: while (moveForward());
: // Snake clean
: rotate(-90);
: while (true) {
: do {
|
g**********y
发帖数: 14569 | 25 按ihasleetcode那个写法更好解释吧
bool isOverlap(int a, int b, int c, int d) {
int b1 = a + (b-a+7)%7;
int d1 = c + (d-c+7)%7;
return max(a, c) < min(b1, d1);
}
【在 g*****k 的大作中提到】
: 可以解决跨周末。
: I got one solution.
: bool isOverlap(int a, int b, int c, int d) {
: int distance = (b-c+7) % 7;
: int d1 = (b-a+7)%7;
: int d2 = (d-c+7)%7;
: return (d1+d2)>distance;
: }
: Proof:
: There are two cases for relationship between b and c:
|
g*****k
发帖数: 623 | 26 我的算法可以解决跨周末。
【在 g**********y 的大作中提到】
: 按ihasleetcode那个写法更好解释吧
: bool isOverlap(int a, int b, int c, int d) {
: int b1 = a + (b-a+7)%7;
: int d1 = c + (d-c+7)%7;
: return max(a, c) < min(b1, d1);
: }
|
g**********y
发帖数: 14569 | 27 那个code也是跨周末的啊
【在 g*****k 的大作中提到】
: 我的算法可以解决跨周末。
|
x****1
发帖数: 118 | 28
你们的解法都挺好的。
ihas1337code的解法比较直观，改一点也可以跨周末。
你这个比较巧，但是不容易想。
我还得多学习学习
【在 g*****k 的大作中提到】
: 我的算法可以解决跨周末。
|
g*****k
发帖数: 623 | 29 哦，没仔细看，呵呵，这就去看看。
【在 g**********y 的大作中提到】
: 那个code也是跨周末的啊
|
g*****k
发帖数: 623 | 30 呵呵，是，1337站长的很简洁，更明了。
【在 g**********y 的大作中提到】
: 那个code也是跨周末的啊
|
|
|
d*******d
发帖数: 2050 | 31 没说不让走重复路线阿.
路。而且这种解法，写起来应该算简单的，其它办法写出来会更复杂。试写一下：
【在 g**********y 的大作中提到】
: 这个解法很好了。如果没有房间大小的参数，很难想象有什么办法可以一点不走重复路。而且这种解法，写起来应该算简单的，其它办法写出来会更复杂。试写一下：
: public void cleanRoom() {
: // Go to top-left corner (this is just imaginary, not matters)
: while (moveForward());
: rotate(-90);
: while (moveForward());
: // Snake clean
: rotate(-90);
: while (true) {
: do {
|
d*******l
发帖数: 338 | 32 我倒是想到一个严格不用<>的办法，想法也比较直接，但就不太简洁了。
bool isOverlap(int a, int b, int c, int d)
{
int i;
for(i = a; i != b; i=(i+1)%7)
if(i == c || i == d)
return true;
for(i = c; i != d; i=(i+1)%7)
if(i == a || i == b)
return true;
if(b == c || b == d || d == a)
return true;
return false;
} |
y*****o
发帖数: 689 | 33 讨论得好热闹阿，虽然看不懂但是LZ加油加油加油！！！ |
F*******0
发帖数: 28 | 34 I think the easiest way is like below:
bool isOverlap(int a, int b, int c, int d)
{
int old = a;
do
{
if (a == b)
return false;
if (a==c || a==d)
return true;
a++;
if (a == 7)
a = 0;
} while (a != old);
} |
F*******0
发帖数: 28 | 35 I think the easiest way is like below:
bool isOverlap(int a, int b, int c, int d)
{
int old = a;
do
{
if (a == b)
return false;
if (a==c || a==d)
return true;
a++;
if (a == 7)
a = 0;
} while (a != old);
} |
F*******0
发帖数: 28 | 36 I think the easiest way is like below:
bool isOverlap(int a, int b, int c, int d)
{
int old = a;
do
{
if (a == b)
return false;
if (a==c || a==d)
return true;
a++;
if (a == 7)
a = 0;
} while (a != old);
} |
F*******0
发帖数: 28 | 37 I think the easiest way is like below:
bool isOverlap(int a, int b, int c, int d)
{
int old = a;
do
{
if (a == b)
return false;
if (a==c || a==d)
return true;
a++;
if (a == 7)
a = 0;
} while (a != old);
} |
F*******0
发帖数: 28 | 38 I think the easiest way is like below:
bool isOverlap(int a, int b, int c, int d)
{
int old = a;
do
{
if (a == b)
return false;
if (a==c || a==d)
return true;
a++;
if (a == 7)
a = 0;
} while (a != old);
} |
F*******0
发帖数: 28 | 39 I think the easiest way is like below:
bool isOverlap(int a, int b, int c, int d)
{
int old = a;
do
{
if (a == b)
return false;
if (a==c || a==d)
return true;
a++;
if (a == 7)
a = 0;
} while (a != old);
} |
F*******0
发帖数: 28 | 40 I think the easiest way is like below:
bool isOverlap(int a, int b, int c, int d)
{
int old = a;
do
{
if (a == b)
return false;
if (a==c || a==d)
return true;
a++;
if (a == 7)
a = 0;
} while (a != old);
} |
|
|
g*****k
发帖数: 623 | 41 哥们您忒激动了吧，发了这么多遍?
【在 F*******0 的大作中提到】
: I think the easiest way is like below:
: bool isOverlap(int a, int b, int c, int d)
: {
: int old = a;
: do
: {
: if (a == b)
: return false;
: if (a==c || a==d)
: return true;
|
y**u
发帖数: 28 | 42 isOverlap(4,3,1,2) ?
【在 g**********y 的大作中提到】
: 按ihasleetcode那个写法更好解释吧
: bool isOverlap(int a, int b, int c, int d) {
: int b1 = a + (b-a+7)%7;
: int d1 = c + (d-c+7)%7;
: return max(a, c) < min(b1, d1);
: }
|
g**********y
发帖数: 14569 | 43 No.
4,3 means from Fri to next Thu; 1,2 means from Tue to Wed.
【在 y**u 的大作中提到】
: isOverlap(4,3,1,2) ?
|
y*******g
发帖数: 6599 | |
g*****k
发帖数: 623 | 45 这也应该算overlap吧。
【在 g**********y 的大作中提到】
: No.
: 4,3 means from Fri to next Thu; 1,2 means from Tue to Wed.
|
s**x
发帖数: 7506 | 46 什么是贪吃蛇走法？ google does not show much info. |
x****1
发帖数: 118 | 47 参考17楼：）
【在 s**x 的大作中提到】
: 什么是贪吃蛇走法？ google does not show much info.
|
x****1
发帖数: 118 | 48 这当然算了
【在 y**u 的大作中提到】
: isOverlap(4,3,1,2) ?
|
h**********s
发帖数: 20 | 49 捣腾出来一个return ((b-a)(d-c)(c-b)(d-a)&(1<<32))>>32 的，对吗？ |
x****1
发帖数: 118 | 50 不好意思，没有去验证你的解法。
但是个人觉得bitewise是个不错的思路
【在 h**********s 的大作中提到】
: 捣腾出来一个return ((b-a)(d-c)(c-b)(d-a)&(1<<32))>>32 的，对吗？
|
|
|
k****n
发帖数: 1334 | 51 觉得最主要是考是否能想到(a-b)*(c-d)的方法来简化分支和比较
【在 x****1 的大作中提到】
: 不好意思，没有去验证你的解法。
: 但是个人觉得bitewise是个不错的思路
|
l****s
发帖数: 165 | 52 Google jobs:
http://jobguiding.com/it-jobs/it-companies/google.html
的说吧。废话不说，直接上题：
的地方。有一道程序改错题，程序大概是替换一个字符串里面的pattern，不知道是谁
写的，不是很organized，估计是其他面试的同学的程序，我看了半天虽然觉的code写
得很别扭，但也没找出什么大错，面试官看我卡住了，就说我们继续吧。好在后来的题
都答得比较顺利。
session，项目中有没有多线程，怎么实现。
是cyclic，所以一开始我理解成{123456456}，后来email问了才明白题意）。
的地方。因为是常见题，很快完成，run了一下没什么问题就发过去了。
【在 x****1 的大作中提到】
: 不好意思，没有去验证你的解法。
: 但是个人觉得bitewise是个不错的思路
|
a***r
发帖数: 93 | 53 My solution is about the same as bitwise, it uses an array:
#include
#include
void add_range(int D[], int l, int a, int b) {
if(b
for (int i=a; i<=b; i++) {
D[i%l]+=1;
}
}
bool is_overlap_array(int a,int b,int c,int d) {
int D[7]= {};
int l=sizeof(D)/sizeof(D[0]);
add_range(D,l,a,b);
add_range(D,l,c,d);
for (int i=0; i
if (D[i]>1) { return true; }
}
return false;
}
void main(int argc, const char *argv[]) {
printf("%d", false == is_overlap_array(1,3,5,6));
printf("%d", false == is_overlap_array(5,6,1,3));
printf("%d", false == is_overlap_array(1,3,5,0));
printf("%d", false == is_overlap_array(5,0,1,3));
printf("%d", true == is_overlap_array(0,5,1,3));
printf("%d", true == is_overlap_array(0,3,1,5));
printf("%d", true == is_overlap_array(3,1,2,4));
} |
a***r
发帖数: 93 | 54 LZ的这个题目， 我搞不懂什么意思，难道不是在两个arraylist中求common movie吗？
谁能说说为什么要用graph及怎么用graph来解？
==================================================================
第二个人是个大牛，言谈举止比较古怪，有点高傲，但还算gentle。
大牛废话特别多，讲题blabla一大堆，都没听明白，不知道重点是什么要让我做什么
。交流过后才大概清楚是一道貌似google题库题（我没见过，但是后面的面试官又提到
过这题）题目大概是这样的：actor和actor之间用同时参演的movie连接，给你两个方
法, getActorsByMovie() 和getMoviesByActor(), 让你去找连接两个actor的movies。
上来先问我这两个方法返回值用什么collection比较好，我说arraylist，然后解释为
什么。接下来开始解题，我说可以看成图，节点是actor，路径是movie，然后用广度或
者深度去遍历。我就回忆cracking the coding上4.2那道题开始写code。写的过程中大
牛随时指出我写的有问题的地方，于是我边写边改边交流，最后时间到了，差一点没写
完。讲了我接下来几行的思路给大牛听。大牛对着白板拍了张照片然后带我吃饭的人就
进来了。（每个面试官都会对白板拍照，不知道其他公司是否也这样）
================================================================== |
x****1
发帖数: 118 | 55 比如说我们有a,b,c三个演员，ab同时参演了甲片，bc同时参演了乙片，我们要找连接
ac的影片，返回的应该是是{甲，乙}。
而两个arraylist没有交集(a{甲},c{乙})。
【在 a***r 的大作中提到】
: LZ的这个题目， 我搞不懂什么意思，难道不是在两个arraylist中求common movie吗？
: 谁能说说为什么要用graph及怎么用graph来解？
: ==================================================================
: 第二个人是个大牛，言谈举止比较古怪，有点高傲，但还算gentle。
: 大牛废话特别多，讲题blabla一大堆，都没听明白，不知道重点是什么要让我做什么
: 。交流过后才大概清楚是一道貌似google题库题（我没见过，但是后面的面试官又提到
: 过这题）题目大概是这样的：actor和actor之间用同时参演的movie连接，给你两个方
: 法, getActorsByMovie() 和getMoviesByActor(), 让你去找连接两个actor的movies。
: 上来先问我这两个方法返回值用什么collection比较好，我说arraylist，然后解释为
: 什么。接下来开始解题，我说可以看成图，节点是actor，路径是movie，然后用广度或
|
a***r
发帖数: 93 | 56 明白了，影片不用都参加的。
【在 x****1 的大作中提到】
: 比如说我们有a,b,c三个演员，ab同时参演了甲片，bc同时参演了乙片，我们要找连接
: ac的影片，返回的应该是是{甲，乙}。
: 而两个arraylist没有交集(a{甲},c{乙})。
|
g*****i
发帖数: 2162 | 57 请问用xml怎么做BT serialization? |
r******n
发帖数: 170 | 58 我也理解成一个两重循环了
getLinkMovie(Actor a, Actor b)
{
foreach m in a.movieList
{
foreach (act in m.actorList)
{
if (act==b)
result.push_back(m)
}
}
}
假如按照graph来dfs/bfs来写，careercup上的写法似乎都没有edge的概念。这里得保
持edge的list,而且还可能有多条路径，是不是得递归的写？那个牛人能给个伪码讲讲
吗？
另外觉得这题，是不是跟在SNS里找出两个人的朋友连接关系是一样的吧？
似乎还没想到比较好的写法。
【在 x****1 的大作中提到】
: 比如说我们有a,b,c三个演员，ab同时参演了甲片，bc同时参演了乙片，我们要找连接
: ac的影片，返回的应该是是{甲，乙}。
: 而两个arraylist没有交集(a{甲},c{乙})。
|
g**********y
发帖数: 14569 | 59 看这个描述，我对问题的理解就是直译：
找出连接两个演员的电影，就是两个演员共同参演的电影。
如果针对这个问题，最方便写code的结构是hashset,
public List getCommonMovies(String actor1, String actor2) {
HashSet hs1 = getMoviesByActor(actor1);
HashSet hs2 = getMoviesByActor(actor2);
ArrayList common = new ArrayList();
for (String movie : hs1) {
if (hs2.contains(movie)) common.add(movie);
}
return common;
}
本来这是个简单题，我想大牛可能打算展开来说，变换问题和条件。后来Interview演
变成写那个实现。
从图的角度，这就是个简单的二分图。左边演员，右边电影。
没准大牛本来打算变化个max-flow出来让你解。
》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》
大牛废话特别多，讲题blabla一大堆，都没听明白，不知道重点是什么要让我做什么。
交流过后才大概清楚是一道貌似google题库题（我没见过，但是后面的面试官又提到过
这题）题目大概是这样的：actor和actor之间用同时参演的movie连接，给你两个方法,
getActorsByMovie() 和getMoviesByActor(), 让你去找连接两个actor的movies。上
来先问我这两个方法返回值用什么collection比较好，我说arraylist，然后解释为什
么。接下来开始解题，我说可以看成图，节点是actor，路径是movie，然后用广度或者
深度去遍历。我就回忆cracking the coding上4.2那道题开始写code。写的过程中大牛
随时指出我写的有问题的地方，于是我边写边改边交流，最后时间到了，差一点没写完
。讲了我接下来几行的思路给大牛听。大牛对着白板拍了张照片然后带我吃饭的人就进
来了。（每个面试官都会对白板拍照，不知道其他公司是否也这样） |
x****1
发帖数: 118 | 60 既然大家开始讨论这道题，我就给一下我的解法吧，抛砖引玉。
有不正确的地方，也希望大侠们给予指点。
ArrayList getMoviesOfActors(
Actor a, Actor b,
HashSet actor_set,
HashSet movie_set)
{
ArrayList movieList = new ArrayList();
if(a==b) return movieList;
for(Movie m : getMoviesOfActor(a)){
if(movie_set.contains(m)) continue;
movie_set.add(m);
for(Actor actor : getActorsOfMovie(m)){
if(actor_set.contains(actor)) continue;
actor_set.add(actor);
movieList = getMoviesOfactors(actor, b, actor_set,
movie_set);
movieList.add(m);
return movieList;
}
}
// not found exception
}
【在 r******n 的大作中提到】
: 我也理解成一个两重循环了
: getLinkMovie(Actor a, Actor b)
: {
: foreach m in a.movieList
: {
: foreach (act in m.actorList)
: {
: if (act==b)
: result.push_back(m)
: }
|
|
|
x****1
发帖数: 118 | 61 如果这两个集合没有交集，返回的就是一个空movie set
比如我前面举得例子，假设有a,b,c三个演员，ab同时参演了甲片，bc同时参演了乙片
，我们要找连接
ac的影片，返回的应该是{甲，乙}。而getMoviesByActor(a)和getMoviesByActor(c)没
有交集。
【在 g**********y 的大作中提到】
: 看这个描述，我对问题的理解就是直译：
: 找出连接两个演员的电影，就是两个演员共同参演的电影。
: 如果针对这个问题，最方便写code的结构是hashset,
: public List getCommonMovies(String actor1, String actor2) {
: HashSet hs1 = getMoviesByActor(actor1);
: HashSet hs2 = getMoviesByActor(actor2);
: ArrayList common = new ArrayList();
: for (String movie : hs1) {
: if (hs2.contains(movie)) common.add(movie);
: }
|
l*****y
发帖数: 476 | |
a**********2
发帖数: 340 | 63 好像有点不懂，判重的话，比方说a,b参演丙，丙这条路还会走吗？
而且没看懂走到死路上了怎么处理，题目要求打印所有的路径吗？
如果在原有的例子上加上a，b参演丙，是返回丙，乙 和 甲 乙 两个结果吗？
【在 x****1 的大作中提到】
: 既然大家开始讨论这道题，我就给一下我的解法吧，抛砖引玉。
: 有不正确的地方，也希望大侠们给予指点。
: ArrayList getMoviesOfActors(
: Actor a, Actor b,
: HashSet actor_set,
: HashSet movie_set)
: {
: ArrayList movieList = new ArrayList();
: if(a==b) return movieList;
: for(Movie m : getMoviesOfActor(a)){
|
x****1
发帖数: 118 | 64 当时大牛出这道题的时候也是很没有头绪，东一句，西一句，我在解题的过程中才慢慢
理解了他的意思。有时间的话，我画张图贴上来可能就好理解了。
你举的这个例子很好，不过当时好像没有涉及这种情况，大牛画的例图每两个演员之间
只有一个电影相连。
【在 a**********2 的大作中提到】
: 好像有点不懂，判重的话，比方说a,b参演丙，丙这条路还会走吗？
: 而且没看懂走到死路上了怎么处理，题目要求打印所有的路径吗？
: 如果在原有的例子上加上a，b参演丙，是返回丙，乙 和 甲 乙 两个结果吗？
|
g*****i
发帖数: 2162 | 65 这个不对吧
比如 a=1 b=2 c=4 d=2
b1=2
d1=9
max(a,c)=4 > min(b1,d1)=2
【在 g**********y 的大作中提到】
: 按ihasleetcode那个写法更好解释吧
: bool isOverlap(int a, int b, int c, int d) {
: int b1 = a + (b-a+7)%7;
: int d1 = c + (d-c+7)%7;
: return max(a, c) < min(b1, d1);
: }
|
h**********8
发帖数: 267 | |
h*u
发帖数: 122 | |
s***c
发帖数: 50 | 68 关于"求两个演员链接"的题，楼主的答案似乎有问题。
我的思路也是用DFS，然后用一个map()来代表predecessor关系。
Set<> actor_set;
Set<> movie_set;
Map< actor, pair > map; //predecessor map
findActorLink(Actor a, Actor b)
{
int flag = 0;
if (a==b) return 1;
for each movie m in getMoviesOfActor(a)
{
if movie_set.contains(m) continue;
movie_set.add(m);
for each actor x in getActorsOfMovie(m)
{
if( actor_set.contains(x) ) continue;
actor_set.add(x);
map.add( x, ); // a & x are connected via movie "m"
flag = findActorLink(x, b);
if( flag ) break;
}
if( flag ) break;
}
return flag;
}
print_out(Actor x)
{
pair p = map.get(x);
print_out( p->actor );
cout << p->movie;
}
/////////////////
by the way, 我的onsite也要开始了。求本版祝福！！ |
s***c
发帖数: 50 | 69 关于"求两个演员链接"的题，楼主的答案似乎有问题。
我的思路也是用DFS，然后用一个map()来代表predecessor关系。
Set<> actor_set;
Set<> movie_set;
Map< actor, pair > map; //predecessor map
findActorLink(Actor a, Actor b)
{
int flag = 0;
if (a==b) return 1;
for each movie m in getMoviesOfActor(a)
{
if movie_set.contains(m) continue;
movie_set.add(m);
for each actor x in getActorsOfMovie(m)
{
if( actor_set.contains(x) ) continue;
actor_set.add(x);
map.add( x, ); // a & x are connected via movie "m"
flag = findActorLink(x, b);
if( flag ) break;
}
if( flag ) break;
}
return flag;
}
print_out(Actor x)
{
pair p = map.get(x);
print_out( p->actor );
cout << p->movie;
}
/////////////////
by the way, 我的onsite也要开始了。求本版祝福！！ |
s***c
发帖数: 50 | 70 关于"求两个演员链接"的题，楼主的答案似乎有问题。
我的思路也是用DFS，然后用一个map()来代表predecessor关系。
Set<> actor_set;
Set<> movie_set;
Map< actor, pair > map; //predecessor map
findActorLink(Actor a, Actor b)
{
int flag = 0;
if (a==b) return 1;
for each movie m in getMoviesOfActor(a)
{
if movie_set.contains(m) continue;
movie_set.add(m);
for each actor x in getActorsOfMovie(m)
{
if( actor_set.contains(x) ) continue;
actor_set.add(x);
map.add( x, ); // a & x are connected via movie "m"
flag = findActorLink(x, b);
if( flag ) break;
}
if( flag ) break;
}
return flag;
}
print_out(Actor x)
{
pair p = map.get(x);
print_out( p->actor );
cout << p->movie;
}
/////////////////
by the way, 我的onsite也要开始了。求本版祝福！！ |
|
|
s***c
发帖数: 50 | 71 关于"求两个演员链接"的题，楼主的答案似乎有问题。
我的思路也是用DFS，然后用一个map()来代表predecessor关系。
Set<> actor_set;
Set<> movie_set;
Map< actor, pair > map; //predecessor map
findActorLink(Actor a, Actor b)
{
int flag = 0;
if (a==b) return 1;
for each movie m in getMoviesOfActor(a)
{
if movie_set.contains(m) continue;
movie_set.add(m);
for each actor x in getActorsOfMovie(m)
{
if( actor_set.contains(x) ) continue;
actor_set.add(x);
map.add( x, ); // a & x are connected via movie "m"
flag = findActorLink(x, b);
if( flag ) break;
}
if( flag ) break;
}
return flag;
}
print_out(Actor x)
{
pair p = map.get(x);
print_out( p->actor );
cout << p->movie;
}
/////////////////
by the way, 我的onsite也要开始了。求本版祝福！！
的说吧。废话不说，直接上题：
的地方。有一道程序改错题，程序大概是替换一个字符串里面的pattern，不知道是谁
写的，不是很organized，估计是其他面试的同学的程序，我看了半天虽然觉的code写
得很别扭，但也没找出什么大错，面试官看我卡住了，就说我们继续吧。好在后来的题
都答得比较顺利。
session，项目中有没有多线程，怎么实现。
是cyclic，所以一开始我理解成{123456456}，后来email问了才明白题意）。
的地方。因为是常见题，很快完成，run了一下没什么问题就发过去了。
【在 x****1 的大作中提到】
: 当时大牛出这道题的时候也是很没有头绪，东一句，西一句，我在解题的过程中才慢慢
: 理解了他的意思。有时间的话，我画张图贴上来可能就好理解了。
: 你举的这个例子很好，不过当时好像没有涉及这种情况，大牛画的例图每两个演员之间
: 只有一个电影相连。
|
x****1
发帖数: 118 | 72 你这个方法挺好的，学习了。用map省了很多空间，我用arraylist存储子路径，递归过
程中占了太多内存空间，但是我也没有看出来我的方法错在哪了。
这种题验证起来太麻烦了，估计面试的时候也就是看看思路。
【在 s***c 的大作中提到】
: 关于"求两个演员链接"的题，楼主的答案似乎有问题。
: 我的思路也是用DFS，然后用一个map()来代表predecessor关系。
: Set<> actor_set;
: Set<> movie_set;
: Map< actor, pair > map; //predecessor map
: findActorLink(Actor a, Actor b)
: {
: int flag = 0;
: if (a==b) return 1;
: for each movie m in getMoviesOfActor(a)
|
w****r
发帖数: 245 | 73 offer搞定没？
【在 x****1 的大作中提到】
: 你这个方法挺好的，学习了。用map省了很多空间，我用arraylist存储子路径，递归过
: 程中占了太多内存空间，但是我也没有看出来我的方法错在哪了。
: 这种题验证起来太麻烦了，估计面试的时候也就是看看思路。
|
x****1
发帖数: 118 | 74 recruiter说这周出结果，不过看到那么多G买了MM就不招人的小道消息，就更不报希望了
【在 w****r 的大作中提到】
: offer搞定没？
|
w****r
发帖数: 245 | 75 如果要给offer会冻结你的offer，不会拒的，祝好运
望了
【在 x****1 的大作中提到】
: recruiter说这周出结果，不过看到那么多G买了MM就不招人的小道消息，就更不报希望了
|
S*****e
发帖数: 229 | 76 多谢分享
的说吧。废话不说，直接上题：
的地方。有一道程序改错题，程序大概是替换一个字符串里面的pattern，不知道是谁
写的，不是很organized，估计是其他面试的同学的程序，我看了半天虽然觉的code写
得很别扭，但也没找出什么大错，面试官看我卡住了，就说我们继续吧。好在后来的题
都答得比较顺利。
session，项目中有没有多线程，怎么实现。
是cyclic，所以一开始我理解成{123456456}，后来email问了才明白题意）。
的地方。因为是常见题，很快完成，run了一下没什么问题就发过去了。
【在 x****1 的大作中提到】
: recruiter说这周出结果，不过看到那么多G买了MM就不招人的小道消息，就更不报希望了
|
b*****c
发帖数: 1103 | |
j********x
发帖数: 2330 | |
c***8
发帖数: 188 | 79 thanks for sharing
Big bless
另外感觉机器人那题 内螺旋也可以的
的说吧。废话
多线程，都
串里面的
了半天虽然
好在后来的题都
端如何实现
coding题，让
rotated
【在 x****1 的大作中提到】
: recruiter说这周出结果，不过看到那么多G买了MM就不招人的小道消息，就更不报希望了
|
