## Google Interview Question for Java Developers

• 0

Country: United States

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

Same idea as dictionary but in addition to the key, record the time it was inserted. You can do this by either using a python tuple or using a separate list which keeps track of the times it inserted. I used the latter approach. I present my solution below.

Solution:

``````class HistoricalDict:
def __init__(self):
self._d = {}

def set(self, time, key, value):
if key not in self._d:
self._d[key] = [[value], [time]]
else:
self._d[key][0].append(value)
self._d[key][1].append(time)

def get(self, key, time):
valueList = self._d[key][0][::-1]
timeList = self._d[key][1][::-1]
if time < timeList[-1]: # HistoricalDict has not been created
return None
else:
# Scan from latest creation date
for ind, tempTime in enumerate(timeList):
if time >= tempTime:
return valueList[ind]
return None

def printHistorialDict(self):
print(self._d)

hdict = HistoricalDict()
hdict.set(2, 'foo', 1)
hdict.set(4, 'foo', 2)
hdict.printHistorialDict() # {'foo': [[1, 2], [2, 4]]}
print(hdict.get('foo', 5)) # 2
print(hdict.get('foo', 4)) # 2
print(hdict.get('foo', 3)) # 1
print(hdict.get('foo', 2)) # 1
print(hdict.get('foo', 1)) # None
print(hdict.get('foo', 0)) # None``````

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

use a bst, each node has time, value.
when a get is called, just find the lower bound for that t value.
O(log n) cost if the bst is kept balanced

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

This is good solution. One optimization is that instead of searching all the values, we can do Binary search since the values are kept sorted by time.

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

Why not just write in a regular dictionary with "foo;;WEIRDSEPARATOR;;0" key and thats it :?

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.

### 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.