几个面试题(二)

随机 shuffle

常见算法有 Fisher-Yates 算法:用容器 track 剩下的元素,随机从里面选,比如对数组来说可以通过与当前位置 swap 来实现。这其实是改进过的算法又叫 Knuth’s shuffle。

template <class Iter, class Gen> void
knuth_shuffle (Iter begin, Iter end, Gen& gen) {
  typedef typename Iter::difference_type diff_type ;
  diff_type n ;
  do {
    n = end - begin ;
    diff_type t = gen (n) ;
    std::swap (*(end-1), *(begin + t)) ;
    -- end ;
  } while (n > 2) ;
} ;

产生随机的 cycle,使用 Sattolo’s algorithm:这时为了产生 cycle 需要去掉最后一个可能性,即这里的 gen(n) 本来返回的是 [0, n-1],现改成 [n, n-1)]就行了,因为这样就会产生一个轮换而不是置换。

blackjack 游戏

类似的游戏一般使用 MVC 进行建模,前面讨论过离散时间时间的建模。这个游戏大概就是说每个人手上的牌点数和取不超过 21 点的最大为赢家。轮流抽取,可以选择放弃或者要牌。model 比较自然就是牌(点数),每个玩家可以用一组牌表示(list),因为牌是按照一定的搭配出厂的,所以还需要生成一个初始牌的状态,游戏开始后对其进行 shuffle。这样模拟的 controller 有下面几个:

  • Game(尚未使用的牌)
  • Player,可能存在几个状态比如说不要牌之后不允许继续要牌,是否 busted(成立后已经输掉了);行为 take 可以是 takeMore/pass,这个部分如何决策交由一个 Strategy 来做,takeMore 和 pass 的实现很简单
  • SeenCards(已经丢弃的牌,如果每轮开始前不见得重新洗牌的话)

模拟一个周期需要 Game.start(决定下一个是谁的 action),Player 的行为包括调用 take 和注册下一个 player 的事件。为了让游戏结束可以让 Game 收集该轮 pass 的个数(也就是说 pass 会注册一个事件要求 Game 记录这一轮的情况),最后一个 Player 注册 Game 的 nextTurn 这个事件用来清零和决定水输谁赢。

因为这个比较简单,所以实际上的时间并没有准确的意义。

产生字符串的所有 permutation

跟前面讨论的可以比较元素的类似(通过回溯算法),通过那个生成给定字符串的 permutation 是可以的,另一种想法就是 recursion,对于字符串 s = at,我们可以生成 t 这部分的 permutation 然后加上 a,当 a 遍历 s 时就获得了所有的 permutation,为了打印方便,可以反过来写,把 a 放在最后打印即可。

void
string_perm (std::ostream& out, std::string& s, int l) {
  if (l == 0)
    out << s << "\n" ;
  else {
    string_perm (out, s, l - 1) ;
    for (int i = 0 ; i < l ; ++ i) {
      std::swap (s[i], s[l]) ;
      string_perm (out, s, l - 1) ;
      std::swap (s[i], s[l]) ;
    }
  }
}

其实这里也可以看出来递归部分后面恢复这点其实跟使用 stack 是一码事,模拟这个过程感觉和写 next_permutation 是一个概念。

atoi 的实现

主要是看一些诡异条件比如判断空白字符 +- 号什么的,随便写个

int atoi (const char* s) {
  int pos = 0 ; bool positive = true ; int val = 0 ;
  while (is_blank (*(s + pos))) ++ pos ;
  if (*(s + pos) == '-') {
    positive = false ; ++ pos ;
  } else if ( == '+') {
    ++ pos ;
  }
  while (is_digit (*(pos + s))) {
    val *= 10 ;
    val += *(pos + s) - '0' ;
  }
  return positive ? val : - val ;
}

如何 model 产品之间的 similarity

其实很容易扯,毕竟是个开放式问题:description、类别、购买行为(frequent pattern 和 collaborate filtering)。注意有些情况下需要考虑 bias,如 popular 的东西跟每个产品的同现程度可能都很高。

如何设计文本编辑器

没设计过,感觉比较复杂:

  • 应用环境:PC 上还是 mobile device,决定了输入形式,键盘、语音、手写等等
  • 进一步需求的细化:高亮?编码?折叠?扩展性?
  • 前端设计讨论(working backwards)
  • 抽象:使用的图形 framework,显示内容的 widget(事件响应等),响应输入的抽象(如果需要有不同于键盘的输入)
  • 具体化到实现?

如何设计地图

其实很复杂,

  • 数据驱动还是产品驱动?前者就是说已经有了数据,需要呈现给用户;后者是说重新设计地图,数据可以根据这个设计进行获得
  • 产品需求:地图本身很简单(相对),有没有额外的要求,导航、辅助信息、是否需要扩展、用户交互形式
  • 基本的构架:C/S,数据的存储(图像 or 图形 or…),经纬度的表示,使用地图坐标系的选择(球面到平面的映射),回答一些基本的 design decision:2D/3D,渲染在 server 做还是在 client,分层显示的基本形式,数据更新,数据关系(不同 layer 上数据如何对齐)
  • API 设计,这时候如果确定了表达形式就能设计比较合理的 API,比如给定经纬度获得什么 scale 上的图形图像,这个因为是个 read-only 的比较好办,万一有用户行为需要写回来可能会复杂很多

找奇数次的非负整数

其他的都是偶数次,只有一个是奇数次:

  • sorting 可以到 O(N \log N)
  • quick sort partition 可以到 O(N)
  • 直接 XOR 之

scheduling

K 台服务器,每次随机取一个处理 job:用个数组,前一半是可用的后一半是不可用的,每次交换即可

K 台服务器处理 N 个 job,要求同类先处理,似乎可以用 map 到 linked list 来做

Head to Tail

要求找到一个变换序列将一个单词变成另一个,每次只能改变一个字符。把这个弄得更有意思一点是也允许增加删减字母。简而言之难点在如何建立这个 graph,两个顶点之间的边 = 相差一个字母。

  • 建立 hash 表,把所有可用的操作(改变字母、增加、减少)用在该单词上,查询 hash 表,这个比较笨,单词比较长就会有问题
  • 不晓得有没有别的什么策略生成 graph

搜索反而比较容易,就是 DFS、BFS 了。

——————
And the man increased exceedingly, and had much cattle, and maidservants, and menservants, and camels, and asses.

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