由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 做了一下merge BST
相关主题
攒人品,Twitter 电面题目今天面的太惨了....
问道G家的面试题。Lowest common ancestor of two nodes of Binary Tree
贡献一道G家的onsite题和简单面经(已悲剧)ms面试题目
很可能被这题搞挂了,sort linked list问个reverse linked list
请问如何sort一个linked list?请教这么一个题:BST maximum sum path
刚才重新回顾了一下那题请教各位大牛一个K-way merge 的问题
MS on-site 面经&求分析(口头offer)binary tree的in-order iterator怎么写?
G题,把binary tree里面的sibling节点连接起来发几个面试题
相关话题的讨论汇总
话题: node话题: pnode话题: null话题: piter话题: prgt
进入JobHunting版参与讨论
1 (共1页)
w****x
发帖数: 2483
1
//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);
}
---- 30 min with IDE
y**********u
发帖数: 6366
2
我觉得唉
这个solution可能不对
谁都想得出来啊。。。

//

【在 w****x 的大作中提到】
: //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;

p*****2
发帖数: 21240
3
不错。我也想做做呢。先mark一下。晚上我也试试。
w****x
发帖数: 2483
4
为啥不对, 这题就是把BST->linkedlist, merge linked list, construct balance
BST from linked list合起来
y**********u
发帖数: 6366
5
这样感觉就没什么意思了。。。就是基础题啊

【在 w****x 的大作中提到】
: 为啥不对, 这题就是把BST->linkedlist, merge linked list, construct balance
: BST from linked list合起来

w****x
发帖数: 2483
6

写写看嘛~~~ 没那么基础. 我觉得一般公司这题够涮掉至少95%以上的人了

【在 y**********u 的大作中提到】
: 这样感觉就没什么意思了。。。就是基础题啊
p*****2
发帖数: 21240
7
这么长,面试不死定了?
w****x
发帖数: 2483
8

面试给45分钟做这题

【在 p*****2 的大作中提到】
: 这么长,面试不死定了?
t*****2
发帖数: 9
9
为啥不用vector用linked list?
w****x
发帖数: 2483
10

BST自己就是linked list啊, vector要额外空间

【在 t*****2 的大作中提到】
: 为啥不用vector用linked list?
相关主题
刚才重新回顾了一下那题今天面的太惨了....
MS on-site 面经&求分析(口头offer)Lowest common ancestor of two nodes of Binary Tree
G题,把binary tree里面的sibling节点连接起来ms面试题目
进入JobHunting版参与讨论
t********e
发帖数: 143
11
Maybe we can do 2 in order traversal at the same time and construct trees
from smallest element.
Here is a way to construct tree from smallest element:
http://www.leetcode.com/2010/11/convert-sorted-list-to-balanced
p*****2
发帖数: 21240
12
写了一下BT 到 linkedlist不好写呀。
Node Convert(Node node)
{
Node head;
if (node.left == null)
head = node;
else
{
Pair1 pair = Change(node.left, null, node, true);
node.left = pair.max;
head = pair.min;
}
if (node.right != null)
{
Pair1 pair = Change(node.right, node, null, false);
node.right = pair.min;
}
return head;
}
Pair1 Change(Node node, Node prev, Node next, boolean left)
{
Pair1 pp = new Pair1(null, null);
if (node.left == null)
{
node.left = prev;
pp.min = node;
}
else
{
Pair1 pair = Change(node.left, prev, node, true);
node.left = pair.max;
pp.min = pair.min;
}
if (node.right == null)
{
node.right = next;
pp.max = node;
}
else
{
Pair1 pair = Change(node.right, node, next, false);
node.right = pair.min;
pp.max = pair.max;
}
return pp;
}
}
class Pair1
{
Node min;
Node max;
public Pair1(Node _min, Node _max)
{
min = _min;
max = _max;
}
}
class Node
{
int value;
Node left;
Node right;
public Node(int v)
{
value = v;
}
}
w****x
发帖数: 2483
13

为啥总觉得你整地代码那么长呢...
用c做代码会短些

【在 p*****2 的大作中提到】
: 写了一下BT 到 linkedlist不好写呀。
: Node Convert(Node node)
: {
: Node head;
: if (node.left == null)
: head = node;
: else
: {
: Pair1 pair = Change(node.left, null, node, true);
: node.left = pair.max;

y**********u
发帖数: 6366
14
左括号占的行数比较多。。。

【在 w****x 的大作中提到】
:
: 为啥总觉得你整地代码那么长呢...
: 用c做代码会短些

p*****2
发帖数: 21240
15

算了。用C去面试吃了大亏了。用C当然是灵活很多了。有指针。

【在 w****x 的大作中提到】
:
: 为啥总觉得你整地代码那么长呢...
: 用c做代码会短些

b********h
发帖数: 2451
16


【在 w****x 的大作中提到】
: //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;

p*****2
发帖数: 21240
17

我一直不习惯把左括号放到上一行,咋办呀。如果那样我看起程序来很费劲。

【在 y**********u 的大作中提到】
: 左括号占的行数比较多。。。
w****x
发帖数: 2483
18
除了这个括号外我还是觉得太多了
y**********u
发帖数: 6366
19
其实我觉得不比你的长啊
而且你的参数传递是指针类型的引用。。。

【在 w****x 的大作中提到】
: 除了这个括号外我还是觉得太多了
b********h
发帖数: 2451
20
不能直接用树?为啥要转换成linked list呢?

【在 w****x 的大作中提到】
: //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;

l*********8
发帖数: 4642
21
转换成linked list后是O(N)算法
直接从一个bst逐个取出node插入到另一个bst,是O(N*logN)算法

【在 b********h 的大作中提到】
: 不能直接用树?为啥要转换成linked list呢?
1 (共1页)
进入JobHunting版参与讨论
相关主题
发几个面试题请问如何sort一个linked list?
FB面试题:binary tree inorder successor刚才重新回顾了一下那题
几道F家面试题MS on-site 面经&求分析(口头offer)
一个树,不一定是2叉树,让设计一个数据结构来serialize和 deserializeG题,把binary tree里面的sibling节点连接起来
攒人品,Twitter 电面题目今天面的太惨了....
问道G家的面试题。Lowest common ancestor of two nodes of Binary Tree
贡献一道G家的onsite题和简单面经(已悲剧)ms面试题目
很可能被这题搞挂了,sort linked list问个reverse linked list
相关话题的讨论汇总
话题: node话题: pnode话题: null话题: piter话题: prgt