Recap on Java basics for coding interviews

LiveRunGrow

7 min readApr 21, 2020

1. Basic class code

A function has to be declared static before using it

2. Scanner to read user input

import java.util.Scanner;

Scanner sc = new Scanner(System.in);

int i = sc.nextInt();

String a = sc.nextLine(); //Reads until next Line \n

String b = sc.next(); //Reads until next space

3. Compiling java program

Compile the .java file to get it translated into the .class file:

javac FirstJavaProgram.java

Run the program:

java FirstJavaProgram

4a. Initialising array

int [] array = {1,2,3,4,5};

int [] array = new int[5];

int [] array2 = new int[array.length];

int [][] b = new int[row][col];

boolean [][] dp = new boolean[row][col];

4b. Initialising strings

String str1 = "good";
String str2 = "good";String str3 = new String("very");
String str4 = new String("very");

Note that in the above, we did not create a string object since the keyword new was not used. Instead, the compiler created a new object for us. If the compiler finds that the object has already been created, it will not create it again but point to that same object. So in the case above, “good” object will only be created once and the two instances str1 and str2 are pointing to the same object.
In the case of str3 and str4, the compiler would create two different objects in memory having the same string.

str.equals(str2);
str.compareTo(str2);

str1 == str2 : return 0
str < str2 : return a positive value
str > str2 : return a negative value

str.length();
str.charAt(1);

String

Immutable -> Once created, cannot be changed. The object created as a String is stored in the Constant String Pool.
Every immutable object in Java is thread safe -> String too -> Cannot be used by two thread simultaneously.

StringBuffer

Mutable -> Can change the value of the object.
Object created is stored in the heap.
It contains the same methods as StringBuilder.
Each method in StringBuffer is thread safe which means each method can only be accessed by one thread at one time.
Thus, StringBuffer is slower.

StringBuilder

Same as StringBuffer and stores object in heap. It is mutable.
However, StringBuilder is not thread safe.

4c. Comparators and Comparables

(1) The Comparator interface defines a compare(arg1, arg2) method with two arguments which represent compared objects and works similarly to the Comparable.compareTo() method.

To create a Comparator, we have to implement the Comparator interface.

PriorityQueue<Node> pq = new PriorityQueue<Node>(new NodeComparator());// Initialise comparator
static class NodeComparator implements Comparator<Node>{
       public int compare(Node n1, Node n2){
           //Method 1 -> min heap           if(n1.getNum()<n2.getNum()) return -1;
           else if (n1.getNum()>n2.getNum()) return 1;
           return 0;           //Method 2 -> Min Heap           
           return n1.getNum-n2.getNum();       } 
}

0, if values in o1 and o2 are equal.
Negative, if the value in o1 is less than in o2.
Positive, if the value in o1 is greater than in o2.

Default: min Heap.

(2) Comparable is an interface defining a strategy of comparing an object with other objects of the same type. This is called the class’s “natural ordering”.

The sorting order is decided by the return value of the compareTo() method.

The method returns a number indicating whether the object being compared is less than, equal to or greater than the object being passed as an argument.

public class Player implements Comparable<Player> {
          //...          @Override  // Min heap          public int compareTo(Player otherPlayer) {              return (this.getRanking() - otherPlayer.getRanking());          }}

Note that when you create a PQ comparator with a custom class, you will need to define in the class

static class Node implements Comparable<Node>{

}

** Note the highlight above.

The Comparable interface is a good choice when used for defining the default ordering or, in other words, if it’s the main way of comparing objects.

Then, we must ask ourselves why use a Comparator if we already have Comparable?

There are several reasons why:

Sometimes, we can’t modify the source code of the class whose objects we want to sort, thus making the use of Comparable impossible
Using Comparators allows us to avoid adding additional code to our domain classes
We can define multiple different comparison strategies which isn’t possible when using Comparable

https://www.baeldung.com/java-comparator-comparable

comparable -> compareTo -> Put in the object class
comparator -> compare -> Pass as a function

https://www.baeldung.com/java-8-comparator-comparing

Comparator.comparing

The Comparator.comparing static function accepts a sort key Function and returns a Comparator.

Arrays.sort(employees, Comparator.comparing(Employee::getName));

We can override the natural ordering (Where we sort names by ascending order) by providing a second argument to make the sorting in a descending order.

Arrays.sort(employees, Comparator.comparing(Employee::getName, (s1,s2) -> {return s2.compareTo(s1);}));

Comparator.reversed

We invoke it on an existing comparator to get the reversed sort order.

Arrays.sort(Comparator.comparing(Employee::getName).reversed());

Comparator.comparingInt

Same as Comparator.comparing but it takes only int selectors.

Arrays.sort(employees, Comparator.comparingInt(Employee::getAge));

Comparator.thenComparing

The thenComparing function lets us set up lexicographical ordering of values by provisioning multiple sort keys in a particular sequence.

Arrays.sort(employees, Comparator.comparing(Employee::getAge).thenComparing(Employee::getName));

Here the ordering will be done by age, and for the values with the same age, the ordering will be done by name.

We can also do thenComparingInt()

5. Dijkstra’s algorithm

Add the first node to the priority queue
Initialise distanceToSource from infinity to zero: Integer.MAX_VALUE
Explore the edges from node popped from PQ and explore those new nodes connected by these edges
Compute their distances and add to PQ if the new distance is smaller

6. Reversing LinkedList

First, you have a linked list that looks like this

Line 15: Secondly, you create two new variables:

nextNode -> point to the next node

reversedLinkedList -> pointer to the head of the reversed list

The reason why nextNode was created is so that you do not lose track of the nextNode since you are going to later remove the Next pointer of current node (which Head is pointing to) to point to reversedLinkedList

Line 16: Thirdly, you change the Next pointer of the current node to point to reverseLinkedList. This current node will be the new head.

Line 17: Fourthly, you need to reassign the new head of reversedLinkedList to currrent node.

Line 18: Lastly, move on to the next node where nextNode is pointing at. Repeat this in a new iteration.

Code:

7. MergeKLists

Note how to use a comparator for java PriorityQueue.

Idea: Maintain a heap of size (3) which is the number of the list. Each time, there should only be one element from each list inside the heap.

createLinkedList are just methods to create linkedlist…

8. DFS, BFS

Queue <Node> q = new LinkedList<Node>();
Remember that Queue is an interface so you cannot instantiate it with Queue. Need to instantiate with LinkedList.
Stack<Node> a = new Stack<Node>();

9. Binary Search Tree

Methods implemented: Delete a value, Select a value
For deletion, we use lazy delete (just initialise a variable to indicate it has been deleted)

if(root == null) return null; //Common check

Deleting a node is harder than it seems. It is the most complicated, but doable operation of all.

There are three cases to this:

(case 1): If the node we want to delete is a leaf node, we can safely remove it without doing anything.

(case 2): If the node we want to delete has either one left child or one right child, then we need to replace the node to be deleted with that child.

(case 3): If the node we want to delete has two children, we have two approaches to this.

First approach: Replace it by the maximum value in its’ left subtree.
Second approach: Replace it by the minimum value node in its’ right subtree.

Note that we do not replace the current node to be deleted completely by its’ replacement because we want to preserve its’ left and right children. Hence, we will only replace it by value, then call the function delete again but this time for the replacement node.