Skip to main content
 首页 » 编程设计

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

2024年05月10日37www_RR

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

描述一个数据结构,其中 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} 的位置,导致返回错误的值。

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