t****a
发帖数: 1212 | 1 可以用DP来做。计算复杂度大约为n^3*len(dict)
假设输入字符串s长度为n，f为求解的函数，那么
f(s, dict) = match_dict(s, dict) 当s可以直接匹配上dict里的某字符串（通过排序
后比较）, match_dict返回dict中匹配上的字符串
f(s, dict) = (max the words length) [f(subs(s, 0, i), dict), f(subs(s, i, n)
, dict)], i=1..n-1 当s不能直接找到dict里的匹配
f(s, dict) = nil 当s为空
clojure程序如下
(defn gen-sorted-dict [dict]
(reduce merge (for [w dict]
{(sort w) w})))
(defn match-dict [s sorted-dict]
(sorted-dict (sort s)))
(def prob10-sub
(memoize
(fn [s sorted-dict]
(wh... 阅读全帖 |
|
s********u
发帖数: 1109 | 2 我现在对这类题目是这么思考的：
1.问题的起点（字符串首）和终点（字符串尾）都是“收敛”的，因此可以考虑用dp。
2.用dp的话，就是从起点开始（终点其实也行，因为空字符串的解都是true，都已知）
，根据1~n-1个节点的情况，推断n的情况。因为需要记录path，又不是backtracking，
所以用prev数组（每个节点的前驱节点）来记录。
3.可能有多条path，所以prev是一个vector >。记录完毕之后需要从终点
出发，回溯遍历这些路径，直到prev取出来的index是-1。 |
|
s********u
发帖数: 1109 | 3 今天在做波兰表达式的时候想到用一下stringstream。
试了一下，发现>>与<<的行为非常诡异，代码和输出如下：
string str = "abc xyz";
stringstream stream(str);
cout << stream.str() <
stream >> str;
cout << str <
stream << str;
cout << stream.str() <
stream >> str;
cout << str <
就是将一个字符串吐出来，再塞回去，这时候stream里的字符串是一样的。
但是再吐出来，就不是这个abc字符串了，而是他后面那个，也就是说abc是塞到流的最
后了。但是stream.str()却一致。太诡异了。 |
|
s********u
发帖数: 1109 | 4 各种不顺，早上apple来了拒信，下午google面的也不好，阿森纳还输球。。
可能还是沟通能力太差了，应该是很简单的题目，就是不知道他想说什么。
我发觉面试相比leetcode一大难度就是有时候面试官会说的比较vague，要靠自己问。
。要是他每次都直接把题目书写出来，倒是方便多了。。
就是实现一个strchr，只不过第二个参数不是字符，而是字符串，返回第一次出现的指
针。
/*
Find the first occurrence in str of _any_ character in set. Both are NULL
terminated ASCII C-strings. This is like strchr, except that the second
parameter functions as a set, rather than a single character.
str set returns
qxcdef csz str + 2 == &str[2]
axcdef wya str + 0 == &str[0]
axcdef cxa... 阅读全帖 |
|
s********u
发帖数: 1109 | 5 各种不顺，早上apple来了拒信，下午google面的也不好，阿森纳还输球。。
可能还是沟通能力太差了，应该是很简单的题目，就是不知道他想说什么。
我发觉面试相比leetcode一大难度就是有时候面试官会说的比较vague，要靠自己问。
。要是他每次都直接把题目书写出来，倒是方便多了。。
就是实现一个strchr，只不过第二个参数不是字符，而是字符串，返回第一次出现的指
针。
/*
Find the first occurrence in str of _any_ character in set. Both are NULL
terminated ASCII C-strings. This is like strchr, except that the second
parameter functions as a set, rather than a single character.
str set returns
qxcdef csz str + 2 == &str[2]
axcdef wya str + 0 == &str[0]
axcdef cxa... 阅读全帖 |
|
b******p
发帖数: 49 | 6 1. 将一个数字的二进制形式以字符串的形式返回
2. 找两个已经排好序了的数组中的中位数（LeetCode原题）
3. 找一个字符串中最长的只含有N种不同的字符的子字符串
4. 设计题：设计一个随机数产生器，有一个以列表形式保存的已经排序blacklist，输
出的数字如果出现在其中就要剔除。（是CareerCup原题）
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
目的是找实习。但是因为平时给老板干活不需要练习面试中考察的技能，所以本来的心
态也就是想试试看自己实习如何，没觉得有一定能通过的把握。面试前一个半月内才做
了90多道LeetCode。和板上刷了很多遍的大神们相比差太远了。
本来想通过找实习来给自己有个合适的定位，如果运气好，就找点自信。
现在看来自信得从别的地方找了。看起来得再多投几家，至少把LeetCode刷完。
请问这样的心态是否正确，谢谢各位 |
|
s******r
发帖数: 21 | 7
想向大家请教一下，第三道题目的意思是什么，什么解法比较好。
对于题意，我的理解是，给一个参数N，找出字符串里面只包含N个不同字符的个数。譬
如N=1，那么在字符串"AAAAAA"里面，包含一个不同字符的最长串是6。不知道我理解的
是不是正确？
如果理解正确的话，有什么比较好的解法？我现在能够想到的是O(N^2)。就是用张二维
表，记录所有区间(i,j)之间不同字符串的个数，(i,j+1)的值可以从（i+1，j), (i, j
) 和(i+1, j+1)推导出来。不知道有没有更简便的做法？ |
|
p**********e
发帖数: 70 | 8 一开始觉得面得很好，结果拒信飘过， 继续努力中。。。。。。
无论结果如何， 发面经先。
小弟CS PHD， 打算找明年的fulltime，move on吧，anyway，跪求推荐 microsoft,。
。。。
一共五轮
round 1：
问简历， 问什么时候毕业，出乎意料的是，他们用的竟然是去年的简历，上
面写expected 今年十二月份毕业，我说这份简历啊好像没有update， 我打算明年7月
毕业了。。。。。
然后他就说做题吧。。。
求两个字符串的公共子串，然后去掉duplicate 部分。
test cases:
round 2: 不知道大小输入一个字符串流， 然后计算最近100个数的平均数，test
cases
round 3： 扑克题， 转化成字符串就可以了， 就是有一次重复得1分。像四个一样的
，就4得分。
round 4： format string 把一个非常非常长的字符串输出line by line， 每行有大
小，每个单词不可以拆开， 结尾不应该有空格， 所以空格要插入到单词之间，尽可能
要求每... 阅读全帖 |
|
x*******6
发帖数: 262 | 9 先sort这个list nlogn,建一个matrix记录字符串是否有相同字符，找出所有有相同字
符的字符串mn记录在matrix里面,再从matrix的一角开始安顺序找到没有被mark的位置
得到那两个字符串worst case n^2,但是average应该还不错 |
|
x*******6
发帖数: 262 | 10 先sort这个list nlogn,建一个matrix记录字符串是否有相同字符，找出所有有相同字
符的字符串mn记录在matrix里面,再从matrix的一角开始安顺序找到没有被mark的位置
得到那两个字符串worst case n^2,但是average应该还不错 |
|
w*****t
发帖数: 485 | 11 这个case确实不work了
另外想到了一个解法:
第一个字符：一个数字表示(1-9)，表示字符串长度有多少位
接下来的1-9个字符，就是字符串的长度
最后是字符串
如 "abcde" --> "15abcde"
"12abc" --> "1512abc"
"123456789abc" --> "212123456789abc" |
|
s******d
发帖数: 424 | 12 华人面试官，nice，赞一个
两道题目
1 整数的binary tree，给定一个整数target，找到第一个从root到leaf的path使得和
为target.竟然还出bug，汗
2 给两个字符串，判断第一个字符串能否用第二个字符串中的字符构成。先给一个int
ncount[256]的方案，提示可以节省空间，换成unordered_map，
pass，等二面
请问二面是不是都会问设计题了？ |
|
s******d
发帖数: 424 | 13 给两个字符串，判断第一个字符串能否用第二个字符串中的字符构成。先给一个int
ncount[256]的方案，提示可以节省空间，换成unordered_map，
这个inplace的办法， 时间复杂度O(MlogM + NlogN)
sort(s1.begin(),s1.end());
sort(s2.begin(),s2.end());
return s2.find(s1) != string::npos; |
|
M********6
发帖数: 67 | 14 1. 极速测试： 2分钟内完成尽可能多的数学、英语类反、智力测验和逻辑题。共10道
，我只完成了六七道就被自动掐掉了。
2. 数学、智力、类反、逻辑、脑筋急转弯等（<=20道）：不限时但强调完成时间和准
确率共同作为评分标准。例如
a.给出一串数3 24 -168 1008 -5040求下一个数是什么
b.一个牛逼的人种了一颗神奇的树，每天高度翻一倍，第十天树高八十尺，问第多少天
树高十尺？
c. 两个木讷的程序员，分别从1号办公室和76号办公室匀速相向而行，1号办公室出发
的程序员每分钟行走5个办公室，76号办公室出发的程序员每分钟行走10个办公室，问
他们在几号办公室相遇。
d. 两个硬币总价值55美分，一个不是nickle，问这两个硬币分别是多少？（选择题，
可以选择不可能选项）
e. 数字填空 4，7，13， ？，49，97
f. 一只搞笑的山羊爬悬崖，崖高80.5英尺，该山羊每分钟上升3英尺后下降2英尺，问
羊多久可爬上悬崖顶端。
g. 公司有一个支票账号内有五万元，另有现金伍佰元。用现金买了一百五十张永久邮
票，每张44美分，又买了两台高配电脑，每台2025元，电脑开销的十... 阅读全帖 |
|
M********6
发帖数: 67 | 15 1. 极速测试： 2分钟内完成尽可能多的数学、英语类反、智力测验和逻辑题。共10道
，我只完成了六七道就被自动掐掉了。
2. 数学、智力、类反、逻辑、脑筋急转弯等（<=20道）：不限时但强调完成时间和准
确率共同作为评分标准。例如
a.给出一串数3 24 -168 1008 -5040求下一个数是什么
b.一个牛逼的人种了一颗神奇的树，每天高度翻一倍，第十天树高八十尺，问第多少天
树高十尺？
c. 两个木讷的程序员，分别从1号办公室和76号办公室匀速相向而行，1号办公室出发
的程序员每分钟行走5个办公室，76号办公室出发的程序员每分钟行走10个办公室，问
他们在几号办公室相遇。
d. 两个硬币总价值55美分，一个不是nickle，问这两个硬币分别是多少？（选择题，
可以选择不可能选项）
e. 数字填空 4，7，13， ？，49，97
f. 一只搞笑的山羊爬悬崖，崖高80.5英尺，该山羊每分钟上升3英尺后下降2英尺，问
羊多久可爬上悬崖顶端。
g. 公司有一个支票账号内有五万元，另有现金伍佰元。用现金买了一百五十张永久邮
票，每张44美分，又买了两台高配电脑，每台2025元，电脑开销的十... 阅读全帖 |
|
w*******i
发帖数: 186 | 16 是的，先找第一个字符重复出现的地方，找到后假设这个字符与第一个字符间就是重复
的短字符串。然后继续扫描逐字匹配，不对就更新假设的重复的短字符串。
最后验证这个重复的短字符串长度是否够大。
pattern |
|
w*******i
发帖数: 186 | 17 是的，先找第一个字符重复出现的地方，找到后假设这个字符与第一个字符间就是重复
的短字符串。然后继续扫描逐字匹配，不对就更新假设的重复的短字符串。
最后验证这个重复的短字符串长度是否够大。
pattern |
|
u*****n
发帖数: 126 | 18 这家也遇到两个三哥，挂了。不过还好，没遇到三哥的公司给了offer。
Phone：
求两个List的交集，假设每个list中的interval都是disjoint的。
onsite:
1）给你一个list的字符串，找出一个list的prefix，从而可以uniquely identify每个
字符串。
Hint：此题可以用trie来解决
2）给你一棵树，implement一个iterator，可以是BFS或者DFS。要求用iterative
method来实现。
Hint：选择DFS
3）压缩算法。用树的变形来表示一个string，比如 B->left = A, B->right = A, 此
种情况我们可以把B的left, right同时指向A。
问题1）对于一个有n个节点的树，可以表示的最长string的长度
问题2）implement get(Tree t, int position)，返回这个字符串在position的字符。
Hint：exponential + binary search
4)猜字游戏，有一个board和dictionary，从一个字符出发... 阅读全帖 |
|
g*********e
发帖数: 14401 | 19 今天HR打电话来说HC没过，记下来参考
电面1：
第一个问题记不得了
第二个，给一系列string，要求找两个string,使得它们没有共同字符，并且长度乘积
最大。好像给了个暴力解
电面2：
给两个string array A,B，要求返回三个array，第一个只包含只出现在A中的字符串，
第二个只包含只出现在B中的字符串，第三个只包含common字符串
然后海量数据下该怎么code。貌似这个电面反馈很好
onsite:
1. 先寒暄介绍，稍稍问现在工作。题目是run length encoding的变种，decoder的规
则是： a3x1bc -> a111bc (用x来表示重复）
该怎么设计encoder。写代码。开头想了很久，才写了代码，写得比较罗嗦。再跑了几
个测试。这轮发挥不好，HR开头也迟到了一会儿，导致时间稍稍不够，没时间再做一题
了，问了几个问题结束。
2. 稍稍介绍下google的工作。题目是常见题二维平面上过最多点的直线。问清后写了
个n^2logn的解法，然后在提示下讲了n^2的方法。扩展问海量数据下的做法，这里纠结
了，给了个比较复杂的方法。时间到。这轮应该... 阅读全帖 |
|
t*********7
发帖数: 255 | 20 攒RP先,刚出炉的面经.面试官烙印,已经在里面工作5+年了.
寒暄5分钟
Q1.一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
Q2.降低时间开销,怎么搞?
头两个问题,写完烙印面试官直接粘贴代码本地跑,说没问题
Q3.一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
Q3不用写代码,谈思路,然后把他的例子按思路走一边,走完他问时间开销.
问问题.
再见 |
|
z**i
发帖数: 86 | 21 来自主题: JobHunting版 - FB 面筋 序列化这个问题比较有意思，我的想法
1）计算长度可能不够好，字符串可能很长，溢出可能。
2）增加offset格式位，增加存储负担。
3）可能最简单就是每行写一个字符串，最多多出"rn"2个char，且容易读取。
4）最优肯定是编码映射或者压缩方案，但要求两个字符串有特定性质。在无限制字符
串环境下，不是很合适。 |
|
d*****0
发帖数: 72 | 22 May 23面的
一共三轮
就第一轮简单问了一下resume的intern
其他的每轮就只有一个算法题
1. 给定rand1()：能够产生random数字0,1
用rand1()实现:
rand3()--> 0, 1, 2, 3
rand4()--> 0, 1, 2, 3, 4
randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
，注意edge case
2. given 一个字符串，这个字符串是一个算式，包含加减乘除，没有括号，符号和数
字之间以一个空格格开，比如：“1 + 2 * 4 / 5”，return算式的结果
3. given两个字符串，分别表示两个元素等和不等，比如：
arr1 = {“A=B”, "B=C", ...}
arr2 = {"A!=C", "F!=R", ...}
判断是否有矛盾，这个例子就有矛盾：A!=C
given提取元素的method: getID(..)，这个不用自己写：String[] sarr = getID(arr1
[0]) --> sarr {A, B... 阅读全帖 |
|
d*****0
发帖数: 72 | 23 May 23面的
一共三轮
就第一轮简单问了一下resume的intern
其他的每轮就只有一个算法题
1. 给定rand1()：能够产生random数字0,1
用rand1()实现:
rand3()--> 0, 1, 2, 3
rand4()--> 0, 1, 2, 3, 4
randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数
，注意edge case
2. given 一个字符串，这个字符串是一个算式，包含加减乘除，没有括号，符号和数
字之间以一个空格格开，比如：“1 + 2 * 4 / 5”，return算式的结果
3. given两个字符串，分别表示两个元素等和不等，比如：
arr1 = {“A=B”, "B=C", ...}
arr2 = {"A!=C", "F!=R", ...}
判断是否有矛盾，这个例子就有矛盾：A!=C
given提取元素的method: getID(..)，这个不用自己写：String[] sarr = getID(arr1
[0]) --> sarr {A, B... 阅读全帖 |
|
G***n
发帖数: 877 | 24 刚收到据信，题目真心很容易，怪我状态不好，感冒头痛，反应迟钝。onsite第一题超
简单，结果搞砸了，然后就。。。唉，写个记录供后人用吧。总的感觉，这次面的A家
的题目不像以前我听过的那样，150题好像也没什么用，很多都是design和behavior
question.
先说店面
很奇怪，板上基本都是2次或以上，我只有一次店面，而且只写了一个coding。
对方有事迟到了10来分钟，我以为不面了，正玩这手机，电话来了。先问了research，
花了很久，大概20多分钟，然后就是基本概念，hash,linklist, sort, 比如hash能不
能2个值map到一个空间，怎么解决。
给一个很大的数组，怎么查找需要的几个数字。只是描述，没让coding。
最后剩下30分钟，coding，找2个linklist的common note.好像150题没有，但很简单，
5分钟写完，发现1个bug，纠正后对方说look good.对方中国人，整个过程很nice。3天
后就收到onsite。
onsite
不算HR,一共见了4组，6个人，其中2组是2个人一组。
1.中国人manager和一个老美... 阅读全帖 |
|
U**m
发帖数: 313 | 25 1， 问了Evaluate Reverse Polish Notation的题目，但是并不是仅仅做一个函数算出
答案，而是说你要怎么样设计各个class，以及互相之间怎么联系。
2， 假设有两个Queue，不停的在进出数据。每个有一个getdata()的函数，返回一个数
据包括了时间以及一个字符串。如果从Queue1的数据的时间和Queue2的数据的时间相差
1秒的话，把两个字符串输出。
3， 如果我有一个网站，卖东西的，跟Amazon差不多这种，然后用户再抱怨我的网站非
常慢，然后聘了你当技术总工，你要怎么样改进？
4， 给一个日期，用字符串表示，比如20140608，求这个日期所在的星期的最后一天。
先说了说算法，然后再到机器上实际把这个已经有的程序debug出来。
求教应该什么方向去学习。尤其对于第3题，应该怎么解答。 |
|
g***j
发帖数: 1275 | 26 来自主题: JobHunting版 - 问一道题目 给定一个字符串，找出所有的可能的字符串，大小不限。
比如给定
aBc
输出
abc
abC
aBc
aBC
就是同样的字母顺序，如果都转换成小写后字符串是一样的。如何高效的输出？
谢谢了 |
|
j********2
发帖数: 82 | 27 1. Print all paths of a binary tree
How to do it iteratively? 用一个stack实现preorder来做？
2. Given an array of integers, find any 3 numbers in array such that they
sum to zero. eg:
[1, 2, -3, 4, 0]
1) 1 , 2, -3
2) 0, 0, 0
这个是不是三重循环？还有更快的吗？
3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了
4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
有什么好思路？
5.多层链表压扁及还原
我用stack写了一下，面试写起来太麻烦。哪位大牛给个简洁的recursion版本？
谢谢！ |
|
l*****a
发帖数: 14598 | 28 1. Print all paths of a binary tree
How to do it iteratively? 用一个stack实现preorder来做？
==>postOrder可做
2. Given an array of integers, find any 3 numbers in array such that they
sum to zero. eg:
[1, 2, -3, 4, 0]
1) 1 , 2, -3
2) 0, 0, 0
这个是不是三重循环？还有更快的吗？
==>sort O(nlogn), then n^2
3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了
==> u should know 2 sum
4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
有什么好思路？
==>懒得想... 阅读全帖 |
|
a***n
发帖数: 623 | 29
1. Print all paths of a binary tree
How to do it iteratively? 用一个stack实现preorder来做？
DFS，每到一个叶子节点打印stack。（不过这里的path是指root到leaf？有见过题目定
义是leaf到leaf）
2. Given an array of integers, find any 3 numbers in array such that they
sum to zero. eg:
[1, 2, -3, 4, 0]
1) 1 , 2, -3
2) 0, 0, 0
这个是不是三重循环？还有更快的吗？
这个已经有数学证明了，X-sum问题最少时间开销是O(N^(X-1))
3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了
同上，应该是O(n)吧，用一个hashmap的话（重复元素可以加个counter）
4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字... 阅读全帖 |
|
j********2
发帖数: 82 | 30 Thanks! Inline ...
1. Print all paths of a binary tree
How to do it iteratively? 用一个stack实现preorder来做？
DFS，每到一个叶子节点打印stack。（不过这里的path是指root到leaf？有见过题目定
义是leaf到leaf）
==> 那就是还是用一个stack来实现preorder了？
2. Given an array of integers, find any 3 numbers in array such that they
sum to zero. eg:
[1, 2, -3, 4, 0]
1) 1 , 2, -3
2) 0, 0, 0
这个是不是三重循环？还有更快的吗？
这个已经有数学证明了，X-sum问题最少时间开销是O(N^(X-1))
===》这个怎么用n^2解？注意这里一个数可以被选多次
3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了... 阅读全帖 |
|
t********n
发帖数: 611 | 31 4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
My answer in Ruby:
def limited_sub(s, arr)
result = Set.new
(0..s.length - 1).each do |i|
(i..s.length - 1).each do |j|
sub = s[i..j]
if sub.split("").to_set.length < arr.length
result.add(sub)
end
end
end
result
end
p limited_sub("abbc", ['a', 'b', 'c'])
I tested and got correct answer. |
|
t********n
发帖数: 611 | 32 4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
有什么好思路？
单机没有好思路，貌似就一边生成一边过滤。不过建议和面试官讨论多机环境下map
reduce->对字符数组中的每个元素（应该可以assume无重复），map到子问题：从字符
串生成所有不包含此元素的子串->再reduce。我觉得我要是面试官会想听到这个思路。
I can't figure out how to implement this to make it faster than O(n ^2)... |
|
s**v
发帖数: 35 | 33 今天面完了，我晕阿，test engineer面的和developer一样阿
1. 谈谈你的某个project, 然后会问你觉得还可以有什么improvement
2. 做题，很简单，输入两个字符串，从第二个字符串中移走第一个字符串中的所有字符
3. 直接问返回一个整数数组中前k个最小值，如果都是大数字怎么办，如果是stream怎
么办，而且这个面试官特别喜欢问你觉得还可以怎么improvement
最后到了提问环节，我忍不住问了我就面个test engineer为啥要一个developer来面试
。。结果他说希望test engineer也懂code, 不要弄坏他们写的东西。。。
总体来说不难，但是能让他impressive也不容易的感觉 |
|
x****B
发帖数: 103 | 34 我前些天被老印这么坑过一次。
他说让我写个encoding的算法。
给了我俩个例子。
abc 输出 abc
abbccc 输出 a2*b3*c
写完了，烙印说我算法有bug.我看了半天没看出来。
过了两三分钟。说encode
a2*b3*c我的算法encoding以后也是a2*b3*c。decoding端没有办法decode。
然后这就出问题了。a2*b3*c按照这个例子就需要encode成这个字符串本身。然后他说
你应该自己考虑encode各种字符串让每一个不同的字符串encode结束了有区别。
按照这种模式，要求修改了两三次以后，白板上写的乱七八糟没法看了时间到。
可以参考这种思路。 |
|
M*******a
发帖数: 1633 | 35 怎么做
就是给一个regular express和一个字符串，找regular expression产生的语言当中离
给定字符串Levenstein distance最近的字符串。 |
|
s*w
发帖数: 729 | 36 你说的是 sort 一个字符串本身； 他问的是 sort 很多个。
不过解法还是类似，4^10 = 2^20 才 1MB 直接转字符串为数字， linear scan 数每
个数的频率；输出的时候再转数字为字符串 |
|
i*********e
发帖数: 21 | 37 去年的onsite，挂在这题上了。其实不难，之前也有人发过，但好像没详细讨论过。
一组字符串，求所有彼此之间无公共字符的两两组合中，两字符串长度乘积的最大值。
上来就是暴力解O(n^2).问有没有更快的。我问:better than O(n^2)? 对方没正面回答
。结果我以为他是默认了。于是挖空心思的找O(nlogn)的解法，建字符索引，后缀树都
想过。最后没办法，问他有没有hint。结果他提了剪枝。当时我就崩溃了，剪枝早想到
了，但剪枝的话worst case还是O(n^2)啊！我立刻说了按长度排序再剪枝的方法。但是
时间已经不够写代码了。
想问问这题究竟有没有优于O(n^2)的解法。当然，假定比较两字符串的时间设为常数。
我的感觉是没有的。当然，我可能是错的。
教训就是面试是交流的过程，想到什么improvement就说出来讨论讨论，就算他不认可
，至少也知道你想到了一个方法。最忌讳闷头苦想，而面试官根本不知道你在想啥。
==========
去年还面了FB的onsite，挂在把二叉树转为双向链表上，吐血。当时昏了头拼了命要写
个functional style的，结果把自己绕进... 阅读全帖 |
|
H*********h
发帖数: 13 | 38 G家电面什么要求？也是bug free吗？最后发现有一题写的代码各种bug，但是思路是OK
的，能过吗？
两道算法题：
1. leetcode missing range
2. css的两种表示方式，根据输入的一种css字符串找到最接近的另一种css字符串，计
算两种字符串之间的相似度有提供一个公式。
java写的，面完发现char做了+, -操作后没有强制(char)，比较的时候没有计算成Math
.abs....
求bless。。。 |
|
l*******0
发帖数: 95 | 39 来自主题: JobHunting版 - G家店面题 这个题就是你要想办法尽量均匀的把1000 billion 字符串“尽量均匀地“分片，每台
机器上面有 1000 billion / N 个字符串。
如果1000 billion / N 可以完全装在10M内存里，那就用HashMap保存结果。
如果10 M 内存太小装不下，那么真正的计数结果应该也只能存在磁盘上，可以用来建
一个索引，用来指向string在磁盘文件以及在文件中的偏移。你也可以根据字符串内容
将结果存在多个文件里。 |
|
A*******e
发帖数: 2419 | 40 如果row key既有字符串，又有数字，然后字符串按字符串排序，数字按数字排序，能
做到吗？
比如按字典排序会是这样：
abc:1
abc:10
abc:2
...
abc:9
但我希望做到这样：
abc:1
abc:2
...
abc:9
abc:10 |
|
m***i
发帖数: 37 | 41 1.老美
一个屏幕给出长和宽，给出字符串s,求s在这个屏幕中能打印出来的最大的字体大小。
陷阱是每个字体所占宽度可能不一样。
2.老美
正方形recursively分成四块，生成四分树。设计数据结构表示之。
树节点有两种颜色，给出树节点相交的产生新节点颜色的逻辑，求两棵四分树相交所产
生的新的四分树。
3.烙印
这个人好像挺nice。
给出一个字符串数组表示一个航班行程单。每个字符串表示"起点-终点"。但是这个行
程单是打乱的。求恢复这个行程单。
4.ABC？
给出一个byte数组，屏幕宽度in bits, 屏幕高度in bits,
求将byte数组所表示的像素从左到右对折后产生的新的图案，用byte数组表示。
5.老美
求二叉树的具有最大数值和的字树。
给出一列的数，一列对应的权值（权值和等于一）。求按权值所代表概率返回列中的一
个数。
1.面得不好。3面得不错。ABC估计不会废我,2和5一般。
攒人品，兼求bless :-) |
|
x*******9
发帖数: 138 | 42 我试试给LZ翻译一下。。。（哭
>> 1.老美
一个屏幕给出长和宽，给出字符串s,求s在这个屏幕中能打印出来的最大的字体大小。
陷阱是每个字体所占宽度可能不一样。
不太明白。猜测是个简单的除法。但是不会这么简单的。
>> 2.老美
正方形recursively分成四块，生成四分树。设计数据结构表示之。
树节点有两种颜色，给出树节点相交的产生新节点颜色的逻辑，求两棵四分树相交所产
生的新的四分树。
类似线段树懒标记的东西，不太好写，不过难度一般。
>> 3.烙印
这个人好像挺nice。
给出一个字符串数组表示一个航班行程单。每个字符串表示"起点-终点"。但是这个行
程单是打乱的。求恢复这个行程单。
拓扑排序？？
>> 4.ABC？
给出一个byte数组，屏幕宽度in bits, 屏幕高度in bits,
求将byte数组所表示的像素从左到右对折后产生的新的图案，用byte数组表示。
不懂。。。。。。。
5.老美
求二叉树的具有最大数值和的字树。
给出一列的数，一列对应的权值（权值和等于一）。求按权值所代表概率返回列中的一
个数。
Leetcode原题？
求看懂的大大给指点一下。。。谢谢 |
|
M*******n
发帖数: 10087 | 43 【 以下文字转载自 Dreamer 讨论区 】
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: 不刷题进Google的经历
发信站: BBS 未名空间站 (Thu Jun 11 18:34:25 2015, 美东)
没有马甲，又不想被认出，所以跑到这里发帖，希望有人能转到Jobhunting板上。
在Jobhunting板上混了很久了，看到大家的共识就是：不管你工作多久，想去FLG必须
刷题。（例外也有人提到，但是似乎不是Google research的职位，就是功成名就的大
牛，都不是普通码工的情况）我自己和周围认识人的经历似乎也验证了这一点。不过最
近我终于在没有刷任何题的情况下拿到了G家的offer，看起来这种“共识”也并不是
100%正确的。由于Jobhunting板上这种经历似乎不多，所以详细写一下，供大家分享，
也给像我一样不愿刷题的人鼓励一下。这个帖子主要侧重分享面试经历，面经记不太清
了，不是太多，放在最后。
我自己四年前也曾经认真刷过0.9遍Leetcode题目，去过G家on site一次。当时自我感
觉答得还不错，但是最终还是被... 阅读全帖 |
|
A*******e
发帖数: 2419 | 44 * Multi task design
用户可以法请求要求某一个task在某一时间开始执行。这样的请求可能很多。设计一个
系统处理这样的请求。问如果处理系统是local的（和发请求的在一起）或者是remote
的有哪些设计上的不同。
这个没怎么实际做过，只能随便侃侃，简单写了几行伪代码。
汗，没看懂要设计啥。什么叫处理这样的请求？同一时间请求太多，资源不够咋办？
* Quad-tree intersection
一个quad－tree表示一个2D的黑白图，每个节点都是平行于坐标轴的矩形，节点的
value 0和1表示黑和白。如果一个节点全黑或全白就是叶子，否则就继续剖分成四份。
要求写一个函数求两个quad－tree的交。
这个比较简单，写了一个递归的程序，不确定是否有bug。
什么是两个树的交？
* Base64 encoding
先解释了一下何谓Base64 encoding（http://en.wikipedia.org/wiki/Base64），然后要求写一个函数将一个字符串按Base64编码。
用位操作实现，写了简单的代码，不确定是否是他想要的答案。
* Swizzle so... 阅读全帖 |
|
f********t
发帖数: 6999 | 45 【 以下文字转载自 Dreamer 讨论区 】
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: 不刷题进Google的经历
发信站: BBS 未名空间站 (Thu Jun 11 18:34:25 2015, 美东)
没有马甲，又不想被认出，所以跑到这里发帖，希望有人能转到Jobhunting板上。
在Jobhunting板上混了很久了，看到大家的共识就是：不管你工作多久，想去FLG必须
刷题。（例外也有人提到，但是似乎不是Google research的职位，就是功成名就的大
牛，都不是普通码工的情况）我自己和周围认识人的经历似乎也验证了这一点。不过最
近我终于在没有刷任何题的情况下拿到了G家的offer，看起来这种“共识”也并不是
100%正确的。由于Jobhunting板上这种经历似乎不多，所以详细写一下，供大家分享，
也给像我一样不愿刷题的人鼓励一下。这个帖子主要侧重分享面试经历，面经记不太清
了，不是太多，放在最后。
我自己四年前也曾经认真刷过0.9遍Leetcode题目，去过G家on site一次。当时自我感
觉答得还不错，但是最终还是被... 阅读全帖 |
|
x*****n
发帖数: 195 | 46 谢谢分享面经。先预祝大牛早日拿到更好的offer。
想咨询下Z家的两个题，看着没思路。。。多多指教，谢谢！
Z：电面：实现带返回当前最小值的STACK，不能用STACK来实现。 ——这个就是用
arraylist模拟stack吧？
ONSITE: 1. 把一个字符串，通过插入字符的方式转化成回文，最小步数是多少。
取现字符串所有可能的位置做新字符串对称中心，然后计算两侧需要最少补多少字符，
因为只能通过插入所以这里贪心就可以了。不知道有没有更好的方法？
2. 实现一个HASHSET，要求O(1)做CLEAN，不能NEW一个新的来做。
修改hashfunction么，是两个function output range没有交集。不落在现在的output
data range里的hit都当作不存在，覆盖之。 |
|
z*******3
发帖数: 13709 | 47 字符填充，url，xml里面经常出现的，什么& lt ;这种
1）先确定你要的分隔符，比如选择,
2）把现有的字符串中所有的,全部改成,1，这样原字符中就没有,了
3）把所有的string全部凑起来，用,2分割，返回
第二步从这里回头做
第一步需要额外包装一个method
切割长字符串，用,2分割，把,1换成，拼凑成list，返回
如果长字符串中出现,1和,2以外的其他组合，比如,3之类的，就是exception |
|
l********s
发帖数: 276 | 48 不知道为啥只有4关
1. 亚裔，聊天，然后一道题: 字符match to 其他字符，给你一个字符串，求所有可能
的字符串match。
2. 亚裔，又是聊天，然后是wordsearch，基本是原题，但四个方向的变成八个方向了。
3. 白人design, geohash + kd tree那道题，感觉做的不好，我说每句话面试官都要打
算一下问个问题，导致最后时间都回答他的问题了，连草图都没画出来。最后果然挂在
这一轮。
4. 白人一个字符串，比如"a(bb)a((bc)())", 返回"a(bb)a(bc)()"就是保留valid的括
号。刚开始这白人一副不屑的样子，我说什么他都说OK, 好像意思是说“我知道你做不
出来”，后来做出来了又一道one edit distance，原题。
面试官都很年轻，这次碰到的亚裔都很nice, 在此表示感谢。道是碰到的白人不行，才
工作了两年就很Arrogant. |
|
l******s
发帖数: 3045 | 49 一点想法对于长字符串数字的除法与取模，可以二分法切割后为左侧字符串做除法及取
模以较快缩短整个字符串到long范围内。
reading |
|
I******c
发帖数: 163 | 50 我的java实现，参考了Blaze的思路，不过不知道真正理解了他的思路没有，因为我不
太看得懂javascript.下面是几个点：
1. 这个题目用的是backtracking而不是dp，因为dp不可能给你产生排列组合。dp通常
就是给你一个最值。
2. 时间复杂度是指数级。
3. 题目的本质是产生排列。
4. 一般的backtracking来形成字符串的话,从现有字母集中每次任意挑一个字母,然后
从剩下的字母里继续挑。把所有字母都加到字符串里面去了，这轮程序也就完了。这个
题目因为有个顺序的限制条件，决定程序怎样进行下去并不能用剩下多少字符来决定，
而应该是用已经加入字符串的字母的位置来决定。
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Set;
public class Example5 {
public static void main(String [] args){
... 阅读全帖 |
|
