详谈如何最大化利用career fair

一亩三分地论坛

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

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 1042|回复: 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
狗家昂赛特五轮算法:

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)   【踩】
全局: 顶  77% (28)
 
 
22% (8)  踩
求问递增的单链是什么意思?多谢楼主!
回复

使用道具 举报

我的人缘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/

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘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% (77)
 
 
12% (11)  踩
能不能问一下楼主 2. 删除额外的边使得图是 这个是什么意思呢?谢谢

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

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

使用道具 举报

我的人缘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% (33)
 
 
19% (8)  踩
Believers 发表于 2018-2-23 12:05
这不是complete bst吧。。

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

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
619899442 发表于 2018-2-23 13:25:07 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (71)
 
 
0% (0)  踩
bambloo 发表于 2018-2-23 11:59
不成熟的想法:
我们知道,有序数组和BST之间的转换是非常方便的,特别当一个数组的规模为2^k-1的时候,只 ...
.本文原创自1point3acres论坛
我觉得可以这样:. 留学申请论坛-一亩三分地
1. 首先将链表转化为数组A,用O(N)时间
Key observation:假设root位于A[x],那么A[x]左边的元素一定位于左子树,右边的元素一定位于右子树. 牛人云集,一亩三分地

2. 定义函数F(int[] A, int left, int right) F将数组转化为完全二叉树:. 一亩-三分-地,独家发布
首先找到根元素的位置:. 围观我们@1point 3 acres
-- 假设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) .本文原创自1point3acres论坛
  root.val = A[idx]. Waral 博客有更多文章,
  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):
  2. 来源一亩.三分地论坛.
  3.   """ Node. """

  4.   def __init__(self, val):
  5.     self.left = None. 留学申请论坛-一亩三分地
  6.     self.right = None.1point3acres网
  7.     self.val = val
  8.     self.level = 1. Waral 博客有更多文章,
  9.    
  10. . 围观我们@1point 3 acres
  11. def toCompleteTree(l):
  12.   """Convert to complete tree. 来源一亩.三分地论坛.

  13.   @param l    List of sorted integers.. 围观我们@1point 3 acres

  14.   @return: A complete tree.
  15. . visit 1point3acres for more.
  16.   """
  17.   nodes = [Node(v) for v in l]
  18.   stack = list()
  19.   i = 0
  20.   cnt = len(nodes). 1point 3acres 论坛
  21.   while i + 2 < len(nodes):
  22.     stack.extend(nodes[i: i + 3])
  23.     cnt -= 3
  24.     while True:.留学论坛-一亩-三分地
  25.       if len(stack) >= 3:
  26.         r = len(stack) - 1. Waral 博客有更多文章,
  27.         if (stack[r].level == stack[r - 2].level):
  28.           right = stack[r]. 围观我们@1point 3 acres
  29.           stack.pop()
  30.           mid = stack[r - 1]
  31.           stack.pop()
  32.           left = stack[r - 2]
  33.           stack.pop()
  34.           mid.left = left
  35.           mid.right = right
  36.           mid.level = max(left.level, right.level) + 1
  37.           stack.append(mid)
  38.         else:. 1point3acres
  39.           break. from: 1point3acres
  40.       else:. Waral 博客有更多文章,
  41.         break
  42.     if cnt == 1:
  43.       nodes[-1].left = stack[-1]
  44.       stack.pop()
  45.       stack.append(nodes[-1])
  46.       cnt -= 1. visit 1point3acres for more.
  47.     else:. from: 1point3acres
  48.       if i + 3 < len(nodes):
  49.         stack.append(nodes[i + 3]). more info on 1point3acres
  50.         cnt -=
  51.     i += 4
  52. . 围观我们@1point 3 acres
  53.   if cnt == 1:
  54.     stack.append(nodes[-1])
  55.   if cnt == 2:
  56.     nodes[-1].left = nodes[-2]
  57.     stack.append(nodes[-1])

  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
  64.     stack.pop()
  65.     stack.pop()
  66.     stack.pop()
  67.     stack.append(mid)
  68. . From 1point 3acres bbs
  69.   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)  踩

                               
登录/注册后可看大图
. Waral 博客有更多文章,

import math

class Node(object):

  """ Node. """

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


def toCompleteTree(l):
  """Convert to complete tree.
. 1point3acres
  @param l    Sorted list of integers.

  @return:    Complete tree.

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

  def build(s, e, level):
    if e - s <= 0:. From 1point 3acres bbs
      return None
    m = int(s + 2 ** (level - 1) - 1)
    r = e - m - 1
    if level >= 2 and r < 2 ** (level - 2) - 1:.本文原创自1point3acres论坛
      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)
. 1point 3acres 论坛    return node

  return build(0, len(l), level)


回复

使用道具 举报

我的人缘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)   【踩】
全局: 顶  53% (17)
 
 
46% (15)  踩
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
我觉得可以这样:
1. 首先将链表转化为数组A,用O(N)时间
Key observation:假设root位于A[x],那么A[x] ...

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

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-9-25 23:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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