Using the TERA approach to solve algorithm and technical interview questions

The technical interview is a critical part of becoming a software engineer. It’s your chance to demonstrate your ability to break down a larger problem into smaller, more easily solvable steps, and to gradually slay the dragon (or chicken).

Moreover, the technical interview showcases how you communicate technical problems and therefore how helpful you’d be when working in a team or handling clients.

Without a methodology or a game plan, this can be a daunting and intimidating process. The solution is to have a systematic way to go about solving every problem. There are several different takes on this, including Launch School’s PEDAC model.

After several weeks trying and testing out different approaches, and applying various ones to multiple different algorithms, I’ve come up with my own approach.

Introducing TERA: a simple and elegant methodology for solving algorithm and technical interview questions.

Courtesy: Diane Kochilas

My wife recently cooked a delicious Greek Roasted Chicken Stuffed with Figs and Olives, using Diane Kochilas’ recipe. This has inspired the name of this methodology.

Tera, as in terabyte, comes from the Greek word for monster, teras. This TERA approach will help you slay terabytes of monsters. As we shall see, the meal also inspired the analogy we’ll use to understand and process the TERA methodology.

TERA stands for: Transformation, Examples, Rules, and Algorithm. These provide you with a step by step roadmap on what you should do–a recipe, if you will.

Here’s a detailed breakdown of this methodology. As you can see, each step leads you to the next, which finally sets you up for a much more enjoyable, intentional, and efficient cooking (I mean coding) process.

1) Transformation

The first step is the easiest: this is your chance to succinctly rephrase the problem in your own words, and explain what your function or method should do with (and to) the given inputs.

In other words, what is the transformation your algorithm must accomplish?

What are your input(s) and required output(s), including data types? Another way to think about this is in terms of arguments passed to a method (i.e. inputs) and the expected return value (i.e. outputs).

The convention “Takes [x] and Returns [y]” is useful here.

The transformation section captures the same elements and plays the same role as the descriptive title of a cooking recipe. For example, think about how “Roasted Chicken Stuffed with Figs and Olives” captures both the main inputs and output of the recipe. It also captures a sense of how the recipe transforms the main ingredients.

2) Examples (and Edge Cases)

Identify several key examples that delineate and showcase the transformation you’re expecting. This is an opportunity to go through and understand the test cases they provide you, to ask further clarifying questions from the interviewer (if possible and necessary), and to generally address some underlying assumptions regarding edge cases.

For our recipe analogy, this section is like surveying the main ingredients available in a local geographic area, and picturing what each region’s final product should look like, given those ingredients. To truly write a world-class and legendary recipe, you need to consider how your recipe would work and be applied in different regions and time periods.

Just visualizing the finished meal for each case will already help you stir up ideas for how to get the ingredients to the finish line, and what tools you might need to satisfy all situations (see what I did there?).

As a sidenote: these examples will also be useful at the end, when you’re ready to test your code. You can declare victory if your method works for all the examples you’ve identified here.

3) Rules (and Requirements)

Once you’ve established several illustrative examples above, you can then move on to expressing the broader, systematic rules that encompass the transformations needed. Make sure to be as succinct, explicit, and comprehensive as possible when listing your main rules & requirements.

This is an opportunity to translate your examples into more explicit rules, and list out any other requirements that are necessary to either get you the transformation you need, or to deal with a particular edge case. For example, if your transformation implicitly requires a data type transformation at any point, the rules section is where you can explicitly mention this.

Your rules don’t need to be listed in chronological or logical order at this point, but they should cover all possible situations you could ever encounter.

It’s important to really think hard at this stage, and to boil down the rules to their logical essentials. Doing so will pave the way for a smoother time when working on the next step.

The recipe analogy is weakest for the rules section, but don’t chicken out yet… we can think of our rules as the combination of both: 1) WHAT we do with and to all the ingredients (e.g. abort the recipe if we don’t have a chicken, always preheat oven, etc), and 2) HOW we do it: the tools, timing, and techniques needed to break down and process the ingredients (e.g. chicken must not contain excess fat, figs must be chopped, chicken must bake for an hour, etc).

4) Algorithm

Finally, you’re ready to write out your algorithm in pseudocode. This is the logical, step by step way you gradually incorporate and address all the rules and requirements you previously identified, to finally achieve the required transformation, for all possible examples.

Any (logical) adult should be able to read your algorithm, even if they don’t know any programming language, and understand your reasoning process and methodology for gradually achieving the expected transformation.

Once you have your algorithm laid out in pseudocode, and it makes sense to you, coding it out should be a breeze. That’s because–well, you guessed it–the algorithm is your personalized recipe for creating the meal.

Your algorithm should therefore be as detailed as you personally need it to be. For example, if one of your steps requires you to identify the maximum element in an array and you’re comfortable using some sort of max method available to array objects, you don’t need to get into the details of how to accomplish this, and you can just mention the method. But if you have any doubts, then break this sub-problem up further. It’s important to take your time and be honest with yourself – if you skip a sub-problem because of overconfidence, this will end up costing you and making you look worse when you’re actually coding it out.

In terms of how much time to spend on each step of TERA, there’s of course no set rule, and every problem might require a slightly different allocation, but here’s a general guidepost:

StepGoalTime allotted
TransformationIn 1-2 sentences, explain your input(s) and output(s), including data types5%
Examples & Edge CasesIdentify and list several illustrative examples & edge cases10%
Rules & ReqsThink about and list all the main logical rules and requirements that should govern your transformation25%
AlgorithmStep by step procedure to achieve transformation (in pseudocode)60%

Notice that each step progressively takes more time: this is intentional. Each step is supposed to be easier than the next one, because this methodology is designed to gradually build confidence in yourself during the interview, by allowing you to solve and complete increasingly more difficult steps.

As you work through each step of TERA, it’s completely ok to go back to a previous step and flesh it out some more, but you don’t actually have to if you’re pressed for time, as long as you properly account for it in that current step. That’s because every step builds only on the immediately preceding step, and what ultimately matters is the final step: your algorithm.

For example, if you’re working on the rules section and you discover that you missed an important edge case, you can go back and actually add it to your list of examples, but you don’t have to. What matters is that you properly account for that edge case in your rules section before you move on to your algorithm, since you should mostly be looking at your rules section when fleshing out your algorithm, and only at your algorithm when writing your code, etc.

Each step does provide you with better hindsight for something you may have missed in a previous step, but as long as you address it then and there, you’re ready for the next, deeper level of abstraction.

Example Prompt

Let’s apply TERA to an example. Consider the following prompt–a classic:

  • Write a method that takes a string as argument, and returns true if all parentheses in the string are properly balanced, false otherwise. To be properly balanced, parentheses must occur in matching ( and ) pairs.
  • Note that balanced pairs must each start with a (, not a ).
  • In addition, we’re given the following 8 test cases:
#Case
1balanced?('What (is) this?') == true
2balanced?('What is) this?') == false
3balanced?('What (is this?') == false
4balanced?('((What) (is this))?') == true
5balanced?('((What)) (is this))?') == false
6balanced?('Hey!') == true
7balanced?(')Hey!(') == false
8balanced?('What ((is))) up(') == false

Example Solution

  1. Transformation
    Takes a STRING and Returns a BOOLEAN true if the string contains parentheses that are properly balanced, or false otherwise.

  2. Examples / Edge Cases

  • “What (is) this?” => true
  • “What is) this?” => false
  • (All given test cases are worthwhile). In addition, we can think of the following additional edge cases based on what they gave us:
  • "” => true (deduced from example 6 above)
  • “)(” => false (deduced from example 7 above)
  1. Rules / Requirements
  • To be properly balanced, parentheses must occur in matching ( and ) pairs
  • Input will always be a string
  • Whenever string has ) that appears before a ( appears, return false
  • String must contain as many ( as ) => otherwise return false
  • Each ) should cancel out the ( that immediately preceded it
  1. Algo
  • Create an integer open_parens, that will contain a count of how many unclosed open parentheses we’ve seen in the string. Initialize this integer to 0.
  • Iterate through each character in the string
    Whenever char is either ( or ), perform the following:
    If the char is ): if open_parens is 0, return false => Otherwise, decrement open_parens by one
    If the char is (: increment open_parens by one.
  • When done with iteration, return true if open_parens is zero, or false otherwise

We are now more than ready to code this solution out.

Here’s our solution using Ruby:

def balanced?(string)
  open_parens = 0
  string.each_char do |char|
    if char == ")"
      return false if open_parens == 0
      open_parens -= 1
    elsif char == "("
      open_parens += 1
    end
  end
  open_parens == 0
end

And in Javascript:

function isBalanced(string){
  let openParens = 0;
  for(let idx=0; idx<string.length; idx++){
    let char = string[idx];
    if (char === ')') {
      if (openParens === 0) return false;
      openParens--;
    } else if (char === '('){
      openParens++;
    }
  }
  return (openParens === 0);
}

Remember that once you write your code, you’re still not done yet.

If possible, make sure to test your code on all the examples you identified. This demonstrates to your interviewer that you respect other people’s time and will not waste it by submitting incorrect code during pull requests–especially code that you could have easily tested yourself first.

The quality of the examples you identified and use also demonstrates to the interviewer how systematic, thorough, and thoughtful you are.

If everything works, great. You’re ready to move on to the next challenge.

Otherwise, troubleshoot & fix your code in the short term (i.e. during the interview). Later on, in the long term, you’re ready to think more deeply about why your process allowed that error to creep in.

Usually, it’s either because you rushed through one of the steps of TERA, or you had an incorrect mental model for how something works. Adapt and correct your model, and identify which step in TERA your error first manifested itself, and improve for next time.

Rinse and repeat, and you’re on your way to becoming an insanely efficient problem solver.

Vahid Dejwakh
Vahid Dejwakh
Founder at Briefcat, LLC & Capstone Participant, Launch School

Vahid writes about interesting ideas at the intersection of data, software, philosophy, psychology, policy, and business. He enjoys coffee and has a palate for spicy and diverse foods.

comments powered by Disqus

Related