Adobe Interview Question for Computer Scientists

Country: India
Interview Type: Phone Interview

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

Turn each Team to a Node(Vertex), if a team has won another team, create an edge from the winning team to the loosing team (a dependency)

You now have a graph.

Run topological sort and you are done.

O(V+E) ~ O(N)

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

Hashmap?

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

There are 2 ways to consider this depending on how this function is operating:
1. If this function is simply to sort based on preexisting data and that data effectively ranks between the two teams then this is a basic sort (this would match what is normally done for a 'tournament'. The best runtime for this would be O(n log n) using something like a MergeSort or generally O(n log n) with a quicksort.
2. Alternatively, this could be a situation where every team has played every other team and the ranking is done on overall win / loss record ('round-robin'). This would require O(n^2) run time.

Tournament implementation:

``````public static Team[] rank(Team[] teams){
Comparator<Team> teamComparator(){
@Override
public int compare(Team t1, Team t2){
if(match(t1, t2) == t1){
return -1;
}
return 1;
}
};
Team[] results = new Team[teams.length];
System.arraycopy(teams, 0, results, 0, teams.length);
Arrays.sort(results, teamComparator);
}``````

Round Robin approach:

``````public static Team[] rank(Team[] teams){
Team[] results = new Team[teams.length];
//make a list of all unassigned positions in the results
ArrayList<Integer> unassigned = new ArrayList<Integer>(teams.length);
for(int i = 0; i < teams.length; i++){
}
//now place the teams
for(int i = 0; i < teams.length; i++){
//count the losses of each team compared to the other remaining teams.
int loseRecord= 0;
for(int j = i+1; j < teams.length; j++){
if(match(teams[i], teams[j]) != teams[i]){
loseRecord++;
}
}
//the losses indicates the position in the remaining results where this team should fall
int index = unassigned.remove(loseRecord);
results[index] = team[i];
}
return results;
}``````

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.

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.

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.