Uber Interview Question Software Developers
Country: United States
Interview Type: In-Person
public class MyHashMap {
// for better re-sizing is taken as 2^4
private static final int SIZE = 16;
private Entry table[] = new Entry[SIZE];
/**
* To store the Map data in key and value pair.
* Used linked list approach to avoid the collisions
*/
class Entry {
final String key;
String value;
Entry next;
Entry(String k, String v) {
key = k;
value = v;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public String getKey() {
return key;
}
}
/**
* Returns the entry mapped to key in the HashMap.
*/
public Entry get(String k) {
int hash = k.hashCode() % SIZE;
Entry e = table[hash];
// Bucket is identified by hashCode and traversed the bucket
// till element is not found.
while(e != null) {
if(e.key.equals(k)) {
return e;
}
e = e.next;
}
return null;
}
/**
* If the map previously contained a mapping for the key, the old
* value is replaced.
*/
public void put(String k, String v) {
int hash = k.hashCode() % SIZE;
Entry e = table[hash];
if(e != null) {
// If we will insert duplicate key-value pair,
// Old value will be replaced by new one.
if(e.key.equals(k)) {
e.value = v;
} else {
// Collision: insert new element at the end of list
// in the same bucket
while(e.next != null) {
e = e.next;
}
Entry entryInOldBucket = new Entry(k, v);
e.next = entryInOldBucket;
}
} else {
// create new bucket for new element in the map.
Entry entryInNewBucket = new Entry(k, v);
table[hash] = entryInNewBucket;
}
}
public static void main(String[] args) {
MyHashMap myHashMap = new MyHashMap();
myHashMap.put("Awadh", "SSE");
myHashMap.put("Rahul", "SSE");
myHashMap.put("Sattu", "SE");
myHashMap.put("Gaurav", "SE");
Entry e = myHashMap.get("Awadh");
System.out.println(""+e.getValue());
}
}
public class MyHashMap {
// for better re-sizing is taken as 2^4
private static final int SIZE = 16;
private Entry table[] = new Entry[SIZE];
/**
* To store the Map data in key and value pair.
* Used linked list approach to avoid the collisions
*/
class Entry {
final String key;
String value;
Entry next;
Entry(String k, String v) {
key = k;
value = v;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public String getKey() {
return key;
}
}
/**
* Returns the entry mapped to key in the HashMap.
*/
public Entry get(String k) {
int hash = k.hashCode() % SIZE;
Entry e = table[hash];
// Bucket is identified by hashCode and traversed the bucket
// till element is not found.
while(e != null) {
if(e.key.equals(k)) {
return e;
}
e = e.next;
}
return null;
}
/**
* If the map previously contained a mapping for the key, the old
* value is replaced.
*/
public void put(String k, String v) {
int hash = k.hashCode() % SIZE;
Entry e = table[hash];
if(e != null) {
// If we will insert duplicate key-value pair,
// Old value will be replaced by new one.
if(e.key.equals(k)) {
e.value = v;
} else {
// Collision: insert new element at the end of list
// in the same bucket
while(e.next != null) {
e = e.next;
}
Entry entryInOldBucket = new Entry(k, v);
e.next = entryInOldBucket;
}
} else {
// create new bucket for new element in the map.
Entry entryInNewBucket = new Entry(k, v);
table[hash] = entryInNewBucket;
}
}
public static void main(String[] args) {
MyHashMap myHashMap = new MyHashMap();
myHashMap.put("Awadh", "SSE");
myHashMap.put("Rahul", "SSE");
myHashMap.put("Sattu", "SE");
myHashMap.put("Gaurav", "SE");
Entry e = myHashMap.get("Awadh");
System.out.println(""+e.getValue());
}
}
public class MyHashMap {
// for better re-sizing is taken as 2^4
private static final int SIZE = 16;
private Entry table[] = new Entry[SIZE];
/**
* To store the Map data in key and value pair.
* Used linked list approach to avoid the collisions
*/
class Entry {
final String key;
String value;
Entry next;
Entry(String k, String v) {
key = k;
value = v;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public String getKey() {
return key;
}
}
/**
* Returns the entry mapped to key in the HashMap.
*/
public Entry get(String k) {
int hash = k.hashCode() % SIZE;
Entry e = table[hash];
// Bucket is identified by hashCode and traversed the bucket
// till element is not found.
while(e != null) {
if(e.key.equals(k)) {
return e;
}
e = e.next;
}
return null;
}
/**
* If the map previously contained a mapping for the key, the old
* value is replaced.
*/
public void put(String k, String v) {
int hash = k.hashCode() % SIZE;
Entry e = table[hash];
if(e != null) {
// If we will insert duplicate key-value pair,
// Old value will be replaced by new one.
if(e.key.equals(k)) {
e.value = v;
} else {
// Collision: insert new element at the end of list
// in the same bucket
while(e.next != null) {
e = e.next;
}
Entry entryInOldBucket = new Entry(k, v);
e.next = entryInOldBucket;
}
} else {
// create new bucket for new element in the map.
Entry entryInNewBucket = new Entry(k, v);
table[hash] = entryInNewBucket;
}
}
public static void main(String[] args) {
MyHashMap myHashMap = new MyHashMap();
myHashMap.put("Awadh", "SSE");
myHashMap.put("Rahul", "SSE");
myHashMap.put("Sattu", "SE");
myHashMap.put("Gaurav", "SE");
Entry e = myHashMap.get("Awadh");
System.out.println(""+e.getValue());
}
}
Thanks for giving such a good and simple example .Given below piece of code
is only checking only first value in list and then appending value at end.here you are checking if other value in list may have duplicate key. Please have a look
if(e != null) {
// If we will insert duplicate key-value pair,
// Old value will be replaced by new one.
if(e.key.equals(k)) {
e.value = v;
} else {
// Collision: insert new element at the end of list
// in the same bucket
while(e.next != null) {
e = e.next;
}
Entry entryInOldBucket = new Entry(k, v);
e.next = entryInOldBucket;
}
}
Please Correct if I am wrong
code snippet will be
while(e!=null){
if(e.key.equals(key)){
e.value=value;
break;
}else{
if(e.next!=null){
e=e.next;
}else{
Entry entryInOldBucket = new Entry(k, v);
e.next = entryInOldBucket;
break;
}
}
}
Thanks for giving such a good and simple example .Given below piece of code
is only checking only first value in list and then appending value at end.here you are checking if other value in list may have duplicate key. Please have a look
if(e != null) {
// If we will insert duplicate key-value pair,
// Old value will be replaced by new one.
if(e.key.equals(k)) {
e.value = v;
} else {
// Collision: insert new element at the end of list
// in the same bucket
while(e.next != null) {
e = e.next;
}
Entry entryInOldBucket = new Entry(k, v);
e.next = entryInOldBucket;
}
}
Please Correct if I am wrong
code snippet will be
while(e!=null){
if(e.key.equals(key)){
e.value=value;
break;
}else{
if(e.next!=null){
e=e.next;
}else{
Entry entryInOldBucket = new Entry(k, v);
e.next = entryInOldBucket;
break;
}
}
}
Thanks for giving such a good and simple example .Given below piece of code
is only checking only first value in list and then appending value at end.here you are checking if other value in list may have duplicate key. Please have a look
if(e != null) {
// If we will insert duplicate key-value pair,
// Old value will be replaced by new one.
if(e.key.equals(k)) {
e.value = v;
} else {
// Collision: insert new element at the end of list
// in the same bucket
while(e.next != null) {
e = e.next;
}
Entry entryInOldBucket = new Entry(k, v);
e.next = entryInOldBucket;
}
}
Please Correct if I am wrong
code snippet will be
while(e!=null){
if(e.key.equals(key)){
e.value=value;
break;
}else{
if(e.next!=null){
e=e.next;
}else{
Entry entryInOldBucket = new Entry(k, v);
e.next = entryInOldBucket;
break;
}
}
}
package shortProjects;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;
public class ImplementHashMap {
public static void main(String[] args) {
MyHashMap<Integer, String> myMap = new MyHashMap<Integer, String>();
myMap.put(1, "Jade");
myMap.put(5, "Smith");
System.out.println(myMap.get(1));
System.out.println(myMap.get(5));
System.out.println(myMap.get(2));
System.out.println(myMap.keySet());
System.out.println(myMap.values());
System.out.println(myMap.toString());
}
}
class MyEntry<K,V> {
private K key;
private V value;
public MyEntry(K key, V value){
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}
class MyHashMap<K,V> {
List<MyEntry<K,V>> list;
private int size;
public <K,V> MyHashMap() {
size = 16;
list = new ArrayList(size);
for(int i=0; i<size; i++) {
list.add(null);
}
}
public int size() {
return list.size();
}
public boolean isEmpty() {
return list.isEmpty();
}
public boolean containsKey(Object key) {
int index = getKey(key);
if(list.get(index) != null)
return true;
return false;
}
public boolean containsValue(Object value) {
boolean result = false;
for(int i=0; i<size; i++) {
if(list.get(i) != null && list.get(i).getValue() == value) {
result = true;
}
}
return result;
}
public V get(Object key) {
int index = getKey(key);
MyEntry<K, V> entry = list.get(index);
return entry != null ? list.get(index).getValue() : null;
}
public void put(K key, V value) {
int index = getKey(key);
MyEntry<K,V> entry = new MyEntry(key, value);
list.add(index, entry);
}
public void remove(Object key) {
int index = getKey(key);
list.add(index, null);
}
public int getKey(Object key) {
return Math.abs(key.hashCode() % size);
}
public void putAll(Map<? extends K, ? extends V> m) {
// TODO Auto-generated method stub
}
public void clear() {
for(int i=0; i<size; i++) {
list.add(null);
}
}
public Set<K> keySet() {
Set<K> result = list.stream().filter(entry -> entry!=null).map(entry -> entry.getKey()).collect(Collectors.toSet());
return result;
}
public Collection<V> values() {
Set<V> result = list.stream().filter(entry -> entry!=null).map(entry -> entry.getValue()).collect(Collectors.toSet());
return result;
}
public Set<MyEntry<K, V>> entrySet() {
Set<MyEntry<K, V>> result = list.stream().filter(entry -> entry != null).collect(Collectors.toSet());
return result;
}
public String toString() {
String result = list.stream()
.filter(entry -> entry!=null)
.map(entry -> "{" + entry.getKey() + "=" + entry.getValue() + "}")
.collect(Collectors.joining(","));
return result;
}
public void printAll() {
System.out.println(list);
}
}
HashMap with generics.
package shortProjects;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;
public class ImplementHashMap {
public static void main(String[] args) {
MyHashMap<Integer, String> myMap = new MyHashMap<Integer, String>();
myMap.put(1, "Jade");
myMap.put(5, "Smith");
System.out.println(myMap.get(1));
System.out.println(myMap.get(5));
System.out.println(myMap.get(2));
System.out.println(myMap.keySet());
System.out.println(myMap.values());
System.out.println(myMap.toString());
}
}
class MyEntry<K,V> {
private K key;
private V value;
public MyEntry(K key, V value){
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}
class MyHashMap<K,V> {
List<MyEntry<K,V>> list;
private int size;
public <K,V> MyHashMap() {
size = 16;
list = new ArrayList(size);
for(int i=0; i<size; i++) {
list.add(null);
}
}
public int size() {
return list.size();
}
public boolean isEmpty() {
return list.isEmpty();
}
public boolean containsKey(Object key) {
int index = getKey(key);
if(list.get(index) != null)
return true;
return false;
}
public boolean containsValue(Object value) {
boolean result = false;
for(int i=0; i<size; i++) {
if(list.get(i) != null && list.get(i).getValue() == value) {
result = true;
}
}
return result;
}
public V get(Object key) {
int index = getKey(key);
MyEntry<K, V> entry = list.get(index);
return entry != null ? list.get(index).getValue() : null;
}
public void put(K key, V value) {
int index = getKey(key);
MyEntry<K,V> entry = new MyEntry(key, value);
list.add(index, entry);
}
public void remove(Object key) {
int index = getKey(key);
list.add(index, null);
}
public int getKey(Object key) {
return Math.abs(key.hashCode() % size);
}
public void putAll(Map<? extends K, ? extends V> m) {
// TODO Auto-generated method stub
}
public void clear() {
for(int i=0; i<size; i++) {
list.add(null);
}
}
public Set<K> keySet() {
Set<K> result = list.stream().filter(entry -> entry!=null).map(entry -> entry.getKey()).collect(Collectors.toSet());
return result;
}
public Collection<V> values() {
Set<V> result = list.stream().filter(entry -> entry!=null).map(entry -> entry.getValue()).collect(Collectors.toSet());
return result;
}
public Set<MyEntry<K, V>> entrySet() {
Set<MyEntry<K, V>> result = list.stream().filter(entry -> entry != null).collect(Collectors.toSet());
return result;
}
public String toString() {
String result = list.stream()
.filter(entry -> entry!=null)
.map(entry -> "{" + entry.getKey() + "=" + entry.getValue() + "}")
.collect(Collectors.joining(","));
return result;
}
public void printAll() {
System.out.println(list);
}
}
Thanks for giving such a good and simple example .Given below piece of code
is only checking only first value in list and then appending value at end.here you are checking if other value in list may have duplicate key. Please have a look
if(e != null) { // If we will insert duplicate key-value pair, // Old value will be replaced by new one. if(e.key.equals(k)) { e.value = v; } else { // Collision: insert new element at the end of list // in the same bucket while(e.next != null) { e = e.next; } Entry entryInOldBucket = new Entry(k, v); e.next = entryInOldBucket; } }Please Correct if I am wrong
code snippet will be
- Anonymous September 07, 2018while(e!=null){ if(e.key.equals(key)){ e.value=value; break; }else{ if(e.next!=null){ e=e.next; }else{ Entry entryInOldBucket = new Entry(k, v); e.next = entryInOldBucket; break; } } }