阅读 58

Arts 第四十三周(1/6~ 1/12)

ARTS是什么?
Algorithm:每周至少做一个leetcode的算法题;
Review:阅读并点评至少一篇英文技术文章;
Tip:学习至少一个技术技巧;
Share:分享一篇有观点和思考的技术文章。

Algorithm

LC 173. Binary Search Tree Iterator

题目解析

题目很直接,让实现一个二叉搜索树的迭代器,迭代器有两个方法,next()hasNext()。如果仅仅是为了 AC 这道题目,一点都不难,你可以套用树的中序遍历,将结果存到一个 list 中,有了这个 list,想必 next()hasNext() 也就都有了。很多人一开始做这道题都是这么想的,也是这么去实现的,但其实这里有个很严重的问题。首先需要解释一下 “什么是迭代器?” 迭代器有一个特点,当然也可以算作是它的优势,那就是 即用即取,前面提到的把所有元素全都取出来放到一个 list 中其实就违反了迭代器 “即用即取” 的性质,虽然说你可以 AC 这道题,但实现方向其实是完全错误的。next() 函数保证了一次只去当前结构中取一个元素,完事后,将指针移到下一位,运行 next() 函数之前,必须用 hasNext() 去进行检查,在确定当前指针指向的元素合法后,才能调用 next(),迭代器在性能和运行效率上有很好的优势,特别是对于一个大小未知的数据结构,如果你需要按一定的顺序遍历一个数据结构,都可以考虑利用迭代器,一般来说,迭代器的 next()hasNext() 的时间复杂度都是 O(1)。

对于实现迭代器一类的题目,都可以考虑使用 这个数据结构,栈中用于存放遍历过程中的数据,当然这不是必须的,但是可以成为你思考该类问题的一个方向。

关于迭代器的问题 LeetCode 上面还有很多,总体来说难度都不大,但是需要强调的是 迭代器的性质,而不是仅仅 AC 题目。


参考代码

class BSTIterator {

    private Stack<TreeNode> tree;
    
    public BSTIterator(TreeNode root) {
        this.tree = new Stack<>();
        addSubTree(root);
    }
    
    private void addSubTree(TreeNode subRoot) {
        while (subRoot != null) {
            tree.push(subRoot);
            subRoot = subRoot.left;
        }
    }
    
    /** @return the next smallest number */
    public int next() {
        TreeNode cur = tree.pop();
        
        if (cur.right != null) {
            addSubTree(cur.right);
        }
        
        return cur.val;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !tree.isEmpty();
    }
    
}
复制代码

Review

Working at Amazon: Software Engineer

一篇介绍亚马逊公司的公司文化的文章,作者在亚马逊当了 2 年半的程序员,学习了许多亚马逊公司的管理理念和人文文化,并在文章中做了分享,主要是亚马逊的 领导力准则,这个可谓是亚马逊员工自我管理的核心理念,加上作者的分享,基本上有以下几个方面:

  • 主人翁精神

    很多的大公司的管理理念强调的是团队作战,一个团队小则几十人,大则成百上千人,这样的团队往往层级很深,每一级听取上一级的命令,大多数的底层员工成了任人摆布的螺丝钉,在这样的层级管理中你很难看到个人领导力。

    亚马逊不同的地方在于,它的一个独立的团队可以小到 4 - 5 人,每个团队也仅由一个 manager 负责,在这个团队的人就会很有归属感,当团队做出产品,做出成绩时,团队成员也能明显地感觉到自己的价值。团队的管理方式也没有严格的规定,每个团队可以自己定义自己团队的文化和秩序,这就给员工当家做主人的机会。

  • 以用户为中心

    如果把一个公司比喻成一颗树,那么用户就是这个树的树干,极其重要。每做一个决定,或者每制定一个计划,都会询问 “我们的用户会满意这个方案吗?”,“这个方案能给我们用户带来什么样的价值?” 等等。领导从用户入手,再反推要做的工作。

  • 有责任感,做有价值的事

    亚马逊的程序员的职位划分并不是特别的细,这也就意味着软件工程师一个人要担当多种角色,一个程序员既可以是开发工程师,也可以是运维或测试工程师,还有可能是产品经理,虽然说这样来看,个人的工作量会很大,但是反过来看可以了解整个软件的生态,学习的机会也大大提升,当然做成一个产品,也会有不小的成就感,这些都会是自己宝贵的经验。

  • 用数据说话

    很多时候,数据可以很客观,很直观地描述一个事物的状态,根据充实有效的数据来做决策或是制定计划会比凭空想象切实的多,同样,亚马逊也强调写作的重要性,往往把自己的想法写下来的过程中你会发现自己之前未曾发现的东西,根据现有的数据还有材料进行写作,这样方案和决策才会更牢靠。

  • 容忍失败

    亚马逊的管理理念中强调,领导需要允许员工犯错,甚至鼓励员工多尝试,不要怕犯错,往往一个上线产品的代码中出现 bug 并不能看作是一个人的责任,因为一个产品上线需要经历很多的流程,比如 代码评审、集成测试、自动部署、错误警报,代码出错证明这些流程都没有 100% 做好,相比于为错误找负责人,还不如积极地寻找策略和解决方案,并从错误中汲取教训,避免下次再犯。

这些个管理理念支撑着这家伟大的公司,当然了,作者也提到,并不是说亚马逊没有缺点,只是说,我们从它的优点上学到的更多。


Tip

这周接触了 MongoDB 相关的工具,首先是 MongoDB 的一个 server cluster,可以去 cloud.mongodb.com 上免费通过邮箱注册账号,上面可以 创建免费的 MongoDB 集群(PS:注意 IP 会时常变动,可以考虑设置成 0.0.0.0/0)

另外的一个比较有用的是 MongoDB Compass,是一个 MongoDB 的图形化控制面板,如果用不习惯命令行的话,可以考虑使用这个工具,管理 DB 比较直观,清晰


Share

看了《深度工作》这本书,这周就来聊聊深度工作,重点在 “深度” 二字

深度工作-如何有效提升工作效率

关注下面的标签,发现更多相似文章
评论