Ebay Interview Question
SDE-2sTeam: Traffic
Country: United States
Interview Type: In-Person
There are at least two ways to implement this: one with linear probing and another one with separate chaining. Here is the version for separate chaining in Java. This also assumes that the key is actually the integers. It will break if the keys are not in integers.
package com.practice.hashtable.separatechaining;
public class SeparateChainingExample {
public static void main(String[] args) {
SeparateChainingExample sce = new SeparateChainingExample();
// Test Hash Table
LinkedHashTable lht = sce.new LinkedHashTable();
lht.put(0, "A");
lht.put(1, "B");
lht.put(2, "C");
lht.put(3, "D");
lht.put(4, "E");
lht.put(5, "F");
lht.put(6, "G");
lht.put(7, "H");
lht.put(13,"I");
lht.put(21, "J");
sce.testPrint(lht.hashTable);
}
public void testPrint(LinkedHashEntry[] list) {
int counter = 0;
for(LinkedHashEntry lhe : list) {
System.out.println("NODE #" + counter + " SIZE: " + lhe.getSize());
LinkedHashEntry entry = lhe;
while((entry != null)) {
System.out.println("\t" + entry.getKey() + " , " + entry.getValue());
entry = entry.getNext();
}
++ counter;
}
}
class LinkedHashTable {
private final static int TABLE_SIZE = 5;
private LinkedHashEntry[] hashTable;
public LinkedHashTable() {
this.hashTable = new LinkedHashEntry[TABLE_SIZE];
for(int i=0; i < TABLE_SIZE; ++ i) {
hashTable[i] = null;
}
}
public void put(Object key, Object value) {
int hashValue = ((Integer)(key) % TABLE_SIZE);
if(hashTable[hashValue] == null) {
hashTable[hashValue] = new LinkedHashEntry(key, value);
}
else {
LinkedHashEntry entry = hashTable[hashValue];
while((entry.getNext() != null) && (!entry.getKey().equals(key))) {
entry = entry.getNext();
}
if(entry.getKey().equals(key)) {
entry.setValue(value);
}
else {
entry.setNext(new LinkedHashEntry(key, value));
}
}
}
public Object get(Object key) {
int hashValue = ((Integer)(key) % TABLE_SIZE);
if(hashTable[hashValue] == null) {
return null;
}
else {
LinkedHashEntry entry = hashTable[hashValue];
while((entry != null) && (!entry.getKey().equals(key))) {
entry = entry.getNext();
}
if(entry == null) {
return null;
}
else {
return entry.getValue();
}
}
}
}
class LinkedHashEntry {
private Object key;
private Object value;
private LinkedHashEntry next;
private int size;
/**
* Default Constructor
*/
public LinkedHashEntry(Object key, Object value) {
this.key = key;
this.value = value;
this.next = null;
this.size = 1;
}
public void setKey(Object key) {
this.key = key;
}
public Object getKey() {
return key;
}
public void setValue(Object value) {
this.value = value;
}
public Object getValue() {
return value;
}
public void setNext(LinkedHashEntry next) {
this.next = next;
++ size;
}
public LinkedHashEntry getNext() {
return next;
}
public int getSize() {
return size;
}
}
}
Trying to be creative...
Public class HashMap
{
Public void put(Object key, Object value) {
// serialize value to a file called "key.id"
}
Public object get(Object key) {
// check if file called "key.id" exists
// if so, deserialize its content and return it
// else return null
}
}
Shouldn't it be public Object get(Object key) ?
- Ragz December 12, 2013