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 .
.

.

Thoughts and an example on Expression-Oriented Programming

Here is the code, to read password from .pgpass to connect o a PostgreSQL database.

object DbUtil {
  def dbPassword(hostname:String, port:String, database:String, username:String ):String = {
    // Usage: val thatPassWord = dbPassword(hostname,port,database,username)
    // .pgpass file format, hostname:port:database:username:password
    val passwdFile = new java.io.File(scala.sys.env("HOME"), ".pgpass")
    var passwd = ""
    val fileSrc = scala.io.Source.fromFile(passwdFile)
    fileSrc.getLines.foreach{line =>
      val connCfg = line.split(":")
      if (hostname == connCfg(0)
        && port == connCfg(1)
        && database == connCfg(2)
        && username == connCfg(3)
      ) { 
        passwd = connCfg(4)
      }
    }
    fileSrc.close
    passwd
  }

  def passwordFromConn(connStr:String) = {
    // Usage: passwordFromConn("hostname:port:database:username")
    val connCfg = connStr.split(":")
    dbPassword(connCfg(0),connCfg(1),connCfg(2),connCfg(3))
  }
}

Thoughts.

* foreach v.s.  map().filter()(0) . e.g.: List(1,2,3).filter(_ > 0)(0)

* var passwd, v.s.  val passwd inside of foreach.

* is it good to do chain of method style?

* how to break when find one, in a for loop ?

import util.control.Breaks._
breakable {
for (i <- 1 to 10) {
println(i)
if (i > 4) break // break out of the for loop }
}

* other improvement ?

From Python chapter 2 code solution

Here is my answer for book:

从Python开始学编程

Chapter 2, Appendix A, Exam.

https://book.douban.com/subject/26919485/

..

from itertools import repeat

def gen():

int_rate = [0.01, 0.02, 0.03, 0.035, 0.05]

for r in int_rate:

yield r

for r in repeat(0.05):

yield r

def num_year_pay() :

house_price = 500000

year_pay = 30000

year_n = 1

rem = house_price

print(year_pay)

for r in gen():

if rem <=0:

break

print(r)

rem = rem * (1 + r) - year_pay

year_n = year_n + 1

print(rem)

return year_n

if __name__ == "__main__":

print("Number of years to pay loan: ", num_year_pay())

Number of years to pay loan: 31

work with a custom schema with Spark loading CSV file

Here's how you can work with a custom schema, a complete demo:

Unix shell code,

$>

echo "
Slingo, iOS 
Slingo, Android
" > game.csv

Scala code:

import org.apache.spark.sql.types._

val customSchema = StructType(Array(
  StructField("game_id", StringType, true),
  StructField("os_id", StringType, true)
))

val csv_df = spark.read.format("csv").schema(customSchema).load("game.csv")
csv_df.show 

csv_df.orderBy(asc("game_id"), desc("os_id")).show
csv_df.createOrReplaceTempView("game_view")
val sort_df = sql("select * from game_view order by game_id, os_id desc")
sort_df.show 

Reference,

https://stackoverflow.com/questions/39926411/provide-schema-while-reading-csv-file-as-a-dataframe/48178180#48178180

spark 2.2.1 installation guide on Mac

// blog install spark 2.2.1 on Mac

Spark is incompatible with Java 9.

Install Java 8 instead.

# to uninstall Java 9

brew cask uninstall java

Here is the complete and simple installation steps for spark on Mac :

brew tap caskroom/versions

brew cask search java

brew cask install java8

# brew install scala # You might need these step,

brew install apache-spark

# Start spark shell,

./bin/spark-shell --master local[2]

./bin/spark-shell --master local[1]

Scala access PostgresQL database complete demo

// Connect o PostgresQL

$>

brew info postgres

// Start manually:

pg_ctl -D /usr/local/var/postgres start

// or, write stats to log,

pg_ctl -D /usr/local/var/postgres -l /usr/local/var/postgres/server.log start

// Stop manually:

pg_ctl -D /usr/local/var/postgres stop

// Status

pg_ctl -D /usr/local/var/postgres status

createdb scala_db

createuser scala_user

psql -U scala_user -d scala_db

SQL>

create table emps

(

id integer,

last_name varchar(100),

email varchar(200),

gender varchar(10),

department varchar(100),

start_date date,

salary integer,

job_title varchar(100),

region_id int,

primary key (id)

);

insert into emps values (1,'Kelley','rkelley0@sours.getString("country")ndcloud.com','Female','Computers','10/2/2009',67470,'Structural Engineer',2);

insert into emps values (2,'Armstrong','sarmstrong1@infoseek.co.jp','Male','Home','3/31/2008',71869,'Financial Advisor',2);

insert into emps values (3,'Carr','fcarr2@woothemes.com','Male','Home','7/12/2009',101768,'Recruiting Manager',3);

insert into emps values (4,'Murray','jmurray3@gov.uk','Female','Jewelery','12/25/2014',96897,'Desktop Support Technician',3);

insert into emps values (5,'Ellis','jellis4@sciencedirect.com','Female','Home','9/19/2002',63702,'Software Engineer III',7);

$>

// scala -classpath ~/app/lib/postgresql-42.1.1.jre6.jar

bin/spark-shell -classpath ~/app/lib/postgresql-42.1.1.jre6.jar

// Scala code,

import java.sql.Driver

import java.sql.DriverManager

import java.sql.Connection

val driver = "org.postgresql.Driver"

val url = "jdbc:postgresql://localhost/scala_db?user=scala_user"

Class.forName(driver)

var connection: Connection = null

connection = DriverManager.getConnection(url)

val statement = connection.createStatement()

val resultSet = statement.executeQuery("select * from emps limit 5")

resultSet.next

resultSet.getString("last_name")

resultSet.getString("department")

while ( resultSet.next() ) {

val last_name = resultSet.getString("last_name")

val dept = resultSet.getString("department")

printf("%s: %s \n", dept, last_name)

}

// Prepare SQL statement

val queryStr = "select * from emps where department = ? "

val ps = connection.prepareStatement(queryStr)

ps.setString(1, "Home")

val rs = ps.executeQuery()

while ( rs.next() ) {

val last_name = rs.getString("last_name")

val dept = rs.getString("department")

val startDate = rs.getString("start_date")

printf("%s: %s \t %s \n", dept, last_name, startDate)

}

JavaScript Closures: setTimeout and loop

Problem:

for (var i = 0; i < 3; i++) {
    setTimeout(function() {
        console.log("My value: " + i);
    }, 1);
}

> 

My value: 3

My value: 3

My value: 3

}

Why:

Variable Global scope, and JavaScript asynchronous event loop single thread execution.

Solution:

// Block scope, ES2005

for (let i = 0; i < 3; i++) {

    setTimeout(function() {

        console.log("My value: " + i);

    }, 1000);

}

//Immediately Invoked creation, and function scope.

for (var i = 0; i < 3; i++) {

    setTimeout((function(pNum) {

        return function() {

            console.log('i: ', pNum)

        }

    })(i), 1000);

}

//  IIFE (Immediately Invoked Function Expression)

for (var i = 0; i < 3; i++) {

    (function(pNum = i) {

        setTimeout(

            function() {

                console.log('i : ', pNum)

            }, 1000)

    })(i);

}

Enjoy the sunshine,

Running jupyter notebook with pyspark shell on Windows 10

# Running jupyter notebook with pyspark shell.

This notebook will not run in an ordinary jupyter notebook server.
Here is how we can load pyspark to use Jupyter notebooks.
On Mac, Linux, something like this will work:
On Windows 10, it works at 2017-Nov-21.

# Install Anaconda

https://www.anaconda.com/download/

## Run "Anaconda Prompt" to open command line:

%windir%\System32\cmd.exe "/K" E:\Users\datab_000\Anaconda3\Scripts\activate.bat E:\Users\datab_000\Anaconda3

Note: above commands are in one single line.

## Then set system environment variables:

rem set PYSPARK_PYTHON=python3
set PYSPARK_DRIVER_PYTHON=jupyter
set PYSPARK_DRIVER_PYTHON_OPTS=notebook

## start pyspark

E:\movie\spark\spark-2.2.0-bin-hadoop2.7\bin\pyspark.cmd

Reference:

Prerequist: http://mujiang.blogspot.com/2017/11/complete-spark-220-installation-guide.html

Complete spark 2.2.0 installation guide on windows 10.

Goal
----
The step by step Apache Spark 2.2.0 installation guide on windows 10.


Steps
----
Download winutils.exe from git, https://github.com/steveloughran/winutils
E.g.: https://github.com/steveloughran/winutils/blob/master/hadoop-2.7.1/bin/winutils.exe

mkdir /tmp/hive

winutils.exe chmod -R 777 E:\tmp\hive
or
winutils.exe chmod -R 777 /tmp/hive

set HADOOP_HOME=E:\movie\spark\hadoop
mkdir %HADOOP_HOME%\bin
copy winutils.exe to %HADOOP_HOME%\bin

Download Spark: spark-2.2.0-bin-hadoop2.7.tgz from http://spark.apache.org/downloads.html
cd E:\movie\spark\
# in MINGW64 (git / cywin)
tar -zxvf spark-2.2.0-bin-hadoop2.7.tgz
# or use 7-Zip

cd E:\movie\spark\spark-2.2.0-bin-hadoop2.7
bin\pyspark.cmd



Notes
----
%HADOOP_HOME%\bin\winutils.exe must be locatable.

Folder "E:\movie\spark\hadoop" is just an example, it can be any folder.

Spark runs on Java 8+, Python 2.7+/3.4+ and R 3.1+.
http://spark.apache.org/docs/latest/

Reference
----
https://wiki.apache.org/hadoop/WindowsProblems


Here is the example output when start pyspark successfully:

E:\movie\spark\spark-2.2.0-bin-hadoop2.7>bin\pyspark.cmd

Python 3.6.1 (v3.6.1:69c0db5, Mar 21 2017, 18:41:36) [MSC v.1900 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
Using Spark's default log4j profile: org/apache/spark/log4j-defaults.properties
Setting default log level to "WARN".
To adjust logging level use sc.setLogLevel(newLevel). For SparkR, use setLogLevel(newLevel).
17/11/17 19:07:31 WARN NativeCodeLoader: Unable to load native-hadoop library for your platform... using builtin-java classes where applicable
17/11/17 19:07:36 WARN ObjectStore: Failed to get database global_temp, returning NoSuchObjectException
Welcome to
      ____              __
     / __/__  ___ _____/ /__
    _\ \/ _ \/ _ `/ __/  '_/
   /__ / .__/\_,_/_/ /_/\_\   version 2.2.0
      /_/

Using Python version 3.6.1 (v3.6.1:69c0db5, Mar 21 2017 18:41:36)
SparkSession available as 'spark'.
>>>
>>> textFile = spark.read.text("README.md")
17/11/17 19:08:03 WARN SizeEstimator: Failed to check whether UseCompressedOops is set; assuming yes
>>> textFile.count()
103

>>> textFile.select(explode(split(textFile.value, "\s+")).name("word")).groupBy("word").count().show()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'explode' is not defined

>>> from pyspark.sql.functions import *
>>> textFile.select(explode(split(textFile.value, "\s+")).name("word")).groupBy("word").count().show()
+--------------------+-----+
|                word|count|
+--------------------+-----+
|              online|    1|
|              graphs|    1|
|          ["Parallel|    1|
|          ["Building|    1|
|              thread|    1|
|       documentation|    3|
|            command,|    2|
|         abbreviated|    1|
|            overview|    1|
|                rich|    1|
|                 set|    2|
|         -DskipTests|    1|
|                name|    1|
|page](http://spar...|    1|
|        ["Specifying|    1|
|              stream|    1|
|                run:|    1|
|                 not|    1|
|            programs|    2|
|               tests|    2|
+--------------------+-----+
only showing top 20 rows

>>>

from pyspark.sql.functions import *


# module for pyspark,
from pyspark.sql import SparkSession
from pyspark.sql.window import Window
from pyspark.sql.functions import *
from pyspark.sql import *

Employee = Row("empno", "ename", "job", "mgr", "hiredate", "sal", "comm", "deptno")

emp1 = Employee(7369, "SMITH", "CLERK", 7902, "17-Dec-80", 800, 20, 10)
emp2 = Employee(7876, "ADAMS", "CLERK", 7788, "23-May-87", 1100, 0, 20)

df1 = sqlContext.createDataFrame([emp1, emp2])

sparkSession = SparkSession.builder.master("local").appName("Window Function").getOrCreate()

empDF = sparkSession.createDataFrame([
      Employee(7369, "SMITH", "CLERK", 7902, "17-Dec-80", 800, 20, 10),
      Employee(7499, "ALLEN", "SALESMAN", 7698, "20-Feb-81", 1600, 300, 30),
      Employee(7521, "WARD", "SALESMAN", 7698, "22-Feb-81", 1250, 500, 30),
      Employee(7566, "JONES", "MANAGER", 7839, "2-Apr-81", 2975, 0, 20),
      Employee(7654, "MARTIN", "SALESMAN", 7698, "28-Sep-81", 1250, 1400, 30),
      Employee(7698, "BLAKE", "MANAGER", 7839, "1-May-81", 2850, 0, 30),
      Employee(7782, "CLARK", "MANAGER", 7839, "9-Jun-81", 2450, 0, 10),
      Employee(7788, "SCOTT", "ANALYST", 7566, "19-Apr-87", 3000, 0, 20),
      Employee(7839, "KING", "PRESIDENT", 0, "17-Nov-81", 5000, 0, 10),
      Employee(7844, "TURNER", "SALESMAN", 7698, "8-Sep-81", 1500, 0, 30),
      Employee(7876, "ADAMS", "CLERK", 7788, "23-May-87", 1100, 0, 20)
])


partitionWindow = Window.partitionBy("deptno").orderBy(desc("empno"))
sumTest = sum("sal").over(partitionWindow)
empDF.select("*", sumTest.name("PartSum")).show()

partitionWindowRow = Window.partitionBy("deptno").orderBy(desc("sal")).rowsBetween(-1, 1)
sumTest = sum("sal").over(partitionWindowRow)
empDF.select("*", sumTest.name("PartSum")).orderBy("deptno").show()