我在互联网上遇到了以下面试问题.
描述getValue(int index),setValue(int index,int value)和setAllValues(int value)都是O(1)的数据结构.
虽然数组足以让第一次和第二次操作在O(1)中执行,但第三次(setAllValues)可以提出什么？
Tim*_*nes 46
一个array元组如何{timestamp, value},另外一个{timestamp, value}叫all.由于您只关心插入的相对时间,因此可以使用单调递增id的时间戳值:
type Entry {
int timestamp,
int value
}
type structure {
int id
Entry all
Entry[] array
}
将所有字段初始化为0.然后以下内容适合您:
setValue(索引i,值v):
array[i] = {id++, value}
value getValue(index 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的条目.insert()与a同时存在,get()那么你最终可能会{new_id, old_value}在数组中说出你的位置,导致返回错误的值.如果这些问题中的任何一个都是问题,那么绝对最简单的解决办法是在文档中使用"not thread safe"(作弊).或者,如果您无法以您选择的语言原子方式实现这些方法,则需要在它们周围放置某种同步锁.
我在其中一次技术访谈中得到了同样的问题.
这是我完整的即用型Java实现,包括测试用例.
关键的想法是保持setAll()特殊变量(例如joker)的值,然后以适当的方式跟踪该值的变化.
为了保持代码清洁,一些访问修饰符已被废除.
节点类:
import java.time.LocalDate;
class Node {
int value;
LocalDate jokerSetTime;
Node(int val, LocalDate jokSetTime) {
value = val;
jokerSetTime = jokSetTime;
}
}
DS类:
class DS {
Node[] arr;
DS(int len) {
arr = new Node[len];
}
}
DataStructure类:
import java.time.LocalDate;
class DataStructure {
private boolean isJokerChanged;
private Integer joker;
private LocalDate jokerSetTime;
private DS myDS;
DataStructure(int len) {
myDS = new DS(len);
}
Integer get(int i) {
Integer result;
if (myDS.arr.length < i) {
return null;
}
// setAll() has been just called
if (isJokerChanged) {
return joker;
}
if (myDS.arr[i] == null) {
// setAll() has been previously called
if (joker != null) {
result = joker;
} else {
result = null;
}
} else if (myDS.arr[i].jokerSetTime == jokerSetTime) {
// cell value has been overridden after setAll() call
result = myDS.arr[i].value;
} else {
result = joker;
}
return result;
}
void setAll(int val) {
isJokerChanged = true;
joker = val;
jokerSetTime = LocalDate.now();
}
void set(int i, int val) {
isJokerChanged = false;
myDS.arr[i] = new Node(val, jokerSetTime);
}
}
主要课程:
class Main {
public static void main(String[] args) {
DataStructure ds = new DataStructure(100);
Integer res;
res = ds.get(3);
ds.set(3, 10);
res = ds.get(3);
ds.setAll(6);
res = ds.get(3);
res = ds.get(15);
ds.set(4, 7);
res = ds.get(4);
res = ds.get(3);
ds.setAll(6);
ds.set(8, 2);
res = ds.get(3);
}
}
更新:
代码已更新.以前的实现并没有考虑到时的情况下setAll()具有相同值的行被称为两次,之后set(x),get(y)如:setAll(100),set(3, 1),setAll(100),set(5, 3),get(3).
添加了时间戳方法的使用,以允许区分setAll()具有相同值的不同调用.
PS此实现不是线程安全的.
一个指向一个公共值的指针数组怎么样？设置值,所有引用都将指向O(1)中的单个更改值.
小智 5
我最近在一次采访中被问到这个问题。我想出了一个哈希表实现。它将解决时间戳值耗尽的问题，但需要实现线程安全功能（可能使用延迟初始化技术）
假设在我们的类中，我们有一个私有变量_defaultValue来保存默认值，并且我们还有一个私有哈希表或字典_hashtable。 SetAllValues可以仅将_defaultValue设置为等于传递的值，并将_hashtable初始化/设置为新的哈希表，并丢弃对旧哈希表的任何引用。SetValue应该只是向_hashtable添加一个新值，或者如果键（或索引）已存在于_hashtable中则更新该值。GetValue应检查_hashtable中是否存在键（或索引） ，然后返回它，否则返回存储在_defaultValue中的值。
这是我在 StackOverflow 上的第一个回答。我有点懒得写代码了。可能很快就会编辑答案。
面试官对这个解决方案点头同意，但坚持不使用哈希表来实现。我想，他是在要求我给出与蒂莫西的回答类似的方法。那一刻我无法得到它:(。无论如何，干杯！
编辑：发布代码（在 C# 中）
class MyDataStruct
{
private int _defaultValue;
private Dictionary<int,int> _hashtable;
public MyDataStruct()
{
_defaultValue = 0; // initialize default with some value
_hashtable = new Dictionary<int, int>();
}
public void SetAllValues(int val)
{
_defaultValue = val;
_hashtable = new Dictionary<int, int>();
}
public void SetValue(int index, int val)
{
if (_hashtable.ContainsKey(index))
{
_hashtable.Add(index, val);
}
else
{
_hashtable[index] = val;
}
}
public int GetValue(int index)
{
if (_hashtable.ContainsKey(index))
{
return _hashtable[index];
}
else
{
return _defaultValue;
}
}
}