Recap on Java basics for coding interviews

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
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();
}
}

(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

5. Dijkstra’s algorithm

  1. Add the first node to the priority queue
  2. Initialise distanceToSource from infinity to zero: Integer.MAX_VALUE
  3. Explore the edges from node popped from PQ and explore those new nodes connected by these edges
  4. 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

Just some code to set up the tree
TYPO: This is preorder, not inorder

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.

10. Parenthesis matching

The hard part about this is that I forgot how string and character work in java…:(

The End! :)

This is a repository of my thoughts on my personal life, my random interests & notes taken down as I navigate my way through the tech world!