Google Interview Question for Software Engineers


Country: United States




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

sorted_list = sorted(L, key=lambda x:x[1], reverse=True)[:10]
print [v[0] for v in sorted_list]

- Anonymous July 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This doesn't work because the question says a video might appear more than once, which suggests that we need to aggregate the scores per video. In other words, we need a dictionary!

- Root July 22, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

sorted_list =  sorted(L, key=lambda x:x[1], reverse=True)[:10]
print [v[0] for v in sorted_list]

- Anonymous July 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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());
	}

- Charles July 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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());
	}

- Charles July 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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());
}

- Anonymous July 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#Swift 5

```
[("A", 1), ("Y", 0), ("X", 1), ("B", 12), ("A", 5)].sorted { $0.1 - $1.1 > 0 }.map { $0.0 }
```

- dimpiax July 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Swift

[("A", 1), ("Y", 0), ("X", 1), ("B", 12), ("A", 5)].sorted { $0.1 - $1.1 > 0 }.map { $0.0 }

- dimpiax July 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

→ 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)

- temp34589 July 05, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- NoOne July 05, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Max Heap

- koustav.adorable July 06, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- nooooob July 07, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use BST

- Anonymous July 10, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

return (L.sort(key = lambda x: x[1], reverse=True))[:10]

- Anonymous July 16, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- HashMap + MaxHeap July 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

cbfc

- HashMap + MaxHeap July 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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] )

- Anonymous August 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are not adding up the counts for the same video. This will fail..

- Anonymous August 06, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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] )

- Rax August 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous August 08, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous August 08, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

just use a binary tree.

log n to update, log n to retrieve top 10.

- unicorn September 13, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const getTop10 = function(videos) {
	if (!videos || !videos.length) return videos;

	const output = [];

	videos.sort((a, b) => b[1] - a[1]);

	for (let i = 0; i < 10; i++) {
		output.push(videos[i][0]);
	}

	return output;
}

- Ricky Cho September 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const getTop10 = function(videos) {
	if (!videos || !videos.length) return videos;

	const output = [];

	videos.sort((a, b) => b[1] - a[1]);

	for (let i = 0; i < 10; i++) {
		output.push(videos[i][0]);
	}

	return output;
}

- Ricky Cho September 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const getTop10 = function(videos) {
if (!videos || !videos.length) return videos;

const output = [];

videos.sort((a, b) => b[1] - a[1]);

for (let i = 0; i < 10; i++) {
output.push(videos[i][0]);
}

return output;
}

- Ricky Cho September 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const getTop10 = function(videos) {
	if (!videos || !videos.length) return videos;

	const output = [];

	videos.sort((a, b) => b[1] - a[1]);

	for (let i = 0; i < 10; i++) {
		output.push(videos[i][0]);
	}

	return output;
}

- Ricky Cho September 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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))

- rainelemental September 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/usr/bin/perl

@L = ( "abc", 10, "def", 15, "ghi", 10, "abc", 12, "xyz", 100 );

for ($i = 0; $i < $#L ; $i+=2)
{
    $map{@L[$i]} += @L[$i+1];
}

foreach $t (sort {$map{$b} <=> $map{$a} } keys %map)
{
    last if (++$x > 3);
    print "$x . $t -> $map{$t} \n";
}

- elf October 15, 2019 | Flag Reply


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