How to solve programming exercises

Coding bootcamps require students to solve self-contained programming exercises (‘toy problems’) that grow in difficulty until they are representative of software engineering interview problems.

I struggled significantly with these exercises until I learned about the OICEPIDR (Mnemonic: “Oh, an ice peddler!”) approach illustrated below.

OICEPIDR Rules

  1. Approach each step one after the other, not in parallel.
  2. Write or type the responses to each step in your editor. Do not rely on your memory.
  3. Do not write any code until the Implementation phase.

Problem Statement

Write a function (sumTree) that adds up the values of all nodes of a two level tree and returns the sum in linear time. Do not use the built in reduce method. The addChildren methods are provided.

var root = new Tree(5);
root.addChildren(2);
root.addChildren(9);
console.log(root);
//{value: 5, children: [{value:2, children: []}, {value: 9, children: []}]}

Output

  1. Determine the output’s type (string, number, array, object, 2D array, etc.)
    The output type is a number.

Input

  1. Determine the input’s type (string, number, array, object, tree, etc.)
    The input type is a node: an object with two properties:
  • Value, which is assigned to a number.
  • Children, which is assigned to an array of nodes.

Constraints

  1. Are there any time complexity constraints? 
    Yes
  2. If so, what are they?
    The function must run in linear time
  3. Are there any space complexity constraints? 
    No.
  4. If so, what are they?
    N/A
  5. Are any techniques (built in methods, etc.) not allowed?
    The built-in reduce method for Arrays is not allowed.

Example test cases

var root = new Tree(5);
root.addChildren(2);
root.addChildren(9);
console.log(sumTree(root)); //should evaluate to 16
  1. Generate at least one test case that maps input to output. See the above as an example simplified test case.
  2. Check the example input and output pairs against the problem statement’s provided examples, your best guess if no examples are provided, or with your interviewer if this is an supervised exercise.
  3. Put a comment next to each input’s log statement with the example output.
  4. Brainstorm other test cases that could break the implementation.
  5. Add these test cases using the same process as above.

Pseudocode

  1. Write how you would solve the problem as if explaining it to a friend.
    Since we want the sum, we will need to create a place to store it. After that, we’ll need to access the value property for the first node, and then add the value properties for its children nodes to the sum.

2. Outline the pseudo code in the same indentations as actual code.

//define the function sumTree that takes a node parameter
//set sum equal to an initial value of zero
  //add the value property of the parent node to sum
  //iterate over each child node
//add the value of each child to sum
  //return sum

Implementation

  1. Convert the pseudocode to your target language (Javascript in this case).
  2. Run the code.
//define the function sumTree that takes a node parameter
//set sum equal to an initial value of zero
//add the value property of the parent node to sum
  //iterate over each child node
//add the value of each child to sum
  //return sum
function sumTree(node) {
var sum = 0;
sum = sum + node.value;

for(i = 0; i < node.children.length; i++) {
sum = sum + node.children[i];
}

return sum;
}
//test cases below
var root = new Tree(5);
root.addChildren(2);
root.addChildren(9);
console.log(sumTree(root)); //should evaluate to 16

Debugging

  1. Compare the output against the test cases.
    The output does not seem to match the first test case.
  2. Mentally walk through the evaluation as if you were the interpreter.
    When passing in root, we find that sum + node.value = 5, so no issue there.
    However, inside our for loop, we are attempting to add each child node’s object, not value, to sum.
  3. Implement the correction and repeat from 1 for other failing test cases
//define the function sumTree that takes a node parameter
//set sum equal to an initial value of zero
//add the value property of the parent node to sum
//iterate over each child node
//add the value of each child to sum
//return sum
function sumTree(node) {
var sum = 0;
sum = sum + node.value;

for(i = 0; i < node.children.length; i++) {
sum = sum + node.children[i].value;
}

return sum;
}
//test cases below
var root = new Tree(5);
root.addChildren(2);
root.addChildren(9);
console.log(sumTree(root)); //should evaluate to 16

Refactor

  1. Reread the code while brainstorming legibility improvements
    1) The for loop can be changed to a forEach loop for shorter code.
    2) Sum can be initialized with the initial node’s value.
  2. Implement the changes.
  3. Check if all tests continue to pass and debug if they do not.
//define the function sumTree that takes a node parameter
//set sum equal to an initial value of zero
//add the value property of the parent node to sum
//iterate over each child node
//add the value of each child to sum
//return sum
function sumTree(node) {
var sum = node.value;

node.children.forEach(function(child){
sum = sum + child.value;
}

return sum;
}
//test cases below
var root = new Tree(5);
root.addChildren(2);
root.addChildren(9);
console.log(sumTree(root)); //should evaluate to 16
One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.