Dude, I am from Detroit

在 功夫梦 中有个这样的场景, 当主人公黑人小朋友试图在去中国的飞机上用刚学的稚嫩的中文试图和旁边一个黄种人小胖聊天的时候, 小胖说, “Dude, I am from Detroit.”

诶, 好像和我要说的主题没有关系? 好像是噢, 哎, 博客不是写作文, 随意一些.

现在在多伦多机场的候机大厅, 这次的路线是 toronto–vancouver–seattle, 之前有过一次完全一样的路线, 所以完全不会陌生, 昨天出去BBQ然后明凯好心的收留我在他家过, 和他家的猫JAVA(yeah, a cat called Java!) 厮杀了一个晚上之后, 突然觉得养个小动物真是很好玩的一件事情, 当然, 他家一如既往的让人觉得温暖无比.

我会继续posting, 看看这第二次seattle的行程会有什么不一样的地方.

Go, go, go!

昨天面试结束, 十分疲倦, 虽然事后想起来还是干了很多二事, 也有几倒题目没有回答的那么完善, 但是比起之前微软的面试, 我觉得我至少把我的水平发挥出来了.

到最后一题的时候真得很累, 超级赛亚人的身体也差点坚持不住了.  西雅图的downtown很漂亮, 不过往往是边这条街很繁华, 马上下一条街就很荒凉, 就像酒店的正面这一个区域很多高楼大厦, 不过背面就很破落. 这是故意的?

谢天谢地, 这里的加拿大移民局的工作人员态度特别好, 让我很是感动, 再过半个小时, 我就可以拿到我的新的study permit了, 在美国申请加拿大的study permit, 真是头一遭, 这样就不会和海关有什么冲突了, oh yeah!

顺便说一说这个移民局, 他在一栋大厦的一层楼, 很小的一个房间, 这大概是我见过最不严肃的政府门面了把, 里面没有像在美国海关那种荷枪实弹的壮汉, 只有一个见到谁都乐呵呵笑, (尤其见到美女…)的黑人大叔, 也不像申美签的多伦多大使馆, 书包,手表,手机都能带进去. 最要命的是, 里面的吵闹程度大概可以和菜市场有的一比, 黑人大叔是不管事的, 只有那些工作人员一遍一遍的重复, 不要太吵, 要不然请你们出去.

不过貌似没人听…

to be continued

顺利拿到visa, 可以会加拿大了, 这之前去starbucks逛了逛, 去一个名叫做japanese cuisine的地方吃了中饭, 再次确认了我的一些想法:

1. 国外的sushi, 除非是很高级的, 一定是中国人开的, 国内的就不说了

2. 热门景点周围的餐馆, 最好不要进, 要不然等死你, 这点全世界都一样.

唯一的亮点是我点啤酒的时候服务员执意要看我的ID, 我又年轻了阿, 哈哈

吃完在晃眼的阳光下有些累, 要找个地方休息休息.

keep posting…hope my phone will ring this afternoon…

没那么简单

好久没有更新了, 我不能这么懒. 毕竟我的博客还是有厉害的人物订阅的, 前面一篇写Dynamic Programming还没有写完, 我有空就补上.

日子过得还是有些昏昏谔谔, 但是总算是出现了点规律, 工作呢还在继续努力, 昨天去面试, 做着他们公司的试卷, 3个小时都没有做完, 有一道题目令人发指的竟然写了9页纸, 我自己都有些尴尬了, 最后一题实在没力气了, 大概没吃中饭的缘故把, 直接写上”too tired to do that, sorry”, 然后交卷走人了, 当时觉得自己挺英勇的. 现在想想挺傻的, 多写些字能怎么样呢, 对吧.

生活中倒是没有太多值得庆祝或者大书特书的地方, 只是觉得多伦多的车挺难开的, A&F的衣服挺显肌肉的(又有了健身的动力), 最近和朋友网络聊天还蛮开心的, 室友大官人洗澡的时候练功竟然把旁边的墙都打穿了, 黄小琥唱歌真是很好听, inception真是太让人期待了.

遇到了孙小胖, 竟然得到他下二周要结婚的消息, 真得好恭喜他, 他们高中就在一起了, 是我见过身边最踏实的感情, 这样的爱情故事实在太稀有太难得, 我虽然遇不到但是看见身边朋友能遇到也替他们高兴, 祝他们幸福.

BTW, 大官人, 那道数组连续乘最大的问题, 我刚刚编出来了, LOL

以后会加油更新, 睡觉睡觉.

每日5题–0710

今天说一些DP(Dynamic Programming)的题目

我对DP的理解, 如果一个问题可以从optimal substructure推出, 那么就可以考虑用DP做, DP的优点, 比较简单直接好理解,

最难的部分应该是找到那个递推表达式.

1. LCS(longest common sequence)
给出数组 a[M], b[N], 找出, 他们之间最长的common sequence, 比如
a = “apple is fashion”
b = “google is not evil”

那么得到的输出结果就是

The LCS number is 7
“le is n”

可见这两句看上去没有什么关系的话还是有一定联系的, lol

如果定义 F(i, j) 是a[0]….a[i], 和 b[0]…b[j]之间的common sequence 的个数

所以

F(i,j) =\left\{\begin{matrix}F(i-1, j-1)+1&if\quad a[i] = b[j] \\max\{F(i-1, j), F(i, j-1)\}&if\quad a[i] !=b[j]\\\end{matrix}\right.

如果两个数组的长度分别是LEN1, LEN2, 那么时间复杂度是O(LEN1*LEN2), 然后还需要O(LEN1*LEN2)的空间复杂度.

2. 操作次数问题(operation)

如果有两个字符串str1, str2, 怎么用最少的操作让str1 变成 str2

你可以利用的操作有 1. 插入(insert) 2. 替换(replace) 3. 删除(delete)

再次开动脑经, 如果记录 F(i, j) 为str1[0…i]变成str2[0….j]所需要的操作的数目.

那么就有

F(i,j) =\left\{\begin{matrix}F(i-1, j-1)&if\quad str1[i] = str2[j] \\min\left\{\begin{matrix}F(i-1, j) (deletion)\\ F(i, j-1) (insertion)\\F(i-1,j-1) (replace)\\\end{matrix}\right.+1&if\quad str1[i] !=str2[j]\\\end{matrix}\right.

时间复杂度是 O(LEN1*LEN2)