Task Constraints

Question 1

Common Constraints Grids/Mazes

Answer 1

• For problems where some actor (e.g. a robot) is moving in a grid or maze, what
  moves are allowed? Can the robot move diagonally (hence 8 valid moves), or only
  horizontally/vertically (hence only 4 valid moves)?
• Are all cells in the grid allowed, or can there be obstacles?
• If the actor is trying to get from cell A to cell B, are cells A and B guaranteed to be
  different from each other?
• If the actor is trying to get from cell A to cell B, is it guaranteed that there’s a path
  between the two cells?

Question 2

Common Constraints Strings, Arrays and Numbers

Answer 2

• How many elements can be in the array?
• How large can each element be? If it’s a string, how long? If it’s a number, what is the minimum and maximum value?
• What is in each element? If it’s a number, is it an integer or a floating point? If it’s a string, is it single-byte or multibyte (unicode)?
• If the problem involves finding a subsequence, does “subsequence” mean that the elements must be adjacent, or is there no such requirement?
• Does the array contain unique numbers or can they be repeated (this is sometimes relevant)?

Question 3

Common Constraints Graphs

Answer 3

• How many nodes can the graph have?
• How many edges can the graph have?
• If the edges have weights, what is the range for the weights?
• Can there be loops in the graph? Can there be negative-sum loops in the graph?
• Is the graph directed or undirected?
• Does the graph have multiple edges and/or self-loops?

Question 4

Common Constraints Return Values

Answer 4

What should my method return? For example, if I’m trying to find the longest
subsequence of increasing numbers in an array, should I return the length, the
start index, or both?
* If there are multiple solutions to the problem, which one should be returned?
* If it should return multiple values, do you have any preference on what to return?
E.g. should it return an object, a tuple, an array, or pass the output parameters as
input references? (This may not be applicable in languages allowing you to return
multiple values, e.g. Python)
* What should I do/return if the input is invalid / does not match the constraints?
Options may be to do nothing (always assume the input is correct), raise an
exception, or return some specific value.
* In problems where you’re supposed to find something (e.g. a number in an array),
what should be returned if the element is not present?

Question 5

How do you figure out the right questions?

Answer 5

Generally speaking, think about all the things that matter to your solution. For example, make sure you know the minimum and maximum possible values for any key value in the statement. These may affect the performance of your solution directly. If there are arrays of values you need to know the range of these values, too. They can be numbers, chars, geometric figures, etc. Some of these should come naturally to you once you hear the statement. If it says that there are N numbers and nothing else is mentioned about N, ask how big it can be. Others could come when you start designing your solution. If a given value is important for the complexity of your solution, don’t hesitate to ask about it. Never assume things on your own.

The Algorithm Design Canvas helps you collect the needed information at an interview. It has a section where you need to fill in all the important constraints in a problem. If you use it while practicing you will get into the habit of making sure you know everything that you need to design an efficient solution.

Filling in the Constraints box is nothing more than asking the interviewer the right questions. Every problem’s different, but to get you started we’ve compiled a pretty extensive list of common things you should keep an eye on. All of them are included in the Common Constraints Handout. Feel free to download it and print it out: It will come in handy!