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

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

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