Interview Question


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)

- diogonlucena May 02, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm not sure aboout variables and constraints

- diogonlucena May 02, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- yehadut June 11, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- yehadut June 11, 2020 | Flag
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)[0])) {
person_friend.put(friends.get(i)[0], person_friend.get(friends.get(i)[0]) + 1);
} else {
person_friend.put(friends.get(i)[0], 1L);
}
if (person_friend.containsKey(friends.get(i)[1])) {
person_friend.put(friends.get(i)[1], person_friend.get(friends.get(i)[1]) + 1);
} else {
person_friend.put(friends.get(i)[1], 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);
}

- I think this should work May 06, 2020 | Flag Reply
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)[0])) {
person_friend.put(friends.get(i)[0], person_friend.get(friends.get(i)[0]) + 1);
} else {
person_friend.put(friends.get(i)[0], 1L);
}
if (person_friend.containsKey(friends.get(i)[1])) {
person_friend.put(friends.get(i)[1], person_friend.get(friends.get(i)[1]) + 1);
} else {
person_friend.put(friends.get(i)[1], 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);

}

- markp May 06, 2020 | 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