我在网上遇到了以下面试问题。
描述一个数据结构,其中 getValue(int index)、setValue(int index, int value) 和 setAllValues(int value) 的复杂度均为 O(1)。
虽然数组足以在 O(1) 内执行第一个和第二个操作,但对于第三个操作 (setAllValues) 可以提出什么建议?
请您参考如下方法:
元组{timestamp, value}
的数组
怎么样,还有一个名为all
<的附加
{timestamp, value}
的附加
/。由于您只关心插入的相对时间,因此可以使用单调递增的
id
作为时间戳的值:
type Entry {
int timestamp,
int value
}
type structure {
int id
Entry all
Entry[] array
}
将所有字段初始化为 0。然后以下内容应该适合您:
setValue(索引 i,值 v):
array[i] = {id++, value}
值 getValue(索引 i)
if(all.timestamp > array[i].timestamp) return all.value else return array[i].value
setAll(值 v)
all = {id++, value}
这种方法的一个问题是,最终您将用完时间戳的 id,并且可能会回绕。如果您选择 64 位值来存储时间戳,那么在此发生之前将为您提供 18,446,744,073,709,551,616 次插入或 setAlls。根据数据结构的预期用途,O(n) 清理阶段可能是合适的,或者您可以只是抛出异常。
另一个可能需要考虑的问题是多线程。三个明显的问题:
- 如果
id++
不是原子的,并且两个线程同时获得了一个新的id
,那么您可以获得两个具有相同 id 的条目。 - 如果 id 的增量和创建的元组的分配不是原子性的(它们可能不是),并且有两个同时插入,那么您可能会遇到竞争条件,旧的 id 获胜。
- 如果元组的赋值不是原子的,并且
insert()
与get()
同时存在,那么您最终可能会遇到数组中{new_id, old_value}
的位置,导致返回错误的值。
如果存在任何问题,最简单的解决方案就是在文档中添加“非线程安全”(作弊)。或者,如果您无法用您选择的语言自动实现这些方法,则需要在它们周围放置某种同步锁。