Google Interview Question Software Developers
Country: United States
Interview Type: Phone Interview
I agree with adr suggestion of using Priority queue but since interviewer's main focus is on optimizing space complexity, storing word information across PQ and hashmap is something that can be improved further.
We can implement a priority queue using a TreeMap itself. This TreeMap will accept a TimeComparator to sort the elements as they are iterated and added to the map. The Key of the Map is Word and value can be timestamp
A couple of key points:
----------
1. Add method on the PriorityQueue (implemented as TreeMap) will first get the element. If the element does not exist, or it exists but the timestamp is older than 10 seconds, we add the element back. Else we ignore the element.
How to remove elements from PQ:
----------
I see 2 ways to do it.
1. A separate thread can pollFirstEntry of the TreeMap and if its older than 10 sec, issue a remove call on TreeMap.
2. Other Map methods like contains, when called, can first check if the key exists, if yes check if the timestamp is older than 10 seconds. If yes, remove the key and return false;
Time Complexity: O(1)
Space complexity: O(N)
Here are some key classes. I havnt shown implementation of the iterator method that will add elements to PQ.
PQ implementation:
=======
public class MinPQ {
private static TreeMap<Word, Long> pq = new TreeMap<Word, Long>(new TimeComparator());
public static void add(Word w) {
Long oldTime = pq.get(w);
if(oldTime == null || System.nanoTime() - oldTime > 1_000_000_000 * 10)
pq.put(w, w.getTime());
else
System.out.println("Word: " + w.getText() + " already exists. Ignoring ...");
}
public static boolean contains(Word w) {
Long oldTime = pq.get(w);
if(oldTime == null)
return false;
if(System.nanoTime() - oldTime > 1_000_000_000 * 10) {
System.out.println("Time stamp old. Removing element: " + w.getText());
pq.remove(w);
return false;
}
return true;
}
public static Word top(){
Map.Entry<Word, Long> entry = pq.pollFirstEntry();
return entry.getKey();
}
}
Word and comparator implementations:
======
public class Word {
String text;
long time;
//constructor and other getter setters
//equals method is critical as this method will be used to compare key already exists in the map based just on the word instead of word and timeStap
@Override
public boolean equals(Object obj) {
Word other = (Word) obj;
if(text.equals(other.text)) return true;
return false;
}
}
public class TimeComparator implements Comparator<Word> {
public int compare(Word w1, Word w2) {
if(w1.getText().equals(w2.getText())) return 0;
return Long.compare(w1.getTime(), w2.getTime());
}
}
Sample Test method:
================
public class TestCode {
public static void main(String[] args) {
MinPQ.add(new Word("word1", System.nanoTime()));
System.out.println("word1 exists = " + MinPQ.contains(new Word("word1", System.nanoTime())));
MinPQ.add(new Word("word3", System.nanoTime()));
System.out.println("word3 exists = " + MinPQ.contains(new Word("word3", System.nanoTime())));
try {
Thread.sleep(15_000); //wait 15 secs and the word is removed from the PQ
}catch(Exception e){}
System.out.println("word3 exists = " + MinPQ.contains(new Word("word3", System.nanoTime())));
}
}
Output:
======
word1 exists = true
word3 exists = true
Time stamp old. Removing element: word3
word3 exists = false
If we can keep it running in the background, the example below is in JS.
Otherwise, when the functions gets called, check the word existence and its date and delete it if applicable.
let words = {};
let selfDestructInterval = 10000;
const pushIt = (wordObj) => {
if (words[wordObj.word]) return false;
else words[wordObj.word] = wordObj.time;
setTimeout(() => {
delete words[wordObj.word]
}, selfDestructInterval);
return true;
}
console.log(pushIt({ word: 'beto', 'time': new Date() })); // true
console.log(pushIt({ word: 'beto', 'time': new Date() })); // false
console.log(pushIt({ word: 'beto', 'time': new Date() })); //true
setInterval(()=>{
console.log(words);
}, 1000)
If we can keep it running in the background, the example below is in JS.
Otherwise, when the functions gets called, check the word existence and its date and delete it if applicable.
let words = {};
let selfDestructInterval = 10000;
const pushIt = (wordObj) => {
if (words[wordObj.word]) return false;
else words[wordObj.word] = wordObj.time;
setTimeout(() => {
delete words[wordObj.word]
}, selfDestructInterval);
return true;
}
console.log(pushIt({ word: 'beto', 'time': new Date() })); // true
console.log(pushIt({ word: 'beto', 'time': new Date() })); // false
console.log(pushIt({ word: 'beto', 'time': new Date() })); // false (correcting previous post)
setInterval(()=>{
console.log(words);
}, 1000)
If we can keep it running in the background, the example below is in JS.
Otherwise, when the functions gets called, check the word existence and its date and delete it if applicable.
let words = {};
let selfDestructInterval = 10000;
const pushIt = (wordObj) => {
if (words[wordObj.word]) return false;
else words[wordObj.word] = wordObj.time;
setTimeout(() => {
delete words[wordObj.word]
}, selfDestructInterval);
return true;
}
console.log(pushIt({ word: 'beto', 'time': new Date() })); // true
console.log(pushIt({ word: 'beto', 'time': new Date() })); // false
console.log(pushIt({ word: 'beto', 'time': new Date() })); // false (correcting previous post)
setInterval(()=>{
console.log(words);
}, 1000)
Thanks for your brilliant idea.
@adr, your idea is very intuitive for me. I combined it with my code and present here.
class WordTime {
String word;
long ts;
public WordTime(String word, long ts) {
this.word = word;
this.ts = ts;
}
}
class Solution implements Iteratable<WordTime> {
Map<String, long> map = new HashMap<String, long>();
Queue<WordTime> minHeap = new PriorityQueue<>((a, b) -> a.ts - b.ts);
Iterator<WordTime> input;
WordTime next = null;
public Solution(Iterator<TimeStr> input) {
this.input = input;
}
@Override
public boolean hasNext() {
if (next != null) {
return true;
}
while (input.hasNext()) {
TimeStr curr = input.getNext();
removeOldTimeWords(curr.ts);
if (!map.containsKey(curr.str)) {
next = curr;
map.put(curr.str, curr.ts + 10000);
return true;
}
if (map.get(curr.str) >= curr.ts) {
continue;
}
next = curr;
map.put(curr.str, curr.ts + 1000);
return true;
}
return false;
}
@Override
public WordTime next() {
if (hasNext()) {
WordTime temp = next;
next = null;
return temp;
}
throw new NoSuchElementException();
}
private void removeOldWords(long ts) {
while (!minHeap.isEmpty() && minHeap.peek().ts < ts - 10000) {
WordTime wt = minHeap.poll();
map.remove(wt.word);
}
}
}
Sounds like you only need 10s worth of data for your check so you could use a priority queue where the key is the timestamp and the value is (word, timestamp). The top element in the queue is the one with the smallest timestamp (oldest). So every time the iterator is used it could repeatedly remove the top element (if it is too old) both from the queue and from the hash map until the oldest stored element's timestamp is not smaller than the current timestamp - 10s.
- adr July 05, 2018