狗狗家onsite面经 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

狗狗家onsite面经

狗狗家onsite面经# JobHunting - 待字闺中

b*u2013-05-29 07:05

1 楼

离婚的时候，保护自己的财产很正常。版上人凭什么骂他！他挣钱很容易吗？有张一功
劳吗？自己血汗
付出的，就应该合理保护

c*y2013-05-29 07:05

2 楼

1)给的一个double linkedlist，给定一个array，包含若干double linkedlist的节点
的地址，统计这个array包含的互相独立部分的数目。用例子说明吧。
一个double linkedlist是A<>B<>C<>...<>X<>Y<>Z（一共26个节点，从A到Z）。
如果array是{A，Z}，那个return 2，因为A和Z两个不相邻的。
如果array是{A，B，D}，那个return 2，因为AB是一个部分，D是另外一个独立的部分。
如果array是{A，B，C，。。。，Y，Z}，那么return 1，因为AtoZ是一个独立的部分。
2)从给定的sorted的array如何build的一个balanced的binary tree？
开始给了一个recursive的方法，后来要一个iterative。
iterative的解法：
a.先建立一个空的balanced binary tree
建立这个空的balanced binary tree的方法可以参见如何用array来表示一个heap的方
法。具体是对于节点i，它的left和right child可以是节点2*i和2*i+1。这里i必须是
从1开始的，不能是0，所以不能直接用array中元素的idx。
b.然后traverse这个空的binary tree，把sorted array的值一个一个拷贝进去。
for (TreeNode *node = minBST(root); node != NULL; node = successorBST(node))
{
node->value = sortedArray[i++];
}
3)reservoir sampling的题。一个无限长的数组，一个buffer有K个cells，如何scan这
个数组一次，并且以相同概率采样K个元素到这个buffer里。

r*k2013-05-29 07:05

3 楼

同意。

r*e2013-05-29 07:05

4 楼

第1题跟那个找数列最长连续子序列一样把
把array所有元素都放进hashset
对每一个元素，如果在hashset里，往左扫，往右扫，把遇到的元素都从hashset里删掉
扫完了计数器加一

分。
))

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

: 1)给的一个double linkedlist，给定一个array，包含若干double linkedlist的节点
: 的地址，统计这个array包含的互相独立部分的数目。用例子说明吧。
: 一个double linkedlist是A<>B<>C<>...<>X<>Y<>Z（一共26个节点，从A到Z）。
: 如果array是{A，Z}，那个return 2，因为A和Z两个不相邻的。
: 如果array是{A，B，D}，那个return 2，因为AB是一个部分，D是另外一个独立的部分。
: 如果array是{A，B，C，。。。，Y，Z}，那么return 1，因为AtoZ是一个独立的部分。
: 2)从给定的sorted的array如何build的一个balanced的binary tree？
: 开始给了一个recursive的方法，后来要一个iterative。
: iterative的解法：
: a.先建立一个空的balanced binary tree

u*w2013-05-29 07:05

5 楼

什么gp逻辑。
正常的东西就是合理合法拉？

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

: 离婚的时候，保护自己的财产很正常。版上人凭什么骂他！他挣钱很容易吗？有张一功
: 劳吗？自己血汗
: 付出的，就应该合理保护

r*h2013-05-29 07:05

6 楼

我觉得第一题从左往右扫一轮就行了

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

: 第1题跟那个找数列最长连续子序列一样把
: 把array所有元素都放进hashset
: 对每一个元素，如果在hashset里，往左扫，往右扫，把遇到的元素都从hashset里删掉
: 扫完了计数器加一
:
: 分。
: ))

m*n2013-05-29 07:05

7 楼

马林又是干吗的？

w*o2013-05-29 07:05

8 楼

第一輪，可不可以直接用strongly connected components 來。

R*n2013-05-29 07:05

9 楼

那你结婚干嘛，结婚之前就公证啊，婚后搞什么

r*e2013-05-29 07:05

10 楼

不要被给的例子误导了
array里面的指针不一定按照list order来

删掉

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

: 我觉得第一题从左往右扫一轮就行了

t*o2013-05-29 07:05

11 楼

赞这逻辑。
LZ跟马琳是什么关系啊，两天发了这么多顶他的帖子。

s*x2013-05-29 07:05

12 楼

如果给的array是sorted的话，yes
不是的话，sort要nlogn，用hash 是linear

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

: 我觉得第一题从左往右扫一轮就行了

f*y2013-05-29 07:05

13 楼

亲友团

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

: 赞这逻辑。
: LZ跟马琳是什么关系啊，两天发了这么多顶他的帖子。

r*h2013-05-29 07:05

14 楼

嗯。。。是我搞错了
不过题目要求的是双向链表中相邻的元素在array中也相邻，还是说只是看链表中所有
被array映射到的节点分成几个连续子段呢？
{A, B, Z, C, D}算2还是3

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

: 不要被给的例子误导了
: array里面的指针不一定按照list order来
:
: 删掉

s*c2013-05-29 07:05

15 楼

楼主就是马琳吗？怎么这么激动，发这么多挺马琳的帖子，呵呵。就是mitbbs上大家都
被你感动了，都去支持马琳，那又能怎么样，他该被分走多少财产，由国家法院判了算
。

B*L2013-05-29 07:05

16 楼

哪个组的面试啊？

t*y2013-05-29 07:05

17 楼

发信人: bobohu (bobohu), 信区: Medicine
标题: 我这些不开心的心理状态正常吗
发信站: BBS 未名空间站 (Thu Jan 28 10:36:21 2010, 美东)
可能就象有些人说的，我心理有创伤
我病过，甲亢。然后变的暴丑，然后自信没了，然后行为发生了变化，然后在很多场合
下不知道怎么说话做事了，然后很多人欺负我，甚至我的亲戚都骂我，在公开场合羞辱
我，有时面带笑容的损我，有时指着我的鼻子骂我。
我忘不了。。。。我有时恨，有时难过
我没有自信，不会发泄愤怒，又觉得如果发泄愤怒，让他们发现我气了，他们更高兴，
因为那样他们得逞了。
然后，我的一些委屈憋在心理。然后，５，６年过去了。我好了，心理却放不下从前的
东西了。
有个医生建议我做EMDR，不知道有没有用？
我这些不开心的心理状态正常吗？

s*x2013-05-29 07:05

18 楼

2吧
class CharNode {
private char value;
private CharNode next;
private CharNode previous;
public CharNode getPrevious() {
return previous;
}
public void setPrevious(CharNode previous) {
this.previous = previous;
}
public char getValue() {
return value;
}
public void setValue(char value) {
this.value = value;
}
public CharNode getNext() {
return next;
}
public void setNext(CharNode next) {
this.next = next;
}
}
public static int findHowManyContinousIntervalInArray(CharNode listRoot,
char[] array)
{
// Key is char, value is the index of the group count
Map map = new HashMap();
for (char a : array)
{
map.put(a, 0);
}

int count = 0;
for (CharNode n = listRoot; n != null; n = n.getNext())
{
char key = n.getValue();
if (map.containsKey(key))
{
CharNode prev = n.getPrevious();
if (prev != null && map.containsKey(prev.getValue()) && map.
get(prev.getValue()) != 0)
{
map.put(key, map.get(prev.getValue())); // use previous
char's group index
continue;
}

CharNode next = n.getNext();
if (next != null && map.containsKey(next.getValue()) && map.
get(next.getValue()) != 0)
{
map.put(key, map.get(next.getValue())); // use next char
's group index
continue;
}

map.put(key, ++count);
}
}
return count;
}
public static void main(String[] args) {
CharNode root = new CharNode();
root.setValue('A');
CharNode prev = root;
for(int i = 1; i < 26; i++)
{
CharNode n = new CharNode();
n.setValue((char)('A' + i));
prev.setNext(n);
n.setPrevious(prev);
prev = n;
}

char[] a = new char[] {'A', 'B', 'Z', 'C', 'D' };
int c = findHowManyContinousIntervalInArray(root, a);
System.out.print(c);
}

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

: 嗯。。。是我搞错了
: 不过题目要求的是双向链表中相邻的元素在array中也相邻，还是说只是看链表中所有
: 被array映射到的节点分成几个连续子段呢？
: {A, B, Z, C, D}算2还是3

S*12013-05-29 07:05

19 楼

马林语文肯定没楼主好

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

: 楼主就是马琳吗？怎么这么激动，发这么多挺马琳的帖子，呵呵。就是mitbbs上大家都
: 被你感动了，都去支持马琳，那又能怎么样，他该被分走多少财产，由国家法院判了算
: 。

h*a2013-05-29 07:05

20 楼

2）iteratively的建一个空树和原问题一个难度吧。你能把你的code show show么？感
觉如果硬要去掉递归，还不如用个栈来机械的模拟递归。

分。

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

k*12013-05-29 07:05

21 楼

我觉得无论男女
离婚的时候都不能要求他分出自己辛辛苦苦挣来的一半财产去，如果他没有做对不起对
方的事情的话。

p*22013-05-29 07:05

22 楼

简单点用个queue就行了吧？

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

: 2）iteratively的建一个空树和原问题一个难度吧。你能把你的code show show么？感
: 觉如果硬要去掉递归，还不如用个栈来机械的模拟递归。
:
: 分。

L*e2013-05-29 07:05

23 楼

lz如果不是马琳的亲戚，建议还是看医生，病得不轻

p*22013-05-29 07:05

24 楼

这个说的不错。我也被误导了。这样的话，你的解法应该可以。

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

: 不要被给的例子误导了
: array里面的指针不一定按照list order来
:
: 删掉

I*92013-05-29 07:05

25 楼

各种大妈

h*a2013-05-29 07:05

26 楼

Not obvious to me. Can you post the code?

【在 p*****2 的大作中提到】

:
: 这个说的不错。我也被误导了。这样的话，你的解法应该可以。

s*x2013-05-29 07:05

27 楼

大概是这个思路吧，没有测
public static TreeNode sortedArrayToBST(int[] a)
{
TreeNode root = new TreeNode();
int left = 0, right = a.length - 1;
Queue indexes = new LinkedList();
Queue nodes = new LinkedList();
nodes.add(root);
indexes.add(left);
indexes.add(right);
while (!indexes.isEmpty())
{
left = indexes.poll();
right = indexes.poll();
TreeNode p = nodes.poll();
int mid = left + (right - left) >>> 1;
p.setValue(a[mid]);
TreeNode leftChild = null, rightChild = null;
if (left <= mid - 1)
{
leftChild = new TreeNode();
indexes.add(left);
indexes.add(mid - 1);
nodes.add(leftChild);
}
if (mid + 1 < right)
{
rightChild = new TreeNode();
indexes.add(mid+1);
indexes.add(right);
nodes.add(rightChild);
}
p.setLeft(leftChild);
p.setRight(rightChild);
}
return root;
}【在 halfsea (tough) 的大作中提到: 】

a*e2013-05-29 07:05

28 楼

既然是2，那这个数组{A,B,Z,C,D}就跟{A,B,C,D,Z}一样喽？
那从左到右扫一遍可以么？

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

: 2吧
: class CharNode {
: private char value;
: private CharNode next;
: private CharNode previous;
: public CharNode getPrevious() {
: return previous;
: }
: public void setPrevious(CharNode previous) {
: this.previous = previous;

r*h2013-05-29 07:05

29 楼

数组存的是链表节点的地址啊，没办法sort
除非你额外做一个hash之类把链表节点的地址映射成该节点在链表中的位置

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

: 既然是2，那这个数组{A,B,Z,C,D}就跟{A,B,C,D,Z}一样喽？
: 那从左到右扫一遍可以么？

c*y2013-05-29 07:05

30 楼

{A, B, Z, C, D}是算2
解法：用一个HashTable来记录array中已经被处理过的元素（即地址(pointer)）。每
次处理一个新的元素，把这个地址加入HashTable。
每次处理一个array里新的地址（元素），看看这个地址是不是已经HashTable里了，如
果是的话，就不更新count，因为已经处理过了。直接跳过。
如果不在HashTable中，根据这个地址，找到相应元素的两个neighbor（还是地址，有
可能为空）。
如果两个neighbor都不空而且不在HashTable中，count加1，因为是一个新的独立部分。
如果有只有一个neighbor在HashTable中的话，count不变，因为这个新的地址的节点属
于已经处理的独立部分中的一个。
如果两个neighbor都在的话，count减1，因为这个地址的元素可以把原来两个独立的部
分连接成一个（即merge）。
处理完这个元素e.g.地址，把这个地址加进HashTable中。
这样只要scan这个array一次，用一个HashTable。算法复杂度是O(m)，m是array中地址
的个数。
另一种解法是scan这个double linkedlist（楼上提到过了），也可以用hashtable来存
储是否在array中的记录。因为每个节点访问一次，所以是0(n)，n是list中节点的数目。

c*y2013-05-29 07:05

31 楼

可以用如下方法建立一个空的balanced的binary tree，复杂度是O(n)，n是给定sorted
array中元素的个数。TreeNode的定义可以参照leetcode上的binary tree的定义。如
果方便后面步骤的traversal，需要加入一个parent指针元素在TreeNode的定义中。
TreeNode **pp_node = (TreeNode **)malloc(n * sizeof(TreeNode *));
for (int i = 0; i < n; i++) {
pp_node[i] = new TreeNode(0);
}
// build a balanaced binary tree by linking them
for (int i = 1; i <= n; i++) {
if (2 * i <= n) {
// link left child node
pp_node[i - 1]->left = pp_node[2 * i - 1];
// link back to parent node
pp_node[2 * i - 1]->parent = pp_node[i - 1];
}
if (2 * i + 1 <= n) {
// linlke right child node
pp_node[i - 1]->right = pp_node[2 * i + 1 - 1];
// link back to parent node
pp_node[2 * i + 1 - 1]->parent = pp_node[i - 1];
}
}
pp_node[0]指向这个空树的root

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

: 2）iteratively的建一个空树和原问题一个难度吧。你能把你的code show show么？感
: 觉如果硬要去掉递归，还不如用个栈来机械的模拟递归。
:
: 分。

q*s2013-05-29 07:05

32 楼

第三题是错的，怎么可能uniformly sampling from infinitely many discrete set.

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

c*y2013-05-29 07:05

33 楼

改了说明。

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

: 第三题是错的，怎么可能uniformly sampling from infinitely many discrete set.

a*e2013-05-29 07:05

34 楼

这个方法很漂亮啊。

sorted

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

: 可以用如下方法建立一个空的balanced的binary tree，复杂度是O(n)，n是给定sorted
: array中元素的个数。TreeNode的定义可以参照leetcode上的binary tree的定义。如
: 果方便后面步骤的traversal，需要加入一个parent指针元素在TreeNode的定义中。
: TreeNode **pp_node = (TreeNode **)malloc(n * sizeof(TreeNode *));
: for (int i = 0; i < n; i++) {
: pp_node[i] = new TreeNode(0);
: }
: // build a balanaced binary tree by linking them
: for (int i = 1; i <= n; i++) {
: if (2 * i <= n) {

a*e2013-05-29 07:05

35 楼

开始只是想到了O(n)的算法。 O(m)的算法可以这么实现
#include
#include
using namespace std;
struct DListNode {
char val;
DListNode *prev;
DListNode * next;
DListNode(char v): val(v), prev(nullptr), next(nullptr) {}
};
void printList(DListNode* head){
while (head!=nullptr) {
cout<val<head = head->next;
}
cout<}
void printSet(unordered_set &s) {
for (auto iter=s.begin(); iter!=s.end(); ++iter)
cout<val<cout<}
// 这个函数每次把s中第一个元素所在的connected component所含元素从s中删除。
// 这样s中的connected component数量减少1.
void explore(unordered_set &s) {
DListNode* prev = *(s.begin());
DListNode* next = prev;
s.erase(prev);
while (prev!=nullptr) {
if (s.find(prev->prev)!=s.end()) {
prev = prev->prev;
s.erase(prev);
} else {
prev = nullptr;
}
}
while (next!=nullptr) {
if (s.find(next->next)!=s.end()) {
next = next->next;
s.erase(next);
} else {
next = nullptr;
}
}
}
int numOfConnectedComponent(DListNode *head, unordered_set &s) {
int count = 0;
while (!s.empty()) {
explore(s);
++count;
}
return count;
}
int main()
{
DListNode *head = new DListNode('A');
DListNode *prev = head;
unordered_set set_ptr;
for (int i=1; i<26; ++i) {
DListNode *new_n = new DListNode(i+'A');
new_n->prev = prev;
prev->next = new_n;
prev = prev->next;
if (rand()%100<60) set_ptr.insert(prev);
}

printList(head);
printSet(set_ptr);
cout<set_ptr)<return 0;
}

分。

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

: {A, B, Z, C, D}是算2
: 解法：用一个HashTable来记录array中已经被处理过的元素（即地址(pointer)）。每
: 次处理一个新的元素，把这个地址加入HashTable。
: 每次处理一个array里新的地址（元素），看看这个地址是不是已经HashTable里了，如
: 果是的话，就不更新count，因为已经处理过了。直接跳过。
: 如果不在HashTable中，根据这个地址，找到相应元素的两个neighbor（还是地址，有
: 可能为空）。
: 如果两个neighbor都不空而且不在HashTable中，count加1，因为是一个新的独立部分。
: 如果有只有一个neighbor在HashTable中的话，count不变，因为这个新的地址的节点属
: 于已经处理的独立部分中的一个。

q*s2013-05-29 07:05

36 楼

有放回的话，(m-1)/m 选之前的数，1/m选新数m.

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

: 改了说明。

h*a2013-05-29 07:05

37 楼

不错，不过值得注意的是这样build的tree和递归建的树形状可能是不同的。但都是
balanced。
public TreeNode buildIteratively(int[] a) {
int n = a.length;
TreeNode root = createTreeOfN(n);
Stack s = new Stack();
TreeNode cur = root;
int i=0;
while (cur != null || !s.isEmpty()) {
if (cur == null) {
cur = s.pop();
cur.val = a[i++];
cur = cur.right;
} else {
s.push(cur);
cur = cur.left;
}
}
return root;
}
private TreeNode createTreeOfN(int n) {
if (n==0) return null;
TreeNode[] nodes = new TreeNode[n];
for (int i=n-1; i>=0; i--) {
nodes[i] = new TreeNode(0);
if (i*2+1 < n) {
nodes[i].left = nodes[i*2+1];
}
if (i*2+2 < n) {
nodes[i].right = nodes[i*2+2];
}
}
return nodes[0];
}

sorted

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