美国买被子or国内带被子?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 899|回复: 20
收起左侧

[找工就业] 狗昂赛特(求第三轮算法解答)

[复制链接] |试试Instant~ |关注本帖
我的人缘0
iker01 发表于 2018-2-23 10:53:43 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (30)
 
 
0% (0)  踩

2018(1-3月)-[]CS硕士+1-3年 - 猎头|BayArea 码农类General全职@Google在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
狗家昂赛特五轮算法:

. from: 1point3acres 1. 利特口 380
2. 删除额外的边使得图是
3. 输入递增的单链,构建complete二叉搜索树。要求O(N),卒。。。
4. 拓扑排序(bfs和dfs两种实现。。。)
5. 算24点和表达式

评分

参与人数 3大米 +35 收起 理由
hurricane_e + 30
closewen + 3 ++
rocketdive + 2 很有用的信息!

查看全部评分


上一篇:应届海本18年5-8月找帝都暑期SDE实习,求经验!
下一篇:CS专业找2018实习经历回顾
我的人缘0
chungjin 发表于 2018-2-23 11:04:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  82% (28)
 
 
17% (6)  踩
求问递增的单链是什么意思?多谢楼主!
回复

使用道具 举报

我的人缘0
 楼主| iker01 发表于 2018-2-23 11:05:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (30)
 
 
0% (0)  踩
chungjin 发表于 2018-2-23 11:04
求问递增的单链是什么意思?多谢楼主!

就是sorted linked list
回复

使用道具 举报

我的人缘0
Believers 发表于 2018-2-23 11:12:27 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (42)
 
 
8% (4)  踩
能用蠡口109解吗?
回复

使用道具 举报

我的人缘0
 楼主| iker01 发表于 2018-2-23 11:16:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (30)
 
 
0% (0)  踩
Believers 发表于 2018-2-23 11:12
能用蠡口109解吗?

我当时这么说的,但好像不是期望的答案。只在网上找到这个link:
http://rhyscitlema.com/algorithms/sorted-list-to-complete-bst/
回复

使用道具 举报

我的人缘0
T大农民伯伯 发表于 2018-2-23 11:24:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (15)
 
 
0% (0)  踩
先利用2^n-1作为满二叉树的size来确定linked list从哪个地方开始分裂,然后递归左右分叉,递归的时候需要传入当前linked list的参数?
回复

使用道具 举报

我的人缘0
 楼主| iker01 发表于 2018-2-23 11:37:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (30)
 
 
0% (0)  踩
T大农民伯伯 发表于 2018-2-23 11:24
先利用2^n-1作为满二叉树的size来确定linked list从哪个地方开始分裂,然后递归左右分叉,递归的时候需要传 ...

当时被告知用queue和level order traverse 来做,一直没弄清楚。。。
回复

使用道具 举报

我的人缘0
rocketdive 发表于 2018-2-23 11:43:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (63)
 
 
12% (9)  踩
能不能问一下楼主 2. 删除额外的边使得图是 这个是什么意思呢?谢谢
Mobile Apps Category (English)728x90
回复

使用道具 举报

我的人缘0
bambloo 发表于 2018-2-23 11:59:35 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  80% (32)
 
 
20% (8)  踩
不成熟的想法:.1point3acres网
我们知道,有序数组和BST之间的转换是非常方便的,特别当一个数组的规模为2^k-1的时候,只需要将最中间的元素放在根上,左右两边继续放中间值就行了。
那么如何构造规模为2^k-1的数组是关键,我的想法是在数组左右补上相等的-inf和+inf:
例如现在有【2,3,4,5,6】,补成【-inf,2,3,4,5,6,+inf】,再转换: 来源一亩.三分地论坛.
          4
        /    \. 1point 3acres 论坛
     2         6
  /     \    /    \. visit 1point3acres for more.
-inf    3  5   +inf    .1point3acres网
不知道理解的对不对。
回复

使用道具 举报

我的人缘0
Believers 发表于 2018-2-23 12:05:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (42)
 
 
8% (4)  踩
bambloo 发表于 2018-2-23 11:59
不成熟的想法:
我们知道,有序数组和BST之间的转换是非常方便的,特别当一个数组的规模为2^k-1的时候,只 ...

这不是complete bst吧。。
回复

使用道具 举报

我的人缘0
bambloo 发表于 2018-2-23 12:32:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  80% (32)
 
 
20% (8)  踩
Believers 发表于 2018-2-23 12:05
这不是complete bst吧。。

啊是这样,那前面就不用加-inf了,全部在后面加+inf就行啦
回复

使用道具 举报

我的人缘0
619899442 发表于 2018-2-23 13:25:07 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (65)
 
 
0% (0)  踩
bambloo 发表于 2018-2-23 11:59. visit 1point3acres for more.
不成熟的想法:
我们知道,有序数组和BST之间的转换是非常方便的,特别当一个数组的规模为2^k-1的时候,只 ...

我觉得可以这样:
1. 首先将链表转化为数组A,用O(N)时间
Key observation:假设root位于A[x],那么A[x]左边的元素一定位于左子树,右边的元素一定位于右子树

2. 定义函数F(int[] A, int left, int right) F将数组转化为完全二叉树:
首先找到根元素的位置:
-- 假设bst一共有N个节点,那么它一共有K = roundUp(log2(N + 1))层 (root是第一层)
-- 不考虑第K层是一个满二叉树,一共有2^(K) - 1节点,所以最后一层共有M = N - 2^K + 1 个节点
-- 接下来求出最后一个节点有多少属于左半部分 L = max(M, 2^(K-2))
-- 最后求得根节点的idx: = 左子树size = (2^(K) - 1 - 1) / 2 + L
有了idx之后可以写出F的递推式
F(int[] A, int left, int right)
  root.val = A[idx]
  root.left = F(A, left, idx - 1)
  root.right = F(A, idx + 1, right)
  return root

回复

使用道具 举报

我的人缘0
c393323264 发表于 2018-2-23 13:56:57 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩

                               
登录/注册后可看大图

是要生成这样的树吗
回复

使用道具 举报

我的人缘0
c393323264 发表于 2018-2-23 13:57:50 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
呃,图发不出来
回复

使用道具 举报

我的人缘0
c393323264 发表于 2018-2-23 14:07:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩

                               
登录/注册后可看大图

如果要生成这样的树的话,我的代码如下
  1. class Node(object):. 1point3acres
  2. .本文原创自1point3acres论坛
  3.   """ Node. """

  4.   def __init__(self, val):
  5.     self.left = None
  6.     self.right = None. 1point3acres
  7.     self.val = val
  8.     self.level = 1
  9.    

  10. def toCompleteTree(l):. 留学申请论坛-一亩三分地
  11.   """Convert to complete tree.

  12.   @param l    List of sorted integers.
  13. . 一亩-三分-地,独家发布
  14.   @return: A complete tree.

  15.   """
  16.   nodes = [Node(v) for v in l]
  17.   stack = list()
  18.   i = 0
  19.   cnt = len(nodes)
  20.   while i + 2 < len(nodes):
  21.     stack.extend(nodes[i: i + 3])
  22.     cnt -= 3
  23.     while True:
  24.       if len(stack) >= 3:
  25.         r = len(stack) - 1
  26.         if (stack[r].level == stack[r - 2].level):
  27.           right = stack[r]
  28.           stack.pop()
  29.           mid = stack[r - 1]
  30.           stack.pop()
  31.           left = stack[r - 2]
  32.           stack.pop()
  33.           mid.left = left
  34.           mid.right = right
  35.           mid.level = max(left.level, right.level) + 1
  36.           stack.append(mid)
  37.         else:. from: 1point3acres
  38.           break
  39.       else:
  40.         break
  41.     if cnt == 1:
  42.       nodes[-1].left = stack[-1]
  43.       stack.pop()
  44.       stack.append(nodes[-1])
  45.       cnt -= 1
  46.     else:
  47.       if i + 3 < len(nodes):
  48.         stack.append(nodes[i + 3])
  49.         cnt -= . Waral 博客有更多文章,
  50.     i += 4. 1point 3acres 论坛

  51. 来源一亩.三分地论坛.
  52.   if cnt == 1:. 1point3acres
  53.     stack.append(nodes[-1])
  54.   if cnt == 2:.留学论坛-一亩-三分地
  55.     nodes[-1].left = nodes[-2]
  56.     stack.append(nodes[-1])
  57. . From 1point 3acres bbs
  58.   while len(stack) != 1:
  59.     right = stack[-1]
  60.     mid = stack[-2]
  61.     left = stack[-3]
  62.     mid.left = left
  63.     mid.right = right.本文原创自1point3acres论坛
  64.     stack.pop()
  65.     stack.pop()
  66.     stack.pop()
  67.     stack.append(mid)

  68.   return stack[0]
复制代码
回复

使用道具 举报

我的人缘0
T大农民伯伯 发表于 2018-2-23 14:31:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (15)
 
 
0% (0)  踩
iker01 发表于 2018-2-23 11:37
当时被告知用queue和level order traverse 来做,一直没弄清楚。。。

我大概知道怎么用queue和level traversal来做了,其实他是要求你用BFS来做。你可以这样,先确定根节点的index,然后依照同样的方法计算出左右两棵树的根节点的index。然后就可以BFS往下做了。所以核心是给你的串长度为n,写出一个函数计算一次分叉的根节点index。
回复

使用道具 举报

我的人缘0
c393323264 发表于 2018-2-23 14:48:48 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩

                               
登录/注册后可看大图


import math

class Node(object):
. 留学申请论坛-一亩三分地
  """ Node. """

  def __init__(self, val):
    self.left = None
    self.right = None-google 1point3acres
    self.val = val
.1point3acres网

def toCompleteTree(l):-google 1point3acres
  """Convert to complete tree..1point3acres网

  @param l    Sorted list of integers.

  @return:    Complete tree.

  """. from: 1point3acres
  level = int(math.ceil(math.log(len(l) + 1, 2)))

  def build(s, e, level):
    if e - s <= 0:
      return None
    m = int(s + 2 ** (level - 1) - 1)
    r = e - m - 1
    if level >= 2 and r < 2 ** (level - 2) - 1:
      m = int(e - 2 ** (level - 2))
    node = Node(l[m])
    node.left = build(s, m, level - 1)
    node.right = build(m + 1, e, level - 1)
    return node
-google 1point3acres
  return build(0, len(l), level).留学论坛-一亩-三分地
. from: 1point3acres
. From 1point 3acres bbs
回复

使用道具 举报

我的人缘0
closewen 发表于 2018-2-23 15:20:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (19)
 
 
5% (1)  踩
5轮是 撸起就 的那个24点么,和加减乘除括号都有的?
回复

使用道具 举报

我的人缘0
落蕊轻飏 发表于 2018-2-23 15:59:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  56% (17)
 
 
43% (13)  踩
leetcode 109 Convert Sorted List to Binary Search Tree。稍微改下排名第二的discuss中recursion的时候list的范围就行了吧。
回复

使用道具 举报

我的人缘0
 楼主| iker01 发表于 2018-2-23 20:25:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (30)
 
 
0% (0)  踩
619899442 发表于 2018-2-23 13:25. 1point3acres
我觉得可以这样:
1. 首先将链表转化为数组A,用O(N)时间. 1point 3acres 论坛
Key observation:假设root位于A[x],那么A[x] ...

当时大概这么说的,但不让这么写。感觉面试官是期望用bfs。。。
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-7-21 19:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表