LinkedIn 面试题讨论 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

LinkedIn 面试题讨论

LinkedIn 面试题讨论# JobHunting - 待字闺中

S*e2014-01-24 08:01

1 楼

就是那个nested array level sum 的问题
比如说： {1，2，{3，4}， {{5，6，7}，8} }
感觉这个还是要用linked list 的结构来存阿，或者是composite pattern.
大家有更好的思路马？

r*r2014-01-24 08:01

2 楼

Linked List好像不好，如果层数太多的话，很难声明。
composite pattern 可以做。
http://www.programcreek.com/2013/02/java-design-pattern-composi

m*n2014-01-24 08:01

3 楼

I wrote a java solution in another thread using iterator-ized (tail)
recursion:
http://www.mitbbs.com/article0/JobHunting/32585567_0.html
It is equivalent to the following python code:
def iterate(list):
for obj in list:
if isinstance(obj, int):
yield obj
else:
for sub_obj in iterate(obj):
yield sub_obj
def main():
list = [ 1, 2, [], 3, [ 4, 5 ], 6 ]
for i in iterate(list):
print i
print 'Done'

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

: 就是那个nested array level sum 的问题
: 比如说： {1，2，{3，4}， {{5，6，7}，8} }
: 感觉这个还是要用linked list 的结构来存阿，或者是composite pattern.
: 大家有更好的思路马？

g*g2014-01-24 08:01

4 楼

定义双重属性的结点
class Node
{
int v;
List subs;
}

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

M*A2014-01-24 08:01

5 楼

list of object, object can be Integer or List, recursion
import java.util.*;
public class NestedList {
public static void main(String[] args) {
List list = new ArrayList();
list.add(1);
list.add(2);
List sublist = new ArrayList();
sublist.add(3);
sublist.add(4);
list.add(sublist);
sublist = new ArrayList();
List sublist2 = new ArrayList();
sublist2.add(5);
sublist2.add(6);
sublist2.add(7);
sublist.add(sublist2);
sublist.add(8);
list.add(sublist);

int sum = new NestedList().sum(list);
System.out.println(sum);
}

public int sum(Object o) {
if (o instanceof Integer) return (int)o;
else if (o instanceof List) {
int sum = 0;
for (Object element : (List)o) {
sum += sum(element);
}
return sum;
}
return 0;
}
}

c*72014-01-24 08:01

6 楼

他面的时候会给你一个结构和一些现成的可调用的函数吧？给你的Input应该是个List<
ObjectWrapper>吧？

S*e2014-01-24 08:01

7 楼

这个题是班上看来的，所以问问，还没有面呢
谢谢大家啊！

List<

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

: 他面的时候会给你一个结构和一些现成的可调用的函数吧？给你的Input应该是个List<
: ObjectWrapper>吧？

y*u2014-01-24 08:01

8 楼

why not json like DataMap?

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

: 这个题是班上看来的，所以问问，还没有面呢
: 谢谢大家啊！
:
: List<

k*a2014-01-24 08:01

9 楼

难道不可以遇到一个括号深度加一，碰到一个数，就用当前深度乘以这个数，然后加到
结果里。遇到右括号深度减一，然后一直这样递归下去，知道扫描完一边，输出结果吗？
谢谢！

P*f2014-01-24 08:01

10 楼

昨天我也被问这个问题了

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

k*a2014-01-24 08:01

11 楼

这题目有哪个网站有online judgement吗

k*a2014-01-24 08:01

12 楼

linkedin电面是在collaedit上吗？那么就是不会编译通过咯？
那面试官怎么知道有没有bug,是不是真的是个workable solution呢?

l*a2014-01-24 08:01

13 楼

人家的输入不是String ah,弟弟

吗？

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

: 难道不可以遇到一个括号深度加一，碰到一个数，就用当前深度乘以这个数，然后加到
: 结果里。遇到右括号深度减一，然后一直这样递归下去，知道扫描完一边，输出结果吗？
: 谢谢！

z*b2014-01-24 08:01

14 楼

这题如果用c++的话，怎么表达{1，2，{3，4}， {{5，6，7}，8} }这个结构比较好呢？
用boost::any 吗？ list?

h*s2014-01-24 08:01

15 楼

这样可以吗？好像就是直接的DFS了。
public int getSum(List

f*t2014-01-24 08:01

16 楼

class Component {
public:
virtual char next() = 0;
virtual bool hasNext() = 0;
virtual void traverse() = 0;
};
class Leaf : public Component {
char val;
bool _hasNext;
public:
Leaf(char v) : val(v), _hasNext(true) { }
char next() {
_hasNext = false;
return val;
}
bool hasNext() {
return _hasNext;
}
void traverse() {
cout << val << ' ';
}
};
class Composite : public Component {
vector children;
size_t _idx = 0;
void goNext() {
while (_idx != children.size() && !children[_idx]->hasNext()) {
++_idx;
}
}
public:
void add(Component *ele) {
children.push_back(ele);
}
void traverse() {
for (auto c : children) {
c->traverse();
}
}
char next() {
char c = children[_idx]->next();
goNext();
return c;
}
bool hasNext() {
return _idx != children.size();
}
/*
class Iter {
vector::iterator cur;
Composite &co;
stack::iterator> sk;
public:
Iter(Composite &co) : co(co) {
cur = co.children.begin();
}
char next() {
if (cur == co.children.end()) {
return '#';
}
if (strcmp(typeid(*cur).name(), "Leaf") == 0) {
return (*cur)->val;
} else {
while (strcmp(typeid(*cur).name(), "Composite") == 0) {
sk.push(cur + 1);
cur = (*cur)->children.begin();
}
}
return true;
}
};*/
};
void CompositeTest() {
const char *s = "{0{12}3{4{56}}}";
Composite comp;
stack sk;
sk.push(&comp);
while (*s) {
if (*s == '{') {
Composite *co = new Composite();
sk.top()->add(co);
sk.push(co);
} else if (*s == '}') {
sk.pop();
} else {
sk.top()->add(new Leaf(*s));
}
++s;
}
cout << "traverse ";
comp.traverse();
cout << endl << "iterator ";
while (comp.hasNext()) {
cout << comp.next();
}
cout << endl;
}