Twitter Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
class Hashtable
{
private int size = 100000;
pair[] slot;
Lock[] write_lock;
int currentSize;
class pair
{
K key;
V value;
}
public Hashtable()
{
value = new V[size];
write_lock = new Lock[size];
currentSize = 0;
}
private int hashcode(K key, S preSlot){}
public V put(K key, V value)
{
int index= -1;
do
{
index = hashcode(K, index);
if(slot[index]==null)
{
write_lock[index].lock();
if(slot[index]==null)
{
slot[index] = new pair();
slot[index].key = key;
slot[index].value = value;
return null;
}
else if(slot[index].key==key)
{
V preValue = null;
preValue = slot[index].value;
slot[index].value = value;
return preValue;
}
write_lock[index].unlock();
}
else
{
if(slot[index].key==key)
{
V preValue = null;
preValue = slot[index].value;
slot[index].value = value;
return preValue;
}
}
}while(currentSize < size*0.5);
this.resize();
return put(key, value);
}
}
Class ReaderWriterLock()
{
// setup internal useful variables
volatile int readLock = 0;
volatile bool writeLock;
object synch = new Object();
// Block until lock is free
//ReadLock
void ReadLock()
{
Lock (synch)
{
while (writeLock == true)
Thread.Sleep(1); // 1 second
readLock++;
}
}
// Block until lock is free
//Write
void WriteLock()
{
Lock (synch)
{
while (writeLock == true || readLock>0)
Thread.Sleep(1); // 1 second
writeLock = true;
}
}
void ReleaseWriteLock()
{
Lock (synch)
{
Assert (writeLock == true);
wrtieLock = false;
}
}
void ReleaseReadLock()
{
Lock (synch)
{
Assert (readLock > 0);
readLock--;
}
}
}
Use ReadWriteLock
- Miz March 06, 2012static class ThreadSafeHashMap<K, V> extends HashMap {
private final ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
private final Lock read = readWriteLock.readLock();
private final Lock write = readWriteLock.writeLock();
public void put(K key, V value) {
write.lock();
try {
super.put(key, value);
} finally {
write.unlock();
}
}
public Object get(K key) {
read.lock();
try {
return super.get(key);
} finally {
read.unlock();
}
}
...
}