请问怎么换电灯的开关盖？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Living

请问怎么换电灯的开关盖？

请问怎么换电灯的开关盖？# Living

d*r2012-12-24 08:12

1 楼

被虐得一塌糊涂
面试官有口音，但不是烙印也不是国人。
先问了好久现在做的project，然后告诉我，接下来我要给你出三道算法题（当时就傻
了，亲，还有半个小时都不到了，真的是三道吗。。。）
1. 括号匹配，给定字符串，输出括号是否匹配，例子如下
"()" yes
")(" no
"(abcd(e)" no
"(a)(b)" yes
我先happy了一下，这个必须会啊。然后面试官开始讲要求，才发现图森破了。。。要
求必须用递归写，整个实现不可以出现一个循环语句。。。于是就华丽丽的跪了。现在
还没有想出来如何完全用递归。。。求版上大神指点。
2. 最长连续上升子串，给定字符串，输出最长连续上升子串的起始点和长度，例子如下
[2,3,4,0,40] => (0, 3)
[-5,-7,10,100,0,-10] => (1,3)
抬头一看，没有几分钟了，一顿狂写，出了点bug，估计这题也华丽丽的跪了
3. 传说中的第三题呢？没有时间了。。。

p*x2012-12-24 08:12

2 楼

房子装修完了，可是发现所有的开关盖都没换，新刷的白墙上映衬着一个个陈旧的暗
黄的电灯开关盖以及电源插座，很难看。
请问自己怎么换？

r*e2012-12-24 08:12

3 楼

验证括号：一个变量记录open的括号数
bool isValid(string &s, int curPos, int nOpen) {
if (curPos == s.size()) return (nOpen == 0);
if (s[curPos] == '(') {
++nOpen;
} else if (s[curPos] == ')') {
--nOpen;
}
if (nOpen < 0) return false;
return isValid(s, curPos + 1, nOpen);
}
调用：
string s = input();
return isValid(s, 0, 0);

如下

【在 d**********r 的大作中提到】

: 被虐得一塌糊涂
: 面试官有口音，但不是烙印也不是国人。
: 先问了好久现在做的project，然后告诉我，接下来我要给你出三道算法题（当时就傻
: 了，亲，还有半个小时都不到了，真的是三道吗。。。）
: 1. 括号匹配，给定字符串，输出括号是否匹配，例子如下
: "()" yes
: ")(" no
: "(abcd(e)" no
: "(a)(b)" yes
: 我先happy了一下，这个必须会啊。然后面试官开始讲要求，才发现图森破了。。。要

Z*e2012-12-24 08:12

4 楼

一个Flathead的螺丝刀就能换
或者家里养个男人。

d*r2012-12-24 08:12

5 楼

嗯，应该是这个。赞！

【在 r*******e 的大作中提到】

: 验证括号：一个变量记录open的括号数
: bool isValid(string &s, int curPos, int nOpen) {
: if (curPos == s.size()) return (nOpen == 0);
: if (s[curPos] == '(') {
: ++nOpen;
: } else if (s[curPos] == ')') {
: --nOpen;
: }
: if (nOpen < 0) return false;
: return isValid(s, curPos + 1, nOpen);

Q*s2012-12-24 08:12

6 楼

pair longestContinousSubArray(int arr, int n) {
if (n==0) return pair(0,0);
if (n==1) return pair(0,1);

int beginIndex = retBegin = 0;
int endIndex = 1;
int len = retLen =1;
for (endIndex=1; endIndexif (arr[endIndex] > arr[endIndex-1]) len++;
else {
len=1;
beginIndex = endIndex;
}
if (retLenretLen = len;
retBegin = endIndex;
}
}
return pair(retBegin, retLen);

}

s*r2012-12-24 08:12

7 楼

感觉不是很难，看来T没多大油水，所以门槛不高

y*g2012-12-24 08:12

8 楼

电面两题不少了，而且lz还说传说是三题

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

: 感觉不是很难，看来T没多大油水，所以门槛不高

x*w2012-12-24 08:12

9 楼

真是人如其名

【在 r*******e 的大作中提到】

s*r2012-12-24 08:12

10 楼

这题是programming pearl里面的经典，好像是递归解法，这么写估计悲剧

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

: pair longestContinousSubArray(int arr, int n) {
: if (n==0) return pair(0,0);
: if (n==1) return pair(0,1);
:
: int beginIndex = retBegin = 0;
: int endIndex = 1;
: int len = retLen =1;
: for (endIndex=1; endIndex: if (arr[endIndex] > arr[endIndex-1]) len++;
: else {

s*r2012-12-24 08:12

11 楼

学习了，感谢。

s*x2012-12-24 08:12

12 楼

mark

★ 发自iPhone App: ChineseWeb 7.8

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

: 这题是programming pearl里面的经典，好像是递归解法，这么写估计悲剧

D*62012-12-24 08:12

13 楼

靠，看来大家都被虐惯了，不考难的不爽。

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

: 感觉不是很难，看来T没多大油水，所以门槛不高

j*x2012-12-24 08:12

14 楼

补两道
一面
最长回文，只要求实现N^2
online stream 最长回文，记录最右端在目前字符串最右端的所有回文，依次扩展
讨论大数据处理中应该用什么system，考虑storm, mapreduce, kafka
最后一题问给定一个queue，两个接口put(int), findSum(T), 找出当前时刻结束的长
度为T（T有给定的最大值）的时间窗口内的值的总和，多线程；按每秒的边界组成子区
间，put 更新最右端区间，findSum顺序查找
二面
LRU cache，考虑实现get(key)的接口如何处理cache miss
Linux System call，write(file descriptor)从invoke到return发生了什么

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

: 这题是programming pearl里面的经典，好像是递归解法，这么写估计悲剧

D*62012-12-24 08:12

15 楼

啥意思？不递归就不对？？没要求就怎么写都行。没那么教条吧。

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

: 这题是programming pearl里面的经典，好像是递归解法，这么写估计悲剧

p*d2012-12-24 08:12

16 楼

mark

d*r2012-12-24 08:12

17 楼

所以说一面果然是三道题吗
这是面的什么组？题目就假设被面者熟悉storm, mapreduce, kafka等系统。。。

【在 j********x 的大作中提到】

: 补两道
: 一面
: 最长回文，只要求实现N^2
: online stream 最长回文，记录最右端在目前字符串最右端的所有回文，依次扩展
: 讨论大数据处理中应该用什么system，考虑storm, mapreduce, kafka
: 最后一题问给定一个queue，两个接口put(int), findSum(T), 找出当前时刻结束的长
: 度为T（T有给定的最大值）的时间窗口内的值的总和，多线程；按每秒的边界组成子区
: 间，put 更新最右端区间，findSum顺序查找
: 二面
: LRU cache，考虑实现get(key)的接口如何处理cache miss

s*r2012-12-24 08:12

18 楼

DP的问题，用来测试牛X度用的
http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-

【在 D****6 的大作中提到】

: 啥意思？不递归就不对？？没要求就怎么写都行。没那么教条吧。

w*t2012-12-24 08:12

19 楼

你说的是非连续的，lz被问的是连续的。难度当然不一样了

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

: DP的问题，用来测试牛X度用的
: http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-

w*y2012-12-24 08:12

20 楼

这个题目我知道答案思路，但是implement成这个样子，还是没看懂
55555

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

: DP的问题，用来测试牛X度用的
: http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-

s*r2012-12-24 08:12

21 楼

怎么用递归来写括号匹配。。。

s*r2012-12-24 08:12

22 楼

如果有好几种括号呢，要怎么做？
{ [(}] )

【在 r*******e 的大作中提到】

s*r2012-12-24 08:12

23 楼

stack，所有的反向括号都不可能往里压，有这种情况就是不匹配

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

: 如果有好几种括号呢，要怎么做？
: { [(}] )

s*r2012-12-24 08:12

24 楼

stack我知道怎么做，如何不用stack，只用递归。

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

: stack，所有的反向括号都不可能往里压，有这种情况就是不匹配

s*r2012-12-24 08:12

25 楼

括号匹配不是有2种做法么，一种是iteration，一种recursion，这个题目用recursion
怎么做阿？用iteration的话就是压stack里。

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

: stack，所有的反向括号都不可能往里压，有这种情况就是不匹配

r*h2012-12-24 08:12

26 楼

def check(a, nQuote, n):
if n==len(a):
return nQuote[0] == 0
if a[n] == '(':
nQuote[0] = nQuote[0] + 1
if a[n] == ')':
nQuote[0] = nQuote[0] - 1
if nQuote[0]<0:
return False
return check(a, nQuote, n+1)
这个可以过lz给的所有case，应该可以吧

r*h2012-12-24 08:12

27 楼

好几种括号的情况下，就要用stack存下前面出现过的左号({[，而不是仅仅用一个变量
来计数了
然后是漫长的match，不知道code可不可以简化的
def check(a, n, prev):
if n == len(a):
return len(prev) == 0

if a[n] == '{':
prev.append('{')
elif a[n] == '}':
if len(prev)!=0 and prev[len(prev)-1] == '{':
prev.pop()
else:
return False
elif a[n] == '[':
prev.append('[')
elif a[n] == ']':
if len(prev)!=0 and prev[len(prev)-1] == '[':
prev.pop()
else:
return False
elif a[n] == '(':
prev.append('(')
elif a[n] == ')':
if len(prev)!=0 and prev[len(prev)-1] == '(':
prev.pop()
else:
return False
return check(a, n+1, prev)
Test case:
prev = []
print("", check("", 0, prev))
prev = []
print("{a(()([]))}", check("{a(()([]))}", 0, prev))
prev = []
print("{(})", check("{(})", 0, prev))
prev = []
print("()[]{}", check("()[]{}", 0, prev))
prev = []
输出：
True
{a(()([]))} True
{(}) False
()[]{} True
[[}]]{ False

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

: 如果有好几种括号呢，要怎么做？
: { [(}] )

s*r2012-12-24 08:12

28 楼

这个是递归么？iteration用stack的我知道怎么做，但不会递归。

【在 r**h 的大作中提到】

:
: 好几种括号的情况下，就要用stack存下前面出现过的左号({[，而不是仅仅用一个变量
: 来计数了
: 然后是漫长的match，不知道code可不可以简化的
: def check(a, n, prev):
: if n == len(a):
: return len(prev) == 0
:
: if a[n] == '{':
: prev.append('{')

r*h2012-12-24 08:12

29 楼

这个明显是递归呀。。。
也正好说明了为啥尾部递归可以优化成循环。。。

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

: 这个是递归么？iteration用stack的我知道怎么做，但不会递归。

s*r2012-12-24 08:12

30 楼

额。。看到了。。。
开始没看明白，这是啥语言？

【在 r**h 的大作中提到】

: 这个明显是递归呀。。。
: 也正好说明了为啥尾部递归可以优化成循环。。。

r*h2012-12-24 08:12

31 楼

python
代码长度短，用来测试一些小算法挺合适的
不过python的各种container我用不来，也记不起来所有的API。。

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

: 额。。看到了。。。
: 开始没看明白，这是啥语言？

s*r2012-12-24 08:12

32 楼

貌似是对的，我读读。。。

【在 r**h 的大作中提到】

: python
: 代码长度短，用来测试一些小算法挺合适的
: 不过python的各种container我用不来，也记不起来所有的API。。

s*r2012-12-24 08:12

33 楼

这个好像真的和iteration是一个意思阿。。。

【在 r**h 的大作中提到】

: python
: 代码长度短，用来测试一些小算法挺合适的
: 不过python的各种container我用不来，也记不起来所有的API。。

e*e2012-12-24 08:12

34 楼

from Queue import LifoQueue
def matched(s, q=None):
if q == None:
q = LifoQueue()
if len(s) == 0:
return q.empty()
if s[0] == '(':
q.put('(')
elif s[0] == ')':
if q.empty():
return False
top = q.get()
if top == ')':
q.put(')')
q.put(')')
return matched(s[1:], q)

【在 d**********r 的大作中提到】

r*h2012-12-24 08:12

35 楼

return matched(s[1:], q)
这样的话不是每次会生成一个当前长度-1的临时变量吗？

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

: from Queue import LifoQueue
: def matched(s, q=None):
: if q == None:
: q = LifoQueue()
: if len(s) == 0:
: return q.empty()
: if s[0] == '(':
: q.put('(')
: elif s[0] == ')':
: if q.empty():

e*e2012-12-24 08:12

36 楼

Good question。在Python中，函数输入参数是by reference的，而且string作为函数
输入参数是immutable的，所以你可以把slice后的string作为函数输入参数而不在内存
新生成一个object并且保证这个string不被修改。

【在 r**h 的大作中提到】

: return matched(s[1:], q)
: 这样的话不是每次会生成一个当前长度-1的临时变量吗？

g*92012-12-24 08:12

37 楼

发个python的第一题试试：
def AllBracketsMatchedImpl(line, counter):
if len(line) == 0:
if counter == 0:
return True
else:
return False
#if
c = line[0]
if c == '(':
counter += 1
elif c == ')':
if counter == 0:
return False
counter -= 1
#if
return AllBracketsMatchedImpl(line[1:], counter)

def AllBracketsMatched(line):
counter = 0
return AllBracketsMatchedImpl(line, counter)

##line = '"()" yes'
##line = '")(" no'
##line = '"(a)(b)" yes'
##line = '"(abcd(e)" no'
line = ')('
print AllBracketsMatched(line)

a*a2012-12-24 08:12

38 楼

题目是说用递归取代循环，如果是多种括号的话，即使递归也得用stack吧。虽然递归
自己就有stack，但是这里左右括号的处理不同，右括号的话需要pop，所以我觉得还是
得用stack。
用java写了一下，欢迎指正
private boolean isValidHelper(String s, int cur, Stack stack) {
if (cur == s.length()) return stack.isEmpty();
char c = s.charAt(cur);
switch (c) {
case '(':
case '[':
case '{':
stack.push(c);
break;
case ')':
if (stack.isEmpty() || stack.pop() != '(') return false;
break;
case ']':
if (stack.isEmpty() || stack.pop() != '[') return false;
break;
case '}':
if (stack.isEmpty() || stack.pop() != '{') return false;
break;
}
return isValidHelper(s, cur+1, stack);
}

public boolean isValid(String s) {
Stack stack = new Stack();
return isValidHelper(s, 0, stack);
}

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

: stack我知道怎么做，如何不用stack，只用递归。