Skip to content

Instantly share code, notes, and snippets.

@frankstepanski
Last active April 11, 2022 00:43
Show Gist options
  • Save frankstepanski/1a52d6f4f9fc6a234616f4125e29b733 to your computer and use it in GitHub Desktop.
Save frankstepanski/1a52d6f4f9fc6a234616f4125e29b733 to your computer and use it in GitHub Desktop.
Data Structure and Algorithm Coding Template
/**
* 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment