Redian新闻
>
想看杜拉拉,给个网址吧
avatar
想看杜拉拉,给个网址吧# Fashion - 美丽时尚
l*s
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。
avatar
s*e
2
想看杜拉拉的电影,给个网址吧。
avatar
w*a
3
顶一下 多谢楼主
avatar
J*p
4
www.tom365.com
avatar
m*s
5
只要Java?其他语言的他们招吗?
avatar
m*a
6
pipi.cn
avatar
l*s
7
应该没啥问题。
当初跟recruiter谈的时候,说是他们主要用java和python
但是面试时,会让你用最熟悉的语言,并没有规定必须java。

【在 m******s 的大作中提到】
: 只要Java?其他语言的他们招吗?
avatar
y*3
8
PPSTREAM就有啊~~~
avatar
j*y
9
面你的人是老印吗?

【在 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中。

avatar
s*e
10
我下载安装了那个播放器,还是看不了啊,怎么回事啊

【在 J*****p 的大作中提到】
: www.tom365.com
avatar
l*s
11
应该不是 听说话没有口音 应该是个native speaker
但是不知道叫啥名字 所以也无从判断是啥人。
我本来想跟人家寒暄两句自我介绍下,没想到直接不给我机会说,上来就做题。

【在 j*****y 的大作中提到】
: 面你的人是老印吗?
avatar
w*x
13

太好了,看了我这一个多星期还没消息的可能还有戏

【在 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中。

avatar
p*a
14
去优酷搜

【在 s**********e 的大作中提到】
: 我下载安装了那个播放器,还是看不了啊,怎么回事啊
avatar
P*r
15
twitter大家咋投的简历?
avatar
g*i
16
看了会失望的
avatar
l*s
17
他们的recruiter找的我

【在 P******r 的大作中提到】
: twitter大家咋投的简历?
avatar
R*a
18
谢谢link。 看了10分钟,满好的。好多年没看过国内影剧,比想像的好多啦。
avatar
p*o
19
估计同电面悲剧的握手,贡献个题目
1。找anagram,这个题据说是练手的,本来应该一口气写出来的常见题目,想了10分钟
2.合并两个BST,也写出来了
45分钟只短不长,上来二话不说直接coding,交流不多,也没问对方提示,对方应该印
度人。虽然都做出来了,但是由于写的不够顺,而且第一题他只说是warmup的,我不知
道后面是不是还有第三题,总之,觉得对方对我感觉不太好,而且题目也太简单,应该
是悲剧了
avatar
w*x
21

你这都杯具了我就没救了, 你啥时候面的, 咋没回复啊?

【在 p**o 的大作中提到】
: 估计同电面悲剧的握手,贡献个题目
: 1。找anagram,这个题据说是练手的,本来应该一口气写出来的常见题目,想了10分钟
: 2.合并两个BST,也写出来了
: 45分钟只短不长,上来二话不说直接coding,交流不多,也没问对方提示,对方应该印
: 度人。虽然都做出来了,但是由于写的不够顺,而且第一题他只说是warmup的,我不知
: 道后面是不是还有第三题,总之,觉得对方对我感觉不太好,而且题目也太简单,应该
: 是悲剧了

avatar
w*x
22

刚收到邮件, 可以onsite了, 8天后回复的, 千万别挂了~~

【在 p**o 的大作中提到】
: 估计同电面悲剧的握手,贡献个题目
: 1。找anagram,这个题据说是练手的,本来应该一口气写出来的常见题目,想了10分钟
: 2.合并两个BST,也写出来了
: 45分钟只短不长,上来二话不说直接coding,交流不多,也没问对方提示,对方应该印
: 度人。虽然都做出来了,但是由于写的不够顺,而且第一题他只说是warmup的,我不知
: 道后面是不是还有第三题,总之,觉得对方对我感觉不太好,而且题目也太简单,应该
: 是悲剧了

avatar
p*2
23

难道它家不是用ruby和scala?

【在 l*******s 的大作中提到】
: 应该没啥问题。
: 当初跟recruiter谈的时候,说是他们主要用java和python
: 但是面试时,会让你用最熟悉的语言,并没有规定必须java。

avatar
p*o
24
今天面的,不算顺利,对方明显在忙别的事情,和我说了anagram就让写,我纠结了很
久anagram是什么,还问了他,我觉得都写了,但是也不一定都对,觉得思路上没什么
问题吧。
第一个就是把每个单词sort,sort了之后再去hashset map
第二个就是把BST的数值read下来,然后一merge两个array,然后重建BST
复杂度也都说了下,我的background是做java backend的一些玩意的

【在 w****x 的大作中提到】
:
: 刚收到邮件, 可以onsite了, 8天后回复的, 千万别挂了~~

avatar
w*x
25

没关系吧,你都做了两题了, 我两个back to back phone interview, 每个才做了一


【在 p**o 的大作中提到】
: 今天面的,不算顺利,对方明显在忙别的事情,和我说了anagram就让写,我纠结了很
: 久anagram是什么,还问了他,我觉得都写了,但是也不一定都对,觉得思路上没什么
: 问题吧。
: 第一个就是把每个单词sort,sort了之后再去hashset map
: 第二个就是把BST的数值read下来,然后一merge两个array,然后重建BST
: 复杂度也都说了下,我的background是做java backend的一些玩意的

avatar
p*2
26

太牛了。膜拜呀。

【在 w****x 的大作中提到】
:
: 没关系吧,你都做了两题了, 我两个back to back phone interview, 每个才做了一
: 题

avatar
l*a
27
存下了,谢谢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中。

avatar
l*a
28
为什么千万别?
那里bar很高的

【在 w****x 的大作中提到】
:
: 没关系吧,你都做了两题了, 我两个back to back phone interview, 每个才做了一
: 题

avatar
l*a
29
第二题用了额外空间,显然不是最优吧

【在 p**o 的大作中提到】
: 今天面的,不算顺利,对方明显在忙别的事情,和我说了anagram就让写,我纠结了很
: 久anagram是什么,还问了他,我觉得都写了,但是也不一定都对,觉得思路上没什么
: 问题吧。
: 第一个就是把每个单词sort,sort了之后再去hashset map
: 第二个就是把BST的数值read下来,然后一merge两个array,然后重建BST
: 复杂度也都说了下,我的background是做java backend的一些玩意的

avatar
w*x
30

如果不用额外空间编程时间肯定不够。

【在 l*****a 的大作中提到】
: 第二题用了额外空间,显然不是最优吧
avatar
l*a
31
至少也要说一下较优算法吧。
纯暴力的话对付这种牛公司恐怕不成

【在 w****x 的大作中提到】
:
: 如果不用额外空间编程时间肯定不够。

avatar
w*x
32

写一个
//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 的大作中提到】
: 至少也要说一下较优算法吧。
: 纯暴力的话对付这种牛公司恐怕不成

avatar
l*a
33
你的比较怎么写的?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中。

avatar
p*o
34
额外空间也就是一个int的array,不用写着有点晕啊,10多分钟

【在 l*****a 的大作中提到】
: 第二题用了额外空间,显然不是最优吧
avatar
w*x
35

额外空间的也不是很简单的,怎么也得写2个函数

【在 p**o 的大作中提到】
: 额外空间也就是一个int的array,不用写着有点晕啊,10多分钟
avatar
l*a
36
一棵树 做 in-order traverse
然后每次插入可以吗?

【在 w****x 的大作中提到】
:
: 额外空间的也不是很简单的,怎么也得写2个函数

avatar
p*o
37
函数和你分得差不多,不过我是Java,所以code短的多。本来也不想去,所以裸面的,
一直也没做过题,所以我的水平必然很抱歉。面一下就当娱乐了,我这么差,刚好给别
人多个机会。
avatar
p*o
38
think about your complexity?
Is insertion to a BST O(1) or O(lg n)?

【在 l*****a 的大作中提到】
: 一棵树 做 in-order traverse
: 然后每次插入可以吗?

avatar
l*a
39
lg(n)吧。

【在 p**o 的大作中提到】
: think about your complexity?
: Is insertion to a BST O(1) or O(lg n)?

avatar
p*o
40
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
: 然后每次插入可以吗?

avatar
w*x
41

要写个平衡的算法另可些那个没有额外空间的算法

【在 l*****a 的大作中提到】
: lg(n)吧。
avatar
p*o
42
If it is O(lgn), you complexity is O(nlgn), but ours is O(n)

【在 l*****a 的大作中提到】
: lg(n)吧。
avatar
l*a
43
中文太差,看不懂:(

【在 w****x 的大作中提到】
:
: 要写个平衡的算法另可些那个没有额外空间的算法

avatar
p*o
44
其实那个老印和我说,你干嘛不用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,这么短的话
,明显也是应付
avatar
r*n
45
twitter放弃ruby了?

【在 l*******s 的大作中提到】
: 应该没啥问题。
: 当初跟recruiter谈的时候,说是他们主要用java和python
: 但是面试时,会让你用最熟悉的语言,并没有规定必须java。

avatar
l*s
46
可能不同的team和project用的语言不一样
不大清楚

【在 r*******n 的大作中提到】
: twitter放弃ruby了?
avatar
p*o
47
update一下,昨天电面,今天悲剧,和感觉的还挺一致
avatar
m*n
48
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中。

avatar
l*s
49
请说明 为什么要非递归写法?

【在 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.

avatar
m*n
50
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 的大作中提到】
: 请说明 为什么要非递归写法?
avatar
p*p
51
关于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.

avatar
s*n
53
典型的tree lock的例子。lock住root.操作,决定进入那个子树,lock children,
release root lock.循环。

【在 p*****p 的大作中提到】
: 关于3:AtomicReference只是标明了谁在用,进来操作的还是得等吧
: 估计是想要锁部分树的答案?

avatar
e*s
54
请问红黑树的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中。

avatar
l*s
55
红黑树的get应该更复杂些,比如balance的时候要看颜色等。

【在 e***s 的大作中提到】
: 请问红黑树的GET跟BST的GET区别在哪里?
avatar
l*s
57
那么balance的时候 左旋右旋 怎么锁?

【在 s*****n 的大作中提到】
: 典型的tree lock的例子。lock住root.操作,决定进入那个子树,lock children,
: release root lock.循环。

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。