First Java classes in practice
Java base constructs
We introduced extra Java 11 constructs including:
- defining final variables (that cannot be reassigned):
final int x = 0; final var y = 0;
- basic list interface that may be useful our future code:
final List<Integer> l = new ArrayList(); final var l = new ArrayList<Integer>(); l.add(42); // adds new element 42 to array l.add(24); l.remove(1); // removes element from array at index 1
Java tasks
We continue working on some Java tasks that are the continuation of the tasks from last exercises.
Implement
celebrity
function. It gets as an argument a boolean arrayknows
for which we assume that ifknows[i][j] == true
then personi
knows personj
. You need to find in linear time the index of person that is known by all others, but it doesn’t know anybody (including itself). If such person doesn’t exist, return-1
.Sample solution
public static int celebrity(boolean[][] knows) { var candidate = 0; final int n = knows.length; for (var row : knows) assert row.length == n; for (int i = 0; i < n; i++) { if (!knows[i][candidate]) candidate = i; } for (int i = 0; i < n; i++) { if (i == candidate) continue; if (knows[candidate][i]) return -1; if (!knows[i][candidate]) return -1; } return candidate; }
Implement
voteResult
function. It gets as an argument an int arrayvotes
of sizen
that contains the integers from[0, n-1]
-votes[x] = y
means that personx
votes for persony
. Our goal is to find the person that has over half of votes.Sample solution
public static int voteResult(int[] votes) { if (votes.length == 0) return -1; var candidate = votes[0]; var count = 1; for (int i = 1; i < votes.length; i++) { if (votes[i] == candidate) count += 1; else if (count > 0) count -= 1; else { candidate = votes[i]; count = 1; } } var candidateVotes = 0; for (var vote : votes) if (vote == candidate) candidateVotes += 1; final var minVotes = votes.length / 2; if (candidateVotes > minVotes) return candidate; else return -1; }
Implement
Poly
class that will allow adding and multiply polynomials. Provide also someString toString()
method that is responsible for creating some pretty string representation of polynomials.Sample solution
public class Poly { private final int[] coeffs; public Poly(int[] coeffs) { var maxIdx = coeffs.length - 1; while (maxIdx > -1) { if (coeffs[maxIdx] != 0) break; maxIdx -= 1; } this.coeffs = Arrays.copyOf(coeffs, maxIdx + 1); } public Poly add(Poly other) { final var result = new int[Math.max(this.coeffs.length, other.coeffs.length)]; for (int i = 0; i < result.length; i++) { if (i < this.coeffs.length) result[i] += this.coeffs[i]; if (i < other.coeffs.length) result[i] += other.coeffs[i]; } return new Poly(result); } public Poly times(Poly other) { final var result = new int[this.coeffs.length + other.coeffs.length]; for (int i = 0; i < result.length; i++) { for (int j = 0; j <= i; j++) { if (j >= this.coeffs.length) continue; if (i - j >= other.coeffs.length) continue; result[i] += this.coeffs[j] * other.coeffs[i - j]; } } return new Poly(result); } @Override public String toString() { if (this.coeffs.length == 0) return "0"; final var result = new StringBuilder(); for (int i = 0; i < this.coeffs.length; i++) { result.append(this.coeffs[i]); if (i == 1) result.append("x"); else if (i > 1) result.append("x^").append(i); if (i < this.coeffs.length - 1) result.append(" + "); } return result.toString(); } }
Implement
Date
class that will allow incrementing its value by 1 day. Provide also someString toString()
method that is responsible for creating some pretty string representation of dates.Sample solution
public class Date { private final int day; private final int month; private final int year; public Date(int day, int month, int year) { if (month < 1 || month > 12) throw new IllegalArgumentException("invalid month " + month); if (day < 1 || day > daysInMonth(month, year)) throw new IllegalArgumentException("invalid day " + day); if (year == 0) throw new IllegalArgumentException("invalid year " + year); this.day = day; this.month = month; this.year = year; } public Date inc() { final var inMonth = daysInMonth(month, year); final var nextMonth = this.day == inMonth; final var day = nextMonth ? 1 : this.day + 1; final var nextYear = this.month == 12 && nextMonth; final var month = nextYear ? 1 : nextMonth ? this.month + 1 : this.month; final var year = nextYear && this.year == -1 ? 1 : nextYear ? this.year + 1 : this.year; return new Date(day, month, year); } @Override public String toString() { return day + "." + month + "." + year; } private static int daysInMonth(int month, int year) { final var isLeapYear = isLeapYear(year); if (month == 2) return 28 + (isLeapYear ? 1 : 0); return 31 - (month - 1) % 7 % 2; } private static boolean isLeapYear(int year) { if (year % 400 == 0) return true; return year % 4 == 0 && year % 100 != 0; } }