Introduction to Java

Java base constructs

We introduced basic Java 11 constructs including:

  • defining variables:
    int x = 0;
    
  • defining arrays initialized with specific values:
    int[] a = {1, 2, 3, 4};
    
  • defining arrays initialized with default values:
    int[] b = new int[bSize];
    
  • declaring methods:
    static int f(int x, int y) {
        return x + y;
    }
    
  • using guessed by compiler types:
    var s = "Hello World";
    var i = 5;
    var j = 3_000_000L;
    
  • using loops:
    • with standard syntax with index
      for (int i = 0; i < array.length; i++) {
          System.out.println(array[i]);
      }
      
    • with syntax allowing to take an element from array
      for (var elem : array) {
          System.out.println(elem);
      }
      
    • other standard (but less used) loops:
      var i = 0;
      while (i < array.length) {
          System.out.println(array[i++]);
      }
      
      int answer;
      do {
          answer = new Random().nextInt();
          System.out.println(answer);
      } while (answer != 42);
      

Java tasks

  1. Implement recursive GCD algorithm in gcdRec

    Sample solution

    public static int gcdRec(int x, int y) {
        if (y != 0) return gcdRec(y, x % y);
        else return x;
    }
    

  2. Implement iterative GCD algorithm in gcdIter

    Sample solution

    public static int gcdIter(int x, int y) {
        while (y != 0) {
            int tmp = y;
            y = x % y;
            x = tmp;
        }
        return x;
    }
    

  3. Implement Fibonacci numbers generation in fibsStandard. It should return count Fibonacci numbers starting from 1, 1, 2, 3, ...

    Sample solution

    public static int[] fibsStandard(int count) {
        final int[] result = new int[count];
        int i = 1;
        int j = 1;
        while (count > 0) {
            result[result.length - count] = i;
            int tmp = j;
            j += i;
            i = tmp;
            count -= 1;
        }
        return result;
    }
    

  4. Implement binomial coefficient calculation. Do it in smart way to handle bigger numbers in a proper way.

    Sample solution

    public static int binomial(int n, int k) {
        int res = 1;
    
        if (k > n - k) k = n - k;
    
        for (int i = 0; i < k; i++) {
            res *= (n - i);
            res /= (i + 1);
        }
    
        return res;
    }
    

  5. Implement eratosthenesSieve that for given n will return an array of all prime numbers not bigger than n.

    Sample solution

    public static int[] eratosthenesSieve(int n) {
        final boolean[] isPrime = new boolean[n + 1];
    
        for (int i = 0; i < n + 1; i++) isPrime[i] = true;
        for (int i = 0; i < 2; i++) isPrime[i] = false;
    
        for (int i = 2; i < Math.sqrt(n) + 1; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    
        int count = 0;
        for (boolean b : isPrime) if (b) count += 1;
    
        final int[] result = new int[count];
        int idx = 0;
        for (int i = 0; i < isPrime.length; i++) {
            if (isPrime[i]) {
                result[idx++] = i;
            }
        }
    
        return result;
    }
    

  6. Implement factorize that for given n will return all prime factors with repetitions for given number that are smaller than n.

    Sample solution

    public static int[] factorize(final int n) {
        final var dividers = eratosthenesSieve(n / 2);
        int currN = n;
        int count = 0;
        for (var div : dividers) {
            while (currN % div == 0) {
                currN /= div;
                count += 1;
            }
        }
    
        final int[] result = new int[count];
        currN = n;
        int idx = 0;
        for (var div : dividers) {
            while (currN % div == 0) {
                currN /= div;
                result[idx++] = div;
            }
        }
    
        return result;
    }
    

  7. Implement intersection that for given two sorted arrays will return a sorted array with the elements that are in both arrays.

    Sample solution

    public static int[] intersection(int[] fst, int[] snd) {
        int i = 0;
        int j = 0;
        int count = 0;
        while (i < fst.length && j < snd.length) {
            if (fst[i] == snd[j]) {
                count += 1;
                i += 1;
                j += 1;
            } 
            else if (fst[i] < snd[j]) i += 1;
            else j += 1;
        }
    
        i = 0;
        j = 0;
        final int[] result = new int[count];
        int idx = 0;
        while (i < fst.length && j < snd.length) {
            if (fst[i] == snd[j]) {
                result[idx++] = fst[i];
                i += 1;
                j += 1;
            } else if (fst[i] < snd[j]) i += 1;
            else j += 1;
        }
        return result;
    }
    

  8. 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.

    Solution template

    public static int celebrity(boolean[][] knows) {
        return -1; // TODO
    }
    

    We're going to continue with this example on next classes.
Previous
Next