小编boa*_*der的帖子

这是我前一段时间接受采访的问题,我找不到答案.

给定一些样本S1,S2,... Sn和它们的概率分布(或权重,无论它叫什么)P1,P2,... Pn,设计算法随机选择样本考虑其概率.我带来的解决方案如下:

1. 构建累积的权重数组Ci,例如

   C0 = 0; Ci = C [i-1] + Pi.

同时计算T = P1 + P2 + ... Pn.这需要O(n)时间

2. 生成均匀随机数R = T*random [0..1]
3. 使用二进制搜索算法,返回最小i,例如Ci> = R.结果是Si.它需要O(logN)时间.

现在的实际问题是:假设我想要改变其中一个初始权重Pj.如何在O(n)时间内做到这一点？其他数据结构是可以接受的,但随机抽样算法不应该比O(logN)差.

我有一个无序事件列表，我的任务是存储它们的第一次和最后一次出现。

我在 Cassandra 中有以下列族：

CREATE TABLE events (
   event_name TEXT,
   first_occurrence BIGINT,
   last_occurrence BIGINT,
   PRIMARY KEY (event_name)
);

因此，如果我有一个名为“some_event”的事件，并且出现次数为 123456，那么我想要做的事情在 MySQL 术语中看起来像这样：

INSERT INTO events (event_name, first_occurence, last_occurence)
VALUES ('some_event', 123456, 123456)
ON DUPLICATE KEY UPDATE 
     first_occurrence = LEAST(first_occurrence, 12345), 
     last_occurrence = GREATEST(last_occurrence, 123456)

我打算在 Cassandra 中使用轻量级事务来完成它，如下所示：

INSERT INTO events(event_name, first_occurrence, last_occurrence) VALUES ('some_event', 12345, 12345) IF NOT EXISTS;
UPDATE events SET first_occurrence = 123456 WHERE event_name='some_event' IF first_occurrence > 123456;
UPDATE events SET last_occurrence = 123456 WHERE event_name='some_event' IF …