Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
9
of 15 vote

This problem is the same as LRU cache design, using double linked list and hash table.

- Jason November 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

for a history of size 5?

- / November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

read the problem carefully, "no duplicates allowed, and 5 can be any N later"

- Jason November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

ha ha yeah it's hidden in there (real problem definition is hidden in an example

in that case your answer should be upvoted highest because you had it before Ajeet

- / November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

good solution

- Anonymous November 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why do you need the list to be double linked?

- Anonymous December 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

To be able to delete node from list for O(1)

- harcisis September 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I thought of the exact same solution!! The only reason deletion in the Java/C++ api linked list is O(n) is because we don't have the reference to the link we want to delete, so we search in O(n). But in this case, the operations are internal and thus the references can be saved. We could keep storing the newly added url nodes' reference in a HashMap. If the new url already exists in the map, get its reference, delete it, update reference. All in O(1).

- renegade403 January 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
4
of 6 vote

O(1) insert and O(1) history retrieve:

#include <iostream>
#include <list>
#include <unordered_map>
#include <string>

class LRU {
    size_t maxSize;
    std::list<std::string> hist;
    std::unordered_map<std::string, std::list<std::string>::iterator>
        histIterators;

public:
    LRU(size_t size) : maxSize(size) {}

    void visit(const std::string &url) {
        auto entry = histIterators.find(url);
        if(entry == histIterators.end()) {
            if(hist.size() > maxSize)
            {
                std::string last = hist.back();
                hist.pop_back();
                histIterators.erase(last);
            }
        } else {
            hist.erase(entry->second);
        }
        hist.push_front(url);
        histIterators.insert(
                    std::pair<std::string, std::list<std::string>::iterator>(
                        url, hist.begin()));
    }

    std::list<std::string> &getHistory() {
        return hist;
    }
};

int main()
{
    LRU bh(5);
    bh.visit("G");
    bh.visit("A");
    bh.visit("B");
    bh.visit("C");
    bh.visit("A");
    bh.visit("Y");

    std::list<std::string> &hist = bh.getHistory();

    return 0;
}

- Iuri Covalisin November 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if(hist.size() > maxSize)

I think it should be

if(hist.size() >= maxSize)

- honghaijie May 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Implementation and unit tests:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class BrowserHistory {
	private int maxSize;
	private Node firstNode;
	private Node lastNode;
	private Map<Character, Node> map = new HashMap<Character, Node>();

	public BrowserHistory(List<Character> characters, int maxSize) {
		this.maxSize = maxSize;
		for(Character character : characters) {
			visit(character);
		}
	}

	public void visit(Character character) {
		if(map.containsKey(character)) {
			putInFront(character);
			return;
		}
		
		// First make sure we have enough space to store the node
		if(map.size() == maxSize) {
			// We are full
			deleteLast();
		}
		insertFirst(character);
	}

	private void insertFirst(Character character) {
		// We don't have it yet: Add it as the first element
		Node newNode = new Node(character);
		if(firstNode == null) {
			// This is the first element: It is the first and last element at the same time now.
			lastNode = newNode;
		} else {
			Node oldFirstNode = firstNode;
			
			newNode.next = oldFirstNode;
			oldFirstNode.previous = newNode;
		}
		firstNode = newNode;
		map.put(character, newNode);
	}

	private void deleteLast() {
		// Detach the last node
		lastNode.previous.next = null;
		map.remove(lastNode);
		
		// Remove the last node
		lastNode = lastNode.previous;
		lastNode.next = null;
	}

	private void putInFront(Character character) {
		// We already have this item. Put it in front
		Node node = map.get(character);
		
		// Remove node from the list and reattach pointers
		if(node.previous != null) {
			node.previous.next = node.next;
		}
		if(node.next != null) {
			node.next.previous = node.previous;
		}
		
		// Prepend the node
		if(node != firstNode) {
			node.next = firstNode;
			firstNode.previous = node;
		}
		node.previous = null;
		
		// Set the first node to be our current node.
		firstNode = node;
	}

	public List<Character> getHistory() {
		List<Character> list = new ArrayList<Character>();
		Node node = firstNode;
		while(node != null) {
			list.add(node.getValue());
			node = node.next;
		}
		return list;
	}
}

------------------------------------------------------------------------

Tests:

import static org.junit.Assert.assertEquals;

import java.util.Arrays;
import java.util.Collections;

import org.junit.Test;

public class BrowserHistoryTest {
	@Test
	public void testNone() throws Exception {
		BrowserHistory history = new BrowserHistory(Collections.<Character> emptyList(), 3);
		assertEquals(Arrays.asList(), history.getHistory());
	}


	@Test
	public void testOne() throws Exception {
		BrowserHistory history = new BrowserHistory(Arrays.asList('a'), 3);
		assertEquals(Arrays.asList('a'), history.getHistory());
	}

	@Test
	public void testNormal() throws Exception {
		BrowserHistory history = new BrowserHistory(Arrays.asList('a', 'b', 'c'), 3);
		assertEquals(Arrays.asList('c', 'b', 'a'), history.getHistory());
	}
	
	@Test
	public void testHistoryFull() throws Exception {
		BrowserHistory history = new BrowserHistory(Arrays.asList('a', 'b', 'c'), 2);
		assertEquals(Arrays.asList('c', 'b'), history.getHistory());
	}
	
	@Test
	public void testSameElement() throws Exception {
		BrowserHistory history = new BrowserHistory(Arrays.asList('a', 'a'), 3);
		assertEquals(Arrays.asList('a'), history.getHistory());
	}
	
	@Test
	public void testSameElementInterleaved() throws Exception {
		BrowserHistory history = new BrowserHistory(Arrays.asList('a', 'b', 'a'), 3);
		assertEquals(Arrays.asList('a', 'b'), history.getHistory());
	}
	
	@Test
	public void testSameElementSizeTwo() throws Exception {
		BrowserHistory history = new BrowserHistory(Arrays.asList('a', 'b', 'b'), 3);
		assertEquals(Arrays.asList('b', 'a'), history.getHistory());
	}
	
	@Test
	public void testSameElementLots() throws Exception {
		BrowserHistory history = new BrowserHistory(Arrays.asList('a', 'b', 'a', 'c', 'a', 'b'), 3);
		assertEquals(Arrays.asList('b', 'a', 'c'), history.getHistory());
	}
}

- A V March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

I took a similar approach by using a Map and Linked List. In the map, I store a pointer to the linked list object corresponding to the URL. If the same page is visited twice, the address is used to find the object in the list, remove it, and re-insert it at the head.

Also, you can always obtain the last "N" pages by traversing through the list from the head down.

Here is the C++ code:

#pragma once
#include <string>
#include <map>
#define nullptr 0
using namespace std;

class URLHistory
{
public:
	URLHistory(void) {
		url_list_head = nullptr;
	};
	~URLHistory(void) {
		//delete the list (not implemented)
	};
	void Insert(string url) {
		if (url_map[url] == 0) {
			// This is a new URL
			URLList* ulist = AddToList(url);
			url_map[url] = ulist;
		}
		else {
			// We had already visited this page. Just bring it to the front
			URLList* ulist = url_map[url];
			if (ulist == url_list_head)
				return;
			ulist->prev->next = ulist->next;
			if (ulist->next)
				ulist->next->prev = ulist->prev;
			delete ulist;
			ulist = AddToList(url);
			url_map[url] = ulist;
		}
	};
	// Returns the top N (most recent)
	string* TopN(int N) {
		string* top_N = new string[N];
		URLList* plist = url_list_head;
		unsigned int pos = 0;		
		while(plist != nullptr) {
			top_N[pos++] = plist->url;
			plist = plist->next;
		};
		return top_N;
	};

public:
	class URLList {
	public:
		URLList(string url_, URLList* prev_, URLList* next_) {
			url = url_;
			next = next_;
			prev = prev_;
		};
		string url;
		URLList*	next;
		URLList*	prev;
	};

private:
	URLList* AddToList(string url) {
		URLList* ulist = new URLList(url, nullptr, url_list_head);
		if (url_list_head)
			url_list_head->prev = ulist;
		url_list_head = ulist;
		return url_list_head;
	}




private:
	URLList* url_list_head;
	map<string, URLList*>	url_map;
};

And a sample usage:

string visited_url[10] = {"A", "B", "C", "D", "E", "A", "B", "A", "X", "A"};
	URLHistory history;
	
	for (int k = 0; k < 10; k++) {
		history.Insert(visited_url[k]);
		string* top_6 = history.TopN(6);
		for (int j = 0; j < 6; j++)
			cout << top_6[j] << "|";
		cout << endl;
	}

Output:

A||||||
B|A|||||
C|B|A||||
D|C|B|A|||
E|D|C|B|A||
A|E|D|C|B||
B|A|E|D|C||
A|B|E|D|C||
X|A|B|E|D|C|
A|X|B|E|D|C|

- Ehsan November 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is wrong in the code above? Let's leave some feedback after up/down voting.

- Ehsan November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 4 vote

Anonymous and multiple personality is angered other win this question before one of his namea can win the upvote. So of course downvote all over like a mess and make this question useless so the win become diminished.

Today you notice that anonymous did not use Subbu name but use the / name
He use Subbu name for post good solution usual these days and other names to mess the questions for others
Have names for both construction and destruction.

- algos November 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I did not register. So cannot vote. But thank you for saying that I post good solutions.

I have to say though, you must have a strange mind to come to such conclusions. Hope you get over it soon.

- Subbu. November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I am surprised to be "winner" of this thread. If you were suggesting that I downvote all other answers, sorry, you are not a good detective. Otherwise, forget this post, I am not interested in discussing non-technical issues.

- Jason November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Two upvotes to this idiotic comment by algos at the same instant. Hmm... talking about multiple personalities...

(upvoted by: Oxana.Sidenko and Luri Covalisin).

- Anonymous November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Its like a LRU cache.
It can be solved using Queue,Doubly Linked List, .
For each address he enters create a hash key and store it in queue.
This browser address and hash key store it in a doubly linked list.
Once user again visits same address break the node and bring it to first.

- prashanth November 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is it true love, or self love? Not sure :(

- algos and urik sitting in a tree, k-i-s-s-i-n-g November 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is it true love, or self love? Not sure :(

- algos and urik sitting in a tree, k-i-s-s-i-n-g November 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since the number of elements to keep in the history was 5, I assumed than an array search would be fast enough to prevent any loss of performance.

function History(item) {   
    var list = (this._list || []);
    list.push(item);
    
    var index = list.slice(0, list.length-1).indexOf(item);
    if (index >= 0) {
        list.splice(index, 1);
    }

    // update the array
    this._list = list.reverse().slice(0, Math.min(5, list.length)).reverse();
}

- sumitrochatterjee November 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C version

#include<stdio.h>
#include<stdlib.h>

struct page {
char letter;
struct page  *next; 
};

struct page*  visit_page(struct page *oldroot, char l)
{

struct page *cpage,*newroot; 

cpage =oldroot;
//Search

if(oldroot==NULL)
{
newroot = malloc( sizeof(struct page) );
newroot->letter=l;
newroot->next= NULL;
return newroot;
}

if(oldroot->letter == l)
{
return oldroot;
}

while(cpage->next != NULL){
	if(cpage->next->letter ==l){
		//Duplicate exists
		newroot = cpage->next;
		cpage->next = newroot->next;
		newroot->next = oldroot; 
		return newroot;	
	}
	
	cpage = cpage->next;

}

//Page not in history

newroot = malloc( sizeof(struct page) );
newroot->letter=l;
newroot->next= oldroot;

return newroot;
}


int main()
{
struct page *root = NULL;

root = visit_page(root,'G');
root = visit_page(root,'A');
root = visit_page(root,'B');
root = visit_page(root,'C');
root = visit_page(root,'A');
root = visit_page(root,'Y');


while(root!=NULL)
{
printf("%c,",root->letter);
root = root->next;
}


}

- Vaibhav Gorde December 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class List {
	Node end;

	Node add(String url) {
		Node node = new Node(url);
		if (end != null) {
			end.next = node;
			node.previous = end;
		}

		end = node;
		return node;
	}

	void remove(Node node) {
		Node previousNode = node.previous;
		Node nextNode = node.next;

		if (previousNode != null) {
			previousNode.next = nextNode;
		}

		if (nextNode != null) {
			nextNode.previous = previousNode;
		} else {
			end = previousNode;
		}
	}

	@Override
	public String toString() {
		Node current = end;
		StringBuilder buf = new StringBuilder();
		while (current != null) {
			buf.append(current + "  ");
			current = current.previous;
		}

		return buf.toString();
	}
}

class Node {

	Node next;
	Node previous;
	String url;

	Node(String url) {
		this.url = url;
	}

	public String toString() {
		return url;
	}
}

public class BrowserHistory {

	public static void main(String[] args) {
		// List l = new List();
		// l.add("a");
		// l.add("b");
		// l.add("c");
		// Node n =l.add("d");
		// l.remove(n);
		// System.out.println(l);

		BrowserHistory h = new BrowserHistory();

		// GABCAY
		h.addToHistory("G");
		h.addToHistory("A");
		h.addToHistory("B");
		h.addToHistory("C");
		h.addToHistory("A");
		h.addToHistory("Y");

		System.out.println(h.getHistory(5));

	}

	List history = new List();
	Hashtable<String, Node> nodes = new Hashtable<String, Node>();

	void addToHistory(String url) {
		Node node = nodes.get(url);
		if (node != null) {
			history.remove(node);
		}

		Node newNode = history.add(url);
		nodes.put(url, newNode);
	}

	String getHistory(int n) {
		StringBuilder buf = new StringBuilder();

		Node current = history.end;
		for (int i = 0; i < n && current != null; i++) {
			buf.append(current.url + "  ");
			current = current.previous;
		}
		return buf.toString();
	}

}

- Serdar January 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have a question:Does it require dynamically generating the answer,can't we do it when we need to check the top N history?
If we do it when we need the answer, it'll be quite a different algorithm!

- xljiasjtu July 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 9 vote

We can achieve it by using a circular doubly linked list and a HashMap. 
HashMap will be used to track duplicate elements.

HashMap <key = url><value=ref of linked list's node> storedElements;

Algorithm:
1. add() : 
          check if it already exists(use HashMap) in list. if it is than just remove it from its old 
          location and add at current\tail.
          If does not exists than add it in list at tail and add its reference in hashMap.
          Complexity =O(1)
2. getMostRecentNelements()
          return all elements from tail to head in reverse order.
          Complexity = (N)
Space complexity = O(2N)

- Ajeet November 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 votes

HashMap & list both will be of size N, in given scenario N = 5.

- Ajeet November 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Doing all this for size 5 is major overkill

- / November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You posted this several hours after Jason's exact answer. Waste of space.

- / November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Strange logic behind downvote ...:(

I have already replied it around a month back ..for similar kind of scenario (question?id=5112274943475712).
So it does not matter, when are you replying. It should be only for optimal and perfect solution.

- Ajeet November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

With Java LinkedHashSet, O(1) solution is

LinkedHashSet<String> history = new LinkedHashSet<String>();
	
	void visitPage(String page) {
		
		history.remove(page);

		history.add(page);
		
		if(history.size()>5) {
			history.remove(new ArrayList<String>(history).get(0));
		}
		
	}
	
	void viewHistory() {

		
		ListIterator<String> iterator = new ArrayList(history).listIterator(history.size());

		while(iterator.hasPrevious()) {
			System.out.println(iterator.previous());
		}
		
	}

- Arth November 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here is an example of the O(1) hashtable implementation. The idea is that the linked list has an ordering of the last n websites, and the hashtable maps website to iterators into the list for O(1) find time (for removal when needed).

///
class History
{
public:
History(unsigned sz) : sz(sz) {}
void add_website(string const &website);
list<string> const &get_history(){ return recentlyVisited;}
private:
unsigned sz;

unordered_map<string, list<string>>::iterator> iterators;
list<string> recentlyVisited;
}

add_website(string const &website)
{
// If the website is already in there, just erase it and put it on the front.
auto hashLookup = iterators.find(website);
if(hashLookup != end(iterators))
{
recentlyVisited.erase(hashLookup->second);
recentlyVisisted.push_front(website);
hashLookup->second = begin(recentlyVisited);
return;
}


// Otherwise, add it. If space is used, remove the one that has been unused longest.
if(recentlyVisisted.size() == sz)
{
iterators.erase(recentlyVisited.back());
recentlyVisited.pop_back();
}
recentlyVisited.push_front(website);
iterators.insert(make_pair(website, begin(recentlyVisited)));
}
\\\

But let's do a little bit of real talk. How many websites could there be stored in a website browser? Maybe 4,000. Maybe 6,000. These are all incredibly tiny numbers, and even an O(n) complexity solution will be just fine. In fact, such a solution will outperform a hashtable implementation for n = 5 due to avoiding the overhead. The O(n) complexity is as follows:

Have a list [doubly linked list with stored size] of top n most recently used. called list<string> recentlyVisited. No need for hashtable this time. Find elements in it with a linear search.
add function:
///
add_website(string const &website)
{
// If the website is already in there, just erase it and put it on the front.
auto itr = find(begin(recentlyVisited), end(recentlyVisited), website);
if(itr != end(recentlyVisited))
{
recentlyVisited.erase(itr);
recentlyVisited.push_front(website);
return;
}

// Otherwise, add it. If space is used, remove the one that has been unused longest.
if(recentlyVisited.size() == sz)
{
recentlyVisited.pop_back();
}
recentlyVisited.push_front(website);
}
\\\

- TheRightAnswer November 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You haven't considered multi-threading issues.

- RightTheAnswer November 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 6 vote

And is this a problem from Google or Bloomberg LP?

- Jason November 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

priority queue, implemented as a 'max-heap' on access-time. most recently visited page will be available on the top of team (its time will be greater than all others).

if heap is full, replace the end element and move up the heap readjusting it.

- confused_banda November 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

instead of 'max-heap', a 'max-treap' can be employed. key will be URL for tree operation (search), and key for heap operation (insert, update) will be access time

- confused_banda November 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

circular buffer of size 5

- / November 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

You missed the part where no duplicates are allowed

- Steve M. November 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

no I did not
it's size 5, slide along 5 elements each time before inserting into the circular buffer

anyone who uses fancy stuff for a history of 5 is kidding themselves

- / November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Anyone who thinks browser history would be restricted to showing just the last 5 entries is smoking something.

- RAT November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

for size 5?

Let's think about the actual use case. Would a company do anything other than a simple 5 element array/buffer/circularbuffer for this problem?

- / November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@/: Will a company hardcode 5 and have such a narrow scope of the browser history? Get real.

All these LRU caches and 'fancy data structure; etc are well known and production versions of those are usually available (either open source etc or within large companies themselves).

Multithreading/multi-process could be a consideration as you will have multiple tabs etc and these days browsers use the multi-process model.

Another aspect that is left is the actual storage on the hard disk, for persisting history and the in-memory structure representing that. Add in other features with history usage (like wordwheel) and your answer changes. This talk about company is nonsense. There will be much more to history than just showing that last 5 visited.

I am glad this has -2. This answer now stands out and is not buried in the noise! Thank you downvoters.

- RightTheAnswer November 22, 2013 | Flag


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