EPI online zoom session 面试算法基础知识直播分享

各位有兴趣做面试算法解题的朋友,

突击九章算法班半年以后, 未来两个月我打算仔细学习 Elements of Programming Interviews in Python, ( EPI ), 夯实基础知识.

为了督促自己保持合理进度, 咱每周都会有两三次学习心得分享, zoom 视频直播, 欢迎报名.

一般直播时间是每天加西时间 7:20pm PST. 美东时间 10:20pm, 北京时间 10:20am.


报名请 email 到我的邮箱: good.goodwish@gmail.com

EPI 的亚马逊链接, https://www.amazon.com/dp/1537713949, 评价还是不错的.


Reference:

EPI Judge:
http://elementsofprogramminginterviews.com/2018/01/30/2018-01-30-judge-beta/
https://github.com/adnanaziz/EPIJudge

contents 内容主体框架: (内容在不断完善当中)

I Data Structures and Algorithms 

1 Primitive Types

1.1 Computing the parity of a word 

2 Arrays

2.1 The Dutch national flag problem

3 Strings
4 Linked Lists
5 Stacks and Queues
6 Binary Trees
7 Heaps
8 Searching
10 Sorting
11 Binary Search Trees
12 Recursion
13 Dynamic Programming
14 Greedy Algorithms and Invariants
15 Graphs
16 Parallel Computing 

II Domain Specific Problems 

17 Design Problems

17.1 Design a system for detecting copyright infringement

18 Language Questions

18.1 Closure

18.2 Shallow and deep copy

19 Object-Oriented Design
20 Common Tools

III The Honors Class

21 Honors Class
21.2 Compute the maximum product of all entries but one
....

Symmetric Tree 解题分析和体验

昨天晚上讲一个 linkedin 的 easy 题， Symmetric Tree.

有 4 种解法。 入门学习和复习不错。

谢谢各位来捧场，运气好，代码一遍通过。 

谢谢坛主和同学们的鼓励。咱新年做简单题，就是找找自信。哈哈哈。

延续前两天知乎的帖子，说到我，理解力和抽象能力差，记忆力也差。

只能靠毅力，依靠咱们这个社区，互相加油督促，帮助前进。

我自己挺喜欢顿悟的，每次突然打通一个环节，都要高兴一阵子。

看了帖子，才知道 顿悟等于理解力差和抽象能力差。 汗颜 😅

我用自己的土办法递归和循环两种方法（global stack 存储所有节点值），做完此题以后，偶尔看到 Gavin Fish 的思路。先是惊喜，然后是感到惭愧。

惊喜我一看到 function definition, 就顿悟了，打通任督二脉，后面的代码都不需要看了。 

（不过， 顿悟 = 理解力和抽象能力差，嘿嘿 ）

函数定义 是 令狐冲老师说的递归三要素，能够定义好 function type (input, output) 还真是特别重要。

惭愧的是 Gavin Fish 的代码量只有咱的三分之一，真是简洁。我就喜欢简洁明了的代码。

我判断了那么多边界条件，人家两行代码就全部解决了。

简明的代码，容易理解，还容易测试，不易出错。

抽象能力太重要了，能够把各种边界条件归类并用简明的代码处理，就是一种抽象能力。

另外, 视频座谈的时候，我个人喜欢观众语音发言提问，多多交互。

好比说相声，有人递话和提问，故事才容易自然发展下去。

同学们的评论：

• 赞多思路总结 把树类型的各个常用解法都用了一遍 非常棒的练习方式.
• 题目做透，举一反三.
• 每一道题其实一体多解是很好的方法复习之前的知识点.
• 我还一个建议，说完算法之后报时间和空间复杂度，这样可以尽快和面试官确认是否是他们理想的复杂度值.

参考：

• 知乎，刷 LeetCode 吃力正常吗？https://www.zhihu.com/question/31092580/answer/439473636
• Symmetric Tree · LeetCode-Python https://shenjie1993.gitbooks.io/leetcode-python/101%20Symmetric%20Tree.html … 递归搜索简单明了。值得学习。

prep coding interview in first round 如何开始准备算法面试?

直接看答案.

因为你没有:
* 特定的算法，数据结构.
* 正确的思维方法 和 思维体系.
* 最优解
* 做题的感觉，代码从哪里开始

面试是考你如何运用算法和数据结构，不是考你创造发明算法。

这两天学到的。特别好。
看答案, 看答案.
第一遍：直接看答案.

有战友问: 看完答案以后呢?
A: 练习`解题`啊.  每道题练习 3~5次, 熟练到这个程度：`hard 题, 15分钟 AC提交`.

Q：第一遍看答案解题，看多少道呢？

A：Leetcode Top 500 道吧。

2018 first mock coding interview

周五进行了一场模拟面试，S是应聘者，咱做考官。

首先说我自己，我一直就没有进入角色，都不知道怎么开展技术面试，我 2015年 在德银面试委员会待过一段时间，面试了40多个候选人，主要就问软技能的问题。那时候我还不会写程序。

下面是我面试过程中的一些感想和议论。

我觉得有一个手写版比较好，像九章令狐冲老师用的，讲解题目，解释原理和概念，很方便，不知道哪里可以买到 价廉物美的先试用？

战友 S，沟通能力特别强，始终都能把自己的意思清楚的表达出来，就是说话的时间多了，写题的时间就少了。

九章老师关于沟通的时间分配是这样讲的:

• 开始，问清楚题目的需求，确保自己完全理解需求，不要主观臆断，然后说出自己的解决方案的思路，征求考官的认可，也可以说出多个方案跟考官商议，共同确定一个较好的实现方法。要点是把考官当成自己未来的同事，你跟同事沟通的时候也要简洁明了，既要说清楚，又不能过于繁琐。
• 然后就让考官去玩手机，自己闷头做题。
• 做完题以后再跟考官简短说个总结就可以了，如果还有时间，可以解释一下代码中比较难以理解的部分。

S同学 分析能力强，思路清晰。

下面这些建议说给我，供给战友们参考。

各种常用基本算法和数据结构 需要多练习，直到熟练掌握，倒背如流。

多学习各种常用的优质模版代码，简短而易读，不容易出错，易于诊断。
代码长了，逻辑复杂，就容易出错。
多仿照练习优质模版代码，4遍5遍，直到熟练掌握。

S同学 大有可为，我们一线大厂见。

再加一句：  S同学的英语比我好多了，阴阳顿挫，发音清晰。

coding interview chat 面试算法座谈

各位老大好，

近期咱不定期的周一周三,进行面试算法解题讲座, 针对一流软件公司的面试题。

欢迎前来当听众和提问。

今天会谈到 基本数据结构：binary heap.
中级数据结构: hash heap, segment tree
和高级数据结构 segment tree with lazy propagation

(各种数据结构都是一层层深入演进，咱尽力解释的简单清晰).

会谈到一个算法: 扫描线算法,

有了这些基础知识以后，会打代码解答一个超高难度问题： 

天际线, https://www.lintcode.com/problem/the-skyline-problem

heap 推荐学习资料:

• Binary Heaps
  tube, https://www.youtube.com/watch?v=YXCeM7w1630
• 3. Heap sort
  tube, https://www.youtube.com/watch?v=H7rI5qtsf_Y

Best Time to Buy and Sell Stock series.

股票收益最大化，一系列有五六个题目。

这里仅回顾我前进中的心路, 停下来, 做个小结。
未来两个月后，下一步，我会重新训练解题思路。

正文开始了，

Q: 允许交易两次的股票收益最大化，这道题是不是枚举/模拟类题目？
Q: 这个题我自己没有想出答案。有没有什么指南训练一下，可以提高解题水平？

我用的是两端扫描的办法，从左和从右扫描得到，每端的依次的最大收益值，然后再扫描一次，两边相加求最大值，时间复杂度还是o(n)。
A：左边和右边加起来，找到全局最大化。

去年夏天，第一次面试前端，问了普通数字和罗马数字转换，我就没有想出解题思路。
普通数字和罗马数字转换，应该是标准的模拟/枚举题目。

2. Best Time to Buy and Sell Stock with Transaction Fee

这道题我毫无头绪。卡住两三天。
这一类题目，该怎么学习和训练呢？

大师点拨：
A：
This is a DP and Greedy related problem, I don't think you learn the algorithm yet.
It will be taught in advanced algorithm jiuzhang class. I will suggest you to skip.

At this moment, you are not the scientist who can invent the algorithm.
In fact almost all people are NOT. This is why...

😇 谢谢分析和打气鼓励。

据说最好的学习策略，就是不断的取得小胜利，我在这个问题上两三天取得了一个大失败，觉得很受挫折。
猛一看像是个简单的小问题，就想给他一举拿下。
这是九章算法班，最后一节课前缀和知识点，引出了一个股票交易问题，没想到延伸出了五六个问题，整个做法思路都变样了。
特别是这一道题，facebook考过，我就想着应该做出来。也算一个准备。

我的直观解法，通过了一多半测试，总是不甘心。
谢谢大师点拨，让我从死胡同里解脱出来，摆正心态，继续前进。

附录:

The hardest problem in this series.

393. Best Time to Buy and Sell Stock IV
lc, https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-iv

constraint: trade k times, get max gain.

idea:

我自己都没有搞清楚是怎么通过测试验收的. 虽然代码是我从头写出来的。

essential code:

    def maxProfit(self, k, prices):
        if not prices or len(prices) == 1:
            return 0
        buy = -prices[0]
        sell = 0
        if k > len(prices):
            for price in prices:
                buy = max(buy, sell - price)  # core code 
                sell = max(sell, buy + price)  # core code 
            return sell
        buys = [-float("inf")] * k
        sells = [0] * k
        for price in prices:
            buys[0] = max(buys[0], -price)
            for i in range(k):
                if i > 0:
                    buys[i] = max(buys[i], sells[i - 1] - price)
                sells[i] = max(sells[i], buys[i] + price)
        return sells[k - 1]

Python read config .ini and connect to a database

This is my first Python application.

There are some knowledge points inline with code.

..
The souce code is here, https://github.com/goodgoodwish/code_tip/blob/master/python/db.py .
.

.