Algo Drills

Summary - Object Declarations in Java

Array Declaration

int[] a = new int[3]; // use [] for array instead of ()
int[] a = new int[] {1, 2, 3};
int[] b = {1, 2, 3}; // Same as above

// Declaring a Rectangular Matrix
String[][] arr = new String[6][7]; // 6 rows and 7 columns
// Iterating through the 2D array and assigning values
for (int i = 0; i < arr.length; i++) { // Loop through rows
    for (int j = 0; j < arr[i].length; j++) { // Loop through columns
        arr[i][j] = "-" + i + "_" + j; // Do something
    }
}

ArrayList Declaration

List<Integer> list = new ArrayList<>();
list.add(10);
list.get(0);

LinkedList Declaration

List<String> list = new LinkedList<>();
list.add("Hello");
list.add("World");
list.getFirst();
list.getLast();
list.removeFirst();
list.removeLast();

Stack Declaration

Stack<Integer> stack = new Stack<>();
stack.push(10);           // Add 10
stack.push(20);           // Add 20
System.out.println(stack.peek());  // 20 (top element)
stack.pop();              // Removes 20
System.out.println(stack.isEmpty()); // false
System.out.println(stack.size());   // 1
stack.clear();            // Clear the stack

Queue Declaration

Queue<Integer> queue = new LinkedList<>();
Deque<Integer> deque = new ArrayDeque<>(); // Doubly ended Queue

// Queue Methods
queue.add(10);        // Adds element to queue at the rear, throws an exception if the operation fails
queue.offer(20);      // Adds element to queue at the rear, returns false if the operation fails
queue.poll();         // Removes element from front
queue.peek();         // Retrieves front element
queue.size();         // Returns size
queue.clear();        // Clears queue

// Deque Methods
deque.addFirst(10);   // Adds element to front
deque.offerFirst(20); // Adds element to front
deque.removeLast();   // Removes element from back
deque.peekLast();     // Retrieves last element
deque.size();         // Returns size
deque.clear();        // Clears deque

PriorityQueue Declaration

Queue<Integer> pq = new PriorityQueue<>();
pq.add(10);              // Add 10
pq.offer(20);            // Add 20
System.out.println(pq.peek());  // 10 (head of the queue)
pq.poll();               // Removes 10
System.out.println(pq.isEmpty()); // false
System.out.println(pq.size());   // 1
pq.clear();              // Clear the queue

Set Declaration

HashSet<Integer> set = new HashSet<>();
Set<String> treeSet = new TreeSet<>(Comparator.reverseOrder());

Map Declaration

Map<String, Integer> map = new HashMap<>();
Map<Integer, String> map = new TreeMap<>(Comparator.reverseOrder());

boolean containsValue = map.containsValue(3);
boolean containsKey = map.containsKey("Harry"); // returns true if the key is in the map, false otherwise

// Iterate over the map using entrySet()
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
}

// Iterate over the map using iterator
Iterator<String> itr = map.keySet().iterator(); // Returns iterator to all the keys
while (itr.hasNext()) {
    String key = itr.next();
    Integer value = map.get(key);
}

---

String Parsing and Conversion in Java

Strings to Primitives using parse

parseInt() and parseDouble()

Used for parsing a String into a primitive int or double.

int i = Integer.parseInt("12345");
int j = Integer.valueOf("1234").intValue(); // From String to Wrapper to Primitive

Creating Wrapper Instances using valueOf

valueOf()

Used to create instances of wrapper classes from a String or primitive.

Integer fromPrimitiveInt = Integer.valueOf(25); // From primitive
Integer fromString = Integer.valueOf("90");   // From String

String.valueOf()

Converts primitives and char arrays into Strings.

String intAsString = String.valueOf(42); 
String doubleAsString = String.valueOf(3.14159);
String booleanAsString = String.valueOf(true);
String charArrayAsString = String.valueOf(new char[] {'H', 'e', 'l', 'l', 'o'});

Key Differences

Between parse and valueOf

• parse: Converts a String to a primitive type.
• valueOf: Converts a String or primitive type to a Wrapper object.

Read more about parse and valueOf

Between parse and format

• parse: Converts a String to the data type of the class being parsed.

  LocalDate startLocalDate = LocalDate.parse("2023-10-30"); // yyyy-MM-dd format by default
  

• format: Converts an object to a formatted String.

  String formattedDate = startLocalDate.format(DateTimeFormatter.ofPattern("dd-MMM-YYYY"));
  

---

1D Array

• a.length is a field in array
• Declare simple array

  int[] a = new int[3]; // use [] for array instead of ()
  int[] a = new int[] {1, 2, 3};
  int[] b = {1, 2, 3}; // Same as above
  

• Declare an ArrayList using Arrays.asList()

  List<String> list = Arrays.asList("str1", "str2");
  

• Linearity vs circularity

  arr[idx] = element; // Assign the element at the current index
    
  idx = idx + 1;      // Increment the index linearly until idx reaches arr.length - 1
  idx = (idx + 1) % arr.length;  // Increment the index circularly. The modulo operator ensures that idx wraps around to 0 when it reaches arr.length
  

---

2D Array

• Declare and Iterate through the 2D Array

  // Declaring a Rectangular Matrix
  String[][] arr = new String[6][7]; // 6 rows and 7 columns
    
  // Iterating through the 2D array and assigning values
  for (int i = 0; i < arr.length; i++) { // Loop through rows
    for (int j = 0; j < arr[i].length; j++) { // Loop through columns
        arr[i][j] = "-" + i + "_" + j; // Do something
    }
  }
  

• Using List of List

  // Declaring a 2D Matrix
  List<List<Integer>> list = new ArrayList<>();
    
  // Adding Elements into 2D ArrayList
  list.add(0, Arrays.asList(11, 12, 13));
  list.add(1, Arrays.asList(21, 22, 23));
  list.add(2, Arrays.asList(31, 32, 33));
    
  // Printing the Matrix using FOR Loop
  for (int i = 0; i < list.size(); i = i + 1) {
      for (int j = 0; j < list.get(i).size(); j = i + 1) {
          System.out.print(list.get(i).get(j) + "\t");
      }
      System.out.println();
  }
  

The Arrays Class

Initializing Arrays

int size = 10; // any chosen size

// Primitive array: Initialized to False
boolean[] arr = new boolean[size];

// Wrapper class array: Initialized to False
Boolean[] array = new Boolean[size];
Arrays.fill(array, Boolean.FALSE);

// Primitive array: Initialized to 0
int[] intArr = new int[size];

// Wrapper class array: Initialized to 0
Integer[] wrapperIntArr = new Integer[size];
Arrays.fill(wrapperIntArr, Integer.valueOf(0));

Copying and Comparing Arrays

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

// Copy array
int[] copy = Arrays.copyOf(original, original.length);

// Compare arrays
boolean areEqual = Arrays.equals(original, copy);

Sorting Arrays

String[] stringArr = new String[5];
Arrays.fill(stringArr, "Default Value"); // Initialize all elements
stringArr[2] = "Custom Value"; // Replacing specific elements

// Sorting the array
Arrays.sort(stringArr); // returns void, changes the original array

Maps

Contains Key or Value

boolean containsValue = map.containsValue(3);
boolean containsKey = map.containsKey("Harry"); // returns true if the key is in the map, false otherwise

getOrDefault

Map<String, Integer> map = new HashMap<>();
for (String str : list) { // Considering a list of Strings
    // Use getOrDefault to fetch the current count (default to 0 if the key is not present)
    int count = map.getOrDefault(str, 0);
    map.put(str, count + 1); // Increment the count and update the map
}

Traditional Map Update

for (String str : namesList) {
    if (treeMap.containsKey(str)) {
        treeMap.put(str, map.get(str) + 1);
    } else {
        treeMap.put(str, 1);
    }
}

Put Key-Value

Map<Integer, Integer> map = new HashMap<>();
map.putIfAbsent(key, value);

map.put(1, 100); // Inserts the key-value pair (1, 100)
map.put(1, 200); // Updates the value associated with key 1 to 200, returns 100

map.putIfAbsent(1, 100); // Inserts the key-value pair (1, 100)
map.putIfAbsent(1, 200); // Does nothing because key 1 already exists, returns 100

Remove from Map

// Removes the key/value pair for this key if present. Does nothing if the key is not present.
map.remove(key); // Concurrent Modification Exception in a Loop
itr.remove(); // Used to avoid concurrent modification exception using an Iterator

Map Iterator

Using map.keySet().iterator()

Iterator<String> itr = map.keySet().iterator(); // Returns iterator to all the keys
while (itr.hasNext()) {
    String key = itr.next();
    Integer value = map.get(key);
}

Using map.entrySet()

// Iterate over the map using entrySet()
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
}

Map forEach

treeMap.forEach((key, value) -> System.out.println(key + " -> " + value));

TreeMap with Comparator

TreeMap keeps the Default Natural Sorting Order with the Keys

Map<String, Integer> treeMap = new TreeMap<>(); // Default Natural Sorting Order
Map<String, Integer> treeMapReversed = new TreeMap<>(Comparator.reverseOrder());
Map<String, Integer> treeMapCustom = new TreeMap<>(Comparator.comparing(String::length)); // Custom key sorter

for (String name : namesList) { // From a list of Strings, put String as key
    treeMap.put(name, name.length());
}

---

Character

Primitive to Wrapper

Character d = Character.valueOf('c'); // From primitive to Wrapper

Get ASCII Value of a Character

char myChar = 'a';
int asciiValue = myChar;
System.out.println("From type Casting " + asciiValue);

Get Int from Char (with numerical value) using -'0'

char charNum2 = '2';
int num2 = charNum2 - '0';

Character Checks

System.out.println(Character.isLetter('r')); // true 'r' is a letter
System.out.println(Character.isDigit('4')); // true
System.out.println(!Character.isLetterOrDigit('!')); // true : punctuation mark

System.out.println(Character.compare('1', '1')); // Compare character

Int Array to Keep Char ASCII as Index and Array Value as Count

int[] chars = new int[127]; // primitive int array initializes all the values with 0
char test = 'a';
chars[test]++;
chars['A']++;
System.out.println(Arrays.toString(chars)); // The value of Array at index = asciiVal of char is increased by 1

Get Numeric Value from Character

// Same can be achieved through the library method
// Returns unicode for characters from 10 to 35
System.out.println(Character.getNumericValue('A')); // DO NOT USE THIS
System.out.println(Character.getNumericValue(myChar));
System.out.println(Character.getNumericValue('1'));
/*
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ##1##, 0, 0, 0, 0, 0, 0, 
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,##1##, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]        
  */ 

String

Basic Methods

str1.equals(str2); // For Equality, DO NOT USE == (will compare objects)

str1.compareTo(str2);
// negative if str is "lexicographically" less than str2
// positive if str is "lexicographically" greater than str2
// ZERO if both strings are equal

Check if Blank

System.out.println(" ".isBlank()); // True -> Returns true if the string is empty or contains only white space

Split

// Cut the Strings from spaces into words
String[] words = strList.split(",");

Trim and Strip

String s = " Malgudi Days   ";
System.out.println(s.trim()); // Trimmed blank spaces with all leading and trailing space removed

System.out.println(s.strip()); // Strip is Unicode Aware
System.out.println(s.stripLeading());
System.out.println(s.stripTrailing());

Contains

String sentence = "Hello, world!";
// Check if the string contains a specific substring
boolean containsHello = sentence.contains("Hello");

charAt and substring()

// returns a character at a given index i
str.charAt(i);
str.substring(i, j); // index j not included
str.substring(i); // from i till end

indexOf and lastIndexOf

// 2 if "er" begins from index 1, -1 if not Found
str.indexOf("er");
str.indexOf("er", 2); // start the search from index 2

str.lastIndexOf("ew"); // searches right to left
str.lastIndexOf("ew", 5); // right to left, from index 5

Case Change

str.toLowerCase();
str.toUpperCase();

Compare and Replace

System.out.println(str.replace("a", "$$"));
System.out.println(str.replace('e', '*')); // Character Replace
String str1 = str.replaceAll(" ", ""); // Replace All, takes RegEx

String to Char Array to String

String str = "Pneumonia";
char[] c = str.toLowerCase().toCharArray();
Arrays.sort(c); // Returns void

String revStr = new String(c);

Turn Anything into String

char c = 'C';
int d = 5;
Integer i = 5;
String newStr = String.valueOf(i);

char[] cArr = {'T', 'e', 's', 't'};
String newStrFromArray = String.valueOf(cArr);

Sorting

All sorts - Arrays.sort, listObj.sort, Collections.sort

• returns void
• changes the input array

Arrays Sort

int[] intArray = {4, 5, 3, 8, 2, 71};
Arrays.sort(intArray); // Default Natural Sorting Order
Arrays.sort(intArray, Comparator.reverseOrder()); // Reverse sorting

ListObject Sort

Comparator.nullsFirst() or Comparator.nullsLast() can be used to accommodate null values.

List<Integer> list = Arrays.asList(null, 4, 5, null, 3, 8, 2, 71, null);
list.sort(Comparator.nullsLast(Comparator.naturalOrder())); // Output: [2, 3, 4, 5, 8, 71, null, null, null]
list.sort(Comparator.nullsFirst(Comparator.reverseOrder())); // Output: [null, null, null, 71, 8, 5, 4, 3, 2]

List<String> stringList = Arrays.asList("apple", "banana", "orange");
stringList.sort(Comparator.comparing(String::length).reversed()); // Output: [banana, orange, apple] (since "banana" and "orange" have 6 characters, and "apple" has 5)

Collections Sort

List<Integer> integerListWithNull = Arrays.asList(5, 6, null, 71, 2, 3);
Collections.sort(integerListWithNull, Comparator.nullsLast(Comparator.naturalOrder())); // Output: [2, 3, 5, 6, 71, null]
Collections.sort(integerListWithoutNull, Collections.reverseOrder()); // Output: [71, 6, 5, 3, 2]

List<String> stringList = Arrays.asList("apple", "banana", "orange");
Collections.sort(stringList, Comparator.comparing(String::length)
                                       .thenComparing(Comparator.reverseOrder()));
// Output: [banana, orange, apple] 
// "banana" and "orange" have the same length (6), but "orange" is lexicographically after "banana".

---

Set

Creating Sets

List<String> namesList = Arrays.asList("Harry", "Hermione", "Ron", "Harry", "Ron", "Ron", "Remus");

// Sorted values returned while iterating in TreeSet
Set<String> treeSet = new TreeSet<>(Comparator.reverseOrder());
treeSet.addAll(namesList); // Output: [Ron, Remus, Hermione, Harry]

// Ordering NOT guaranteed in HashSet
Set<Integer> hashSet = new HashSet<>();
hashSet.addAll(namesList); // Output: (Unordered, but no duplicates, e.g., [Hermione, Remus, Harry, Ron])

Add Elements to a Set

// boolean add(E e);
/* Adds the element to the set and returns true if this set does not have this element.
if the element already exists, the call leaves the set unchanged and returns false */
set.add(value);

Find an Element in a Set

/* Returns true if the key is in the set, false otherwise. */
set.contains(key);

Remove from Set

boolean remove(Object o);
// Removes the specified element from this set if it is present. Returns true if this set contained the element
set.remove(key); // Concurrent Modification Exception in a Loop
itr.remove(); // Use of Iterator to avoid concurrent modification exception

Set Iteration

Iterator<String> itr = set.iterator();
while (itr.hasNext()) {
    if (itr.next().length() % 2 == 0) {
        itr.remove();
    }
}

Heap

Declaring Min and Max Heaps

// Primitive Types
Queue<Integer> pq = new PriorityQueue<>(); // Default Natural Sorting Order
Queue<Integer> pq = new PriorityQueue<>(Comparator.naturalOrder()); // Min Heap
Queue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder()); // Max Heap

Heap Methods

// Heap methods
pq.offer(100);
pq.poll(); // Pops the root of the heap

Heap/Priority Queue of Type T

// For Type T
Queue<Employee> heapMax = new PriorityQueue<>(Comparator.comparing(Employee::getAge) // If the employee age is same
                                                .thenComparing(Employee::getSalary)); // Natural Sort Order

Queue

Queue Methods

• offer(): Enqueue (add) elements to the queue
• peek(): Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
• poll(): Retrieves and removes the head of this queue, or returns null if this queue is empty.
• remove(): Removes a single instance of the specified element from this queue, if it is present.
• element(): Retrieves, but does not remove, the head of this queue; differs from peek() -> throws an exception if queue is empty.

// Declare a queue using LinkedList
Queue<String> queue = new LinkedList<>();

// Enqueue (add) elements to the queue
queue.offer("Apple");
queue.offer("Banana");
queue.offer("Orange");

Stack

Stack Methods

• push(E item): Pushes an item onto the top of the stack.
• pop(): Removes the object at the top of the stack and returns that object.
• peek(): Looks at the object at the top of the stack without removing it.
• empty(): Checks if the stack is empty.
• search(Object o): Searches for the specified object in the stack and returns its position.

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);

System.out.println("Top element: " + stack.peek());  // Output: 3

while (!stack.empty()) {
    System.out.println("Popped element: " + stack.pop());
}

// This does not work as stack.pop reduces the size of the stack each time
for (int i = 0; i < stack.size(); i++) {
    System.out.println(stack.pop());
}

Math

Min and Max

int maxNumber = Math.max(10, 20);
float maxFloat = Math.max(15.5f, 12.7f);

int minNumber = Math.min(10, 20);
float minFloat = Math.min(15.5f, 12.7f);

Power and Square Root

double powerIntResult = Math.pow(2, 3);
double powerFloatResult = Math.pow(2.5, 2);

double sqrtResult = Math.sqrt(25);

Absolute Value

int absoluteIntValue = Math.abs(-5);
float absoluteFloatValue = Math.abs(-8.9f);

Ceil and Floor

double ceilIntResult = Math.ceil(5.3);
float ceilFloatResult = (float) Math.ceil(5.3f);

double floorIntResult = Math.floor(5.9);
float floorFloatResult = (float) Math.floor(5.9f);

Logarithm

double log10IntResult = Math.log10(1000);
double log10FloatResult = Math.log10(1000.0f);
double logResult = Math.log(Math.E); // Log base e of e is 1

Bitwise

Left Shift («)

Shifts the bits to the left by a specified number of positions (n) value « n.

• The vacant positions on the right are filled with zeros.
• It effectively multiplies the operand by 2^n.

Signed Right Shift (»)

Shifts the bits of the operand to the right by a specified number of positions.

• It fills the vacant positions on the left with the sign bit (the leftmost bit) to preserve the sign of the number.
• If the number is positive, it fills with 0, and if negative, it fills with 1.
• Divides the number by 2^n.

Unsigned Right Shift (»>)

• It fills the vacant positions on the left with zeros, regardless of the sign bit.
• It is used for logical right shifts, and it treats the operand as an unsigned quantity.
• ALWAYS use this for the while loop, else infinite loop for negative numbers.

Bit Representation

short x = 0b11101011;
Integer.toBinaryString(235);

Negative Number Representation

int positiveNum = 0b00101100; // 44
int twoScomplement = 0b11010100;

Extracts the LSB of a Number

(number & 1);

Clear/Unset the Rightmost Set Bit

x & (x - 1);

Extracts the Rightmost Set Bit

x & ~(x - 1); // Isolates the rightmost 1-bit of y and sets all other bits to 0

Set the Nth Bit (Bitmask)

1 << n;

XOR #1 Cancels When Same

(x ^ x); // 0
(x ^ (~x)); // -1

XOR #2 Adding Without Carrying

// Example usage

Parity = 1 When #1’s Odd

x = (x & (x - 1));
parity = (parity ^ 1);