明星程序员被Google挂掉的故事

首先要提一个软件Homebrew

Homebrew可能是Mac上最好用的包管理器, 地位相当于Ubuntu的apt, 也相当于命令行版的AppStore

Max Howell是Homebrew的作者, 某天去google面试, 面试官出了一道反转二叉树的题目, 然而Max Howell没答上来, 最后, 就成为了一段佳话.


  • Google面试官:Max Howell来我大Google,这是好事情,一定要留下他! 不能出太难的题,也不能太直白; 所以题目既要简单又要逼格,树结构应该是比较合适了,树里最常见的就是二叉树,考的最多的也是二叉搜索树了, 那就反转二叉树了吧, 哈哈, 我真的太tm机智了!
  • Max Howell: 老兄,你这让我很尴尬呀,今天的事儿就算了,求不说...

哈哈,挖坑不填不是我的风格,python版解题源码奉上!

class Node(object):
    def __init__(self, value = None):
        self.value = value
        self.left = None
        self.right = None



class Tree(object):
    def __init__(self):
        self.root = Node()
        self.queue = []
        pass

    def add(self, value):
        # 创建一个节点
        tmp_node = Node(value)
        # 如果根节点为空, 则添加根节点
        if len(self.queue) == 0:
            self.root = tmp_node
            self.queue.append(tmp_node)
        # 如果根节点不为空
        else:
            # 获取当前子树未满的节点(当前临时父节点)
            nowRoot = self.queue[0]
            # 如果临时父节点左子树为空
            if nowRoot.left == None:
                nowRoot.left = tmp_node
                self.queue.append(tmp_node)
            # 如果临时父节点右子树为空
            else:
                nowRoot.right = tmp_node
                self.queue.append(tmp_node)
                # 从队列清除父节点(这个父节点现在已经满了)
                self.queue.pop(0)
    # 中序遍历
    def recursion_lvr(self, root):
        # 如果节点为空, 则返回
        if not root:
            return
        self.recursion_lvr(root.left)
        print(root.value)
        self.recursion_lvr(root.right)

    # 反转二叉树(HomeBrew的作者被坑的题目)
    def reverse_tree(self, root):
        if not root:
            return
        # 获取当前左右子树的根节点
        tmp_left_node = root.left
        tmp_right_node = root.right

        # 反转二叉树的左右子树
        root.left = tmp_right_node
        root.right = tmp_left_node

        # 将左右子树加入新的序列
        self.reverse_tree(root.left)
        self.reverse_tree(root.right)



def main():
    tree = Tree()
    for i in range(1,8):
        tree.add(i)

    tree.recursion_lvr(tree.root);

    tree.reverse_tree(tree.root)


    print("反转之后的结果:")
    tree.recursion_lvr(tree.root);


if __name__ == '__main__':
    main()

综上所述, 算法的确很重要......

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏技术小黑屋

Java性能调优之容器扩容问题

在Java和Android编程中,我们经常使用类似ArrayList,HashMap等这些容器。这些容器少则存储几条,多则上千甚至更多。作为性能调优的一部分,容...

12110
来自专栏coolblog.xyz技术专栏

TreeMap 源码分析

TreeMap最早出现在JDK 1.2中,是 Java 集合框架中比较重要一个的实现。TreeMap 底层基于红黑树实现,可保证在log(n)时间复杂度内完成 ...

63290
来自专栏数据结构与算法

Day2平衡树笔记

线段树不支持的操作:删除,插入 ---- 常见的平衡树 treap 慢||好写 sbt(大小平衡的树) 非常快 比较好写 ||功能不全 rbt 红黑树 特...

32660
来自专栏大史住在大前端

野生前端的数据结构基础练习(7)——二叉树

一棵树最上面的点称为根节点,如果一个节点下面连接多个节点,那么该节点称为父节点,下面的节点称为子节点,二叉树的每一个节点最多有2个子节点,一个节点子节点的个数称...

9520
来自专栏Petrichor的专栏

leetcode: 75. Sort Colors

16430
来自专栏desperate633

LintCode N皇后问题题目分析代码

每个解决方案包含一个明确的n皇后放置布局,其中“Q”和“.”分别表示一个女王和一个空位置。

8720
来自专栏数据处理

leetcode222求完全二叉树节点个数

38140
来自专栏算法与数据结构

PTA 7-4 排座位(25 分)

7-4 排座位(25 分) 布置宴席最微妙的事情,就是给前来参宴的各位宾客安排座位。无论如何,总不能把两个死对头排到同一张宴会桌旁!这个艰巨任务现在就交给你,对...

25190
来自专栏Android知识点总结

看得见的数据结构Android版之二分搜索树篇

9840
来自专栏尾尾部落

[剑指offer] 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

16110

扫码关注云+社区

领取腾讯云代金券