logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
rocket fuel第一轮面经
avatar
rocket fuel第一轮面经# JobHunting - 待字闺中
p*u
1 楼
有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
注意不是求合法的括号个数。。。
三哥面试官，感觉算三哥里面比较好听懂的发音了
就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
。。
感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
长时间。
avatar
f*3
2 楼
这回不是三哥黑你，这是rf常见题

【在 p*u 的大作中提到】
: 有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
: 注意不是求合法的括号个数。。。
: 三哥面试官，感觉算三哥里面比较好听懂的发音了
: 就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
: 。。
: 感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
: 长时间。
avatar
p*u
3 楼
感觉比较tough啊，有题解没？

【在 f**********3 的大作中提到】
: 这回不是三哥黑你，这是rf常见题
avatar
w*s
4 楼
直接枚举吧？内存不会吃不消，如果数目很大，枚举输出会很长时间。

【在 p*u 的大作中提到】
: 有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
: 注意不是求合法的括号个数。。。
: 三哥面试官，感觉算三哥里面比较好听懂的发音了
: 就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
: 。。
: 感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
: 长时间。
avatar
l*n
5 楼
应该类似BackTrack吧，不用都存起来。

【在 p*u 的大作中提到】
: 有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
: 注意不是求合法的括号个数。。。
: 三哥面试官，感觉算三哥里面比较好听懂的发音了
: 就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
: 。。
: 感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
: 长时间。
avatar
l*z
6 楼
我面过这题 是让直接打出来 不会存在内存里
用stack做 和leetcode上的generate parenthesis差不多
avatar
p*u
7 楼
时间复杂度很高啊？

【在 l***z 的大作中提到】
: 我面过这题 是让直接打出来 不会存在内存里
: 用stack做 和leetcode上的generate parenthesis差不多
avatar
f*e
8 楼
一个比较简单的办法是用递归来逐步添加各种括号 可以用一个stack来判断每次加的括
号是否合理
应该是可以把以上这个递归的过程改称迭代的 逻辑上可能会比较复杂一些 在电话面
试里写这个还是挺不容易的

【在 p*u 的大作中提到】
: 有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
: 注意不是求合法的括号个数。。。
: 三哥面试官，感觉算三哥里面比较好听懂的发音了
: 就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
: 。。
: 感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
: 长时间。
avatar
p*u
9 楼
你这个思路挺好！
我当时是写的这种，你看下能过不？。。。空间消耗很大
https://code.stypi.com/b9fzywss

【在 f********e 的大作中提到】
: 一个比较简单的办法是用递归来逐步添加各种括号 可以用一个stack来判断每次加的括
: 号是否合理
: 应该是可以把以上这个递归的过程改称迭代的 逻辑上可能会比较复杂一些 在电话面
: 试里写这个还是挺不容易的
avatar
c*p
10 楼
mark
avatar
f*e
11 楼
恩 好的 我看看

【在 p*u 的大作中提到】
: 你这个思路挺好！
: 我当时是写的这种，你看下能过不？。。。空间消耗很大
: https://code.stypi.com/b9fzywss
avatar
f*a
12 楼
cc150原题
avatar
m*k
13 楼
这么做有重复吧，
start with {}{}(),
then
{} ({})
and
{}({})
are actually the same.

【在 p*u 的大作中提到】
: 你这个思路挺好！
: 我当时是写的这种，你看下能过不？。。。空间消耗很大
: https://code.stypi.com/b9fzywss
avatar
B*D
14 楼
这题的思路是这样的.
首先, 因为需要罗列, 速度不是问题, 你必须一一枚举所有有效排列. 因为是打印, 你
不必把所有答案都存起来. 产生一个, 打一个.
这题相当于, 你有三个水管喝水, 如何排列组合的问题. 很明显, 递归是最容易想到的
.
举例来说. 如果是2, 2, 2的情况, 假设你走到某一步, 比如说, 你已经各用了一个左
括号, 每种左括号还各剩一个, 你怎么办?
你有四种选择, 取一个左括号(三种), 或者加一个右括号. 右括号必须与最近一次的左
扩号匹配. 因此, 你需要4个参数.
1. 还剩几个 "("
2. 还剩几个 "["
3. 还剩几个 "{"
4. 当前的结果.
下面是用JAVA写的CODE. 为了方便, 多加了一个参数, 所有目前为止的左括号的STACK.
这是为了不用分析当前结果去找下一个右括号.
public class ListP
{
static int count = 0;
public static void main(String args[])
{
int n1 = 2;
int n2 = 2;
int n3 = 1;
PrintP(n1, n2, n3, "", "");

}
static String rightPart(String left)
{
if (left.equals("(")) return ")";
if (left.equals("[")) return "]";
return "}";
}
static void PrintP(int n1, int n2, int n3, String result, String
leftStack)
{
if (n1 == 0 && n2 ==0 && n3 == 0 && leftStack.length() == 0)
{
count ++;
System.out.println ("" + count + ":" + result + "\r\n");
}

if (leftStack.length() > 0)
{
PrintP(n1, n2, n3, result + rightPart(leftStack.substring(0, 1))
, leftStack.substring(1));
}

if (n1 > 0)
{
PrintP(n1 - 1, n2, n3, result + "(", "(" + leftStack);
}

if (n2 > 0)
{
PrintP(n1, n2-1, n3, result + "[", "[" + leftStack);
}
if (n3 > 0)
{
PrintP(n1, n2, n3-1, result + "{", "{" + leftStack);
}
}
}
avatar
z*e
15 楼
re一个

【在 B****D 的大作中提到】
: 这题的思路是这样的.
: 首先, 因为需要罗列, 速度不是问题, 你必须一一枚举所有有效排列. 因为是打印, 你
: 不必把所有答案都存起来. 产生一个, 打一个.
: 这题相当于, 你有三个水管喝水, 如何排列组合的问题. 很明显, 递归是最容易想到的
: .
: 举例来说. 如果是2, 2, 2的情况, 假设你走到某一步, 比如说, 你已经各用了一个左
: 括号, 每种左括号还各剩一个, 你怎么办?
: 你有四种选择, 取一个左括号(三种), 或者加一个右括号. 右括号必须与最近一次的左
: 扩号匹配. 因此, 你需要4个参数.
: 1. 还剩几个 "("
avatar
c*p
16 楼
mark
avatar
f*x
17 楼

大神！多谢

【在 B****D 的大作中提到】
: 这题的思路是这样的.
: 首先, 因为需要罗列, 速度不是问题, 你必须一一枚举所有有效排列. 因为是打印, 你
: 不必把所有答案都存起来. 产生一个, 打一个.
: 这题相当于, 你有三个水管喝水, 如何排列组合的问题. 很明显, 递归是最容易想到的
: .
: 举例来说. 如果是2, 2, 2的情况, 假设你走到某一步, 比如说, 你已经各用了一个左
: 括号, 每种左括号还各剩一个, 你怎么办?
: 你有四种选择, 取一个左括号(三种), 或者加一个右括号. 右括号必须与最近一次的左
: 扩号匹配. 因此, 你需要4个参数.
: 1. 还剩几个 "("
avatar
k*o
18 楼
mark
avatar
S*o
19 楼
这个不是leetcode的原题么。。
avatar
l*a
20 楼
mark
avatar
n*a
21 楼
mark
avatar
p*u
22 楼
有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
注意不是求合法的括号个数。。。
三哥面试官，感觉算三哥里面比较好听懂的发音了
就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
。。
感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
长时间。
avatar
f*3
23 楼
这回不是三哥黑你，这是rf常见题

【在 p*u 的大作中提到】
: 有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
: 注意不是求合法的括号个数。。。
: 三哥面试官，感觉算三哥里面比较好听懂的发音了
: 就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
: 。。
: 感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
: 长时间。
avatar
p*u
24 楼
感觉比较tough啊，有题解没？

【在 f**********3 的大作中提到】
: 这回不是三哥黑你，这是rf常见题
avatar
w*s
25 楼
直接枚举吧？内存不会吃不消，如果数目很大，枚举输出会很长时间。

【在 p*u 的大作中提到】
: 有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
: 注意不是求合法的括号个数。。。
: 三哥面试官，感觉算三哥里面比较好听懂的发音了
: 就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
: 。。
: 感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
: 长时间。
avatar
l*n
26 楼
应该类似BackTrack吧，不用都存起来。

【在 p*u 的大作中提到】
: 有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
: 注意不是求合法的括号个数。。。
: 三哥面试官，感觉算三哥里面比较好听懂的发音了
: 就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
: 。。
: 感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
: 长时间。
avatar
l*z
27 楼
我面过这题 是让直接打出来 不会存在内存里
用stack做 和leetcode上的generate parenthesis差不多
avatar
p*u
28 楼
时间复杂度很高啊？

【在 l***z 的大作中提到】
: 我面过这题 是让直接打出来 不会存在内存里
: 用stack做 和leetcode上的generate parenthesis差不多
avatar
f*e
29 楼
一个比较简单的办法是用递归来逐步添加各种括号 可以用一个stack来判断每次加的括
号是否合理
应该是可以把以上这个递归的过程改称迭代的 逻辑上可能会比较复杂一些 在电话面
试里写这个还是挺不容易的

【在 p*u 的大作中提到】
: 有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
: 注意不是求合法的括号个数。。。
: 三哥面试官，感觉算三哥里面比较好听懂的发音了
: 就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
: 。。
: 感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
: 长时间。
avatar
p*u
30 楼
你这个思路挺好！
我当时是写的这种，你看下能过不？。。。空间消耗很大
https://code.stypi.com/b9fzywss

【在 f********e 的大作中提到】
: 一个比较简单的办法是用递归来逐步添加各种括号 可以用一个stack来判断每次加的括
: 号是否合理
: 应该是可以把以上这个递归的过程改称迭代的 逻辑上可能会比较复杂一些 在电话面
: 试里写这个还是挺不容易的
avatar
c*p
31 楼
mark
avatar
f*e
32 楼
恩 好的 我看看

【在 p*u 的大作中提到】
: 你这个思路挺好！
: 我当时是写的这种，你看下能过不？。。。空间消耗很大
: https://code.stypi.com/b9fzywss
avatar
f*a
33 楼
cc150原题
avatar
B*D
34 楼
这题的思路是这样的.
首先, 因为需要罗列, 速度不是问题, 你必须一一枚举所有有效排列. 因为是打印, 你
不必把所有答案都存起来. 产生一个, 打一个.
这题相当于, 你有三个水管喝水, 如何排列组合的问题. 很明显, 递归是最容易想到的
.
举例来说. 如果是2, 2, 2的情况, 假设你走到某一步, 比如说, 你已经各用了一个左
括号, 每种左括号还各剩一个, 你怎么办?
你有四种选择, 取一个左括号(三种), 或者加一个右括号. 右括号必须与最近一次的左
扩号匹配. 因此, 你需要4个参数.
1. 还剩几个 "("
2. 还剩几个 "["
3. 还剩几个 "{"
4. 当前的结果.
下面是用JAVA写的CODE. 为了方便, 多加了一个参数, 所有目前为止的左括号的STACK.
这是为了不用分析当前结果去找下一个右括号.
public class ListP
{
static int count = 0;
public static void main(String args[])
{
int n1 = 2;
int n2 = 2;
int n3 = 1;
PrintP(n1, n2, n3, "", "");

}
static String rightPart(String left)
{
if (left.equals("(")) return ")";
if (left.equals("[")) return "]";
return "}";
}
static void PrintP(int n1, int n2, int n3, String result, String
leftStack)
{
if (n1 == 0 && n2 ==0 && n3 == 0 && leftStack.length() == 0)
{
count ++;
System.out.println ("" + count + ":" + result + "\r\n");
}

if (leftStack.length() > 0)
{
PrintP(n1, n2, n3, result + rightPart(leftStack.substring(0, 1))
, leftStack.substring(1));
}

if (n1 > 0)
{
PrintP(n1 - 1, n2, n3, result + "(", "(" + leftStack);
}

if (n2 > 0)
{
PrintP(n1, n2-1, n3, result + "[", "[" + leftStack);
}
if (n3 > 0)
{
PrintP(n1, n2, n3-1, result + "{", "{" + leftStack);
}
}
}
avatar
z*e
35 楼
re一个

【在 B****D 的大作中提到】
: 这题的思路是这样的.
: 首先, 因为需要罗列, 速度不是问题, 你必须一一枚举所有有效排列. 因为是打印, 你
: 不必把所有答案都存起来. 产生一个, 打一个.
: 这题相当于, 你有三个水管喝水, 如何排列组合的问题. 很明显, 递归是最容易想到的
: .
: 举例来说. 如果是2, 2, 2的情况, 假设你走到某一步, 比如说, 你已经各用了一个左
: 括号, 每种左括号还各剩一个, 你怎么办?
: 你有四种选择, 取一个左括号(三种), 或者加一个右括号. 右括号必须与最近一次的左
: 扩号匹配. 因此, 你需要4个参数.
: 1. 还剩几个 "("
avatar
c*p
36 楼
mark
avatar
f*x
37 楼

大神！多谢

【在 B****D 的大作中提到】
: 这题的思路是这样的.
: 首先, 因为需要罗列, 速度不是问题, 你必须一一枚举所有有效排列. 因为是打印, 你
: 不必把所有答案都存起来. 产生一个, 打一个.
: 这题相当于, 你有三个水管喝水, 如何排列组合的问题. 很明显, 递归是最容易想到的
: .
: 举例来说. 如果是2, 2, 2的情况, 假设你走到某一步, 比如说, 你已经各用了一个左
: 括号, 每种左括号还各剩一个, 你怎么办?
: 你有四种选择, 取一个左括号(三种), 或者加一个右括号. 右括号必须与最近一次的左
: 扩号匹配. 因此, 你需要4个参数.
: 1. 还剩几个 "("
avatar
k*o
38 楼
mark
avatar
S*o
39 楼
这个不是leetcode的原题么。。
avatar
n*a
40 楼
mark
avatar
l*1
41 楼
void dfs(int n1, int n2, int n3, string transfer, set &dict){
if(n1 == 0 && n2 == 0 && n3 == 0){
if(dict.find(transfer) == dict.end()){
dict.insert(transfer);
cout<}
return;
}
if(transfer.size() == 0){
if(n1 > 0){
string temp = "()";
dfs(n1 - 1, n2, n3, temp, dict);
}
if(n2 > 0){
string temp = "[]" ;
dfs(n1, n2 - 1, n3, temp, dict);
}
if(n3 > 0){
string temp = "{}";
dfs(n1, n2, n3 - 1, temp, dict);
}
}

for(int i = 0; i < transfer.size(); ++i){
if(transfer[i] == '(' || transfer[i] == '[' || transfer[i] == '{'){
if(n1 > 0){
string temp = transfer.substr(0, i + 1) + "()" + transfer.
substr(i + 1);
dfs(n1 - 1, n2, n3, temp, dict);
}
if(n2 > 0){
string temp = transfer.substr(0, i + 1) + "[]" + transfer.
substr(i + 1);
dfs(n1, n2 - 1, n3, temp, dict);
}
if(n3 > 0){
string temp = transfer.substr(0, i + 1) + "{}" + transfer.
substr(i + 1);
dfs(n1, n2, n3 - 1, temp, dict);
}
}
}
}
void generateParenthesis(int n1, int n2, int n3) {
set dict;
dfs(n1, n2, n3, "",dict);
}
avatar
w*r
42 楼
来个简单易懂的python版, n1是剩余左括号， n1_是剩余右括号
res = []
def gen(sol, stk, n1, n2, n3, n1_, n2_, n3_):
if n1 == 0 and n2 == 0 and n3 == 0 and n1_ == 0 and n2_ == 0 and n3_ ==
0:
res.append("".join(sol))
return

if n1 > 0:
gen(sol[:] + ["("], stk[:] + [1], n1-1, n2, n3, n1_, n2_, n3_)
if n2 > 0:
gen(sol[:] + ["["], stk[:] + [2], n1, n2-1, n3, n1_, n2_, n3_)

if n3 > 0:
gen(sol[:] + ["{"], stk[:] + [3], n1, n2, n3-1, n1_, n2_, n3_)
if len(stk) > 0 and stk[-1] == 1:
gen(sol[:] + [")"], stk[:-1], n1, n2, n3, n1_-1, n2_, n3_)
if len(stk) > 0 and stk[-1] == 2:
gen(sol[:] + ["]"], stk[:-1], n1, n2, n3, n1_, n2_-1, n3_)

if len(stk) > 0 and stk[-1] == 3:
gen(sol[:] + ["}"], stk[:-1], n1, n2, n3, n1_, n2_, n3_-1)

gen([], [], 2, 2, 1, 2, 2, 1)
for i in res:
print i
avatar
w*r
43 楼
我在想，有没有办法能求出solution的个数?
相关阅读
他妈的这个月光有病？ (转载)说说自己被国人帮助的经历大家negotiate的时候会多要base还是RSU？最近大公司招人情况如何，小公司一年经验貌似完全被ignore攒人品，junior engineer以及实习生职位招毕业生或毕业生gonna (转载)Re: 提供T家内推最近各种面试感受求中文老师或者其他教育专业工作问个关于RSU的问题微软需要合同工 ，特别需要会说中文的 (转载)Oracle 湾区和 Amazon offer 求建议研究型职位还是swe职位？h1b transfer申请提交之后可以撤销吗问一下OPT申请的状态求助CMU毕业的朋友 --- 择专业请教恳请分析电面的问题（半导体）抽大麻打吗啡的怎么通过drug test？Amazon被不同组店面再问一个关于摆渡的情况问一道Facebook近期电面题
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。