Common algorithms

Dijkstra algorithm

1 Comment / Common algorithms, Interview preparation /

The Dijkstra algorithm serves to find the cheapest path in acyclic graphs with positive weights.

The algorithms can be described as following actions:

  1. Introduce 2 maps:
    – the costs to store the minimum cost of reaching a node from the starting node
    – the parents to store the shortest path.
  2. Introduce a list of processed nodes.
  3. Start with the cheapest and not processed node (according to the map costs and the list of processed nodes).
  4. Find all neighbors of the current node.
  5. Update costs and parents maps if the path through the current node is cheaper than it was.
  6. Put the current node to the list of processed node.
  7. Recursively start from point 3.
  8. After processing, we will have to maps: with the cheapest path from the starting node to all nodes, and the map describing the shortest path from start to finish.

Time complexity: O(n2+m), where n – the number of vertices (nodes), m – the count of the edges

Space complexity: O(n2)

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ImplementDijkstraAlgorithm {

  private static final Map<String, Map<String, Integer>> graph = Map.of(
      "start", Map.of("a", 6, "b", 2),
      "a", Map.of("fin", 1),
      "b", Map.of("a", 3, "fin", 5),
      "fin", Map.of()
  );

  private static final Map<String, Integer> costs = new HashMap<>() {
    {
      put("a", 6);
      put("b", 2);
      put("fin", Integer.MAX_VALUE);
    }
  };

  private static final Map<String, String> parents = new HashMap<>() {
    {
      put("a", "start");
      put("b", "start");
      put("fin", null);
    }
  };

  private static final List<String> processed = new ArrayList<>();

  private static String findLowestNodeCost() {
    return costs.entrySet().stream()
        .filter(entry -> !processed.contains(entry.getKey()))
        .sorted(Comparator.comparingInt(Map.Entry::getValue))
        .map(Map.Entry::getKey)
        .findFirst().orElse(null);
  }

  public static void main(String[] args) {
    var node = findLowestNodeCost();
    while (node != null) {
      var neighbors = graph.get(node);
      var cost = costs.get(node);
      for (var entry : neighbors.entrySet()) {
        var newCost = cost + entry.getValue();
        if (newCost < costs.get(entry.getKey())) {
          costs.put(entry.getKey(), newCost);
          parents.put(entry.getKey(), node);
        }
      }
      processed.add(node);
      node = findLowestNodeCost();
    }
    System.out.println(costs.get("fin"));
  }
}

Dijkstra algorithm Read More »

Counting sort

Leave a Comment / Common algorithms, Interview preparation /

This is a very fast algorithm, but can only be used with arrays with integer values.

This algorithm can be explained as follows:

  • find minimum (min) and maximum (max) value in the integer array
  • create a new array with length = max – min + 1 to store statistics
  • iterate through the initial array and count the array values. Put the value statistics into the previously created array at indexes equal to the values

For example, the initial array:

[1, 2, 3, 2, 1, 5, 0], min = 0, max = 5

Statistics array:

[1, 2, 1, 1, 0, 1]

  • iterate through a statistic array and restore the initial array:

[0, 1, 1, 2, 3, 5]

  • time complexity: O(n+m), where n – the length of the initial array, m – the length of the statistical array
  • space complexity: O(m)
import java.util.Arrays;

public class ImplementCountingSort {

  private static void sort(int[] input) {
    var min = Integer.MAX_VALUE;
    var max = Integer.MIN_VALUE;
    for (int j : input) {
      if (j < min) {
        min = j;
      }
      if (j > max) {
        max = j;
      }
    }
    var arrayLength = max - min + 1;
    var counts = new int[arrayLength];
    for (var i = 0; i < input.length; i++) {
      counts[input[i] - min]++;
    }
    var i = 0;
    for (var j = 0; j < counts.length; j++) {
      while (counts[j] > 0) {
        input[i] = min + j;
        i++;
        counts[j]--;
      }
    }
  }

  public static void main(String[] args) {
    int[] array = {-6, -6, -6, 3, 2, 1};
    System.out.println(Arrays.toString(array));
    sort(array);
    System.out.println(Arrays.toString(array));
  }
}

Counting sort Read More »

Quick sort

Leave a Comment / Common algorithms, Interview preparation /

This algorithm is slightly faster than merge sort and heap sort on random data. Uses a divide-and-conquer approach.

The main idea of the algorithm is as follows:

  • select an element from the array, we will call this element as “pivot”. This element can be any element, let’s take the rightmost element
  • place elements that are smaller than the pivot value to the left side of the pivot
  • place elements that exceed the pivot value to the right side of the pivot
  • recursively call the sort function on the left subarray and the right subarray.

Time complexity (average): O(n log n)

Space complexity: O(n)

import java.util.Arrays;

public class ImplementQuickSort {

  public static void quickSort(int[] array, int left, int right) {
    if (right <= left) {
      return;
    }
    int pivot = array[right];
    int i = left;
    for (int j = left; j < right; j++) {
      if (array[j] < pivot) {
        int buffer = array[i];
        array[i] = array[j];
        array[j] = buffer;
        i++;
      }
    }
    int temp = array[right];
    array[right] = array[i];
    array[i] = temp;

    quickSort(array, left, i - 1);
    quickSort(array, i + 1, right);
  }

  public static void main(String[] args) {
    int[] array = {6, 5, 4, 3, 2, 1};
    System.out.println(Arrays.toString(array));
    quickSort(array, 0, array.length - 1);
    System.out.println(Arrays.toString(array));
  }
}

Quick sort Read More »

Merge sort

1 Comment / Common algorithms, Interview preparation /

Merge sort is an efficient, stable divide-and-conquer algorithm. The main idea of this algorithm is as follows:

  1. Divide the array into parts until the size of the part exceeds 1 element.
  2. Sort each part with another part of the same size using merging sort.
  3. Move forward to merge larger parts than in the previous step.

Time complexity: O(n log n).

Space complexity: O(n).

import java.util.Arrays;

public class ImplementMergeSort {

  private static void mergeSort(int[] array) {
    var length = array.length;
    if (length == 1) {
      return;
    }
    var leftArray = Arrays.copyOfRange(array, 0, length / 2);
    var rightArray = Arrays.copyOfRange(array, length / 2, length);
    mergeSort(leftArray);
    mergeSort(rightArray);
    merge(leftArray, rightArray, array);
  }

  private static void merge(int[] leftArray, int[] rightArray, int[] array) {
    var i = 0;
    var l = 0;
    var r = 0;
    while (l < leftArray.length && r < rightArray.length) {
      if (leftArray[l] < rightArray[r]) {
        array[i++] = leftArray[l++];
      } else {
        array[i++] = rightArray[r++];
      }
    }
    while (l < leftArray.length) {
      array[i++] = leftArray[l++];
    }
    while (r < rightArray.length) {
      array[i++] = rightArray[r++];
    }
  }

  public static void main(String[] args) {
    var array = new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    System.out.println(Arrays.toString(array));
    mergeSort(array);
    System.out.println(Arrays.toString(array));
  }
}

Merge sort Read More »

Insertion sort

Leave a Comment / Common algorithms, Interview preparation /

This algorithm is smarter than bubble sort and selection sort. The main idea of the algorithm is as follows:

  1. Take the i-element from the array.
  2. Swap the elements, starting with element i back to the beginning of the array, until they are in order.

The time complexity is also O(n2), but for small arrays this algorithm is faster than quick sort or merge sort.

import java.util.Arrays;

public class ImplementInsertionSort {

  public static void insertionSort(int[] nums) {
    int i = 1;
    while (i < nums.length) {
      int j = i;
      while (j >= 1 && (nums[j] < nums[j - 1])) {
        var buf = nums[j];
        nums[j] = nums[j - 1];
        nums[j - 1] = buf;
        j--;
      }
      i++;
    }
  }

  public static void main(String[] args) {
    var numbers = new int[]{10, 9, 1, 2, 3, 4, 5, 6, 1};
    System.out.println(Arrays.toString(numbers));
    insertionSort(numbers);
    System.out.println(Arrays.toString(numbers));
  }
}

Insertion sort Read More »

Selection sort

1 Comment / Common algorithms, Interview preparation /

The idea of selection sort: iteratively find a smallest (or biggest) element in the remaining part of array and put it to the appropriate position.

The time complexity is pretty bad: O(n2).

This algorithm can only be used for fairly small arrays.

public class ImplementSelectionSort {

  private static void selectionSort(int[] array) {
    for (int i = 0; i < (array.length - 1); i++) {
      var smallestIndex = findSmallest(array, i);
      var buf = array[i];
      array[i] = array[smallestIndex];
      array[smallestIndex] = buf;
    }
  }

  public static int findSmallest(int[] array, int startingIndex) {
    var smallest = startingIndex;
    for (int i = startingIndex; i < array.length; i++) {
      if (array[i] < array[smallest]) {
        smallest = i;
      }
    }
    return smallest;
  }

  public static void main(String[] args) {
    var array = new int[]{22, 1, 3, 99, 8};
    selectionSort(array);
    for (var elem : array) {
      System.out.println(elem);
    }
  }
}

Selection sort Read More »

Bubble sort

1 Comment / Common algorithms, Interview preparation /

Bubble sort algorithm is the most famous sorting algorithm as it is studied in schools, universities and various computer courses.

The idea of the algorithm is as follows:

  • we iterate through the array and swap adjacent elements pair by pair if they aren’t in the required order.
  • each iteration through the array pushes one item (“bubble”) to the outermost position.

The main weak point of this approach: the time complexity is O(n2).

This algorithm is created for educational purposes only: never use it in production code!

import java.util.Arrays;

public class ImplementBubbleSort {

  // An optimized version of Bubble Sort
  private static void bubbleSort(int[] arr, int n)
  {
    int buffer;
    boolean swapped;
    for (var i = 0; i < n - 1; i++) {
      swapped = false;
      for (var j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          buffer = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = buffer;
          swapped = true;
        }
      }
      if (!swapped)
        break;
    }
  }

  public static void main(String[] args)
  {
    var array = new int[] { 64, 34, 25, 12, 22, 11, 90 };
    var n = array.length;
    bubbleSort(array, n);
    System.out.println("Sorted array: ");
    System.out.println(Arrays.toString(array));
  }
}

Bubble sort Read More »

Binary search algorithm

Leave a Comment / Common algorithms, Interview preparation /

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

Leave a Comment / Common algorithms, Interview preparation /

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

Leave a Comment / Common algorithms, Interview preparation /

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 »

Scroll to Top