发一个Startup的面经 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

发一个Startup的面经

发一个Startup的面经# JobHunting - 待字闺中

a*i2015-04-20 07:04

1 楼

Recruiter主动联系的. 电面就挂了. 题目如下
有如下的表达式. add表示+, mult表示*
(add 1 2)
(mult 3 (add 2 3))
(let x 2 (mult x 5)
(let x 2 (mult x (let x 3 y 4 (add x y)))
计算表达式结果, 前两个返回3 和 15
第三个式子表示令x=2, 计算x * 5
第四个式子有两个赋值, x和y, 且在不同嵌套里有不同的赋值
给了三十分钟,要求编译通过. 我连parse表达式都没有写完... 另外let的情况如何处
理?

s*12015-04-20 07:04

2 楼

学haskell走遍天下都不怕的赶脚……
.net系的就去学f#吧……

n*a2015-04-20 07:04

3 楼

接到过他的OA 也是这个题

p*m2015-04-20 07:04

4 楼

三十分钟干这事还真有点紧张

【在 a*********i 的大作中提到】

: Recruiter主动联系的. 电面就挂了. 题目如下
: 有如下的表达式. add表示+, mult表示*
: (add 1 2)
: (mult 3 (add 2 3))
: (let x 2 (mult x 5)
: (let x 2 (mult x (let x 3 y 4 (add x y)))
: 计算表达式结果, 前两个返回3 和 15
: 第三个式子表示令x=2, 计算x * 5
: 第四个式子有两个赋值, x和y, 且在不同嵌套里有不同的赋值
: 给了三十分钟,要求编译通过. 我连parse表达式都没有写完... 另外let的情况如何处

b*52015-04-20 07:04

5 楼

看了看affirm，又是个傻逼类似lendingtree的公司。。。

【在 a*********i 的大作中提到】

b*02015-04-20 07:04

6 楼

用递归感觉还挺简单直接的先找括号对处理里面的内容然后用结果替换掉整个括号
临界条件没有括号对的时候空格分隔然后根据第一个字符串相应处理
let 就用一个key-value pair的链表如果没有特殊要求的话就够了
这个和计算表达式的要求感觉差不多吧

【在 a*********i 的大作中提到】

b*52015-04-20 07:04

7 楼

我觉得不用对parentheses处理吧，因为已经prefix了。。。
如果没有let的话，就是recursive， termination condition就是遇到 number就
return

【在 b********0 的大作中提到】

: 用递归感觉还挺简单直接的先找括号对处理里面的内容然后用结果替换掉整个括号
: 临界条件没有括号对的时候空格分隔然后根据第一个字符串相应处理
: let 就用一个key-value pair的链表如果没有特殊要求的话就够了
: 这个和计算表达式的要求感觉差不多吧

a*i2015-04-20 07:04

8 楼

同意. 面的时候用stack写的. 但是后来想想还是递归最简单

b*02015-04-20 07:04

9 楼

我的意思是嵌套的括号啊要优先处理内部的括号然后再处理当前表达式

【在 b**********5 的大作中提到】

: 我觉得不用对parentheses处理吧，因为已经prefix了。。。
: 如果没有let的话，就是recursive， termination condition就是遇到 number就
: return

f*d2015-04-20 07:04

10 楼

这公司看着不错

h*y2015-04-20 07:04

11 楼

recursion比较robust但是短时间内不好写. 因为你没有可以用的语法树，所以要花力
气来tokenize. 只有用Stack才有希望在规定时间里写完，虽然这样的程序完全没有用。
public class EvalExpression {
private Stack results = new Stack();
private Stack operators = new Stack();
private Stack> vars = new Stack>>();
private static final String ADD = "add";
private static final String MULT = "mult";
private static final String LET = "let";
private static final String LPAREN = "(";
private static final String RPAREN = ")";
public int calcExpression(String expr) {
String [] exprs = tokenizeExpr(expr);
for (int i = 0; i < exprs.length; i++) {
String token = exprs[i];
if (ADD.equals(token) || MULT.equals(token)) {
operators.push(token);
} else if (LET.equals(token)) {
operators.push(token);
Map map = new HashMap();
i++;
while (!LPAREN.equals(exprs[i])) {
map.put(exprs[i], Integer.valueOf(exprs[i + 1]));
i += 2;
}
vars.push(map);
} else if (LPAREN.equals(token)) {
continue;
}
else if (RPAREN.equals(token)) {
if (LET.equals(operators.peek())) {
operators.pop();
} else {
calcValue();
}
} else {
results.push(getValue(token));
}
}
return results.peek();
}
private void calcValue() {
int temp1 = results.pop();
int temp2 = results.pop();
String operation = operators.pop();
if (ADD.equals(operation)) {
results.push(temp1 + temp2);
}
if (MULT.equals(operation)) {
results.push(temp1 * temp2);
}
}
private int getValue(String token) {
if (token.matches("\d+")) {
return Integer.parseInt(token);
}
return searchTable(token);
}
private int searchTable(String token) {
return vars.peek().get(token);
}

【在 b********0 的大作中提到】

: 我的意思是嵌套的括号啊要优先处理内部的括号然后再处理当前表达式

l*k2015-04-20 07:04

12 楼

用一个hashtable 保持当前变量值（x,y,etc)，扫描的时候更新。
两个stack分别存变量和运算符。每次遇到非数字变量时从hashtable里替换存到变量
stack。
然后就好处理了。
当然，先得有个tokenizer和简单的parser。

x*42015-04-20 07:04

13 楼

import re
class Solution:
def evaluate(self, expr):
tokens = re.split('[ ()]', expr)
tokens = [token for token in tokens if token]
var, stack, i = {}, [], 0
keywords = set(['add', 'mult', 'let'])
while i < len(tokens):
if tokens[i] == 'add' or tokens[i] == 'mult':
stack.append(tokens[i])
i += 1
elif tokens[i] == 'let':
i += 1
while i < len(tokens) and tokens[i] not in keywords:
var[tokens[i]] = int(tokens[i+1])
i += 2
else:
if tokens[i].isdigit():
stack.append(int(tokens[i]))
else:
stack.append(var[tokens[i]])
while len(stack) > 2 and isinstance(stack[-1], int) and
isinstance(stack[-2], int):
num2, num1, op = stack.pop(), stack.pop(), stack.pop()
stack.append(self.compute(op, num1, num2))
i += 1
return stack[0]

def compute(self, op, num1, num2):
if op == 'add': return num1 + num2
if op == 'mult': return num1 * num2
sol = Solution()
exprs = {
'(add 1 2)': 3,
'(mult 3 (add 2 3))': 15,
'(let x 2 (mult x 5)': 10,
'(let x 2 (mult x (let x 3 y 4 (add x y)))': 14,
'(let a 2 (add a 2))': 4,
'(let a 2 (add a let b 3 (mult b 3)))': 11
}
for expr, val in exprs.items():
print(expr, val, sol.evaluate(expr))

j*y2015-04-20 07:04

14 楼

尼玛阿猫阿狗的公司都这么难。 CS 就和千老行业越来越近了。

p*22015-04-20 07:04

15 楼

lisp?

【在 a*********i 的大作中提到】

z*o2015-04-20 07:04

16 楼

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

: 尼玛阿猫阿狗的公司都这么难。 CS 就和千老行业越来越近了。

s*g2015-04-20 07:04

17 楼

用python写了下 30分钟完全搞不定啊最后倒是test case都没问题了用的stack 两个
要点一是push stack之前要查是不是let 是的话先update hashtable 然后push空串到
stack里面确保let先算
另一个是hashtable要对每次push存transaction 我是同步维护一个hashtable的stack
每次push 操作数的同时把当前hashtable的deepcopy也push了下次pop的时候也pop出
上一级存的hashtable来这样确保不同级的let赋值不会互相覆盖

【在 a*********i 的大作中提到】