Log in

Log in or create an account.

Behavioural interviews

Behavioural Interviews

System Design Interviews

System Design Interviews

After the interviews

CompensationNegotiation

Sorting

Let's learn one of the most important algorithms you need to know: how to sort stuff.

First thing you need to know about sorting is how to use it in your code. And in 99% of the cases you should use your language's built-in sorting library. Let's see how to use it:

Java
C++
int[] a = {5, 7, 8, 9, -1, 3};
Arrays.sort(a); // sorts a in non-decreasing order

List<Integer> list = Arrays.asList(5, 7, 8, 9, -1, 3);
Collections.sort(list); // sorts list in non-decreasing order

The library sorting methods above in Java and C++ run in O(NlogN) time, which is about as fast as you can do for general sorting.

Let's practice on some real examples. Try to solve the following problem using sorting:

Hint
Solution

Here are some more good sorting problems:

Sorting structs. Intervals.

Another important thing to learn about sorting is to sort custom classes. Usually for this we need to implement some kind of comparator. Let's say we have the following interval class:

Java
C++
private class Interval {
    int from, to; // note: you should generally make these private :)
    public Interval(int from, int to) {
        this.from = from; 
        this.to = to;
    }
    @Override
    public String toString() {
        return "[" + Integer.toString(from) + "," + Integer.toString(to) + "]";
    }
}

To sort intervals by it's starting point (variable from), we will need to somehow implement comparators. Here is how you can do it for Java and C++:

Java
C++
public class Main {
  private static class Interval implements Comparable<Interval> {
      int from, to;
      public Interval(int from, int to) {
          this.from = from; 
          this.to = to;
      }
      @Override
      public String toString() {
          return "[" + Integer.toString(from) + "," + Integer.toString(to) + "]";
      }
      // compareTo implements Comparable interface and allows us to compare and sort the class.
      @Override
      public int compareTo(Interval other) {
          return this.from - other.from;
      }
  }
  public static void main(String[] args) {
      List<Interval> list = Arrays.asList(
          new Interval(5, 7),
          new Interval(3, 8),
          new Interval(4, 6)
      );
      
      // We can create a comparator with lambda function:
      Collections.sort(list, (a, b) -> a.from - b.from);
      System.out.println(list.toString());
      
      // This uses class' compareTo() function
      Collections.sort(list);
      System.out.println(list.toString());
  }
}

If you are not sure how this works, please read more about comparators in your language. It's very important, and very widely used.

Let's practice comparators on the following problem:

Hint
Solution

Here are some more good problems to practice writing comparators: