From Ace of Programming Interview, Cpt1 - Hiring Programmers: The Inside Story

Establish a Rapport

For an interviewee, one the the most efficient way to build a rapport is to try to see things in from the interviewer's perspective.

• understand the motivation of the interviewer
• establishing a common ground
• adapting your …

Hey man, I don't know that stuff

Stevey's talking aboooooout

If my boss thinks it's important

I'm gonna get fiiiiiiiiiired

Oooh yeah baaaby baaaay-beeeeee....

非技术部分

热身

好好读一本讲数据结构和算法的书

熟悉一些“术语”，可以强化分辨问题的能力。

Yegge推荐了 Steven S. Skiena 的《算法设计手册》，而我推荐的是 Udi Manber 的《算法引论》。

每一本书都有它的长处短处。找一本评价不错的书，认真读完，肯定会有收获。

找个朋友来面试你，尝试白板编程

在白纸/白板上编程的体验和在计算机上大有不同。没有条件的情况下 …

写在前面

问题是非常流行的，也确实流行了一阵的system-design问题。在知乎上再次被人提起。然后我非常欣赏陈硕的回答。所以要写一篇文章，记下自己的感想。

问题

海量数据算法:如何从超过10G的记录IP地址的日志中，较快的找出登录次数最多的一个IP？

银弹？

面对这种system-design问题，尤其是这种，非高并发、非实时的问题，很多人会采用_map-reduce_ —— 解决system-design问题的银弹。

我对map-reduce的理解非常肤浅，但是可以解释一下大概的流程。

1. 将日志进行分片。把hash(ip)相同的ip地址分到同一个片中。（注：这里的hash并不是签名函数，只是一个分片标示）
2. 分片后的日志的大小会小很多，可以方便的进行排序，记数。
3. 然后再从各个片中，统计出最热门的IP地址。（或TopK的IP地址）

如果不满意我的答案的话，推荐Mining of Massive Datasets一书，其中对map-reduce算法做一番不错的介绍。

正确的分析姿势

业务实体

业务实体拥有四种主要的组件： 信息模型、生命周期模型 …

题目大意

给你三个数组:A[N], B[M], C[M]。让你按如下pseudo-code给出的规则计算，求出最终A[N]每一项的值。

for i = 1 to M do
    for j = 1 to N do
        if j % B[i] == 0 then
            A[j] = A[j] * C[i]
        endif
    end do
end do

数据范围

1≤ N,M ≤ 10^5

1 ≤ B[i …

Background

This problem is from the book "Algorithm 4th edition" (Exersise 4.1.10)

There are N cities and M undirected roads between those cities. People can travel to any city along the roads.

One day, a war breaks out. Our cities are under attack! As we can't defend all …