|
j*****y
发帖数: 1071 | 2 比如 算 dp[4]， n = 100
先初始化 dp[4] = 100, 这个数字表示没办法 break s[0,...,4]
j = 0, 表示 break s[0,...,4]成 s[0] 和 s[1,...,4]
这时候如果 s[1,...,4]是一个单词的话，
那么 dp[4] = min(dp[4], dp[0] + 1)
j = 1, 表示 break s[0,...,4]成 s[0,...,1] 和 s[2,...,4]
这时候如果 s[2,...,4]是一个单词的话，那么 dp[4] = min(dp[4], dp[1] + 1)
j = 2,...
j = 3,... |
|
|
M********5
发帖数: 715 | 4 anything is possible
你也可能不会想到面Graph里面的shortest path的，所以做好准备确实是最关键的。。。
anyway, Big Bless for your Google interview! |
|
w****a
发帖数: 710 | 5 我也不知道。。反正他给我指出让我改了
代码洁癖吧 |
|
|
|
l*********8
发帖数: 4642 | 8 谢谢解释。我把题目理解为：把字符串分成尽量多的单词了。。。。 |
|
|
z*******8
发帖数: 30 | 10 新手弱弱的回你，dynamic programming，动态规划。。 |
|
b*w
发帖数: 14917 | 11 谢了。知道了这个，我也应该从新新手升级到新手了 |
|
|
|
|
|
c********t
发帖数: 5706 | 16 够简洁，不懂c++,但目测好像过不了test case "bafireman" |
|
w****a
发帖数: 710 | 17 DP思路对了就很简单了，代码好写啊。
递归考编码功底，我就出了BUG了。虽然后来改对了但是面试官肯定不开心了。
我现在吸取经验了，考功底的题，一定要实现把所有的测试用例都写好。代码写完了挨
个测试，都通过了再跟面试官说it's ok。这次就是吃的这个亏。 |
|
b********e
发帖数: 43 | 18 lz说了这个题有个前提是 All subwords can be found within a given dictionary，
否则的话就复杂了吧。 |
|
|
c********t
发帖数: 5706 | 20 哦，这样啊，其实也不复杂，加个判断if(i==0)....就可以了 |
|
j******2
发帖数: 362 | 21 这题跟cc150的17.14几乎一样吧？只不过17.14是求令非法字符最少的分法，这个是求
令合法单词数最多的分法，只要小小改动就行。递归DP。循环DP不行吧？ |
|
e***s
发帖数: 799 | 22 这题他是要随意一个分法，还是有要求（分出最少的词 或 分出最多的词）
下面是一个递归写法，DFS找到第一个分法
public static String segmentStringRecursive(String s, Set dict){
if(dict.contains(s)) return s;
int len = s.length();
for(int i = 1; i < len; i++)
{
String prefix = s.substring(0, i);
if(dict.contains(prefix))
{
String suffix = s.substring(i);
String segSuffix = segmentStringRecursive(suffix, dict);
if(segSuffix != nul... 阅读全帖 |
|
|
x******a
发帖数: 6336 | 24 is it the same as fibonacci?
#(fireman)= #(eman)+#(man) |
|
s***u
发帖数: 101 | 25 没有800题大牛那么有冲劲。。不过我leetcode做过好几遍，如果算重复的，应该也写
了好几百道了。。我觉得我算是运气很好的。F家的那个onsite只写了3题，一般来说都
是必挂的，我知道拿到offer的一般都是onsite 8题左右。。。 |
|
s***u
发帖数: 101 | 26 没有800题大牛那么有冲劲。。不过我leetcode做过好几遍，如果算重复的，应该也写
了好几百道了。。我觉得我算是运气很好的。F家的那个onsite只写了3题，一般来说都
是必挂的，我知道拿到offer的一般都是onsite 8题左右。。。 |
|
l******d
发帖数: 530 | 27 半年前一个公司联系我面试，我推说要做论文忙，最近又联系我，可最近又要赶几个老
板paper的deadline……我倒是很想去那公司，但没时间准备的话，必挂无疑。咋办？ |
|
l******d
发帖数: 530 | 28 那咋办，我这样裸面必挂无疑阿
像我这种不聪明又被老板按着干活的人真悲催阿，本来做题就比别人慢，还没那么多时间 |
|
w********g
发帖数: 106 | 29 还有，recruiter的话不可全信。说是完全不问简历上的内容，也不问general
questions，只问coding，结果coding之前就花了20分钟时间。 |
|
g********E
发帖数: 178 | 30 15分钟写出来很快了啊，deep copy关键是用个map记录copied nodes防止重复copy。当
然对这个题来说还有个高级解法不要extra space,扫两遍list就行了。
-----
另外我45分钟就做了一道题，也过了，还是个老印面试官，所以你也很有希望的，
bless! |
|
w********g
发帖数: 106 | 31 我用HashTable做的。其实本质上就是deep copy一个图。当然因为是list也能按list线
性做，麻烦点，但还是O(n)。
他对用hashTable很不满意，于是追问为什么真运行起来会比O(n)慢很多，我不知道，
他说你一行一行看，我说因为HashTable真运行起来会冲突，hash一次就不是O(1)了，
他同意。
请问你说的那个不要extra space的高级解法怎么做？ |
|
h********e
发帖数: 1972 | 32 不出意料的话，这题的另一个解法是图的深度优先搜索。复杂度边线性。不需要额外空
间和hashtable |
|
g*******s
发帖数: 2963 | 33 第一遍follow next指针copy所有node
第二遍copy extra指针，这时所有node都已经存在了，也不用create新node了，所以不
用hash判断了。 |
|
g*******e
发帖数: 91 | 34 别灰心。非大牛问一道题也过，比如我去年。不过onsite还是被拒。如果真没过，想想
你至少省下来了一天假期。再说你不是给了面经，攒的人品可能够你过了。 |
|
w********g
发帖数: 106 | 35 原图
a----b----c----d
|___________^
新图
A----B----C----D
|___________^
第二遍copy extra指针时，怎么确定 a->b 和 A->B 的对应关系呢？ |
|
g********E
发帖数: 178 | 36 你这样还是得用map来记录原node和目标node的对应关系。
图的DFS也是需要map记录visited nodes的
如果只是这样一个list with arbitrary pointer,第一遍在每个node后面复制一个：
a->b->c => a->a'->b->b'->c->c'
第二遍添加arbitrary pointer, 比如a'->child = a->child->next
最后把origin nodes都去掉就行了，因为是linked list,总时间还是线性的。 |
|
|
g****y
发帖数: 2810 | 38 海涛程序员面试题100问原题
此题过于技巧化，没什么大意思。但是只要在国内找过工作的都知道，烙印基本都不会
但凡问你这道题8,9成都是想放水的国人
你自己赚了却不知道…… |
|
|
n*******p
发帖数: 72 | 40 到时没被问到三驾马车。问到三驾马车到也还好，现成的东西可以套。这个system
desgin其实主要是考察思维逻辑性，思考问题的方式，交流讨论的方式和domain
knowledge的深度。目前遇到的设计题有以下：
Twitter ： 设计data visualization的系统，从数据如何存储，到如何获取数据，到
前台的显示。设计一个分布式cache的lock。
Turn： 设计一个scheduler。设计一个search engine。设计一个online ads display
system。
Box： 设计一个类似于amazon catalog的system。
Uber： 设计一个web app,可以用来在某个范围内查询各种打车的数据。
基本上一出来这种题必挂。 大牛指点。真是救命啊！！！ |
|
|
|
|
L****Y
发帖数: 355 | 44 好几个公司了：一个公司在店面的时候，那个三哥不停的说vely good，sounds great
，而从来不给实质性的反馈。 然后店面结束后说its good talking to you。 结果第
二天收到HR的拒信。
还有一个公司，那个三哥是个大头。前面所有的店面和onsite technical面试都进
行的不错，HR给的反馈是“its quite positive”。 和team的hiring manager见面也
聊的非
常愉快，然后最后一面是见他，见面后第二天收到HR的邮件说“not match。HR自己也
说， “I'm sorry to share that we will not be moving forward with the
interview process at this time -- I know, I was surprised too. ”
还有其他的公司，不一一列举了。 |
|
|
x****o
发帖数: 29677 | 46
great
很正常，烙印从来不吝啬招自己人，如果候选者有三哥，老中基本上都会被挤掉
而且烙印从来不在乎一个组全招烙印，所以你经常可以看到乌洋洋一片烙印的，反过来
老中一个组招了几个，马上就不会再招老中，生怕别人说三道四 |
|
s***y
发帖数: 10 | 47 我这次面试最后一个是个三姐，然后题做得磕磕绊绊，她也一直在那good，it's good
talking to you. 然后最后居然过了。。。 |
|
|
j*****8
发帖数: 3635 | 49
~~~~~~~~~~~~最后这段不敢苟同，这不完全是误人子弟吗。。简历吹的厉害，面试那是
必挂无疑的 |
|
z*****4
发帖数: 63 | 50 是啊不过我是裸奔来湾区找工作的，学渣一枚，就懂点数电，毕业到现在找了三个月了
，面过俩台商，都挂了。。。
今年真是杯具啊 |
|
