Author name: Mike

Binary search algorithm

Binary search algorithm is a widely used algorithm for sorted sequences. It can be utilized not only for searching, but also for sorting and proving hypotheses on ranges.

The idea of the algorithm is quite simple:

  • divide the range equally into 2 parts
  • only the potential part of the range will be used for further processing.

For example, if we want to find some value in a sorted array:
– we divide the array into 2 equal parts
– we continue searching in potential parts that may contain the searchable value, and skip the other part.

Binary search algorithm is quite fast. Is time complexity is O(log n).

public class ImplementBinarySearch {

  public static void main(String[] args) {
    var sortedArray = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 19};
    var searchItem = 4;
    System.out.println(binarySearch(sortedArray, searchItem));
  }

  private static Integer binarySearch(int[] sortedArray, int searchItem) {
    var low = 0;
    var high = sortedArray.length;
    var mid = (high + low) / 2;
    while (low <= high && sortedArray[mid] != searchItem) {
      if (searchItem > sortedArray[mid]) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
      mid = (high + low) / 2;
    }
    if (sortedArray[mid] == searchItem) {
      return mid;
    } else {
      return null;
    }
  }
}

Binary search algorithm Read More »

BFS in Graphs

The BFS algorithm in Graphs implies the following:

  • predefine a list of visited nodes
  • create a queue instance, put the starting node in the queue
  • while a queue is not empty:
    – poll the queue, take the head element
    – if the head element has already been visited, continue the loop
    – analyze the value of the retrieved node and mark it as visited
    – put to the queue all child nodes
  • time complexity: O(n)
  • space complexity: O(m), where m is the maximum graph width.
public class ImplementGraphBFS {

  private static final Map<String, List<String>> graph = new HashMap<>();

  static {
    graph.put("you", List.of("alice", "bob", "claire"));
    graph.put("bob", List.of("anuj", "peggy"));
    graph.put("alice", List.of("peggy"));
    graph.put("claire", List.of("thom", "jonny"));
    graph.put("anuj", List.of());
    graph.put("peggy", List.of());
    graph.put("thom", List.of());
    graph.put("jonny", List.of());
  }

  public static String search(String startName, String searchable) {
    var queue = new LinkedList<>(graph.get(startName));
    var searched = new ArrayList<String>();
    while (!queue.isEmpty()) {
      var person = queue.poll();
      if (searched.contains(person)) {
        continue;
      }
      if (person.equals(searchable)) {
        return person;
      } else {
        searched.add(person);
        queue.addAll(graph.get(person));
      }
    }
    return null;
  }

  public static void main(String[] args) {
    System.out.println(search("you", "jonny"));
  }
}

BFS in Graphs Read More »

DFS in Graphs

Graph DFS algorithm is so similar to DFS in Trees. Two differences:
– a graph node can have more than 2 children
– a node can be visited multiple times, hence we must mark the visited node to prevent repeated processing.

Text description of the algorithm:
– predefine a list to store all visited nodes
– start DFS from the root node, pass the list of visited nodes as an argument
– if the current node has been already visited, return from the recursive function
– run a DFS on all child nodes

Time complexity: O(n).

Space complexity: O(m), where m – maximal depth of the graph.

public class ImplementGraphDFS {

  private static final Map<String, List<String>> graph = new HashMap<>();

  static {
    graph.put("you", List.of("alice", "bob", "claire"));
    graph.put("bob", List.of("anuj", "peggy"));
    graph.put("alice", List.of("peggy"));
    graph.put("claire", List.of("thom", "jonny"));
    graph.put("anuj", List.of());
    graph.put("peggy", List.of());
    graph.put("thom", List.of());
    graph.put("jonny", List.of());
  }

  public static String search(String startName, String searchable) {
    var searched = new ArrayList<String>();
    return searchDFS(startName, searchable, searched);
  }

  private static String searchDFS(String currentName, String searchable,
      ArrayList<String> searched) {
    if (searched.contains(currentName)) {
      return null;
    }
    searched.add(currentName);
    var nodes = graph.get(currentName);
    if (nodes.contains(searchable)) {
      return searchable;
    }
    for (var node : nodes) {
      var result = searchDFS(node, searchable, searched);
      if (result != null) {
        return result;
      }
    }
    return null;
  }

  public static void main(String[] args) {
    System.out.println(search("you", "jonny"));
  }
}

DFS in Graphs Read More »

BFS (iterative and recursive) in Tree

There are 2 approaches to traversing a binary tree: use Depth-First search (DFS) and Breadth-First search (BFS). In case of BFS, we process the tree as follows:

Iterative processing:

  • start from the root node
  • push current node into queue
  • while the queue is not empty:
    – poll the queue to retrieve node to process
    – analize the value of the retireved node
    – put to the queue both childs of the retireved node.

Recursive processing:

  • start from the root node
  • push current node into queue
  • if the queue is not empty:
    – poll the queue to retrieve node to process
    – analize the value of the retireved node
    – put to the queue both childs of the retireved node.
  • make a recursive call to itself

Time complexity: O(n)

Space complexity: O(l), where l – max width of the tree

import java.util.LinkedList;

public class ImplementBFSInBinaryTree {

  private static void bfsIterative(Node node) {
    var queue = new LinkedList<Node>();
    queue.push(node);
    while (!queue.isEmpty()) {
      var curNode = queue.poll();
      System.out.println(curNode.value);
      if (curNode.left != null) {
        queue.add(curNode.left);
      }
      if (curNode.right != null) {
        queue.add(curNode.right);
      }
    }
  }

  private static void bfsRecursive(LinkedList<Node> queue) {
    if (queue.isEmpty()) {
      return;
    }
    var curNode = queue.poll();
    System.out.println(curNode.value);
    if (curNode.left != null) {
      queue.add(curNode.left);
    }
    if (curNode.right != null) {
      queue.add(curNode.right);
    }
    bfsRecursive(queue);
  }

  public static void main(String[] args) {
    var tree = new BinaryTree<>(50);
    tree.insert(10);
    tree.insert(5);
    tree.insert(15);
    tree.insert(60);
    tree.insert(55);
    tree.insert(65);

    System.out.println("BFS iterative:");
    bfsIterative(tree.root);

    System.out.println("BFS recursive:");
    var queue = new LinkedList<Node>();
    queue.push(tree.root);
    bfsRecursive(queue);
  }
}

BFS (iterative and recursive) in Tree Read More »

DFS in Tree (Pre-order, In-order, Post-order)

There are 2 approaches to traversing a binary tree: use Depth-First search (DFS) and Breadth-First search (BFS). In case of DFS, we process the tree as follows:

In-Order processing:

  • make a recursive call on the left child (1)
  • analyze node value (2)
  • make a recursive call on the right child (3)

Pre-Order processing:

  • analyze a node value (1)
  • make a recursive call on the left child (2)
  • make a recursive call on the right child (3)

Post-Order processing:

  • make a recursive call on the left child (1)
  • make a recursive call on the right child (2)
  • analyze a node value (3)

Time complexity: O(n)

Space complexity: O(m), where m – max depth of the tree

public class ImplementDFSInBinaryTree {

  private static void dfsPreOrder(Node node) {
    System.out.println(node.value);
    if(node.left!=null) {
      dfsPreOrder(node.left);
    }
    if(node.right!=null) {
      dfsPreOrder(node.right);
    }
  }

  private static void dfsInOrder(Node node) {
    if(node.left!=null) {
      dfsInOrder(node.left);
    }
    System.out.println(node.value);
    if(node.right!=null) {
      dfsInOrder(node.right);
    }
  }

  private static void dfsPostOrder(Node node) {
    if(node.left!=null) {
      dfsPostOrder(node.left);
    }
    if(node.right!=null) {
      dfsPostOrder(node.right);
    }
    System.out.println(node.value);
  }

  public static void main(String[] args) {
    var tree = new BinaryTree<>(50);
    tree.insert(10);
    tree.insert(5);
    tree.insert(15);
    tree.insert(60);
    tree.insert(55);
    tree.insert(65);

    System.out.println("DFS preOrder:");
    dfsPreOrder(tree.root);

    System.out.println("DFS inOrder:");
    dfsInOrder(tree.root);

    System.out.println("DFS postOrder:");
    dfsPostOrder(tree.root);
  }
}

DFS in Tree (Pre-order, In-order, Post-order) Read More »

Implement a Binary Tree

To implement a simple binary tree, firstly we have to create a traverse function.

Traverse function

Node<T>[] traverseDFS(Node<T> root, T value, Node<T> parent)

is used to find node with a required value or to find an appropriate insertion position for a value. For example, if this function returns the node with the exact value, it means that the tree contains that value. And if the function returns a node with a different value, it means the returned node might be a good parent for the new node.

The algorithm of traverse function:
– if the required value is less than the current value and a left child exists, re-run the traverse function on the left child
– if the required value is greater than the current value and a right child exists, re-run the traverse function on the right child
– otherwise return the current node.

And only then we will able to build the following methods:

  1. Node insert(T value).
    – run a traverse function on the root node, use the return value as the parent for the new node
  2. Node lookup(T value)
    – run a traverse function on the root node. If the return value is equal to the search value, hence the tree contains a searchable value.
  3. Node remove(T value)
    – run a lookup by value. If returned value is not equal to the search value, then return null.
    Let’s consider 4 possible cases:
    – the node to be deleted doesn’t have children: remove the node link from the parent.
    – the node be deleted has only a left or right child (successor): connect the parent node to the successor.
    – the node to be deleted has both childs: find in the right subtree the closest greater value to the value to be deleted, put the found value in the place of the node to be deleted, remove the found node (use a recursive call).
  4. Time complexity:
    insert, lookup, delete – in worst case O(n)
  5. Space complexity:
    insert, lookup, delete – in worst case O(n), because we need to store a stack for recursive calls.
import java.lang.reflect.Array;

public class ImplementBinaryTree {

  public static class BinaryTree<T extends Comparable<T>> {

    private Node<T> root;

    public BinaryTree(T value) {
      this.root = new Node<>(value, null, null);
    }

    public Node<T> insert(T value) {
      var nodeWithParent = traverseDFS(root, value, null);
      var node = new Node<>(value, null, null);
      if (value.compareTo(nodeWithParent[0].value) < 0) {
        nodeWithParent[0].left = node;
      } else {
        nodeWithParent[0].right = node;
      }
      return node;
    }

    public Node<T> lookup(T value) {
      var nodeWithParent = traverseDFS(root, value, null);
      if (nodeWithParent[0].value == value) {
        return nodeWithParent[0];
      }
      return null;
    }

    public Node<T> remove(T value) {
      var nodeWithParent = traverseDFS(root, value, null);
      var node = nodeWithParent[0];
      var parent = nodeWithParent[1];
      if (node.value != value) {
        return null;
      }
      // node without children
      if (node.left == null && node.right == null) {
        if (parent != null && parent.left == node) {
          parent.left = null;
        }
        if (parent != null && parent.right == node) {
          parent.right = null;
        }
        if (parent == null) {
          this.root = null;
        }
      }
      // node with only left children
      if (node.left != null && node.right == null) {
        if (parent != null && parent.left == node) {
          parent.left = node.left;
        }
        if (parent != null && parent.right == node) {
          parent.right = node.left;
        }
        if (parent == null) {
          this.root = node.left;
        }
      }
      // node with only right children
      if (node.left == null && node.right != null) {
        if (parent != null && parent.left == node) {
          parent.left = node.right;
        }
        if (parent != null && parent.right == node) {
          parent.right = node.right;
        }
        if (parent == null) {
          this.root = node.right;
        }
      }
      // node with both children
      if (node.left != null && node.right != null) {
        var successorWithParent = traverseDFS(node.right, node.value, null);
        var successor = successorWithParent[0];
        var valueReplacement = successor.value;
        remove(successor.value);
        node.value = valueReplacement;
      }
      return node;
    }

    private Node<T>[] traverseDFS(Node<T> root, T value, Node<T> parent) {
      if (value.compareTo(root.value) < 0 && root.left != null) {
        return traverseDFS(root.left, value, root);
      } else if (value.compareTo(root.value) > 0 && root.right != null) {
        return traverseDFS(root.right, value, root);
      } else {
        var result = (Node<T>[]) Array.newInstance(root.getClass(), 2);
        result[0] = root;
        result[1] = parent;
        return result;
      }
    }

    private void printTree() {
      System.out.println(this.root.toString(1));
    }

    public static class Node<T extends Comparable<T>> {

      public T value;
      public Node<T> left;
      public Node<T> right;

      @Override
      public String toString() {
        return String.format("value = %s%nleft = %s%nright = %s%n", value,
            left == null ? "" : left.toString(),
            right == null ? "" : right.toString());
      }

      public String toString(int tabs) {
        return String.format("value = %s%n%sleft = %s%n%sright = %s%n",
            value,
            "\t".repeat(tabs), left == null ? "" : left.toString(tabs + 1),
            "\t".repeat(tabs), right == null ? "" : right.toString(tabs + 1));
      }

      public Node(T value, Node<T> left, Node<T> right) {
        this.value = value;
        this.left = left;
        this.right = right;
      }
    }
  }

  public static void main(String[] args) {
    /*
                50
           10         60
         5    15   55   65
     */
    var tree = new BinaryTree<>(50);
    tree.insert(10);
    tree.insert(5);
    tree.insert(15);
    tree.insert(60);
    tree.insert(55);
    tree.insert(65);
    tree.printTree();
    System.out.println(tree.lookup(55));
    System.out.println(tree.lookup(70));

    tree.remove(50);
    System.out.println(tree.lookup(50));
  }
}

Implement a Binary Tree Read More »

Implement a Queue

Implementation of the Queue is so similar to a Stack. We operate with the queue using a FIFO-approach: add elements to the end (tail) of the queue and retrieve (poll) from the head.

General points of the algorithm:

  1. Store the head and tail in the class fields.
  2. Implement the add(…) method to extend the queue and poll() methods to retrieve the first (head) element.
  3. add(…) appends the queue and assigns the tail to the previous node.
  4. poll() method retrieves the head element and reassigns the new head to the previous element.
  5. Time complexity: O(1) for the add(..) and poll() methods.
  6. Space complexity: O(1) for the add(…) and poll() methods.
public class ImplementQueue {

  private static class Queue<T> {

    private Node<T> head;
    private Node<T> tail;

    private static class Node<T> {

      private final T value;
      private Node<T> prev;

      public Node(T value, Node<T> prev) {
        this.value = value;
        this.prev = prev;
      }
    }

    public void add(T value) {
      var node = new Node<>(value, null);
      if (head == null) {
        head = node;
      } else {
       tail.prev = node;
      }
      tail = node;
    }

    public T poll() {
      if (this.tail == null) {
        throw new IllegalArgumentException("The stack is empty");
      }
      var node = this.head;
      this.head = this.head.prev;
      return node.value;
    }
  }

  public static void main(String[] args) {
    var stack = new Queue<Integer>();
    stack.add(1);
    stack.add(2);
    stack.add(3);
    stack.add(4);
    System.out.println(stack.poll());
    System.out.println(stack.poll());
    System.out.println(stack.poll());
    System.out.println(stack.poll());
    System.out.println(stack.poll());
  }
}

Implement a Queue Read More »

Implement a Stack

Stack is also a type of LinkedList, but without the ability to retrieve i-th element. We can only retrieve (pop) the last added element and add (push) a new element to the top of the stack (LIFO approach).

General points of the algorithm:

  1. Implement the push() method to add an element to the top of the stack. Store the last previous element (tail) in the “prev” property of the new tail.
  2. Implement the pop() method: retrieve the tail node and reassign the tail to the previous element.
  3. Time complexity: O(1) for the push() and pop() methods.
  4. Space complexity: O(1) for the push() and pop() methods.
public class ImplementStack {

  private static class Stack<T> {

    private Node<T> tail;

    private static class Node<T> {

      private final T value;
      private Node<T> prev;

      public Node(T value, Node<T> prev) {
        this.value = value;
        this.prev = prev;
      }
    }

    public void push(T value) {
      var node = new Node<>(value, null);
      if (tail != null) {
        node.prev = this.tail;
      }
      this.tail = node;
    }

    public T pop() {
      if (this.tail == null) {
        throw new IllegalArgumentException("The stack is empty");
      }
      var node = this.tail;
      this.tail = this.tail.prev;
      return node.value;
    }
  }

  public static void main(String[] args) {
    var stack = new Stack<Integer>();
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    System.out.println(stack.pop());
  }
}

Implement a Stack Read More »

Implement a LinkedList

The task of implementing LinkedList can also be encountered during interviews with newcomers. The solution depends on the type of list you require: unidirectional (singly linked) or bidirectional. The following implementation uses a unidirectional (singly linked) LinkedList.

General points of the algorithm:

  1. Store head and tail in the class fields.
  2. Create the following methods:
    – void add(T value)
    – void remove(int i)
    – T get(int i)
  3. Method add(…) is used for add a new node to the list: set the new node as a next node of the tail and reassign the tail.
  4. Method remove(int i) is used to remove i node in order. Iterate through the list, incrementing the counter to position on the correct node. Reassign the tail of the previous node to the next one after the removed node.
  5. Method get(int i) is used accordingly own name to get i node in order the list. To do this, iterate through the list, incrementing the counter to position on the desired node, similar to the remove method.
  6. Time complexity:
    add(…): O(1)
    remove(int i): O(n) in worst case
    get(int i): O(n) in worst case
  7. Space complexity:
    add(…): O(1)
    remove(int i): O(1)
    get(int i): O(1)
public class ImplementLinkedList {

  static class LinkedList<T> {

    private Node<T> head;
    private Node<T> tail;

    private static class Node<T> {

      private final T value;
      private Node<T> next;

      public Node(T value, Node<T> next) {
        this.value = value;
        this.next = next;
      }
    }

    public void add(T value) {
      var node = new Node<T>(value, null);
      if (head == null) {
        this.head = node;
        this.tail = node;
      }
      if (tail != node) {
        this.tail.next = node;
        this.tail = node;
      }
    }

    public void remove(int i) {
      var j = 0;
      Node<T> prevNode = null;
      var currentNode = this.head;
      while (currentNode != null && j != i) {
        prevNode = currentNode;
        currentNode = currentNode.next;
        j++;
      }
      if (i == j) {
        if (prevNode == null) {
          this.head = currentNode.next;
        } else {
          prevNode.next = currentNode.next;
        }
        if (currentNode.next == null) {
          this.tail = prevNode;
        }
      } else {
        throw new IllegalArgumentException("The node with %d index doesn't exist.".formatted(i));
      }
    }

    public T get(int i) {
      var j = 0;
      var currentNode = this.head;
      while (currentNode != null && j != i) {
        currentNode = currentNode.next;
        j++;
      }
      if (i == j) {
        return currentNode.value;
      } else {
        throw new IllegalArgumentException("The node with %d index doesn't exist.".formatted(i));
      }
    }
  }

  public static void main(String[] args) {
    var list = new LinkedList<Integer>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);

    System.out.println(list.get(0));
    System.out.println(list.get(1));
    System.out.println(list.get(2));
    System.out.println(list.get(3));
    System.out.println(list.get(4));
    System.out.println();

    list.remove(0);
    list.remove(2);

    System.out.println(list.get(0));
    System.out.println(list.get(1));
    System.out.println(list.get(2));
  }
}

Implement a LinkedList Read More »

Implement a HashTable

The task to implement a HashTable is the most popular one in interviews.

General points of this algorithm:

  1. Use an array of buckets to store “key-value” pairs .
  2. The number of current bucket is a reminder of the hashed key value divided by the number of buckets.
  3. Usually it’s enough to implement the following methods:
    – void set(String key, T value)
    – T get(String key)
    – List keys()
  4. Method set(…) includes the following logic:
    – calculate the number of bucket to store the “key-value” pair
    – if the bucket is empty, store the “key-value” pair
    – if the bucket is not empty, find the last pair in the stored linked list and add a new pair
  5. Method get(…) implies similar logic to the set method:
    – calculate the number of bucket to store the “key-value” pair
    – find a matching pair in a stored linked list by comparing the keys
  6. Method keys(…) does the following: it iterates through the bucket array and retrieves all the keys of each pair in the stored linked list.
  7. Time complexity:
    set: O(n) in worst case
    get: O(n) in worst case
    keys: O(n)
  8. Space complexity:
    set: O(1)
    get: O(1)
    keys: O(n)
import java.util.ArrayList;
import java.util.List;

public class ImplementHashTable {

  static class HashTable<T> {

    private static final int BUCKETS = 10;
    private final Object[] data;

    public HashTable() {
      this.data = new Object[BUCKETS];
    }

    public void set(String key, T value) {
      var bucket = bucket(key);
      if (this.data[bucket] == null) {
        this.data[bucket(key)] = new Object[]{key, value, null};
      } else {
        var currentNode = ((Object[]) this.data[bucket(key)]);
        var currentKey = (String) ((Object[]) this.data[bucket(key)])[0];
        Object[] prevNode = null;
        while (currentNode != null && !currentKey.equals(key)) {
          prevNode = currentNode;
          currentNode = (Object[]) (currentNode)[2];
          if (currentNode != null) {
            currentKey = (String) (currentNode)[0];
          }
        }
        if (currentNode != null) {
          currentNode[1] = value;
        } else {
          prevNode[2] = new Object[]{key, value, null};
        }
      }
    }

    public T get(String key) {
      var currentNode = ((Object[]) this.data[bucket(key)]);
      var currentKey = (String) ((Object[]) this.data[bucket(key)])[0];
      while (currentNode != null && !currentKey.equals(key)) {
        currentNode = (Object[]) (currentNode)[2];
        if (currentNode != null) {
          currentKey = (String) (currentNode)[0];
        }
      }
      if (currentNode == null) {
        return null;
      } else {
        return (T) currentNode[1];
      }
    }

    public List<String> keys() {
      var result = new ArrayList<String>();
      for (Object datum : this.data) {
        var currentNode = ((Object[]) datum);
        while (currentNode != null) {
          result.add((String) currentNode[0]);
          currentNode = (Object[]) (currentNode)[2];
        }
      }
      return result;
    }

    private int bucket(String key) {
      return key.hashCode() % data.length;
    }
  }

  public static void main(String[] args) {
    var map = new HashTable<Integer>();
    map.set("one", 1);
    map.set("two", 2);
    map.set("three", 3);
    map.set("four", 4);
    map.set("five", 5);
    map.set("six", 6);

    System.out.println(map.get("one"));
    System.out.println(map.get("two"));
    System.out.println(map.get("three"));
    System.out.println(map.get("four"));
    System.out.println(map.get("five"));
    System.out.println(map.get("six"));

    System.out.println(map.keys());
  }
}

Implement a HashTable Read More »

Scroll to Top