车版热帖:大家对买豪车怎么看

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
[Google级团队]:实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 753|回复: 20
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
iker01 发表于 2018-2-23 10:53:43 | 显示全部楼层 |阅读模式

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

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

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

x
狗家昂赛特五轮算法:

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

评分

3

查看全部评分

chungjin 发表于 2018-2-23 11:04:08 | 显示全部楼层
求问递增的单链是什么意思?多谢楼主!
回复 支持 反对

使用道具 举报

 楼主| iker01 发表于 2018-2-23 11:05:15 | 显示全部楼层
chungjin 发表于 2018-2-23 11:04
求问递增的单链是什么意思?多谢楼主!
. more info on 1point3acres.com
就是sorted linked list
回复 支持 反对

使用道具 举报

Believers 发表于 2018-2-23 11:12:27 | 显示全部楼层
能用蠡口109解吗?
回复 支持 反对

使用道具 举报

 楼主| iker01 发表于 2018-2-23 11:16:39 | 显示全部楼层
Believers 发表于 2018-2-23 11:12. visit 1point3acres.com for more.
能用蠡口109解吗?

我当时这么说的,但好像不是期望的答案。只在网上找到这个link:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
http://rhyscitlema.com/algorithms/sorted-list-to-complete-bst/
回复 支持 反对

使用道具 举报

T大农民伯伯 发表于 2018-2-23 11:24:41 | 显示全部楼层
先利用2^n-1作为满二叉树的size来确定linked list从哪个地方开始分裂,然后递归左右分叉,递归的时候需要传入当前linked list的参数?
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

rocketdive 发表于 2018-2-23 11:43:20 | 显示全部楼层
能不能问一下楼主 2. 删除额外的边使得图是 这个是什么意思呢?谢谢
回复 支持 反对

使用道具 举报

bambloo 发表于 2018-2-23 11:59:35 | 显示全部楼层
不成熟的想法:
我们知道,有序数组和BST之间的转换是非常方便的,特别当一个数组的规模为2^k-1的时候,只需要将最中间的元素放在根上,左右两边继续放中间值就行了。
那么如何构造规模为2^k-1的数组是关键,我的想法是在数组左右补上相等的-inf和+inf:
例如现在有【2,3,4,5,6】,补成【-inf,2,3,4,5,6,+inf】,再转换:
          4
        /    \
     2         6
  /     \    /    \
-inf    3  5   +inf    . more info on 1point3acres.com
不知道理解的对不对。
回复 支持 反对

使用道具 举报

Believers 发表于 2018-2-23 12:05:41 | 显示全部楼层
bambloo 发表于 2018-2-23 11:59
不成熟的想法:
我们知道,有序数组和BST之间的转换是非常方便的,特别当一个数组的规模为2^k-1的时候,只 ...

这不是complete bst吧。。
回复 支持 反对

使用道具 举报

bambloo 发表于 2018-2-23 12:32:37 | 显示全部楼层
Believers 发表于 2018-2-23 12:05. 鍥磋鎴戜滑@1point 3 acres
这不是complete bst吧。。

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

使用道具 举报

619899442 发表于 2018-2-23 13:25:07 | 显示全部楼层
bambloo 发表于 2018-2-23 11:59
不成熟的想法:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我们知道,有序数组和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-google 1point3acres
有了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

回复 支持 反对

使用道具 举报

c393323264 发表于 2018-2-23 13:56:57 | 显示全部楼层

                               
登录/注册后可看大图

是要生成这样的树吗
回复 支持 反对

使用道具 举报

c393323264 发表于 2018-2-23 13:57:50 | 显示全部楼层
呃,图发不出来
回复 支持 反对

使用道具 举报

c393323264 发表于 2018-2-23 14:07:23 | 显示全部楼层

-google 1point3acres                               
登录/注册后可看大图

如果要生成这样的树的话,我的代码如下
  1. class Node(object):
  2. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  3.   """ Node. """

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

  10. def toCompleteTree(l):
  11.   """Convert to complete tree.
  12. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  13.   @param l    List of sorted integers.

  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):-google 1point3acres
  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:
  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:. visit 1point3acres.com for more.
  47.       if i + 3 < len(nodes):
  48.         stack.append(nodes[i + 3])
  49.         cnt -=
  50.     i += 4

  51.   if cnt == 1:
  52.     stack.append(nodes[-1])-google 1point3acres
  53.   if cnt == 2:
  54.     nodes[-1].left = nodes[-2]. Waral 鍗氬鏈夋洿澶氭枃绔,
  55.     stack.append(nodes[-1])
  56. . Waral 鍗氬鏈夋洿澶氭枃绔,
  57.   while len(stack) != 1:
  58.     right = stack[-1]
  59.     mid = stack[-2]
  60.     left = stack[-3]. 1point3acres.com/bbs
  61.     mid.left = left
  62.     mid.right = right
  63.     stack.pop()
  64.     stack.pop()
  65.     stack.pop()
  66.     stack.append(mid)

  67.   return stack[0]
复制代码
回复 支持 反对

使用道具 举报

T大农民伯伯 发表于 2018-2-23 14:31:25 | 显示全部楼层
iker01 发表于 2018-2-23 11:37. 鍥磋鎴戜滑@1point 3 acres
当时被告知用queue和level order traverse 来做,一直没弄清楚。。。

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

使用道具 举报

c393323264 发表于 2018-2-23 14:48:48 | 显示全部楼层

                               
登录/注册后可看大图


import math
. 1point3acres.com/bbs
class Node(object):

  """ Node. """
. visit 1point3acres.com for more.
  def __init__(self, val):
    self.left = None.鏈枃鍘熷垱鑷1point3acres璁哄潧
    self.right = None
    self.val = val
. from: 1point3acres.com/bbs

def toCompleteTree(l):
  """Convert to complete tree.

  @param l    Sorted list of integers.

  @return:    Complete tree.
. more info on 1point3acres.com
  """
  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. 1point3acres.com/bbs
    if level >= 2 and r < 2 ** (level - 2) - 1: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
      m = int(e - 2 ** (level - 2))
    node = Node(l[m]). 1point3acres.com/bbs
    node.left = build(s, m, level - 1). from: 1point3acres.com/bbs
    node.right = build(m + 1, e, level - 1)
    return node
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  return build(0, len(l), level)


回复 支持 反对

使用道具 举报

closewen 发表于 2018-2-23 15:20:44 | 显示全部楼层
5轮是 撸起就 的那个24点么,和加减乘除括号都有的?
回复 支持 反对

使用道具 举报

落蕊轻飏 发表于 2018-2-23 15:59:37 | 显示全部楼层
leetcode 109 Convert Sorted List to Binary Search Tree。稍微改下排名第二的discuss中recursion的时候list的范围就行了吧。
回复 支持 反对

使用道具 举报

 楼主| iker01 发表于 2018-2-23 20:25:43 | 显示全部楼层
619899442 发表于 2018-2-23 13:25
我觉得可以这样:
1. 首先将链表转化为数组A,用O(N)时间. more info on 1point3acres.com
Key observation:假设root位于A[x],那么A[x] ...

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

使用道具 举报

本版积分规则

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

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

关闭

一亩三分地推荐上一条 /5 下一条

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

custom counter

GMT+8, 2018-4-23 19:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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