Capstone: stdin, FizzBuzz, and beyond

Reading input

Everything so far hardcoded its data. Real judged problems, whether in interviews or in competitive programming, hand your program its data through standard input, the text stream a program can read at runtime, and grade whatever it prints to standard output.

Master that handshake and every DSA problem reduces to three steps: read, solve, print. Java's tool is Scanner:

import java.util.Scanner;

Scanner in = new Scanner(System.in);
int a = in.nextInt();        // next whole number
double d = in.nextDouble();  // next decimal
String w = in.next();        // next single word
String line = in.nextLine(); // rest of the line

nextInt skips spaces and line breaks on its own, so 3 4 on one line and 3 then 4 on two lines both work.

One classic trap is worth memorizing. After nextInt(), a following nextLine() first consumes the leftover end-of-line and often returns an empty string, so call in.nextLine() once to flush before reading a real line.

Reading two numbers and printing a sum

The whole read-solve-print shape in five lines.

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int a = in.nextInt();
    int b = in.nextInt();
    System.out.println(a + b);
  }
}

Input

3 4

Output

7

Two nextInt() calls read the two numbers from one line, since the scanner treats any run of whitespace as a separator. The same code works unchanged if the input arrives as two separate lines.

Note that a + b adds here rather than joining, because both sides are ints. Writing System.out.println("" + a + b) would print 34, which is the lesson 1-3 trap arriving in a program that otherwise looks correct.

The toolkit you now hold

Ten units in, the pieces fit together. A judged problem is read with Scanner, solved with the constructs below, and reported with System.out.println.

The habit that ties them together is naming the complexity of your plan before writing it, then checking whether a map, a sort, or two pointers removes a nested loop.

Where to go next: the data structures and algorithms course builds on exactly this base, adding linked lists, trees, recursion, and graph traversal. Everything there is written in the Java you already read fluently.

FizzBuzz

The classic screening problem, one if chain and one loop.

public class Main {
  public static void main(String[] args) {
    for (int i = 1; i <= 15; i++) {
      if (i % 15 == 0) {
        System.out.println("FizzBuzz");
      } else if (i % 3 == 0) {
        System.out.println("Fizz");
      } else if (i % 5 == 0) {
        System.out.println("Buzz");
      } else {
        System.out.println(i);
      }
    }
  }
}

Output

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz

The order of the branches is the entire difficulty. Testing i % 15 == 0 first is required, because 15 is divisible by 3 as well and an earlier Fizz branch would claim it, given that the first matching branch wins.

println(i) handles the plain-number case with no String conversion, since println is overloaded for int as noted in lesson 4-2. The loop uses i <= 15 because these are values rather than indexes.

The complexity of a frequency-map anagram check

Checking whether two strings of length n are anagrams by building a frequency map of each, as in lesson 10-2, and comparing the maps is O(n).

Building each frequency map is one pass over n characters with O(1) HashMap updates, so O(n) per string. Comparing the maps touches at most n entries. Adding the three parts gives O(n) + O(n) + O(n), which is O(n) because sequential steps add and constants drop.

The sort-based check from lesson 10-2 is O(n log n), so the frequency-map version is asymptotically faster, and saying so is the answer an interviewer is listening for.

For lowercase English letters the map can be replaced by an int[26], which keeps the O(n) time and drops the extra space to a fixed 26 slots. That is the last refinement, and it is why new int[26] appeared as an example back in lesson 7-1.