那年后台人手不足，需要请个人过来帮忙，但是又不知道水平如何。苦思之下，想了几道机试题让应聘者做做。有一其中有道题目是这样：
给出一系列不重复的字母和对应的权重值(如下所示)，就可以根据权重大小，随机抽取到不同的字母。
字母 权重
‘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是提供给业务的接口抽象，调用方只关心此类。
