几个面试题目(一)

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.

Advertisements
几个面试题目(一)

一个有关“几个面试题目(一)”的想法

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s