Google Interview Question for Software Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Saurabh July 05, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
		}
	}
}

- Anonymous July 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we can make the words a tree. For exapmle, if we have 3 words: 'abcdefg', 'abcdefh', 'abcdefi', make a tree having the parent node as 'abcdef' with 3 child nodes as 'g', 'h' & 'i'.

- Antonio Yu August 26, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Anonymous September 30, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Beto September 30, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Beto September 30, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More