10 Sorting Algorithms Interview Questions: Theory and Practice for 2019

In our previous article, we explored an overview of various sorting algorithms: how they operate, which scenarios they excel in, and what drawbacks they might have. We also mentioned that you should stay tuned for a more detailed write-up — and here it is! Having refreshed our knowledge of algorithms, we move on to the next stage: interview questions.

Proficiency in algorithms is such an essential part of programming knowledge that it’s hard to imagine great remote developers without it. The great thing about algorithms and when utilized properly, they can really make you shine in the eyes of your employer and colleagues. For this reason, these sorting algorithms interview questions will be a fine addition to your bookmark collection as they will help you become an even better developer!

Theory

Foundational understanding of algorithms and how they work reigns supreme: it’s an indispensable tool for every developer, no matter their specialization. Use this “Theory” section to improve how well you understand algorithms!

1. What is time complexity of an algorithm?

Generally speaking, algorithms are designed to solve problems — in our case, problems of sorting elements in a list. To solve this problem, different approaches can be utilized — and the efficiency of each approach is also different. A good scenario to illustrate this point is finding the square of a number: we can either use n*n or send n into a for loop n times. Naturally, using a method like n*n is far more efficient because it has better time complexity.

The algorithm’s time complexity is a key aspect of its performance. It denotes the total time the algorithm requires to run until it completes. To estimate it, we can count the number of elementary steps that the algorithm performs from start to finish. For n*n, for instance, the algorithm only performs one step (using the mathematical operator *), while the for … n loop requires exactly n steps.

Most importantly, the algorithm’s performance is heavily reliant on the input data and its type; therefore, the worst-case time complexity (the maximum time required) is normally used because it’s impossible to predict all variations in the input data.

2. What are the most common types of sorting algorithms? What is their time complexity?

3. What is a data structure?

To organize the data we want to work with, we utilize data structures: this way, we ensure that the data is organized in an efficient manner. These structures come in different shapes and sizes, allowing the developer to work with their application of choice.

What are linear and non-linear data structures?

• Linear structure organized the elements in a sequence/linear list. Examples of this data structures are: arrays, linked lists, queues, and stacks.
• Non-linear structure, as the name suggests, allows the nodes to traverse and intertwine. Examples of this data structures are: graphs and trees.

Which operations can be performed on various data structures?

• Insert: Add a new element to the given list.
• Delete: Delete an existing element from the given list.
• Traverse: Access each element once for later processing.
• Search: Locate an element if it exists in the list.
• Sort: Arrange the elements in some order.

4. How does Algorithm X work?

A picture is worth a thousand words — so you’re in luck! In our “Sorting Algorithms Overview” article, we created visualizations of how bubble sort, selection sort, insertion sort, quick sort, and merge sort work:

5. What is a binary tree?

Binary tree is tree-type data structure. Its nodes only branch out into 2 directions; they are called “left child” and “right child”, while the tree’s main (i.e. topmost) node is called the root.

Practice

Now it’s time to put your knowledge to practice. Let’s get coding!

6. Create a bubble sort algorithm

public static void sort(int[] input) {
	int inputLength = input.length;
	int temp;
	boolean is_sorted;
	for (int i = 0; i < inputLength; i++) {
		is_sorted = true;
		for (int j = 1; j < (inputLength - i); j++) {
			if (input[j - 1] > input[j]) {
				temp = input[j - 1];
				input[j - 1] = input[j];
				input[j] = temp;
				is_sorted = false;
			}
		}
		if (is_sorted) break;
		System.out.println("\n");
	}
}

7. Compare time complexity of two algorithms

This function will get an array of integers and return the indices of two numbers, adding them to a specific element.

Sample 1:

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

Sample 2:

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

Answer for sample 1: Time complexity : O(n^2). For each element, we try to find its complement by looping through the rest of array which takes O(n) time.

Answer for sample 2: Time complexity : O(n). We traverse the list containing nn elements only once. Each table access costs only O(1) time.

8. Write an algorithm to sort the specified array

int[] input = { 4, 1, 2, 7, 10, 1, 2, 4, 4, 7, 1, 2, 1, 10, 1, 2, 4, 1, 2, 7, 10, 1, 2};

Answer:

import java.util.Arrays;
public class CountiSorter{
  public static void main(String[] args) {
    int[] input = { 4, 1, 2, 7, 10, 1, 2, 4, 4, 7, 1, 2, 1, 10, 1, 2, 4, 1, 2, 7, 10, 1, 2};
    int k = 10;
    // sorting array using Counting Sort Algorithm
    countingSort(input, k);
    System.out.println(Arrays.toString(input));
  }
  public static void countingSort(int[] input, int k) {
    // create buckets
    int counter[] = new int[k + 1];
    // fill buckets
    for (int i : input) {
      counter[i]++;
    }
    // sort array
    int ndx = 0;
    for (int i = 0; i < counter.length; i++) {
      while (0 < counter[i]) {
        input[ndx++] = i;
        counter[i]—;
      }
    }
  }
}

9. Remove duplicates from a sorted list

In a sorted linked list, delete all duplicates.

Sample:

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
Input: 1->1->2->3->3->3->4
Output: 1->2->3->4

Answer:

public ListNode deleteDuplicates(ListNode head) {
    ListNode current = head;
    while (current != null && current.next != null) {
        if (current.next.val == current.val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    return head;
}

10. Find the element’s first and last positions in a sorted array

In an array of integers sorted in ascending order, find the starting and ending positions of a given element. If the target element cannot be located, return [-1, -1].
Sample:

Input:
int[] input = {2,3,3,5,5,5,5,6,8,8,8,10,12,14};
int target = 5;
Output: [3, 6]

Answer:

class Solution {
    private int extremeInsertionIndex(int[] nums, int target, boolean left) {
        int lo = 0;
        int hi = nums.length;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (nums[mid] > target || (left && target == nums[mid])) {
                hi = mid;
            }
            else {
                lo = mid+1;
            }
        }
        return lo;
    }
    public int[] searchRange(int[] nums, int target) {
        int[] targetRange = {-1, -1};
        int leftIdx = extremeInsertionIndex(nums, target, true);
        if (leftIdx == nums.length || nums[leftIdx] != target) {
            return targetRange;
        }
        targetRange[0] = leftIdx;
        targetRange[1] = extremeInsertionIndex(nums, target, false)-1;
        return targetRange;
    }
}

Conclusion

Sorting algorithms and technical interviews might seem like a challenging combo. Still, they’re vital for creation of various awesome projects that we all enjoy. With just enough perseverance, you’ll become the master of data — and our blog will help you do just that! 🙂