Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CS 245 – Practice Assignment
Practice Assignment 11 – Find the Judge
The goal of this assignment is to practice designing solutions using data structures from this course.
Premise and Task
In a town, there are N people. There is a rumor that one of these people is secretly the town judge. If the
town judge exists, then:
1. The town judge trusts nobody.
2. Everybody (except for the town judge) trusts the town judge.
3. There is exactly one person that satisfies properties 1 and 2.
You are given trust — an array of pairs trust[i] = [a, b] representing that the person labelled a
trusts the person labelled b. Note that the number of people in the town is always between 1 and 1000.
If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1.
Examples of inputs and outputs are shown in Table 1.
N trust Output
Example 1 2 [[1, 2]] 2
Example 2 3 [[1, 3], [2, 3]] 3
Example 3 3 [[1, 3], [2, 3], [3, 1]] -1
Example 4 3 [[1, 2], [2, 3]] -1
Example 5 4 [[1, 3], [1, 4], [2, 3], [2, 4], [4, 3]] 3
Table 1: Examples of inputs (N, trust) and output
Note that:
● The number of people in the town is always between 1 and 1000.
● The number of entries in trust is always less than 10,000
● Each item in the trust array is unique and different
Requirements (Process)
Your implementation must have a class named Judge, and it must contain a function:
public int findJudge (int N, int [][] trust)
… which takes two parameters, in order:
● N: int = number of people in the town
● trust: int [] [] = the trust array, in the form provided above
… and returns the ID of the judge or -1 if no judge is found.
Outside this document, no starter code or other supporting files or documents are provided. You are
expected to design
Grading
The assignment is graded for correctness only. However, other than the contents of Table 1, you are not
provided a test set.
Submission
You are required to submit any number of classes for this assignment. Use GitHub to check in the class
required to complete the implementation. On Canvas, submit the URL for your GitHub repository.