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 array knows for which we assume that if knows[i][j] == true then person i knows person j. 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 array votes of size n that contains the integers from [0, n-1] - votes[x] = y means that person x votes for person y. 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 some String 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 some String 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;
    }
}

Last updated on Mar 23, 2022