LeetCode Review

[benluiwj]

Revise these LC Questions!!

Leetcode : Word Ladder DCP : Word Ladder

DSA: BFS

Key Idea: BFS since finding shortest

[benluiwj]

Job Scheduling

DSA: Stack

Idea: create an array of triplet [startTime, endTime, profit] sort the array by endTime initialise a sequence array with [[0,0]] since at time 0 the profit we get is 0 for every job: binary search the profit array to obtain the maximum profit before performing this job if that profit + doing this job is greater than the last profit of the sequence array, then we add it (ie do this job) otherwise we don't do this job and not add it. return the last profit in the array

[benluiwj]

Largest Rectangle in Histogram Video Explanation

DSA: Stack

Idea: Use a stack and pop rectangles when the height isn't increasing. when popping, calculate the possible area it could have formed by taking the start index and end index as the width and multiplying by the height. then when pushing onto the stack, take the index as the last element that was popped since its possible to extend left.

[benluiwj]

Basic Calculator

DSA: Stack

Idea: Use a stack. when we reach operators like -, +, we have reached the end of the number. then we just calculate it and add it to the result. have a sign for each number which indicates whether its positive or negative. everything seen as addition and subtraction is just addition of negative numbers. when we reach (, push the result and sign onto the stack. the stack basically maintains everything we have done so far outside of any parenthesis. when we reach ), calculate the result. then pop to get the sign and then pop again to get the number. at the end just take the sign and number multiplied together.

[benluiwj]

Maximum Subarray

DSA: Array

Idea: KADANE ALGORITHM neetcode solution

CAME OUT FOR JPMORGAN!

[benluiwj]

DCP

DSA: Stack, Queue

Idea: Reconstruct from the final state and notice that its a rotation.