问一道Facebook近期电面题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道Facebook近期电面题

问一道Facebook近期电面题# JobHunting - 待字闺中

d*42015-03-20 07:03

1 楼

富贵生活（24）
http://vip.book.sina.com.cn 2013年12月20日02:39 新浪读书
（二十四）
两人走出唐人街。还是上坡路，有一段路真陡，不常锻炼的冯珊珊累得直喘气。王富贵
接过老婆的挎包，拉着老婆的手吃力地往上走。
街道两旁的房子还是一座紧挨着一座很拥挤的模样，但外表看上去要比唐人街的老房子
光鲜很多，更体面一些。
街道两旁的房子都是两层或三层高的小楼。一楼很多是各种小店铺，地处旅游区，针对
的客户群主要是外地游客，所以大多卖吃的、用的，还有五花八门的旅游纪念品。
这条街上的居民也象国内许多地方一样，每家每户都装了防盗门和防盗栏杆，阳台上多
多少少都放了些杂物，想必里面的居住空间很有限。
但无论是放杂物的阳台角落，还是堆满瓶瓶罐罐的窗台上，或是屋檐、栏杆和前门的石
阶旁，都零零散散地摆放着一些花草，在阳光里生气勃勃，显示着屋子的主人热爱生活
追求美的积极生活态度......
走了20多分钟，两人抵达圣彼得与圣保罗(Peter & Paul )教堂。圣彼得与圣保罗教堂
是一座罗马天主教堂，也是旧金山的地标之一，果然名不虚传。
教堂洁白的锥形塔尖在碧蓝的晴空下气势雄伟，庄严肃穆。
教堂的前面有一块很大的草坪。
好一块都市净土：阳光穿过绿树的枝叶缝隙洒下斑驳的光影，人们或坐或躺，读书、聊
天、晒日光浴或写生......嬉笑玩耍的孩子与狗以及成群觅食的白鸽和欢快的小松鼠互
不打扰，和睦相处......祥和的气氛，欢乐的地方，让人不由地想在此处悠哉一会儿。
阳光如此灿烂，微风让人沉醉，王富贵和冯珊珊也找了一块有绿荫的僻静角落下来。半
小时的日光浴晒得两人有点昏昏欲睡。
王富贵站起身来说：“如果衣食无忧，在美国生活挺好，就凭这蓝天、白云、绿树和花
草，还有清新无比的干净空气。”
冯珊珊听这话却问：“这些你老家都有，你怎么不搬到那儿去？”
王富贵一时怔住，无言以对。
从教堂走到Lombard街，远远就可以看到著名的九曲花街了。
看景不如听景，真走到花街，放眼望去王富贵却有些失望。
这条十九世纪二十年代为行路安全而设计的被称为‘世界上最弯曲的街道’实在是太短
了。长度才不到400米的单行道，居然有九个湾。据说一年四季，世界各地的游客源源
不断地慕名而来，开着车以不超过五英里的限速蜿蜒下行。
30度左右的斜坡，车挨着车，一不留神就会亲到前面的车。
王富贵发现旧金山真是个考验司机开车技术的好地方。街斜坡陡，两旁还趴满了车，拿
着钱都找不到趴车位，技术不好即使有趴车位也趴不进去。
如果是菜鸟级的司机，在旧金山最好别自己开车。这个城市公交系统很发达，设施完善
，服务也周到，乘公交车更方便快捷。
九曲花街对冯珊珊来说也没有什么惊艳的感觉，她倒是觉得这一代的居民真是好福气。
九曲花街行车道两旁是花坛，花坛旁边是观光道，观光道旁就是民宅。
这一带是旧金山的富人区。每栋小洋楼外观精美，红瓦青砖，花艳草碧，十分美丽。
拾级而上，时不时地从窗帘后面探出的猫或狗，抑或白色木栅栏围墙内伸出的各色玫瑰
以及绿树浓荫处挂在枝头的黄柠檬或红石榴，都让人惊喜万分......
王富贵和冯珊珊走得腰酸腿困，才跟随其他游客爬到了花街的顶端。远处的刻伊特塔及
海湾大桥矗立在风光旖旎的海湾里，美不胜收。
王富贵对老婆说：“美国的贫富差距也很明显嘛！你看这些豪宅跟刚才走过的贫民区的
破旧鸽子笼相比，岂不是天壤之别？”
冯珊珊没有听见王富贵在说什么。冯珊珊微闭着眼睛陶醉地嗅着空气里的花草芳香，大
声说：“太美了！太美了！老公，我们什么时候能住上这样的房子？我就是死了也值了
！”
王富贵心头一沉，没有吭声，心里嘀咕：“老婆的心很大啊！我这英语说不流利，连工
作都还没影的人，如何有能力买得起这样的豪宅？这一带的房子一栋少说也值几百万美
金吧？”
老婆的一句玩笑话惊醒了逍遥半日的王富贵，内心的轻松愉悦也荡然无存......
两人沿着缆车道走到海边。天气很暖和，不知是不是海风的缘故王富贵却觉得有点冷。
风景依旧美丽迷人，但王富贵失去了欣赏富人们的豪华游艇和别墅的兴致。
对穷人来说，这些浮华都是镜中月水中花，不能填饱肚子，没用！
王富贵觉得自己就像那些空中盘旋忙着觅食的海鸥，现在应该考虑的是如何在美国生存
。否则，饿着肚子哪有心思享受蓝天白云？饿着肚子哪有心思琢磨浪漫情趣？
两人按照地图的指示沿着海滨大街继续往前走，看到螃蟹的标志牌就知到了著名的渔人
码头（Pier 39）。
在渔人码头游客能坐船游览金门大桥，但王富贵和冯珊珊到渔人码头时已是下午4点多
，游船公司的最后一班船是4点整，所以两人今天没机会坐船看金门桥了。
冯珊珊因此很沮丧，提不起兴致挨个逛码头上鳞次栉比的特色旅游商铺。
王富贵嘴上安慰着老婆以后还有机会，心里却偷着乐：“坐游船两个人的票价要花52美
元，旧金山市今年的最低时薪是10.24美元，穷人干5个小时才能挣这么多钱，能省钱何
乐而不为呢？”
这念头一起，王富贵不由地心生悲哀：“我这是怎么了？我花了50多万美元移民美国，
我却开始算计省下50美元。在北京我随便穿的一件体恤也超过了50美元。难道真的象人
们所说的那样，中国人在美国无依无靠，心里没底就变小器了？自己怎么又回到了十几
年前计较每一分钱的穷学生心态？”
在渔人码头，王富贵和冯珊珊终于如愿以偿地吃到了著名的旧金山深海大螃蟹和酸面包
碗奶油海鲜蛤蜊汤。
冯珊珊连声赞美这汤浓而不腻，鲜美十足，马上用手机拍照发给国内的众亲友一饱眼福。
可王富贵却大煞风景地说：“我觉得这两样名吃还不如我们河南家乡的小吃胡辣汤呢。
热乎乎的来一碗从头顶舒服到脚跟，才花1美元，这儿可是贵了十几倍。”
“钱，钱，钱，就知道算钱，在北京你可不是这样的，真俗！”冯珊珊不耐烦地数落王
富贵。
夕阳西下，彩霞满天，旧金山海湾被镀了一层美丽的金，水面上波光粼粼，白色的海鸟
三五成群地聚集在一起小憩，美景如画，王富贵的心里却犹如身边的海浪翻腾不已....
..
当年他孤身来北京上学，交完学杂费兜里就没剩几个钱。一天要买几个馒头都要考虑半
天，肚子饿时经常靠喝水充饥。
如今身处异国他乡，天天要花钱，处处离不了钱。如果找不到工作，光靠积蓄维持不了
多久，当然要精打细算了。
可是，一直养尊处优的老婆冯珊珊如何能体会到苦出身的王富贵的危机感呢？
“钱，钱，钱，少花钱是生存王道，多挣钱是致富王道！”王富贵告诉自己。
其实，王富贵自己也有些糊涂了。
放着北京衣食无忧的安稳日子不过偏要移民美国，脑子进水啦？

t*t2015-03-20 07:03

2 楼

Given a string with parentheses, return a string with balanced parentheses
by removing the fewest characters possible. You cannot add anything to the
string.
Examples:
balance("()") -> "()"
balance(")(") -> "".
balance("(((((") -> ""
balance("(()()(") -> "()()"
balance(")(())(") -> "(())"
注意：balance(")(())(") != "()()"
这题看上去比较像LeetCode的Longest Valid Parentheses，求大神们指教只用一个
stack怎么做？

C*t2015-03-20 07:03

3 楼

def longestValid(s):
if s == None: return 0
m = len(s)
res, begin = [0,0], 0
stack = []
for i in range(m):
if s[i] == '(':
stack.append(i)
elif len(stack) == 0:
begin = i + 1
else:
stack.pop()
if len(stack) == 0:
if res[1]-res[0] < i-begin:
res = [begin, i]
else:
if res[1] - res[0] < i - stack[-1] -1:
res = [stack[-1]+1, i]
return s[res[0]:res[1]+1]

【在 t*****t 的大作中提到】

: Given a string with parentheses, return a string with balanced parentheses
: by removing the fewest characters possible. You cannot add anything to the
: string.
: Examples:
: balance("()") -> "()"
: balance(")(") -> "".
: balance("(((((") -> ""
: balance("(()()(") -> "()()"
: balance(")(())(") -> "(())"
: 注意：balance(")(())(") != "()()"

t*t2015-03-20 07:03

4 楼

这个代码貌似只是找到了最长的，原题是要求删除尽可能少的括号，使得原string为一
个valid的，和LeetCode原题好像还是有不同的。

【在 C****t 的大作中提到】

: def longestValid(s):
: if s == None: return 0
: m = len(s)
: res, begin = [0,0], 0
: stack = []
: for i in range(m):
: if s[i] == '(':
: stack.append(i)
: elif len(stack) == 0:
: begin = i + 1

S*w2015-03-20 07:03

5 楼

String balance(String s) {
int start = 0, i = 0;
Stack stack = new Stack();
String cur = "", ret = "";
while (i < s.length()) {
if (s.charAt(i) == '(') {
stack.push(i);
i = i + 1;
}
else {
if (stack.isEmpty()) {
ret += cur;
i = i + 1;
start = i;
cur = "";
}
else {
stack.pop();
// 这里与lc不同，直接移动start
if (stack.isEmpty()) {
ret += s.substring(start, i + 1);
cur = "";
i = i + 1;
start = i;
}
else {
cur = s.substring(stack.peek() + 1, i + 1);
i = i + 1;
}
}
}
}
return ret + cur;
}

【在 t*****t 的大作中提到】

t*t2015-03-20 07:03

6 楼

我用"(((()()(()))(((()()"做输入，你的代码貌似输出的是"()()"，好像是代码有点
问题。。。

【在 S***w 的大作中提到】

: String balance(String s) {
: int start = 0, i = 0;
: Stack stack = new Stack();
: String cur = "", ret = "";
: while (i < s.length()) {
: if (s.charAt(i) == '(') {
: stack.push(i);
: i = i + 1;
: }
: else {

w*32015-03-20 07:03

7 楼

先除去左（右）括号，再除去右（左）括号。
这应该算是一个stack吧。
string rmRight(string bal)
{
int low = 0;
string result;
int pos = 0;
int count = 0;
while(pos{
if(bal[pos]=='(')
{
result.push_back('(');
count++;
}
else
{
if(count>0)
{
count--;
result.push_back(')');
}
}
pos++;
}
return result;
}
string rmLeft(string bal)
{
int pos = 0;
string result;
int count = 0;
pos = bal.length()-1;
while(pos>=0)
{
if(bal[pos]==')')
{
result.push_back('(');
count++;
}
else
{
if(count>0)
{
count--;
result.push_back(')');
}
}
pos--;
}
return result;
}
int main()
{
string bal = "(((()()(()))(((()()";
string result = rmRight(bal);
result = rmLeft(bal);
cout<}

a*u2015-03-20 07:03

8 楼

balance应该怎么定义？　( ( ) )( ) 这个算是balance么？( )( )( )这个算是
balance吗？

z*m2015-03-20 07:03

9 楼

找到最长的括号就等价于删除最少啦
就用leetcode上那题的思路，用stack，然后加入一个变量记录最长括号的起始结束
index就可以了吧。
然后最后extract一下substr就好了吧

【在 t*****t 的大作中提到】

: 这个代码貌似只是找到了最长的，原题是要求删除尽可能少的括号，使得原string为一
: 个valid的，和LeetCode原题好像还是有不同的。

c*12015-03-20 07:03

10 楼

$ cat x.cc; g++ x.cc; ./a.out
#include
void f(char* str) {
int left = 0;
char* p;
for (p = str; *p; ++p) {
if (*p == '(') {
++left;
} else if (left != 0) {
--left;
} else {
*p = ' ';
}
}
for (--p; p >= str && left != 0; --p) {
if (*p == '(') {
*p = ' ';
--left;
}
}
}
int main() {
char buf[] = ")()))))))(()()(())())()))))))))";
printf("%s\n", buf);
f(buf);
printf("%s\n", buf);
return 0;
}
)()))))))(()()(())())()))))))))
() (()()(())())()

c*w2015-03-20 07:03

11 楼

Suppose the input is a string s
dp(i, j) = min removal for s(i, j)
then ans = dp(0, n-1)
dp(i, j) = min of the followings
dp(i, k) + dp(k, j), i < k < j --> break the string in the middle
dp(i, j-1) + 1 --> remove s[j]
dp(i-1, j) + 1 --> remove s[i]
dp(i-1, j-1) --> if s[i] == '(' and s[j] == ')'
O(n^3), may be able to optimized to O(n^2)

【在 t*****t 的大作中提到】

r*72015-03-20 07:03

12 楼

遇到valid的就存下来不就行了。。。
你这个id可是tc上的大牛啊

【在 t*****t 的大作中提到】

s*y2015-03-20 07:03

13 楼

我面试时不说思路上来写代码的第一印象一下就不好了。。。

【在 C****t 的大作中提到】

: def longestValid(s):
: if s == None: return 0
: m = len(s)
: res, begin = [0,0], 0
: stack = []
: for i in range(m):
: if s[i] == '(':
: stack.append(i)
: elif len(stack) == 0:
: begin = i + 1

p*02015-03-20 07:03

14 楼

skipskip

【在 t*****t 的大作中提到】

W*u2015-03-20 07:03

15 楼

用一个stack 扫一遍，把不valid的符号存里面，最后再筛一次。 O(n) + O(n)
我理解对了么？
String balance(String par) {
if (par.length() < 1)
return null;
String rlt = "";
Stack upSt = new Stack();
for (int i = 0; i < par.length(); i++) {
char c = par.charAt(i);
if (c == '(' || c == ')') {
if (upSt.isEmpty()) {
upSt.push(i);
} else {
char topChar = par.charAt(upSt.peek());
if (topChar != c && topChar == '(') {
upSt.pop();
} else {
upSt.push(i);
}
}
} else {
System.out.println("Error!! Not valid input. ");
return null;
}
}
for (int i = 0; i < par.length(); i++) {
if (!upSt.contains(i)) {
rlt += par.charAt(i);
}
}
return rlt;
}

n*y2015-03-20 07:03

16 楼

用stack 扫，不match 的 ) 全部删掉。
最后如果有剩下的 ( , 从右往左删掉对应的个数就可以了。因为 ( 如果在右边是
match的，往左移仍然match.
随后好像不是唯一解
比如输入
(()()
可以是
()()
也可以是 (())
我的算法会得出
(())的结果

n*y2015-03-20 07:03

17 楼

上面的算法可以这样实现
def string(s)
tot = len(s)
if tot == 0
return s
cnt = 0
res = ""
index = 0
for index in range(tot):
if s[index] == "(":
res += "("
cnt += 1
elif (cnt > 0):
cnt -= 1
res += ")"
if cnt == 0:
return res
if cnt == len(res)
return ""
cnt2 = 0
index = len(res) - 1
while(cnt>0):
if (res[index] == "(")
cnt -= 1
else:
cnt2 += 1
index -= 1
return res[0:index+1] + ")" * cnt2

p*g2015-03-20 07:03

18 楼

string balance(string s)
{
stack> st;
for (int i = 0; i < s.length(); i++)
{
char c = s[i];
if (c == '(') st.push(make_pair(c, i));
else
{
if (!st.empty() && st.top().first == '(') st.pop();
else st.push(make_pair(c, i));
}
}
for(; !st.empty(); s.erase(st.top().second, 1), st.pop());
return s;
}

p*g2015-03-20 07:03

19 楼

补个说明：
算法和前面诸神的一样，stack存放pair。（1）先扫描一遍字符串，
stack里只会剩下"bad guys"，（2）然后从stack里pop出bad guys，根据index在原字
符串里删除掉（index backward，所以不影响删除）。
所有的test case已过。

b*i2015-03-20 07:03

20 楼

大体思路就是记录下所有当前是反括号但是没有正括号pop出来的，和最后剩下的正括号
class Solution {
public:
string balance(string s) {
int n = s.length();
if(n == 0)
return 0;
vector stk;
vector to_remove(n, false);
for(int i = 0; i < n; i++) {
char c = s[i];
if(c == '(') {
stk.push_back(i);
} else {
if(stk.empty())
to_remove[i] = true;
else {
stk.pop_back();
}
}
}
for(auto i : stk)
to_remove[i] = true;
string ret;
for(int i = 0; i < n; i++)
if(!to_remove[i])
ret.push_back(s[i]);
return ret;
}
};
int main() {
Solution solution;
cout << solution.balance("()") << endl;
cout << solution.balance(")(") << endl;
cout << solution.balance("(((((") << endl;
cout << solution.balance("(()()(") << endl;
cout << solution.balance(")(())(") << endl;
cout << solution.balance("(()))(()") << endl;
cout << solution.balance("(((()()(()))(((()()") << endl;
}
()
()()
(())
(())()
(()()(()))()()

c*12015-03-20 07:03

21 楼

You don't need a stack, just a counter. Look at my solution at Floor 9,
which is O(n) time in-place.

s*y2015-03-20 07:03

22 楼

OP asks for the longest subsequence, NOT substring. Stack is probably
inapplicable when dealing with subsequence, not substring as leetcode's
Longest Valid Parentheses. One solution is at http://stackoverflow.com/questions/26643697/longest-subsequence-of-balanced-parentheses. It computes the longest length, but can be easily changed to compute the longest subsequence by remembering all left and right parentheses whenever a pair is found.

d*v2015-03-20 07:03

23 楼

这题挺难的

n*n2015-03-20 07:03

24 楼

stack 怎么和substr有关了？没看懂。

【在 s*********y 的大作中提到】

: OP asks for the longest subsequence, NOT substring. Stack is probably
: inapplicable when dealing with subsequence, not substring as leetcode's
: Longest Valid Parentheses. One solution is at http://stackoverflow.com/questions/26643697/longest-subsequence-of-balanced-parentheses. It computes the longest length, but can be easily changed to compute the longest subsequence by remembering all left and right parentheses whenever a pair is found.

t*i2015-03-20 07:03

25 楼

这个方法挺好的，不用stack。但是要求不要改变输入string，重新建立一个str就行。

【在 c**1 的大作中提到】

: You don't need a stack, just a counter. Look at my solution at Floor 9,
: which is O(n) time in-place.