Thursday, September 20, 2018

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]

Friday, April 13, 2018

Thursday, April 05, 2018

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 ?

Wednesday, March 14, 2018

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

Thursday, January 11, 2018

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,