Amazon Interview Question Software Engineer / Developers
1of 1 voteImplement Hashtable in Java
Country: United States
Interview Type: Phone Interview
You can take a look at the Hashtable class in the JDK source code.
The implementation is huge.
but basically,
1) you need to syncronized any operation that alters the table, because Hashtable are syncronized.
2) get, put and contains should run in avg O(1)
3) you need to provide a way to deal with collitions
4) you need to implement an efficient hashcode method for the keys
5) care need to be taken when modifying the load factor and initial capacity of the hashTable
Ok. Here is a C++ version.
// To be implemented.
class HashTable<Key, Value> {
private:
std:vector<Pair<Key,Value>> _map;
}
Please find Implementation in java:
Code is as below:
public class HashTableDemo {
public static void main(String[] args) {
Hashtable<Integer, String> rollNumberName = new Hashtable<Integer, String>();
System.out.println("Starting The Demo\n\n");
rollNumberName.put(1, "ABC");
rollNumberName.put(2, "DEF");
rollNumberName.put(3, "GHI");
System.out.println("Initially In HashTable: " + rollNumberName);
System.out.println("Adding new value to existing key-1 : "
+ rollNumberName.put(1, "XYZ"));
System.out
.println("\nAfter replacing the value for key-1 in HashTable: "
+ rollNumberName);
}
Output will be as below :
---------------------------------
Starting The Demo
Initially In HashTable: {3=GHI, 2=DEF, 1=ABC}
Adding new value to existing key: ABC
After replacing the value for key 1 in HashTable: {3=GHI, 2=DEF, 1=XYZ}
question.replace("in Java", "in Python")
Hash table implementation in python
class Element(object):
def __init__(self, key, value):
self.key = key
self.value = value
class HashTable(object):
"""
Hash table implementation using modulo hash algorithm and linked list for storing hashed elements
"""
def __init__(self):
self.size = 8 # Lets start with 8 buckets
self.table = list((None for i in range(self.size)))
self.num_elements = 0
def set_key(self, key, value):
h = self._hash(key)
if not self.table[h]:
self.table[h] = list()
bucket = self.table[h]
bucket.append(Element(key, value))
self.num_elements = self.num_elements + 1
return True
def get_key(self, key):
h = self._hash(key)
if self.table[h] is None:
return False
bucket = self.table[h]
for item in bucket:
if item.key == key:
return item.value
def _hash(self, key):
if type(key) == str:
value = sum((ord(x) for x in key))
elif type(key) == int:
value = key
else:
value = 0
return value % self.size
def get_size(self):
return self.num_elements
def print_table(self):
for i, bucket in enumerate(self.table):
print "{0}: {1}".format(i, self.print_bucket(bucket))
def print_bucket(self, bucket):
if bucket is None:
return "None"
return ", ".join("-->{0}::{1}".format(element.key, element.value) for element in bucket)
Driver program
myhash = HashTable()
print myhash.print_table()
for i in range(10):
print myhash.set_key(i,i)
for i in range(10):
print myhash.get_key(i)
print myhash.get_size()
myhash.print_table()
package cracking.coding.interview;
public class CustomHashMap {
private LinkedHashEntry[] hashTable;
private static final int HASH_LENGTH = 100;
public CustomHashMap(){
hashTable = new LinkedHashEntry[HASH_LENGTH];
}
public void put(Object key,Object value){
LinkedHashEntry node = getNode(key);
if(node == null){
hashTable[getHashCode(key)]=new LinkedHashEntry(key, value);
return;
}
while(node.hasNext() && !(node.getKey().equals(key)))
node=node.next;
//updation
if(key.equals(node.getKey()))
node.value=value;
System.out.println(" Node "+node.getKey()+" "+ node.value+ " "+node.next);
//addition
LinkedHashEntry newEntry = new LinkedHashEntry(key, value);
node.next=newEntry;
System.out.println(" Node "+node.getKey()+" "+ node.value+ " "+node.next);
System.out.println(" newEntry "+newEntry.getKey()+" "+ newEntry.value+ " "+newEntry.next);
System.out.println(newEntry);
}
public Object get(Object key){
if(key == null)
return null;
LinkedHashEntry node = getNode(key);
if(node == null)
return null;
while(node.hasNext() && !key.equals(node.getKey()))
node=node.next;
if(key.equals(node.getKey()))
return node.value;
return null;
}
public Boolean remove(Object key){
if(key == null)
return false;
LinkedHashEntry node = getNode(key);
LinkedHashEntry previousNode=node;
while(node.hasNext() && !key.equals(node.getKey())){
previousNode=node;
node=node.next;
}
if(key.equals(node.getKey())){
previousNode.next=node.next;
node.next=null;
return true;
}
return false;
}
private LinkedHashEntry getNode(Object key) {
System.out.println("getHashCode(key) "+ getHashCode(key));
return hashTable[getHashCode(key)];
}
private int getHashCode(Object key) {
return (key.hashCode() % HASH_LENGTH);
}
private class LinkedHashEntry{
private Object key;
private Object value;
private LinkedHashEntry next;
LinkedHashEntry(Object key,Object value){
this.key=key;
this.value=value;
this.next=null;
}
Object getKey(){
return key;
}
Boolean hasNext(){
return (next != null);
}
}
public static void main(String ... s){
CustomHashMap customHashMap = new CustomHashMap();
customHashMap.put("hi","hi");
customHashMap.put(29,"hi bye");
}
}
public class CustomHashMap {
private LinkedHashEntry[] hashTable;
private static final int HASH_LENGTH = 100;
public CustomHashMap(){
hashTable = new LinkedHashEntry[HASH_LENGTH];
}
public void put(Object key,Object value){
LinkedHashEntry node = getNode(key);
if(node == null){
hashTable[getHashCode(key)]=new LinkedHashEntry(key, value);
return;
}
while(node.hasNext() && !(node.getKey().equals(key)))
node=node.next;
//updation
if(key.equals(node.getKey()))
node.value=value;
System.out.println(" Node "+node.getKey()+" "+ node.value+ " "+node.next);
//addition
LinkedHashEntry newEntry = new LinkedHashEntry(key, value);
node.next=newEntry;
System.out.println(" Node "+node.getKey()+" "+ node.value+ " "+node.next);
System.out.println(" newEntry "+newEntry.getKey()+" "+ newEntry.value+ " "+newEntry.next);
System.out.println(newEntry);
}
public Object get(Object key){
if(key == null)
return null;
LinkedHashEntry node = getNode(key);
if(node == null)
return null;
while(node.hasNext() && !key.equals(node.getKey()))
node=node.next;
if(key.equals(node.getKey()))
return node.value;
return null;
}
public Boolean remove(Object key){
if(key == null)
return false;
LinkedHashEntry node = getNode(key);
LinkedHashEntry previousNode=node;
while(node.hasNext() && !key.equals(node.getKey())){
previousNode=node;
node=node.next;
}
if(key.equals(node.getKey())){
previousNode.next=node.next;
node.next=null;
return true;
}
return false;
}
private LinkedHashEntry getNode(Object key) {
System.out.println("getHashCode(key) "+ getHashCode(key));
return hashTable[getHashCode(key)];
}
private int getHashCode(Object key) {
return (key.hashCode() % HASH_LENGTH);
}
private class LinkedHashEntry{
private Object key;
private Object value;
private LinkedHashEntry next;
LinkedHashEntry(Object key,Object value){
this.key=key;
this.value=value;
this.next=null;
}
Object getKey(){
return key;
}
Boolean hasNext(){
return (next != null);
}
}
public static void main(String ... s){
CustomHashMap customHashMap = new CustomHashMap();
customHashMap.put("hi","hi");
customHashMap.put(29,"hi bye");
}
}
i think they want you to write a new class HashTable using a HashMap.
- Anonymous November 16, 2013- check to ensure that the keys/valus are not null
- synchronize put/containsKey/contains/get