11601 Week 5 - Recursion

作者 QIFAN 日期 2016-09-29
11601 Week 5 - Recursion

CMU 11601 Coding BootCamp


本周递归。

作业涉及了递归的时间复杂度计算和基本思想的理解。

知识点整理

In Class Practice

  1. Zombie Cluster
    比较有趣的题。老师给的解法是BFS

  2. Pascal’s Triangle
    课上的题给出了公式,是应该用递归做的,而我偷懒用了数组 = =

Homework

Part 1

  1. 时间计算

  2. Matched delimiters. check一串括号是否为成对,若成对返回最长没有关闭的左括号数。
    经典的stack题,增加的一点是在遇见右括号时要track stack的size,存下max。
    有两点易错:stack为空时不能peek和pop,最后若stack不为空,也是unmatched。

Part 2

  1. 时间计算

  2. Tuple is possible.
    数字对(x, y)可进行如下变换:

    (x, y) --> (x+y, y)
    (x, y) --> (x, x + y)

    给四个数字a, b, c, d,判断(a, b)能否最终变换为(c, d)
    递归。注意base case。{(x, y), (x+y, y)}, {(x, y), (x, x+y)}{(x, y), (x, y)}true,最后一种容易忘记。若a>cb>dfalse

Shuffle

Interviewee

Question 1: Power Set (cc 150 8.4)

总结:一拿到题目就在想这不是一个典型的recursion么,然后就想不出base case是什么,最后还是用了iterative的方法。听面试小哥说最快的是位运算的方法。

Question 2: No Test Tools (cc 150 11.4)

How would you load test a webpage without using any test tools?

总结:第一次拿到这种题目,一脸懵逼。但是实际上只要考虑一下反应时间,吞吐量,capacity之类。

Question 3: Call Center (cc 150 7.2)

总结:虽然做过两次了。但是竟然还是没长记性。

Interviewer

Question 1: Queue via Stacks (cc150 3.4)
总结:小哥的思路很清晰,先说了互换的思路,然后问了一些细节,比如type,写之前也列出了要implement的方法。

Question 2: Circular Array (cc150 7.9)
总结:明白efficient rotate的意思,和Iterable类(iterator(), next, hasNext())。尤其hasNext()设置offset时要注意,第一个元素不要忘记数。

Question 3: Permutations with Duplicates (cc150 8.8)
总结:比较难的题。