## Interview Question

• 0

Country: France
Interview Type: Written Test

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

1.

Create a class with the name of the person and the number of people this person knows.
Create a hash where the key would be the person name and the value would be an instance of the class.
this is O(m) in time because you need to loop trough all the pairs and O(n) in memory because you'll have one entry on the hash for each person.
Then you could all all the values to an array (O(n) in memory), sort the array (O(nlog(n) in time) and get the k latest (O(k)) or just add all the values to a priority queue and get the top k times (complexity won't change)
so time complexity would be MAX(O(m), O(nlogn)) and memory would be O(n)

2. I could only think of a O(m * n^2) solution

create a class that represents and edge and for each entry on the lsit of people who know each other, create an instance and add to set. By doing this, you can easily know if there's an edge between 2 nodes. (O(n) in time and memory to create the set and O(1) to check an edge)

now you can loop trough the orinal list again and each entry would represent a group (you could use an array to represent this group).

eg: (1, 6) means we have a group with 2 people inside: 1 and 6.

now, for each possible node, check if they can be added to that group. To do this, you'll need to check if the given node has an edge for evey person in the group.
Once you finished the checking for each node, you'll have a full group and you know its size.
by having the size of all the groups, you have the greatest of them (you don't need to save every size. You can just store the greatest)

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

I'm not sure aboout variables and constraints

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

1. Instead of sorting (O(nlog(n))), you can put them in a min heap (O(n)) and then take the top k (O(k log(k))). If k > n/2, you can use a max heap and remove n-k (O((n-k)log(n-k))).

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

1. Instead of sorting (O(nlog(n))), you can put them in a min heap (O(n)) and then take the top k (O(k log(k))). If k > n/2, you can use a max heap and remove n-k (O((n-k)log(n-k))).

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

public static List<Map.Entry<String, Long>> getMostFriends(List<String[]> friends, int k) {
HashMap<String, Long> person_friend = new HashMap<String, Long>();
Comparator<Map.Entry<String, Long>> valueComparator = new Comparator<Map.Entry<String,Long>>() { @Override public int compare(Map.Entry<String, Long> e1, Map.Entry<String, Long> e2) { Long v1 = e1.getValue(); Long v2 = e2.getValue(); return v2.compareTo(v1); } };

for (int i = 0; i < friends.size(); i++) {
if (person_friend.containsKey(friends.get(i))) {
person_friend.put(friends.get(i), person_friend.get(friends.get(i)) + 1);
} else {
person_friend.put(friends.get(i), 1L);
}
if (person_friend.containsKey(friends.get(i))) {
person_friend.put(friends.get(i), person_friend.get(friends.get(i)) + 1);
} else {
person_friend.put(friends.get(i), 1L);
}
}
List<Map.Entry<String, Long>> listOfEntries = new ArrayList<Map.Entry<String, Long>>(person_friend.entrySet());
Collections.sort(listOfEntries, valueComparator);
return listOfEntries.subList(0,k);
}

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

public static List<Map.Entry<String, Long>> getMostFriends(List<String[]> friends, int k) {
HashMap<String, Long> person_friend = new HashMap<String, Long>();
Comparator<Map.Entry<String, Long>> valueComparator = new Comparator<Map.Entry<String,Long>>() { @Override public int compare(Map.Entry<String, Long> e1, Map.Entry<String, Long> e2) { Long v1 = e1.getValue(); Long v2 = e2.getValue(); return v2.compareTo(v1); } };

for (int i = 0; i < friends.size(); i++) {
if (person_friend.containsKey(friends.get(i))) {
person_friend.put(friends.get(i), person_friend.get(friends.get(i)) + 1);
} else {
person_friend.put(friends.get(i), 1L);
}
if (person_friend.containsKey(friends.get(i))) {
person_friend.put(friends.get(i), person_friend.get(friends.get(i)) + 1);
} else {
person_friend.put(friends.get(i), 1L);
}
}
List<Map.Entry<String, Long>> listOfEntries = new ArrayList<Map.Entry<String, Long>>(person_friend.entrySet());
Collections.sort(listOfEntries, valueComparator);
return listOfEntries.subList(0,k);

}

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.