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)

- Gil May 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hashmap?

- Bhaavan May 22, 2015 | Flag Reply
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++){
        unassigned.add(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;
}

- zortlord May 22, 2015 | 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