## Google Interview Question

Software Engineers**Country:**United States

```
public static void main(String[] args) {
// set up data
ArrayList<Tuple<String, Integer>> MoviesAndFrequency = new ArrayList(
Arrays.asList(new Tuple("abc", 10), new Tuple("def", 15), new Tuple("ghi", 10),
new Tuple("abc", 12), new Tuple("xyz", 100)));
for (Tuple T : MoviesAndFrequency)
T.displayTuple();
HashMap<String, Integer> MovieHash = new HashMap<>();
for (Tuple T : MoviesAndFrequency) {
if (MovieHash.containsKey(T.getX()))
MovieHash.put(T.getX().toString(), MovieHash.get(T.getX().toString()) + (Integer) T.getY());
else
MovieHash.put(T.getX().toString(), (Integer) T.getY());
}
System.out.println("\n" + MovieHash.toString() + "\n");
Map<String, Integer> sorted = MovieHash.entrySet()
.stream()
.sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))
.collect(toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e2,
LinkedHashMap::new));
System.out.println(sorted.toString());
}
```

```
public static void main(String[] args) {
// set up data
ArrayList<Tuple<String, Integer>> MoviesAndFrequency = new ArrayList(
Arrays.asList(new Tuple("abc", 10), new Tuple("def", 15), new Tuple("ghi", 10),
new Tuple("abc", 12), new Tuple("xyz", 100)));
for (Tuple T : MoviesAndFrequency)
T.displayTuple();
HashMap<String, Integer> MovieHash = new HashMap<>();
for (Tuple T : MoviesAndFrequency) {
if (MovieHash.containsKey(T.getX()))
MovieHash.put(T.getX().toString(), MovieHash.get(T.getX().toString()) + (Integer) T.getY());
else
MovieHash.put(T.getX().toString(), (Integer) T.getY());
}
System.out.println("\n" + MovieHash.toString() + "\n");
Map<String, Integer> sorted = MovieHash.entrySet()
.stream()
.sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))
.collect(toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e2,
LinkedHashMap::new));
System.out.println(sorted.toString());
}
```

public static void main(String[] args) {

// set up data

ArrayList<Tuple<String, Integer>> MoviesAndFrequency = new ArrayList(

Arrays.asList(new Tuple("abc", 10), new Tuple("def", 15), new Tuple("ghi", 10),

new Tuple("abc", 12), new Tuple("xyz", 100)));

for (Tuple T : MoviesAndFrequency)

T.displayTuple();

HashMap<String, Integer> MovieHash = new HashMap<>();

for (Tuple T : MoviesAndFrequency) {

if (MovieHash.containsKey(T.getX()))

MovieHash.put(T.getX().toString(), MovieHash.get(T.getX().toString()) + (Integer) T.getY());

else

MovieHash.put(T.getX().toString(), (Integer) T.getY());

}

System.out.println("\n" + MovieHash.toString() + "\n");

Map<String, Integer> sorted = MovieHash.entrySet()

.stream()

.sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))

.collect(toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e2,

LinkedHashMap::new));

System.out.println(sorted.toString());

}

→ traverse through the videos

→ add or update the video you have come across in the results array and add or update the value in a hashtable

→ Initially have an array of size 10, and add the updated value of the video according to insertion sort.

```
def mostRatedVideos(videos):
result = [None]*10
hashtable = {}
for video in videos:
# On first entry add directly, if it doesnt exist in the hashtable update the rate
if(video[0] in hashtable):
hashtable[video[0]] += video[1]
else:
hashtable[video[0]] = video[1]
index = 0
swapping = False
indexOfVideo = -1
while(index < 10):
if(result[index] == None):
result[index] = video[0]
break
if(hashtable[result[index]] > hashtable[video[0]] ):
index += 1
continue
else:
swapping = True
if (video[0] in result):
indexOfVideo = result.index(video[0])
break
index += 1
if(swapping and indexOfVideo == -1):
result[index+1:10] = result[index:9]
result[index] = video[0]
elif(swapping):
result[index+1:indexOfVideo+1] = result[index:indexOfVideo]
result[index] = video[0]
return result
ratedVids = mostRatedVideos([('abc', 10), ('apple', 9), ("banana", 45), ("fanugreek", 1), ("abc", 100), ("dragonfruit", 6), ('frank', 12), ('apricote', 7), ("cherry", 4), ("grape", 17), ("apple", 11), ("dragonfruit", 6)])
print(ratedVids)
```

```
L = [['abc', 10], ['def', 15], ['ghi', 10], ['abc', 12], ['xyz', 100]]
g = group( L ) as { $.o[0] } as { sum( $.value ) as { $.o[1] } }
l = list(g) as { [ $.key, $.value ] }
sortd( l ) where { sign( $.l[1] - $.r[1] ) }
println( str(l , "\n") as { str($.o, "->") } )
```

Produces:

```
xyz->100
abc->22
def->15
ghi->10
```

Use Min Heap, min heap allows you to check with O(1), is the new entry in top 10 rates at the given time t.

For solving this problem, we could use min heap and hashmap. HashMap for locating existing video entry in heap in O(1) time. Asymptotically, O(10), linear search in heap of size 10 (implemented using array) is O(1). But for a considerable size of heap, we could use hashmap.

1. Use Hashmap [<Key>Clip, <Value>WatchRate] to store each entry, and append the watch rate as and when key matches the existing collection.

2. Iterate over the HashMap and build MaxHeap with <Value>WatchRate.

3. Pop the max heap and fill a vector & return.

4. Complexity = (Step 1)N + (Step 2) N log N + (Step 3) N => N Log N

No need to sort full array. We can do in O(k*n) time, where k =10

```
def bubbleSort(arr,k):
n = len(arr)
# Traverse through all array elements
for i in range(k):
# Last i elements are already in place
for j in range(0, n-i-1):
# traverse the array from 0 to n-i-1
# Swap if the element found is greater
# than the next element
if arr[j][1] > arr[j+1][1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [('abc', 100),('abc', 105), ('def', 15), ('ghi', 10), ('abc', 12),
('xyz', 9),('xyz', 19),('xyz', 25),('xyz', 1),('ghi', 11),('xyz', 200),('xyz', 9)]
k =10
bubbleSort(arr,k)
print( arr[::-1][:k] )
```

One way to doing is using Bubble sort O(n*K). Using min heap, we can do it in O(nlogK)

#Bucket Sort

```
def bubbleSort(arr,k):
n = len(arr)
# Traverse through all array elements
for i in range(k):
# Last i elements are already in place
for j in range(0, n-i-1):
# traverse the array from 0 to n-i-1
# Swap if the element found is greater
# than the next element
if arr[j][1] > arr[j+1][1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [('abc', 100),('abc', 105), ('def', 15), ('ghi', 10), ('abc', 12),
('xyz', 9),('xyz', 19),('xyz', 25),('xyz', 1),('ghi', 11),('xyz', 200),('xyz', 9)]
k =10
bubbleSort(arr,k)
print( arr[::-1][:k] )
```

import collections

def findTopTen (aList):

d = collections.defaultdict(list)

final_d = {}

for element in aList:

movie, rate = element[0],element[1]

d[movie].append (rate)

print (d)

for movie, rate in d.items():

final_d[movie] = max(rate)

res =[movie for movie, rate in sorted(final_d.items(),reverse = True, key=lambda x:x[1])]

return res

```
import collections
def findTopTen (aList):
d = collections.defaultdict(list)
final_d = {}
for element in aList:
movie, rate = element[0],element[1]
d[movie].append (rate)
print (d)
for movie, rate in d.items():
final_d[movie] = max(rate)
res =[movie for movie, rate in sorted(final_d.items(),reverse = True, key=lambda x:x[1])]
return res
```

Here's my solution using python

```
L = [("abc", 10), ("def", 15), ("ghi", 10), ("abc", 12), ("xyz", 100)]
# get the top 10 video ratings
def top_video_ratings(L):
# create a dict to sum all the values, O(n)
video_ratings = {}
for (name, rates) in L:
if not name in video_ratings:
video_ratings[name] = 0
video_ratings[name] += rates
# create a list with tuple, that's because we can't sort a dict, O(n)
video_ratings_list = []
for name in video_ratings:
video_ratings_list.append((name, video_ratings[name]))
bubble_sort_desc(video_ratings_list) # sort descending, O(n^2) <-- we can do better with quick sort
# return the top 10
return video_ratings_list[0:10]
def bubble_sort_desc(array):
n = len(array)
for i in range(n):
for j in range(n - i - 1):
# swap values
if array[j][1] < array[j+1][1]:
array[j], array[j+1] = array[j+1], array[j]
print(top_video_ratings(L))
```

sorted_list = sorted(L, key=lambda x:x[1], reverse=True)[:10]

- Anonymous July 03, 2019print [v[0] for v in sorted_list]