Receive New Tutorials

How to Optimize Your Code for Interview Questions

– {{showDate(postTime)}}

optimize your code

There are many different ways to solve interview-type algorithm questions. However given different constraints, some methods become unusable as input size grows. In this tutorial, we’ll analyze the time and space complexity for two different versions of the range summary algorithm. Through this problem, we’ll learn how to optimize code given different constraints and how to analyze the efficiency of our solution.

In this tutorial, we will learn how to optimize solutions to interview type questions by looking into two versions of the range summary algorithm in Ruby.

Let’s begin!

Want to ace your technical interview? Schedule a Technical Interview Practice Session with an expert now!

The Problem

We are given a sorted array of unique integers and must write a method that takes this array and returns an array of ranges of contiguous values. Each range is an array with the start and end integers (inclusive) of the contiguous portions of the original array (see below for a few examples).

Input: [2, 3, 6, 7, 8, 9, 14, 15, 16, 17]
Output: [[2, 3], [6, 9], [14, 17]]

Input: [8, 9]
Output: [[8, 9]]

Input: [1, 3, 5]
Output: [[1, 1], [3, 3], [5, 5]]

Method 1: The Unoptimized (and Ugly) Nested While Loop Way

Let’s begin by taking a look at an unoptimized way to solve this problem to get an idea of what not to do. In this method, we use nested while loops where the outer loop tracks the index of the start of each range and the inner loop tracks the index of the end of each range. Let’s begin by walking through some pseudocode for the solution.

# Define a method, range_summary, that takes in a single array of integers, nums.
# Initialize ranges, as an array with one empty range array inside of it. 
# Initialize index iterators, i and j. i, the index of the beginning of each range starts at 0, and j, the index of the end of each range, starts at 1.
	# Create while loop that iterates while i is less than the length of  nums - 1.
		# If the last range in ranges is empty, add nums[i] to it. 
	# Create inner while loop that iterates until j <= to the  length of nums.
	# Set i equal to j and j equal to i + 1.
	# If nums[j] does not equal nums[i] + 1,
# push nums[i] onto the last range in ranges.
		# Unless nums[j] is the last element of nums,
			# add an empty range array to ranges.
		# Break inner while loop.
	# Set j equal to i + 1.
# Return ranges.

Now, let’s turn that pseudocode into real Ruby code.

def range_summary(nums)
 ranges = [[]]

 i = 0
 j = 1
 while i < nums.length - 1
   ranges.last << nums[i] if ranges.last.empty?

   while j <= nums.length
     i = j
     j = i + 1

     if nums[j] != nums[i] + 1
       ranges.last << nums[i]
       ranges << [] if j != nums.length
       break
     end
   end
   j = i + 1
 end
 ranges
end

As we can see, iterating through the nums array while keeping track of two different indices and instantiating multiple conditionals is complicated and not very readable. When you find yourself nesting loops, that should be a sign that there is possibly a more efficient and legible method.

But how inefficient is our solution? We loop through the outer loop n – 1 times where n is the length of nums. We also iterate through the inner loop n – 1 times in the worst case (if each number in nums is separated by more than 1). In the best case, we loop through the inner loop only once if all the numbers are in order. However, keep in mind that we always want to optimize our solution to handle the worst case. Putting it all together, we can conclude that the worst case time complexity for this solutions is O((n – 1)^2), which reduces to O(n^2).

Space complexity for our solution is actually pretty good. The only two items we store are the integers for the index iterators, i and j. Therefore, the space complexity is constant.

In summary:

Time Complexity: O(n^2)
Space Complexity: O(1)
Readability: 3/10

Method 2: The Elegant Each Loop Way

We’ve hinted that there is a better way to solve the range summary algorithm—so let’s see it! By using variables (first and last for each range that contains) we eliminate the need for an inner loop. Instead, we just iterate through each integer in nums and update the first and last variables. This way ends up being much more readable because we don’t have to keep track of two indices, and we use appropriate variable names. As always, let’s begin with pseudocode.

# Define method, range_summary, that takes in a single array of integers, nums.
	# Initialize ranges to be an empty array.
	# Initialize variable first to equal first value of nums.
	# Create and each_with_index loop, where num is the current element and i is the index.
		# Set variable last equal to num.
		# If the next element is equal to last + 1, 
			# set last equal to the next element.
		# Otherwise,
			# add [first, last] to ranges, 
			# and set first equal to the next element.}
	# Return ranges.

Let’s see it in action.

def range_summary(nums)
 ranges = []
 first = nums.first

 nums.each_with_index do |num, i|
   last = num
   if nums[i + 1] == last + 1
     last = nums[i + 1]
   else
     ranges << [first, last]
      first = nums[i + 1]
   end
 end
 ranges
end

Off the bat, we can see that this is a more optimized solution because it is much more legible. Writing legible code significantly cuts down on development time and makes it easier to make quick updates to code bases. The each_with_index loop iterates through n times in both the worst and best cases. By using a single loop and keeping track of the first and last elements of the ranges, we cut efficiency down from O(n^2) to O(n). Now that’s an optimized solution!

Space complexity for this solution is also constant. We only store the two variables, first and last.

In summary:

Time Complexity: O(n)
Space Complexity: O(1)
Readability: 9/10

Conclusion

Now that we understand how to optimize the range summary algorithm, how do we extend what we have learned and apply it to other algorithmic problems?

First of all, we have to understand what we are trying to optimize for, whether it be time, space, readability, or cost. Many times, optimizing for one of these negatively impacts another, thus we must know which constraint is most important.

Next, we need to understand what data structures (arrays, hashes, linked lists, etc.) are available to us and the strengths and weaknesses of each. For example, searching an array for a particular value is an O(n) operation, while accessing a value by its key in a hash is an O(1) operation. Having information like this readily available will help us evaluate what the most efficient solution is for our constraints. Given an algorithmic problem, we should first always ask ourselves the following two questions:

What are we doing with our data structures? (adding, deleting, accessing, etc.)
Can we use a different data structure that would be better suited for this?

Lastly, we just have to practice! These are difficult problems, and the only way to really become better at writing efficient solutions is to keep doing it.

Author’s Bio

vigenere cypher Hannah Squier is a self-taught software developer, with a background in GIS and civil engineering. As a UC Berkeley Engineering graduate and early startup employee, she has navigated many complex challenges with her technical know-how and perseverance. While preparing for her next adventure to become a full time software engineer, she writes tutorials to give back to the developer community. When she’s not coding, Hannah plays frisbee and thinks about how to make cities better places to live in. Get in touch at hannahsquier@gmail.com.