一道机试题

那年后台人手不足，需要请个人过来帮忙，但是又不知道水平如何。苦思之下，想了几道机试题让应聘者做做。有一其中有道题目是这样：
给出一系列不重复的字母和对应的权重值(如下所示)，就可以根据权重大小，随机抽取到不同的字母。
字母权重
‘a’ 5
‘b’ 4
‘c’ 4
‘d’ 20
‘e’ 13

根据此场景，完成如下要求
a、计算出每个字母被随机选中的概率。
b、请随机抽取N次，将抽取到的字母以及频率打印出来。
c、能够动态添加【新的的字母和权重】，并重新计算的字母选中的概率。
d、进行扩展，使之支持【带权重的数字】【带权重的字符】【带权重的复杂对象】的随机抽取算法

虽然题目很简单，可以检测编码水平。

Level1：套着面向对象的皮，但是以过程式的思维完成此功能。
Level2：会将重复逻辑抽象出来，进行复用。
Level3：发现潜在的联系，对逻辑进行抽象，完成功能。

这是一个优化后的版本

public interface Weightable<Key> {
    /**
     * @return 权重
     */
    public Integer weight();
    /**
     * @return 标识
     */
    public Key key();
}

public class WeightSelect<Key> implements Serializable {
    private Map<Key, Integer> rw = new LinkedHashMap<>();
    private int sum = 0;
    public void addWeight(Key key, Integer value) {
        if (value > 0) {
            sum += value;
            rw.put(key, sum - 1);
        }
    }
    public Key selectKey() {
        int i = ThreadLocalRandom.current().nextInt(sum);
        for (Entry<Key, Integer> e : rw.entrySet()) {
            if (i > e.getValue()) continue;
            if (i <= e.getValue()) return e.getKey();
        }
        return null;
    }
}
public abstract class AbstractWeightSelector<Key, Value extends Weightable<Key>> {
    public Map<Key, Value> entries = new LinkedHashMap<>();
    protected WeightSelect<Key> selector = new WeightSelect<Key>();

    public AbstractWeightSelector() {

    }
    public AbstractWeightSelector(Collection<Value> values) {
        initSelect(values);
    }
    protected void initSelect(Collection<Value> values){
        for (Value v : values) {
            if (v.weight()> 0) {
                this.entries.put(v.key(), v);
                selector.addWeight(v.key(), v.weight());
            }
        }
    }
    public Value select() {
        return entries.get(selector.selectKey());
    }
}

凡是继承 Weightable接口的对象，都可以进行权重选择。
WeightSelect是随机选择的算法实现。
AbstractWeightSelector是提供给业务的接口抽象，调用方只关心此类。

一道机试题

推荐阅读更多精彩内容