几个面试题目（一）

2013/11/17 ztdiff， permutation， rotation， wordcount1条评论

tree depth

递归的版本很好写 depth = 1 + max{depth (left), depth (right)}，非递归可以类似 BFS 来做，最后出队的就是 depth 最大的。

site is slow

这个问题其实是个 open question，

首先应该了解现象，比如某人说慢，你是否能够重现
然后应该了解结构，比如系统是怎么搭的，有没有 load balancer，多少应用服务器，数据库在哪里等等
有了这些东西之后就应该开始排错，排错的意思就是你需要将问题定位到某些部件上，比如看看 load balancer 是否配置正确，对应的服务器有没有过载，数据库有没有出现问题，网络是否通畅等等

感觉主要跟面试官沟通了。一般做过一个完整的网站的人，每个地方有些什么 pitfall 可能都能搞清楚，因此就能说很多；相反如果一个人经验有限，这个问题就怕说不了几句话。

实现 wordcount

本质上这个问题就是数 character、word 和 line 的数目，这个可以看成是几个 pattern，之间存在迁移的时候就需要计数了。比如设计一个 Counter 类，有一个 read 方法读入一个字符，里面有个计数，结束后读出来即可。那么 character 的纯粹是 ++，后两者基本是根据读入字符做状态迁移：

struct Counter {
  int count = 0 ;
  virtual void
  read (char c) {
    ++ count ;
  }
} ;
struct WordCounter : public Counter {
  bool word = true ;
  static std::regex p = "\\S" ;
  virtual void read (char c) {
    if (word)
      if (c matched)
        return ;
      else {
        ++ count ;
        word = false ;
      }
    else
      if (c matched)
        word = true ;
      else
        continue ;
  }
} ;

类似的 line counter，之后就能写个 loop 喂数据了。

实现 diff

diff 也算是常见的工具了，生成 diff 却不是那么容易，其实也有很多种 diff，首先应该问清楚需要的哪种 diff，比如有的情况只有 delete 和 insert，有的还加上了 change，生成 diff 本身是一个优化问题，即通过给定的操作集合以及每个操作的代价，将一个文件变成另一个文件并且代价最低。这里我们认为操作是基于行的，比如一个文件表示为 $a_1, \ldots a_n$ ，另一个是 $b_1, \ldots, b_m$ ，记删除代价为 $C_d$ ，插入为 $C_i$ ，修改是一个函数 $C_c (a, b)$ （如果 a b 相同返回 0），很显然 $c[n, m] = \min\{c[n - 1, m] + C_d, c[n, m-1] + C_i, c[n-1, m-1] + C_c (a_n, b_m) \}$ ，所以这个是个 $m\times n$ 的表，如果需要 back track 的话另外需要记录每步操作用的是啥。

编程排错

给一个 n 行的程序，找里面的 bug（已知某一行出错导致的），假定你可以为某行添加 println 进行排查，添加这行的 cost 是 $a$ ，编译执行的代价是 $b$ ，问怎样设计调试过程让 worst case 的 cost 最低（如果没有 worst case 这个问题就复杂很多了）。问题是如果你看到第 k 行的 println 结果不对你只能说之前行存在 bug。这本质上是在 recursion tree 上加了额外的 cost，比如如果分 k 段，分别加一个 println，然后执行，这个 cost 每层是 ka，确定了范围后问题规模变成 n / k，因此迭代 $\log_k n$ 次，也就是说需要运行这么多次，于是最后的代价大概是 $ak \log_k n + b \log_k n = \frac{ak \ln n}{\ln k} + \frac{b \ln n}{\ln k}$ ，对 $k$ 求导 ms 是个超越方程？不晓得这题到底要问啥…

longest duplicate string

给定一个字符串，找到里面最长的重复的子串。据说解复杂度在 $O(N)$ 到 $O(N^3)$ 之间都有：

最暴力的莫过于穷搜，遍历每个子串这个过程就是 $O(N^2)$ ，同时比较相同长度的（k），这个可以从最长的子串（N – 1）开始做，一直到找到相同的停止，每次比较代价也是 k，所以整个的复杂度至少是立方级别
稍微通过存储可以加速到平方，即把遍历过的部分放到一个 hash 表里面，每次查表即可，这样有了个平方级别的
如果把字符串的后缀取出来，按照字母序排列，那么具有 duplicate 的子串就会聚合在一起，因此只需要比较前后两个字符串取公共子串的长度即可，排序是 $O(N^2 \log N)$ 的而后面扫一遍感觉还是 $O(N^2)$
后缀树等价于找内部最深的节点，构造树一般是 $O(N)$ 使用 Ukkonen’s algorithm，文献在此；

比较字符串自己和反序找公共子串是不足够的。对应的 suffix array 可能也有解法，感觉不如 suffix tree 直观。

in-place rotation

如果一个长度为 n 做 k 元素的 rotation，可以做 k 次 shift，代价为 $\min {k, n - k} n$ ，写起来简单。有没有别的策略？先讨论 $k < n/2$ 的情况，可以将 n 分为若干段 0 到 k – 1、k 到 2k – 1 等等，最后剩下的是 $\lfloor\frac{n}{k} \rfloor *k$ 到 n – 1，可以做块为 k 的平移，当头上到倒数第二块时，递归的做剩下的部分，这是个 tail recursion 所以没啥问题。

in-shuffle permutation of size 2n

简单的说就是 inplace 将 $a_1, \ldots, a_n, b_1, \ldots, b_n$ 弄成 $a_1 b_1, \ldots, a_n b_n$ ，一直一来只会平方和 $n\log n$ 的，今天看到了一个线性的，其实和以上 rotation 类似，归约的本质是通过线性算法将其降低到问题一半大小以下（rotation 归约为 $<\frac{n}{2}$ ），递归进行下去时就能得到线性的算法，那么如何归约其实是很具有技巧性的：这篇文章使用的技巧就是利用特殊情况 $2n = 3^m - 1$ 时对应的 permutation 的分解容易获得（因此可以直接使用 cycle 的 inplace 实现一个一个 cycle 的完成置换）这样一个事情将问题的大部分使用这个技巧直接求解，剩下的递归求解即可。

——————
And he set three days’ journey betwixt himself and Jacob: and Jacob fed the rest of Laban’s flocks.

scala 的 stream 应用一则

2013/05/082013/05/09 ztoptimization， searching发表评论

Stream 作为一个 lazy 的 list 最重要的就是获得一个逐渐自动生长的搜索空间，通过这个搜索空间我们可以求解多种有意思的问题。

优化问题的求解，在连续函数问题上，我们可以认为优化变量的取值本身构成一个状态，状态的迁移是通过诸如梯度、共轭梯度或者 Newton 法（or quasi-Newton）获得的更新量，这样当前的更新量实际可能依赖于前一个或者多个状态 or 搜索方向，我们大可以将 $(x_i, \Delta x_i)$ 作为这个 stream 的类型，而更新方程对应的就是生成这个 stream 的递归调用
图搜索问题，不少离散的问题最后可以归结到图上的搜索，经典的过河问题、水杯倒水和这次作业里面的游戏 Bloxorz，这类问题首先需要把实际问题通过 graph 来进行建模，也就是状态是什么，对应的操作会导致什么样的状态迁移，有了这些，加上初始状态，你就会得到或者 BFS/DFS 的搜索算法，如果你有一些 heuristic，还能改成 A* search。

我们来看看这些问题如何转换的。首先看问题：

过河问题：河一边若干人，一条船，一次载两人，人群里面有些 constraints，比如某两个人不能单独在某侧，问如何将这群人从一边运送到另一边
若干个已知总容量的杯子，可以将某些杯子倒满水，也可以倒掉，或者杯子之间互相倒，但是杯子没有刻度，问如何精确倒出指定容积的水
bloxorz 控制 1×2 的 block，在一个网格上通过翻转滚动且避免从不应该的位置掉下去，让它移动到指定的位置（这里不考虑原游戏的桥）

第一步就是抽象出来状态和迁移的可能

我们可以将河两侧的人作为两个 set，另船的位置，这两者是状态；操作包括运送船从一边到另一边，船上可以上 1-2 人，合法的操作不会导致每边出现违背要求的状态
杯子里面有多少水作为状态，操作有三种，将某个杯子倒满/倒空，从某个杯子倒入另外一个
当前 block 的位置作为状态，如用两个坐标表示，操作包括各个方向的运动，对这两个坐标分别操作即可

第二步确定起始状态：

开始状态是人都在一边，船也在那边；结束是都到另一边
开始是全空，结束是某一/几个杯子的水正好是指定大小
开始是指定位置，结束是指定位置

一般将状态作为一个类，对应的操作可以作为其成员或者另外的方法，通常复杂的情况需要写个判断是否合法的东西，通过这些方法或者函数我们就能生成新的状态，为了回溯，我们可能还会记录这个操作序列，有了这些我们就能产生 stream 了。就不贴程序了，某作业里面要求解 bloxorz 的问题如下

ooo-------
oSoooo----
ooooooooo-
-ooooooooo
-----ooToo
------ooo-

通过 BFS 输出如下：

block: Pos(1,2), Pos(1,3), 1 moves: List(Right)
block: Pos(2,1), Pos(3,1), 1 moves: List(Down)
block: Pos(1,4), Pos(1,4), 2 moves: List(Right, Right)
block: Pos(2,2), Pos(2,3), 2 moves: List(Down, Right)
block: Pos(2,2), Pos(3,2), 2 moves: List(Right, Down)
block: Pos(2,4), Pos(3,4), 3 moves: List(Down, Right, Right)
block: Pos(2,1), Pos(2,1), 3 moves: List(Left, Down, Right)
block: Pos(2,4), Pos(2,4), 3 moves: List(Right, Down, Right)
block: Pos(3,2), Pos(3,3), 3 moves: List(Down, Down, Right)
block: Pos(2,3), Pos(3,3), 3 moves: List(Right, Right, Down)
block: Pos(1,2), Pos(1,2), 3 moves: List(Up, Right, Down)
block: Pos(2,3), Pos(3,3), 4 moves: List(Left, Down, Right, Right)
block: Pos(2,5), Pos(3,5), 4 moves: List(Right, Down, Right, Right)
block: Pos(0,1), Pos(1,1), 4 moves: List(Up, Left, Down, Right)
block: Pos(2,5), Pos(2,6), 4 moves: List(Right, Right, Down, Right)
block: Pos(3,1), Pos(3,1), 4 moves: List(Left, Down, Down, Right)
block: Pos(3,4), Pos(3,4), 4 moves: List(Right, Down, Down, Right)
block: Pos(1,3), Pos(1,3), 4 moves: List(Up, Right, Right, Down)
block: Pos(1,0), Pos(1,1), 4 moves: List(Left, Up, Right, Down)
block: Pos(1,3), Pos(1,4), 4 moves: List(Right, Up, Right, Down)
block: Pos(1,3), Pos(1,3), 5 moves: List(Up, Left, Down, Right, Right)
block: Pos(2,6), Pos(3,6), 5 moves: List(Right, Right, Down, Right, Right)
block: Pos(1,5), Pos(1,5), 5 moves: List(Up, Right, Down, Right, Right)
block: Pos(4,5), Pos(4,5), 5 moves: List(Down, Right, Down, Right, Right)
block: Pos(0,0), Pos(1,0), 5 moves: List(Left, Up, Left, Down, Right)
block: Pos(0,2), Pos(1,2), 5 moves: List(Right, Up, Left, Down, Right)
block: Pos(2,7), Pos(2,7), 5 moves: List(Right, Right, Right, Down, Right)
block: Pos(3,5), Pos(3,6), 5 moves: List(Down, Right, Right, Down, Right)
block: Pos(1,1), Pos(2,1), 5 moves: List(Up, Left, Down, Down, Right)
block: Pos(3,5), Pos(3,6), 5 moves: List(Right, Right, Down, Down, Right)
block: Pos(1,4), Pos(2,4), 5 moves: List(Up, Right, Down, Down, Right)
block: Pos(1,1), Pos(1,2), 5 moves: List(Left, Up, Right, Right, Down)
block: Pos(1,4), Pos(1,5), 5 moves: List(Right, Up, Right, Right, Down)
block: Pos(0,0), Pos(0,1), 5 moves: List(Up, Left, Up, Right, Down)
block: Pos(2,0), Pos(2,1), 5 moves: List(Down, Left, Up, Right, Down)
block: Pos(1,5), Pos(1,5), 5 moves: List(Right, Right, Up, Right, Down)
block: Pos(2,3), Pos(2,4), 5 moves: List(Down, Right, Up, Right, Down)
block: Pos(1,1), Pos(1,2), 6 moves: List(Left, Up, Left, Down, Right, Right)
block: Pos(1,4), Pos(1,5), 6 moves: List(Right, Up, Left, Down, Right, Right)
block: Pos(2,7), Pos(3,7), 6 moves: List(Right, Right, Right, Down, Right, Right)
block: Pos(4,6), Pos(4,6), 6 moves: List(Down, Right, Right, Down, Right, Right)
block: Pos(4,6), Pos(4,7), 6 moves: List(Right, Down, Right, Down, Right, Right)
block: Pos(2,0), Pos(2,0), 6 moves: List(Down, Left, Up, Left, Down, Right)
block: Pos(2,2), Pos(2,2), 6 moves: List(Down, Right, Up, Left, Down, Right)
block: Pos(3,7), Pos(4,7), 6 moves: List(Down, Right, Right, Right, Down, Right)
block: Pos(3,7), Pos(3,7), 6 moves: List(Right, Down, Right, Right, Down, Right)
block: Pos(4,5), Pos(4,6), 6 moves: List(Down, Down, Right, Right, Down, Right)
block: Pos(1,0), Pos(2,0), 6 moves: List(Left, Up, Left, Down, Down, Right)
block: Pos(1,2), Pos(2,2), 6 moves: List(Right, Up, Left, Down, Down, Right)
block: Pos(0,1), Pos(0,1), 6 moves: List(Up, Up, Left, Down, Down, Right)
block: Pos(3,7), Pos(3,7), 6 moves: List(Right, Right, Right, Down, Down, Right)
block: Pos(4,5), Pos(4,6), 6 moves: List(Down, Right, Right, Down, Down, Right)
block: Pos(1,3), Pos(2,3), 6 moves: List(Left, Up, Right, Down, Down, Right)
block: Pos(1,5), Pos(2,5), 6 moves: List(Right, Up, Right, Down, Down, Right)
block: Pos(1,0), Pos(1,0), 6 moves: List(Left, Left, Up, Right, Right, Down)
block: Pos(0,1), Pos(0,2), 6 moves: List(Up, Left, Up, Right, Right, Down)
block: Pos(2,1), Pos(2,2), 6 moves: List(Down, Left, Up, Right, Right, Down)
block: Pos(2,4), Pos(2,5), 6 moves: List(Down, Right, Up, Right, Right, Down)
block: Pos(0,2), Pos(0,2), 6 moves: List(Right, Up, Left, Up, Right, Down)
block: Pos(2,2), Pos(2,2), 6 moves: List(Right, Down, Left, Up, Right, Down)
block: Pos(2,5), Pos(2,5), 6 moves: List(Right, Down, Right, Up, Right, Down)
block: Pos(3,3), Pos(3,4), 6 moves: List(Down, Down, Right, Up, Right, Down)
block: Pos(1,0), Pos(1,0), 7 moves: List(Left, Left, Up, Left, Down, Right, Right)
block: Pos(0,1), Pos(0,2), 7 moves: List(Up, Left, Up, Left, Down, Right, Right)
block: Pos(2,1), Pos(2,2), 7 moves: List(Down, Left, Up, Left, Down, Right, Right)
block: Pos(2,4), Pos(2,5), 7 moves: List(Down, Right, Up, Left, Down, Right, Right)
block: Pos(2,8), Pos(3,8), 7 moves: List(Right, Right, Right, Right, Down, Right, Right)
block: Pos(4,7), Pos(4,7), 7 moves: List(Down, Right, Right, Right, Down, Right, Right)
List(Down, Right, Right, Right, Down, Right, Right)

其实对 C/C++/Java 程序员来说这类问题也是类似求解的，但是会更依赖于 stack/queue 这些东西，而 scala 的 functional 的这面试图通过一些规则和诡异的 lazy 结构（stream）简化这些问题求解的细节。不得不说算是另外的一种思路吧

——————
When Esau saw that Isaac had blessed Jacob, and sent him away to Padanaram, to take him a wife from thence; and that as he blessed him he gave him a charge, saying, Thou shalt not take a wife of the daughters of Canaan;

几种 cache

2013/02/03 ztBelady algorithm， cache， LRU， MRU2条评论

不少应用里面希望用 cache 提高访问某些资源的速度，设计这类东西一般都是给一个 key，如果这个 cache 找不到自己里面的 value 就会调用 delegation 函数用来获得这个 value 并将其存放在自己的 cache 里面，如果 cache 已满，往往需要去掉其中一部分空出位置。理论上最优的 cache 料事如神知道什么时候能

实际的 cache 做不到这一点，或者用近似的概念或者根据特定问题来进行优化。比较常用的 cache 有 LRU、

cache 的概念

其实我们从前面的说明可以看出，一个 cache 需要：

提供类似 map 接口（key/value 映射），但是是只读
提供一个供应用需求实现的函数

那么写成 template 大致如下：

template <typename Key, typename Value>
class cache {
public:
  typedef Key key_type ;
  typedef Value value_type ;

  const value_type&
  operator[] (const key_type&) ;

  boost::function<value_type(const key_type&)> handler ;
private:
  std::size_t max ;
} ;

LRU 的实现

经典的 LRU 的实现为了能常数时间找到对应的元素势必要使用 hash 表，通过 hash 如果直接拿到对应对象，那么就得另外通过某种手段获得当前最早被访问的对象，所以比较适合的做法是访问对象的时候同时将它移动到最晚更新的位置。这就要求实际存放数据的东西能较快的删掉，还能较快的添加到某头上，另一头的访问也是很快的。正好双向链表这种接口非常适合干这个事情，因此我们实际存放的结构包括

一个 hash map，用它获得常数时间到对象的指向
这个对象存放在一个双向链表中
由于需要从链表里面删掉一些 node 同时也对 hash map 里对应项进行更新，我们至少要在 list 存放原始 key

所以我们从某种意义上来说需要一个“bimap”，left map 是一个 hash，而 right map 是一个双向链表。一种可能的数据结构是

template <typename Key, typename Value>
class lru_cache {
  public:
    typedef Key key_type ;
    typedef Value value_type ;

    value_type // for multi-threading safety
    operator[] (const key_type& k) {
      MIterator i = m.find (k) ;
      if (i == m.end ()) { // not found
        l.push_back (k) ;
        m [k] = std::make_pair (--l.end (), handler (k)) ;
        i = m.find (k) ;
        while (m.size () > max) {
          m.erase (l.front ()) ;
          l.pop_front () ;
        }
      } else {
        l.erase (i->first) ;
        l.push_back (key) ;
        (i->second).first = --l.end () ;
      }
      return (i->second)->second) ;
    }

    boost::function<value_type(const key_type&)> handler ;
private:
    typedef std::list<key_type> Container ;
    typedef typename Container::iterator CIterator ;
    typedef std::pair<CIterator, value_type> MapValue ;
    typedef std::unordered_map<key_type, MapValue > Map ;
    typedef typename Map::Iterator MIterator ;
    Container c ;
    Map m ;
    std::size_t max ;
} ;

如果使用 boost::bimap 来做这个事情，可以参看这里，bimap 的 list_of 提供了 relocate，应该比直接删掉然后 push_back 这种更快一点吧。

MRU 的实现

说起来 MRU 就只需要把上面的逻辑稍微改改，访问的放到前面去（而不是后面）就行了。

Belady algorithm

如果知道 cache 里面每个元素下次被访问的时间戳，就可以使用 Belady algorithm 弄成最优的算法，这个每次去掉其中对应时间戳最大的即可。简单的想来就是 hash map + heap，如果是 d-ary heap，似乎是 $\log (N)$ 级别的。不知道有没有更快的实现。类似的诸如 LFU 之类的 cache 是不是也是类似实现的呢？

其他一些 LRU 变种

真正在 CPU 上实现的 cache 实际上不可能那么复杂，除了 ARM 使用的随机替换的技术以外（好处是不需要存储别的任何信息了），还有一些 LRU 的变种，如 Pseudo-LRU 的两种实现，一种是基于 tree 结构的，每个元素多存 1bit 表示寻找 LRU 的方向，比如 0 向左，1 向右，访问的时候根据到元素的路径将对应 bit 需要的 flip 一下；另一种就是一组里面只能有一个 1 其余都是 0，1 表示最近访问过，扔掉的是最先碰到的为 0 的（似乎还不如直接 random…）。

—————-
And Esau said to Jacob, Feed me, I pray thee, with that same red pottage; for I am faint: therefore was his name called Edom.

demonstrate 的 blog

where there is a will, there is a trail

algorithm

几个面试题目（一）

scala 的 stream 应用一则

几种 cache

2024年 5月
日	一	二	三	四	五	六
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

分享到：

分享到：

分享到：