Skip to content

Instantly share code, notes, and snippets.

@marcellodesales
Last active April 30, 2022 15:21
Show Gist options
  • Save marcellodesales/6df7791b3fbe7b325c97e39b286e4dee to your computer and use it in GitHub Desktop.
Save marcellodesales/6df7791b3fbe7b325c97e39b286e4dee to your computer and use it in GitHub Desktop.
Simple HashMap implementation during interviews, without key-collision
/*
* Click `Run` to execute the snippet below!
*/
import java.io.*;
import java.util.*;
/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* This is a HashMap implementation where
K -> V
*/
interface AppleHashMap {
void upsert(Object k, Object v);
void remove(Object k);
int size();
List<Object> keys();
Object value(Object k);
}
class Solution implements AppleHashMap {
private Object[] keys;
private Object[] values;
private int numberOfElements = 0;
public Solution(int initialSize) {
this.keys = new Object[initialSize];
this.values = new Object[initialSize];
}
public void upsert(Object k, Object v) {
// key collesions will be acceptable as updates
this.keys[this.numberOfElements] = k;
this.values[this.numberOfElements] = v;
this.numberOfElements++;
}
private int index(Object k) {
int foundIndex = -1;
for (Object value : this.keys) {
++foundIndex;
if (value.equals(k)) {
return foundIndex;
}
}
return foundIndex;
}
public void remove(Object k) {
if (this.numberOfElements == 0) {
throw new IllegalStateException("There's nothing to be removed");
}
int keyIndex = this.index(k);
if (keyIndex == -1) {
throw new IllegalArgumentException("There's no key '" + k + "' on the map");
}
this.keys[this.numberOfElements] = null;
this.values[this.numberOfElements] = null;
// implement removal
this.numberOfElements--;
}
public int size() {
return this.numberOfElements;
}
public List<Object> keys() {
return Arrays.asList(this.keys);
}
public Object value(Object k) {
if (k == null) {
throw new IllegalArgumentException("Pass a key");
}
int keyIndex = this.index(k);
if (keyIndex == -1) {
throw new IllegalArgumentException("There's no value associated with key '" + k + "' on the map");
}
return this.values[keyIndex];
}
public static void main(String[] args) {
AppleHashMap interviewMap = new Solution(2);
System.out.println("Init Current size: " + interviewMap.size());
interviewMap.upsert("Marcello", "San Diego");
interviewMap.upsert("Stanley", "San Francisco");
System.out.println("Current size: " + interviewMap.size());
for (Object personName: interviewMap.keys()) {
System.out.println("Key: " + personName + " = " + interviewMap.value(personName));
}
}
}
Marcello DeSales ran 105 lines of Java (finished in 2.58s):
Init Current size: 0
Current size: 2
Key: Marcello = San Diego
Key: Leandro = Maceio
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment