data-structures - 面试问题: data structure to set all values in O(1)

Question

我在网上遇到了以下面试问题。

描述一个数据结构，其中 getValue(int index)、setValue(int index, int value) 和 setAllValues(int value) 的复杂度均为 O(1)。

虽然数组足以在 O(1) 内执行第一个和第二个操作，但对于第三个操作 (setAllValues) 可以提出什么建议？

Answer 1

元组{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} 的位置，导致返回错误的值。

如果存在任何问题，最简单的解决方案就是在文档中添加“非线程安全”(作弊)。或者，如果您无法用您选择的语言自动实现这些方法，则需要在它们周围放置某种同步锁。