Programming Questions

#1 Two Sum => https://leetcode.com/problems/two-sum

#2 Add Two Numbers => https://leetcode.com/problems/add-two-numbers

#3 Longest Substring Without Repeating Characters => https://leetcode.com/problems/longest-substring-without-repeating-characters

#5 Longest Palindromic Substring => https://leetcode.com/problems/longest-palindromic-substring

#7 Reverse Integer => https://leetcode.com/problems/reverse-integer

#13 Roman to Integer => https://leetcode.com/problems/roman-to-integer

#20 Valid Parentheses => https://leetcode.com/problems/valid-parentheses

#21 Merge Two Sorted Lists => https://leetcode.com/problems/merge-two-sorted-lists

#26 Remove Duplicates from Sorted Array => https://leetcode.com/problems/remove-duplicates-from-sorted-array

#28 Implement strStr() => https://leetcode.com/problems/implement-strstr

#31 Next Permutation => https://leetcode.com/problems/next-permutation

#38 Count and Say => https://leetcode.com/problems/count-and-say

#42 Trapping Rain Water => https://leetcode.com/problems/trapping-rain-water

#53 Maximum Subarray => https://leetcode.com/problems/maximum-subarray

#56 Merge Intervals => https://leetcode.com/problems/merge-intervals

#66 Plus One => https://leetcode.com/problems/plus-one

#69 Sqrt(x) => https://leetcode.com/problems/sqrtx

#70 Climbing Stairs => https://leetcode.com/problems/climbing-stairs

#88 Merge Sorted Array => https://leetcode.com/problems/merge-sorted-array

#94 Binary Tree Inorder Traversal => https://leetcode.com/problems/binary-tree-inorder-traversal

#101 Symmetric Tree => https://leetcode.com/problems/symmetric-tree

#104 Maximum Depth of Binary Tree => https://leetcode.com/problems/maximum-depth-of-binary-tree

#108 Convert Sorted Array to Binary Search Tree => https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree

#118 Pascal's Triangle => https://leetcode.com/problems/pascals-triangle

#121 Best Time to Buy and Sell Stock => https://leetcode.com/problems/best-time-to-buy-and-sell-stock

#122 Best Time to Buy and Sell Stock II => https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii

#125 Valid Palindrome => https://leetcode.com/problems/valid-palindrome

#136 Single Number => https://leetcode.com/problems/single-number

#138 Copy List with Random Pointer => https://leetcode.com/problems/copy-list-with-random-pointer

#139 Word Break => https://leetcode.com/problems/word-break

#141 Linked List Cycle => https://leetcode.com/problems/linked-list-cycle

#155 Min Stack => https://leetcode.com/problems/min-stack

#160 Intersection of Two Linked Lists => https://leetcode.com/problems/intersection-of-two-linked-lists

#169 Majority Element => https://leetcode.com/problems/majority-element

#171 Excel Sheet Column Number => https://leetcode.com/problems/excel-sheet-column-number

#172 Factorial Trailing Zeroes => https://leetcode.com/problems/factorial-trailing-zeroes

#189 Rotate Array => https://leetcode.com/problems/rotate-array

#190 Reverse Bits => https://leetcode.com/problems/reverse-bits

#191 Number of 1 Bits => https://leetcode.com/problems/number-of-1-bits

#198 House Robber => https://leetcode.com/problems/house-robber

#200 Number of Islands => https://leetcode.com/problems/number-of-islands

#202 Happy Number => https://leetcode.com/problems/happy-number

#204 Count Primes => https://leetcode.com/problems/count-primes

#206 Reverse Linked List => https://leetcode.com/problems/reverse-linked-list

#217 Contains Duplicate => https://leetcode.com/problems/contains-duplicate

#234 Palindrome Linked List => https://leetcode.com/problems/palindrome-linked-list

#237 Delete Node in a Linked List => https://leetcode.com/problems/delete-node-in-a-linked-list

#242 Valid Anagram => https://leetcode.com/problems/valid-anagram

#244 Intersection of Two Arrays => https://leetcode.com/problems/intersection-of-two-arrays

#268 Missing Number => https://leetcode.com/problems/missing-number

#283 Move Zeroes => https://leetcode.com/problems/move-zeroes

#326 Power of Three => https://leetcode.com/problems/power-of-three

#344 Reverse String => https://leetcode.com/problems/reverse-string

#350 Intersection of Two Arrays II => https://leetcode.com/problems/intersection-of-two-arrays-ii

#371 Sum of Two Integers => https://leetcode.com/problems/sum-of-two-integers

#387 First Unique Character in a String => https://leetcode.com/problems/first-unique-character-in-a-string

#412 Fizz Buzz => https://leetcode.com/problems/fizz-buzz

#681 Next Closest Time => https://leetcode.com/problems/next-closest-time

Remove a character from String =>

https://www.toptal.com/javascript/interview-questions

http://www.thatjsdude.com/interview/js2.html

https://github.com/h5bp/Front-end-Developer-Interview-Questions/blob/main/src/questions/coding-questions.md

https://www.careercup.com/page?pid=google-interview-questions

=========================================================================

There's a staircase with N steps, and you can climb 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.

For example, if N is 4, then there are 5 unique ways:

1, 1, 1, 1

2, 1, 1

1, 2, 1

1, 1, 2

2, 2

What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time. Generalize your function to take in X.

Solution

It's always good to start off with some test cases. Let's start with small cases and see if we can find some sort of pattern.

N = 1: [1]

N = 2: [1, 1], [2]

N = 3: [1, 2], [1, 1, 1], [2, 1]

N = 4: [1, 1, 2], [2, 2], [1, 2, 1], [1, 1, 1, 1], [2, 1, 1]

What's the relationship?

The only ways to get to N = 3, is to first get to N = 1, and then go up by 2 steps, or get to N = 2 and go up by 1 step. So f(3) = f(2) + f(1).

Does this hold for N = 4? Yes, it does. Since we can only get to the 4th step by getting to the 3rd step and going up by one, or by getting to the 2nd step and going up by two. So f(4) = f(3) + f(2).

To generalize, f(n) = f(n - 1) + f(n - 2). That's just the Fibonacci sequence!

def staircase(n):
    if n <= 1:
        return 1
    return staircase(n - 1) + staircase(n - 2)

Of course, this is really slow (O(2N)) — we are doing a lot of repeated computations! We can do it a lot faster by just computing iteratively:

def staircase(n):
    a, b = 1, 2
    for _ in range(n - 1):
        a, b = b, a + b
    return a

Now, let's try to generalize what we've learned so that it works if you can take a number of steps from the set X. Similar reasoning tells us that if X = {1, 3, 5}, then our algorithm should be f(n) = f(n - 1) + f(n - 3) + f(n - 5). If n < 0, then we should return 0 since we can't start from a negative number of steps.

def staircase(n, X):
    if n < 0:
        return 0
    elif n == 0:
        return 1
    else:
        return sum(staircase(n - x, X) for x in X)

This is again, very slow (O(|X|N)) since we are repeating computations again. We can use dynamic programming to speed it up.

Each entry cache[i] will contain the number of ways we can get to step i with the set X. Then, we'll build up the array from zero using the same recurrence as before:

def staircase(n, X):
    cache = [0 for _ in range(n + 1)]
    cache[0] = 1
    for i in range(1, n + 1):
        cache[i] += sum(cache[i - x] for x in X if i - x >= 0)
    return cache[n]

This now takes O(N * |X|) time and O(N) space.

=========================================================================