Introduction
It is Sunday morning 8:00 AM. I had chance to talk to my ex-coach forty minutes about a few algorithms and he also gave me his analysis. He is in the city of Beijing and I am in the city of Vancouver.
It is so surprising to have a coach and then I know what to do next. I like to write down the conversation by the time.
Time line
8:00 - 8:10
I described the algorithm called to define an iterator for list of iterators. He said that he did not really understand the problem, so I explained the problem to him. There are two possibilities, one is all lists are sorted, second one is not sorted. If all lists are sorted, then define a minimum heap. If all lists are not sorted, then put everything in the minimum heap. The time complexity should be nlogm, n is total nodes in all lists, m is number of lists.
He said that if the list is not sorted, it can be sorted using in place, like quick sort as well. ( I like the idea and did not think about it at all. )
你也可以把一个 iterator 排好序， 用 inplace, quick sort.
I told him that I studied the algorithm one day before, called Merge k sorted lists in Leetcode.
The coach said that you have to calm down, work on more Leetcode easy level algorithm. You can finish 40 algorithms in one month (July 10 - August 5), one year you can finish 400 algorithms. Overall, if you do not practice enough, you will be nervous, or all kinds of problems.
Julia： 我感觉紧张。 我照你说的去做， 刷了四十道题。 二道题都在里面。
Coach： 刷题没有刷够。 就会出各种问题。 就像高考， 你没有考好。 不是再考一次， 应该准备一年， 基本功练好。 中国人就只能刷题。
Coach： 你现在一个月刷了 40 道题， 一年就能刷400 道题。你可以写邮件要求第二次，但是只看现场表现。
Julia： 刷题感觉累。 周六就刷了五道题。
Coach：不能赶速度。 有时候我刷题也感觉累。 动脑太多。
8:10 - 8:20
我开始讲bad version 这道题。 我想用数值， 提醒用数组， 预处理就用了时间 O(N). 我用了二个变量， 好的和坏的version。 用二分法， 找中间值。 如果是坏的， 看左边的邻居是好还是坏。
这道题从开始到结束就用了20分钟。 我就没有给机会回到第一道题。 不停地提问题。
8:20 - 8:30
我开始讲 infix expression to construct binary expression tree. 用堆栈来做。(1+2), 把(1+2推进栈， 碰到)， 开始出栈。
其实我想拿一部分分数， 没有用堆栈。不管如何，用堆栈。postfix 用堆栈。但是infix也是可以用堆栈， 你自己多用几个左右括号，就自己搞定规则。
coach： 可以转换成 postfix expression.
Julia: 不用转。 直接用堆栈。 反正用多余的左右() enforce priority. 多余的左右() 便宜。
8:30 - 8:40
Julia: 我开始讲刷题把一个BST转换成链表。 我开始把左子树换成链表， 连到右子树链表。 花了一个小时。 通不过。 换一种思路， 用二个变量， 前一个和当前， 五分钟写出来。 觉得不对， 把第一个思路做通。 用中序做了， 想想后序也有可能做通。
coach: 刷题把几种思路都做了。 有时刷了100道， 其实就刷了10道。 你把多个思路都刷了， 下一道就可能有同样的思路。
Julia： 我觉得这次刷四十道题， 刷出兴趣来了。 以前刷题少， 因为没有体会到乐趣和好处。 还有就是刷题好的多的， 就不在朋友圈里。
Julia： 我又讲一道难题， 一年前刷了， 几个月前又研究了， 写了十个博客。各种想法。 结果还是不会做。 这次我就记住一个例子， 自己解释如何用这个例子， 解释如何除去多余括号。链接在这：去除多余的左右括号。
Julia: 我还在做面试, interviewing.io, 我最近碰到一个Waterloo本科生， 做过二次谷歌实习。他解题就比较有策略。把问题弄清楚。
Julia： 我沟通问题， 一问一答。我有时回答问题。接着说。
coach：这个不好指导。只能靠多刷题。 题目见的多了，自然就会轻松应付。
No comments:
Post a Comment