Recursion and Sorting

Recursion

Recursion is fundamental to many algorithms, but many people find it hard to understand. As a result, interviewers may use recursion challenges to quickly determine who has a good programming IQ.

Recursion in its simplest form involves a function which calls itself once, but this form of recursion can easily be replaced with a loop. Recursion becomes more powerful when the function calls itself multiple times, "branching out" quickly when executing, which let you solve complex problems with little code. Always remember to include a 'base case' in your recursive function so it doesn't cause a stack overflow!

Recursion challenges can be solved with similar strategies as before. If you're stuck, see if you can solve the problem directly for 0, 1 and 2 elements. When solving a case with n elements, try to build off the solution for n-1 elements (or do it in reverse, building off n elements to solve n-1 elements). This approach can then be turned into a recursive function. See Towers of Hanoi I for a walk-through of solving such a problem.

Tutorial & Challenges

You should be able to quickly do Basic Recursion like Factorial and Binary Search. Recursion also comes up in other areas, such as Tree and Graph Algorithms and Sorting Algorithms (see below). Some interviewers may even expect you to know more advanced recursion techniques, such as how to solve the Towers of Hanoi or even Backtracking.

Sorting

Sorting Algorithms

You're unlikely to code your own sorting Algorithm in the real world, but it's still a common interview topic. At the very least, you should know how implement the simple Insertion Sort, but some interviewers may expect you to be familiar with more efficient sorting Algorithms.

Quick Sort is usually the fastest algorithm in the real-world, but you probably won't need to create it 'in-place' on an interview. The key idea behind Quick Sort is to compare a list of elements to one element, partition the list to less-than and greater-than halves, and recursively repeat that process for smaller pieces of the list. Another fast algorithm, Merge Sort starts sorting from small pieces and repeatedly merges the sorted pieces together until the whole array is sorted. These algorithms can be a bit tricky to get right, but practice makes perfect!

Sorting Challenges

Interviewers more often ask about challenges that involve sorting rather than about re-implementing sorting algorithms. Make sure you can solve these challenges:

• Index Match - Simple Binary search challenge.
• Time Scheduler - Can sorting by a certain property help you solve this challenge? (Java Note: you should know how to have a Class implements Comparable so you can use Java's Collection.sort.)
• Maximum Time Range - Similar to the previous challenge.
• Smallest Difference - You can solve this problem in the straightforward manner.
• The Median - Can you use the idea behind Quick Sort to solve this challenge in linear time?
• Extra Credit: Find the Duplicates - Less likely to appear on an interview, but can you use the idea behind Counting Sort to solve this challenge in linear time?