l*******s
发帖数: 1258 | 1 上周电面Twitter，挂。贡献题目，攒rp。
大约45分钟，那哥们上来就说开始做题，打开一个类似google doc的网站。连互相介绍
寒暄都没有。我怀疑是急着下班去过长周末。
题目不难，我发挥的太烂。
1.描述一下HashMap和TreeMap的区别。
2.实现一个TreeMap里的get(K key)方法，自己定义树的node，最好用java。我写了个
BST的get方法，就是简单的比较根节点然后递归左右子树那个，他说差不多。其实当时
觉得应该用红黑树，只是实现起来太麻烦，就没写。
3.如何防止这个TreeMap里的get，insert，delete等方法多线程调用时出现数据读写出
乱子？答曰用synchronized关键字。然后让直接写到第二题的code中。
4.加synchronnized之后，会有什么不好的影响。答曰会降低concurrence性能。
下午4点面的，晚上9他们给打电话，我当时在外面玩，没听到。三天后接到email，说
是挂了。
总结一下，估计最大的问题还是在coding上。犯了俩语法错误。有个别条件可能写的也
不大严谨。今后要加强练习。老用Eclipse，有些基本语法都不注意了。实在是发挥失
常，一年多没面试了，不在状态，准备不充分。以后要多多白板coding。 |
w****a
发帖数: 710 | |
m******s
发帖数: 21 | |
l*******s
发帖数: 1258 | 4 应该没啥问题。
当初跟recruiter谈的时候，说是他们主要用java和python
但是面试时，会让你用最熟悉的语言，并没有规定必须java。
【在 m******s 的大作中提到】
: 只要Java？其他语言的他们招吗？
|
j*****y
发帖数: 1071 | 5 面你的人是老印吗？
【在 l*******s 的大作中提到】
: 上周电面Twitter，挂。贡献题目，攒rp。
: 大约45分钟，那哥们上来就说开始做题，打开一个类似google doc的网站。连互相介绍
: 寒暄都没有。我怀疑是急着下班去过长周末。
: 题目不难，我发挥的太烂。
: 1.描述一下HashMap和TreeMap的区别。
: 2.实现一个TreeMap里的get(K key)方法，自己定义树的node，最好用java。我写了个
: BST的get方法，就是简单的比较根节点然后递归左右子树那个，他说差不多。其实当时
: 觉得应该用红黑树，只是实现起来太麻烦，就没写。
: 3.如何防止这个TreeMap里的get，insert，delete等方法多线程调用时出现数据读写出
: 乱子？答曰用synchronized关键字。然后让直接写到第二题的code中。
|
l*******s
发帖数: 1258 | 6 应该不是 听说话没有口音 应该是个native speaker
但是不知道叫啥名字 所以也无从判断是啥人。
我本来想跟人家寒暄两句自我介绍下，没想到直接不给我机会说，上来就做题。
【在 j*****y 的大作中提到】
: 面你的人是老印吗？
|
w****x
发帖数: 2483 | 7
太好了，看了我这一个多星期还没消息的可能还有戏
【在 l*******s 的大作中提到】
: 上周电面Twitter，挂。贡献题目，攒rp。
: 大约45分钟，那哥们上来就说开始做题，打开一个类似google doc的网站。连互相介绍
: 寒暄都没有。我怀疑是急着下班去过长周末。
: 题目不难，我发挥的太烂。
: 1.描述一下HashMap和TreeMap的区别。
: 2.实现一个TreeMap里的get(K key)方法，自己定义树的node，最好用java。我写了个
: BST的get方法，就是简单的比较根节点然后递归左右子树那个，他说差不多。其实当时
: 觉得应该用红黑树，只是实现起来太麻烦，就没写。
: 3.如何防止这个TreeMap里的get，insert，delete等方法多线程调用时出现数据读写出
: 乱子？答曰用synchronized关键字。然后让直接写到第二题的code中。
|
P******r
发帖数: 842 | |
l*******s
发帖数: 1258 | 9 他们的recruiter找的我
【在 P******r 的大作中提到】
: twitter大家咋投的简历？
|
p**o
发帖数: 1012 | 10 估计同电面悲剧的握手，贡献个题目
1。找anagram,这个题据说是练手的，本来应该一口气写出来的常见题目，想了10分钟
2.合并两个BST，也写出来了
45分钟只短不长，上来二话不说直接coding，交流不多，也没问对方提示，对方应该印
度人。虽然都做出来了，但是由于写的不够顺，而且第一题他只说是warmup的，我不知
道后面是不是还有第三题，总之，觉得对方对我感觉不太好，而且题目也太简单，应该
是悲剧了 |
|
|
w****x
发帖数: 2483 | 11
你这都杯具了我就没救了, 你啥时候面的， 咋没回复啊？
【在 p**o 的大作中提到】
: 估计同电面悲剧的握手，贡献个题目
: 1。找anagram,这个题据说是练手的，本来应该一口气写出来的常见题目，想了10分钟
: 2.合并两个BST，也写出来了
: 45分钟只短不长，上来二话不说直接coding，交流不多，也没问对方提示，对方应该印
: 度人。虽然都做出来了，但是由于写的不够顺，而且第一题他只说是warmup的，我不知
: 道后面是不是还有第三题，总之，觉得对方对我感觉不太好，而且题目也太简单，应该
: 是悲剧了
|
w****x
发帖数: 2483 | 12
刚收到邮件， 可以onsite了， 8天后回复的， 千万别挂了~~
【在 p**o 的大作中提到】
: 估计同电面悲剧的握手，贡献个题目
: 1。找anagram,这个题据说是练手的，本来应该一口气写出来的常见题目，想了10分钟
: 2.合并两个BST，也写出来了
: 45分钟只短不长，上来二话不说直接coding，交流不多，也没问对方提示，对方应该印
: 度人。虽然都做出来了，但是由于写的不够顺，而且第一题他只说是warmup的，我不知
: 道后面是不是还有第三题，总之，觉得对方对我感觉不太好，而且题目也太简单，应该
: 是悲剧了
|
p*****2
发帖数: 21240 | 13
难道它家不是用ruby和scala？
【在 l*******s 的大作中提到】
: 应该没啥问题。
: 当初跟recruiter谈的时候，说是他们主要用java和python
: 但是面试时，会让你用最熟悉的语言，并没有规定必须java。
|
p**o
发帖数: 1012 | 14 今天面的，不算顺利，对方明显在忙别的事情，和我说了anagram就让写，我纠结了很
久anagram是什么，还问了他，我觉得都写了，但是也不一定都对，觉得思路上没什么
问题吧。
第一个就是把每个单词sort,sort了之后再去hashset map
第二个就是把BST的数值read下来，然后一merge两个array,然后重建BST
复杂度也都说了下，我的background是做java backend的一些玩意的
【在 w****x 的大作中提到】
:
: 刚收到邮件， 可以onsite了， 8天后回复的， 千万别挂了~~
|
w****x
发帖数: 2483 | 15
没关系吧，你都做了两题了， 我两个back to back phone interview, 每个才做了一
题
【在 p**o 的大作中提到】
: 今天面的，不算顺利，对方明显在忙别的事情，和我说了anagram就让写，我纠结了很
: 久anagram是什么，还问了他，我觉得都写了，但是也不一定都对，觉得思路上没什么
: 问题吧。
: 第一个就是把每个单词sort,sort了之后再去hashset map
: 第二个就是把BST的数值read下来，然后一merge两个array,然后重建BST
: 复杂度也都说了下，我的background是做java backend的一些玩意的
|
p*****2
发帖数: 21240 | 16
太牛了。膜拜呀。
【在 w****x 的大作中提到】
:
: 没关系吧，你都做了两题了， 我两个back to back phone interview, 每个才做了一
: 题
|
l*****a
发帖数: 14598 | 17 存下了，谢谢LZ share
【在 l*******s 的大作中提到】
: 上周电面Twitter，挂。贡献题目，攒rp。
: 大约45分钟，那哥们上来就说开始做题，打开一个类似google doc的网站。连互相介绍
: 寒暄都没有。我怀疑是急着下班去过长周末。
: 题目不难，我发挥的太烂。
: 1.描述一下HashMap和TreeMap的区别。
: 2.实现一个TreeMap里的get(K key)方法，自己定义树的node，最好用java。我写了个
: BST的get方法，就是简单的比较根节点然后递归左右子树那个，他说差不多。其实当时
: 觉得应该用红黑树，只是实现起来太麻烦，就没写。
: 3.如何防止这个TreeMap里的get，insert，delete等方法多线程调用时出现数据读写出
: 乱子？答曰用synchronized关键字。然后让直接写到第二题的code中。
|
l*****a
发帖数: 14598 | 18 为什么千万别？
那里bar很高的
【在 w****x 的大作中提到】
:
: 没关系吧，你都做了两题了， 我两个back to back phone interview, 每个才做了一
: 题
|
l*****a
发帖数: 14598 | 19 第二题用了额外空间，显然不是最优吧
【在 p**o 的大作中提到】
: 今天面的，不算顺利，对方明显在忙别的事情，和我说了anagram就让写，我纠结了很
: 久anagram是什么，还问了他，我觉得都写了，但是也不一定都对，觉得思路上没什么
: 问题吧。
: 第一个就是把每个单词sort,sort了之后再去hashset map
: 第二个就是把BST的数值read下来，然后一merge两个array,然后重建BST
: 复杂度也都说了下，我的background是做java backend的一些玩意的
|
w****x
发帖数: 2483 | 20
如果不用额外空间编程时间肯定不够。
【在 l*****a 的大作中提到】
: 第二题用了额外空间，显然不是最优吧
|
|
|
l*****a
发帖数: 14598 | 21 至少也要说一下较优算法吧。
纯暴力的话对付这种牛公司恐怕不成
【在 w****x 的大作中提到】
:
: 如果不用额外空间编程时间肯定不够。
|
w****x
发帖数: 2483 | 22
写一个
//Merge two BST
//O(n) solution
//1. Change BST into linked list
//2. Merge 2 linked lists
//3. Change linked list into a balanced BST
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
////////////////////change BST to linked list///////////////////////////////
void _inner_chng_link(NODE* pNode, NODE*& ph, NODE*& pt)
{
if (NULL == pNode) return;
NODE* pLft1 = pNode;
NODE* pLft2 = pNode;
_inner_chng_link(pNode->pLft, pLft1, pLft2);
if (pNode != pLft2) //forget this link logic
{
pNode->pLft = pLft2;
pLft2->pRgt = pNode;
}
NODE* pRgt1 = pNode;
NODE* pRgt2 = pNode;
_inner_chng_link(pNode->pRgt, pRgt1, pRgt2);
if (pNode != pRgt1) //forget this link logic
{
pRgt1->pLft = pNode;
pNode->pRgt = pRgt1;
}
ph = pLft1;
pt = pRgt2;
}
NODE* ChngToLink(NODE* pRoot)
{
assert(pRoot);
NODE* ph = pRoot;
NODE* pt = pRoot;
_inner_chng_link(pRoot, ph, pt);
return ph;
}
//////////////////////////////////////////////////////////////////////////
///////////////////Merge 2 linked lists/////////////////////////////////
NODE* MergeLink(NODE* pHead1, NODE* pHead2)
{
assert(pHead1 && pHead2);
NODE* pNewHead = NULL;
NODE* pIter = NULL;
NODE* pIter1 = pHead1;
NODE* pIter2 = pHead2;
while (pIter1 != NULL && pIter2 != NULL)
{
NODE* pTmp = NULL;
if (pIter1->nVal <= pIter2->nVal)
{
pTmp = pIter1;
pIter1 = pIter1->pRgt;
}
else
{
pTmp = pIter2;
pIter2 = pIter2->pRgt;
}
if (pIter == NULL)
{
pNewHead = pTmp;
pIter = pTmp;
}
else
{
pIter->pRgt = pTmp;
pTmp->pLft = pIter;
pIter = pIter->pRgt;
}
}
if (pIter1 != NULL)
{
pIter->pRgt = pIter1;
pIter1->pLft = pIter;
}
if (pIter2 != NULL)
{
pIter->pRgt = pIter2;
pIter2->pLft = pIter;
}
return pNewHead;
}
//////////////////////////////////////////////////////////////////////////
////////////////Construct BST from linked list/////////////////////////////
NODE* _inner_construct(NODE* pHead, int nLen)
{
if (NULL == pHead || nLen <= 0)
return NULL;
NODE* pNode = pHead;
int nCount = (nLen + 1)/2;
for (int i = 1; i < nCount; i++)
pNode = pNode->pRgt;
pNode->pLft = _inner_construct(pHead, (nLen + 1)/2 - 1);
pNode->pRgt = _inner_construct(pNode->pRgt, nLen - (nLen + 1)/2);
return pNode;
}
NODE* ConstructBST(NODE* pHead)
{
assert(pHead);
int nLen = 0;
NODE* pIter = pHead;
while (pIter != NULL)
{
nLen++;
pIter = pIter->pRgt;
}
return _inner_construct(pHead, nLen);
}
//////////////////////////////////////////////////////////////////////////
NODE* MergeBST(NODE* pRoot1, NODE* pRoot2)
{
assert(pRoot1 && pRoot2);
NODE* ph1 = ChngToLink(pRoot1);
NODE* ph2 = ChngToLink(pRoot2);
NODE* ph = MergeLink(ph1, ph2);
return ConstructBST(ph);
}
【在 l*****a 的大作中提到】
: 至少也要说一下较优算法吧。
: 纯暴力的话对付这种牛公司恐怕不成
|
l*****a
发帖数: 14598 | 23 你的比较怎么写的？K/V type固定吗？
为什么recursion直接比下去好了
【在 l*******s 的大作中提到】
: 上周电面Twitter，挂。贡献题目，攒rp。
: 大约45分钟，那哥们上来就说开始做题，打开一个类似google doc的网站。连互相介绍
: 寒暄都没有。我怀疑是急着下班去过长周末。
: 题目不难，我发挥的太烂。
: 1.描述一下HashMap和TreeMap的区别。
: 2.实现一个TreeMap里的get(K key)方法，自己定义树的node，最好用java。我写了个
: BST的get方法，就是简单的比较根节点然后递归左右子树那个，他说差不多。其实当时
: 觉得应该用红黑树，只是实现起来太麻烦，就没写。
: 3.如何防止这个TreeMap里的get，insert，delete等方法多线程调用时出现数据读写出
: 乱子？答曰用synchronized关键字。然后让直接写到第二题的code中。
|
p**o
发帖数: 1012 | 24 额外空间也就是一个int的array，不用写着有点晕啊，10多分钟
【在 l*****a 的大作中提到】
: 第二题用了额外空间，显然不是最优吧
|
w****x
发帖数: 2483 | 25
额外空间的也不是很简单的，怎么也得写2个函数
【在 p**o 的大作中提到】
: 额外空间也就是一个int的array，不用写着有点晕啊，10多分钟
|
l*****a
发帖数: 14598 | 26 一棵树 做 in-order traverse
然后每次插入可以吗？
【在 w****x 的大作中提到】
:
: 额外空间的也不是很简单的，怎么也得写2个函数
|
p**o
发帖数: 1012 | 27 函数和你分得差不多，不过我是Java,所以code短的多。本来也不想去，所以裸面的，
一直也没做过题，所以我的水平必然很抱歉。面一下就当娱乐了，我这么差，刚好给别
人多个机会。 |
p**o
发帖数: 1012 | 28 think about your complexity?
Is insertion to a BST O(1) or O(lg n)?
【在 l*****a 的大作中提到】
: 一棵树 做 in-order traverse
: 然后每次插入可以吗？
|
l*****a
发帖数: 14598 | 29 lg(n)吧。
【在 p**o 的大作中提到】
: think about your complexity?
: Is insertion to a BST O(1) or O(lg n)?
|
p**o
发帖数: 1012 | 30 But if you keep the current position, I am not sure whether you can do O(n).
The question also require the new BST to be balance.
【在 l*****a 的大作中提到】
: 一棵树 做 in-order traverse
: 然后每次插入可以吗？
|
|
|
w****x
发帖数: 2483 | 31
要写个平衡的算法另可些那个没有额外空间的算法
【在 l*****a 的大作中提到】
: lg(n)吧。
|
p**o
发帖数: 1012 | 32 If it is O(lgn), you complexity is O(nlgn), but ours is O(n)
【在 l*****a 的大作中提到】
: lg(n)吧。
|
l*****a
发帖数: 14598 | 33 中文太差，看不懂：（
【在 w****x 的大作中提到】
:
: 要写个平衡的算法另可些那个没有额外空间的算法
|
p**o
发帖数: 1012 | 34 其实那个老印和我说，你干嘛不用list,用array.他觉得list insert，比我copy出来一
个array要好些，其实我觉得半斤八两，因为我觉得array其实存储空间更省，操作更快
，因为list 要存pointer.另一方面，List就不用后面多出一个整个的空间merge了，会
省空间。还有array 需要连续空间，List可以做linkedList,所以array太大容易内存溢
出。最后就是array建立BST的时候更方便，可以直接定位index,List虽然也可以用
index定位，但是其实还是按照一个个pointer链接过去的，说是建立BST的时候，复杂
度O(n)其实我觉得是不真实，因为List.get(i)不是绝对的O(1),所以很冷淡地回复了印
度人，List虽然有好处，不过也就是那样，两个相比，未必谁好谁坏。
我觉得那个印度人大概也感觉到我的态度不好了，其实他对我态度也不好，比如说题目
的时候，根本没举例具体说，就直接说一个find anagram,merge two BST,这么短的话
，明显也是应付 |
r*******n
发帖数: 3020 | 35 twitter放弃ruby了？
【在 l*******s 的大作中提到】
: 应该没啥问题。
: 当初跟recruiter谈的时候，说是他们主要用java和python
: 但是面试时，会让你用最熟悉的语言，并没有规定必须java。
|
l*******s
发帖数: 1258 | 36 可能不同的team和project用的语言不一样
不大清楚
【在 r*******n 的大作中提到】
: twitter放弃ruby了？
|
p**o
发帖数: 1012 | 37 update一下，昨天电面，今天悲剧,和感觉的还挺一致 |
m*****n
发帖数: 204 | 38 Just some random thoughts:
2. It has nothing to do with red-black tree. You should write the non-
recursive version.
3. synchronized is very coarse-grained. There should be more fine-grained
ways, e.g.,using AtomicReference to hold pointers.
【在 l*******s 的大作中提到】
: 上周电面Twitter，挂。贡献题目，攒rp。
: 大约45分钟，那哥们上来就说开始做题，打开一个类似google doc的网站。连互相介绍
: 寒暄都没有。我怀疑是急着下班去过长周末。
: 题目不难，我发挥的太烂。
: 1.描述一下HashMap和TreeMap的区别。
: 2.实现一个TreeMap里的get(K key)方法，自己定义树的node，最好用java。我写了个
: BST的get方法，就是简单的比较根节点然后递归左右子树那个，他说差不多。其实当时
: 觉得应该用红黑树，只是实现起来太麻烦，就没写。
: 3.如何防止这个TreeMap里的get，insert，delete等方法多线程调用时出现数据读写出
: 乱子？答曰用synchronized关键字。然后让直接写到第二题的code中。
|
l*******s
发帖数: 1258 | 39 请说明 为什么要非递归写法？
【在 m*****n 的大作中提到】
: Just some random thoughts:
: 2. It has nothing to do with red-black tree. You should write the non-
: recursive version.
: 3. synchronized is very coarse-grained. There should be more fine-grained
: ways, e.g.,using AtomicReference to hold pointers.
|
m*****n
发帖数: 204 | 40 Recursion is perceived to be inefficient. Two problems with recursion:
- Invocation overhead: cost to setup the call frame
- Call depth: stack may overflow.
In some language tail-recursion optimization is the norm, but in Java, I
believe the majority of JVM implementations do not optimize it.
【在 l*******s 的大作中提到】
: 请说明 为什么要非递归写法？
|
|
|
p*****p
发帖数: 379 | 41 关于3：AtomicReference只是标明了谁在用，进来操作的还是得等吧
估计是想要锁部分树的答案？
【在 m*****n 的大作中提到】
: Just some random thoughts:
: 2. It has nothing to do with red-black tree. You should write the non-
: recursive version.
: 3. synchronized is very coarse-grained. There should be more fine-grained
: ways, e.g.,using AtomicReference to hold pointers.
|
m*****k
发帖数: 731 | 42 面试官想听
http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/C
??
【在 p*****p 的大作中提到】
: 关于3：AtomicReference只是标明了谁在用，进来操作的还是得等吧
: 估计是想要锁部分树的答案？
|
s*****n
发帖数: 5488 | 43 典型的tree lock的例子。lock住root.操作，决定进入那个子树，lock children,
release root lock.循环。
【在 p*****p 的大作中提到】
: 关于3：AtomicReference只是标明了谁在用，进来操作的还是得等吧
: 估计是想要锁部分树的答案？
|
e***s
发帖数: 799 | 44 请问红黑树的GET跟BST的GET区别在哪里？
【在 l*******s 的大作中提到】
: 上周电面Twitter，挂。贡献题目，攒rp。
: 大约45分钟，那哥们上来就说开始做题，打开一个类似google doc的网站。连互相介绍
: 寒暄都没有。我怀疑是急着下班去过长周末。
: 题目不难，我发挥的太烂。
: 1.描述一下HashMap和TreeMap的区别。
: 2.实现一个TreeMap里的get(K key)方法，自己定义树的node，最好用java。我写了个
: BST的get方法，就是简单的比较根节点然后递归左右子树那个，他说差不多。其实当时
: 觉得应该用红黑树，只是实现起来太麻烦，就没写。
: 3.如何防止这个TreeMap里的get，insert，delete等方法多线程调用时出现数据读写出
: 乱子？答曰用synchronized关键字。然后让直接写到第二题的code中。
|
l*******s
发帖数: 1258 | 45 红黑树的get应该更复杂些，比如balance的时候要看颜色等。
【在 e***s 的大作中提到】
: 请问红黑树的GET跟BST的GET区别在哪里？
|
p*********y
发帖数: 17 | |
l*******s
发帖数: 1258 | 47 那么balance的时候 左旋右旋 怎么锁？
【在 s*****n 的大作中提到】
: 典型的tree lock的例子。lock住root.操作，决定进入那个子树，lock children,
: release root lock.循环。
|
