Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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
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).
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;
}
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());
}
}
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|
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.
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.
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.
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();
}
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;
}
}
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();
}
}
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)
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());
}
}
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);
}
\\\
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.
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
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?
@/: 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.
This problem is the same as LRU cache design, using double linked list and hash table.
- Jason November 21, 2013