Data Structure and Algorithm Coding Template

algorithm-template.js

/**
  *  Interivew Tips:
  *
  *  - Write examples and clarify the question
  *  - Ask questions that unearth the actual problem the interviewer wants you to solve.
  *  - Come up with solutions and explain them to the interviewer.
  *  - Once the interviewer seems to settle on one, write down simple steps, not more than a few lines. 
  *  - Doing this makes it clear (to both of you) what you will code for the rest of the interview.
  *  - Write down test cases, when an interviewer sees you do this, they know you are legit. 
  *  - Make liberal use of helper functions.
  *  - Verify code and test cases Once you are done, make sure you step through the code and make sure it works.
  *  - Going through this approach proves that you are professional and a systematic problem solver
  *  - Use the acronym E.S.T.C.V (Examples, Solutions, Test Cases, Code, Verify).
  *  - https://medium.com/@InterviewTable/5-step-approach-to-leave-your-interviewer-starstruck-d3236a5c99ce
  *  - A variation can be: Repeat, Examples, Approach, Code, Test, Optimize 
  *  - https://www.fullstackacademy.com/blog/whiteboard-coding-interviews-a-6-step-process-to-solve-any-problem
  *
  *   Problem: Two Sum
  *   Description: Given an array of integers nums and an integer target, return indices of the two numbers such that
  *                they add up to target.
  *
  *   Template:
  *
  *   - Inputs: Array object, target number
  *   - Output: Array indices of the numbers that sum to the target
  *   - Assumptions: Array elements will be whole positive number integers; no array element duplicates; function will
  *                  return indices for the first valid sum it finds.
  *   - Edge case: Empty array, array with 1 element, array elements that do not match target sum
  *   - Test Cases: 
  *      Inputs --> arr[1,2,3,4,5,6], target_num = 9
  *      Outputs --> Indices: arr[3],arr[4]  [first valid sum --> 4 + 5 = 9]
  *   - BigO:  Brute force: time: O(n2), space - O(1) Optimized: Using Hash map: time O(n), space - O(1)
  *   - PSEUDOCODE:
  *     Brute force: One pointer will iterate through array and calculate the desired target value for the 2nd pointer.
  *                  The second pointer will iterate through the remaining array elements starting with the next index
  *                  in the array. The second pointer will check if the 
  *     Optimized: 
  *   - CODE Draft: Write a code draft first (in comments if whiteboarding)
  *
*/

// First Attempt: Brute Force: 
// time - quadratic O(n2), space - constant O(1)

function twoSum(nums, target) {
    for (let i = 0; i < nums.length; i++) { // O(n)
        const numToFind = target - nums[i];
        for (let j=i +1; j< nums.length; j++) { // O(n)
            if (numToFind === nums[j]) return [i,j]
        }
    }
    return null;
}

// Optimization: (ask interviewer if time allowed, always do brute force first)
// Using Hash Map: time - linear O(n), space - linear O(n)

function twoSum(nums, target) {
    const numsMap = {};
    for (let i = 0; i < nums.length; i++) { // time: O(n)
        const currentMapVal = numsMap[nums[i]];
        if (currentMapVal >= 0) { 
            return [currentMapVal, i];
        } else {
            const numToFind = target - nums[i];
            numsMap[numToFind] = i; // space: O(1)
        }
    }
    return null;
}