# Interview Hell: Leetcode

> Published  Jan 01 2022, last updated Aug 08 2022  
> By Ryan Fleck <hello@this-site> and written without LLMs!  
> Original post at <https://ryanfleck.ca/reference/interview-hell-leetcode/>  
> An article of astonishing quality and insight. Happy Hacking!

The sad truth about the software engineering industry is that the challenges presented in programming interviews and actual day-to-day work couldn't be more different.

This page is dedicated to different categories of programming puzzles that will be thrown out during interviews, including sample solutions.

<!--more-->

These are personal solutions that are absolutely **not the best, fastest, or most memory efficient,** though I do try my best to target these metrics. It is solely for personal reference so I don't have to re-solve the same problem over and over and over again.

For this round, I'm solving everything in **Python3**. I wish I could start thinking with a functional language, but right now I need to pay off my student loans and would like to have a relatively seamless transition from Job A to Job B if that happens.

{{< toc >}}

# Leetcode

By far the most famous platform for alleged _10x L33T hackerz_, [leetcode.com](https://leetcode.com/) is full of programming challenges.

## Top Interview Questions: Easy

This is a Leetcode collection with easy questions frequently asked in interviews. I'll be running through Medium and Hard afterwards, but this is a good place to start and warm up again.

View the problems [here.](https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/)

### Arrays

You know, these: `[ 1, 2, 3 ]`

#### Remove Duplicates from Sorted Array

Given an integer array `nums` sorted in **non-decreasing order**, remove the duplicates [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) such that each unique element appears only **once**. The **relative order** of the elements should be kept the **same**.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the **first part** of the array `nums`. More formally, if there are `k` elements after removing the duplicates, then the first `k` elements of `nums` should hold the final result. It does not matter what you leave beyond the first `k` elements.

Return `k` _after placing the final result in the first_ `k` _slots of_ `nums`.

Do **not** allocate extra space for another array. You must do this by **modifying the input array** [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) with O(1) extra memory.

**Submitted Solution:**

```py
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
       
        length = len(nums) 
        indice = 0
        max_indice = length - 1
        
        while indice < max_indice:
            if nums[indice] == nums[indice+1]:
                del nums[indice+1]
                max_indice = max_indice - 1
            else:
                indice = indice + 1

        return max_indice + 1
```

**Other Notable Solutions:**

```py
class Solution:
    def removeDuplicates(self, nums):
        nums[:] = sorted(set(nums))
        return len(nums)
```

```py
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        x = 1
        for i in range(len(nums)-1):
            if nums[i]!=nums[i+1]:
                nums[x] = nums[i+1]
                x+=1

        return (x)
```

#### Best Time to Buy and Sell Stock II

You are given an integer array `prices` where `prices[i]` is the price of a given stock on the `ith` day.

On each day, you may decide to buy and/or sell the stock. You can only hold **at most one** share of the stock at any time. However, you can buy it then immediately sell it on the **same day**.

Find and return _the **maximum** profit you can achieve_.

    Input: prices = [7,1,5,3,6,4]
    Output: 7
    Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
    Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
    Total profit is 4 + 3 = 7.

**Submitted Solution:**

```py
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profits = 0 
        for i in range(len(prices)-1):
            if prices[i] < prices[i+1]:
                profits += prices[i+1] - prices[i]
  
        return profits
```

#### Rotate Array

Given an array, rotate the array to the right by `k` steps, where `k` is non-negative.

    Input: nums = [1,2,3,4,5,6,7], k = 3
    Output: [5,6,7,1,2,3,4]
    Explanation:
    rotate 1 steps to the right: [7,1,2,3,4,5,6]
    rotate 2 steps to the right: [6,7,1,2,3,4,5]
    rotate 3 steps to the right: [5,6,7,1,2,3,4]

**Submitted Solution:**

Originally I had something very close to the notable solution but forgot to replace the full slice (`[:]`) instead of merely trying to replace the variable.

```py
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        x = k % len(nums)
        while x > 0:
            temp = nums.pop()
            nums.insert(0, temp)
            x -= 1
```

**Other Notable Solutions:**

```py
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        k %= len(nums)
        nums[:] = nums[-k:] + nums[:-k]
```

```py
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        newarr=collections.deque(nums)
        newarr.rotate(k%len(nums))
        nums[:]=list(newarr)
```

```py
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        if k % len(nums) == 0:
            return  # this edge case pushes this answer into the top results
        k = k % len(nums)
        nums[:] = nums[-k:] + nums[:-k]
```

```py
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """Lower memory than the others."""
        
        k=k%len(nums)
        nums2=[]
        
        for i in range(len(nums)-k,len(nums)):
            nums2.append(nums[i])
            
        for i in range(len(nums)-k):
            nums2.append(nums[i])
        
        nums[:]=nums2
```

#### Contains Duplicate

Given an integer array `nums`, return `true` if any value appears **at least twice** in the array, and return `false` if every element is distinct.

    Input: nums = [1,2,3,1]
    Output: true
    Input: nums = [1,2,3,4]
    Output: false

**Submitted Solution:**

```py
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(len(nums) - 1):
            if nums[i] == nums[i+1]:
                return True

        return False
```

**Other Notable Solutions:**

```py
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return True if (len(set(nums))<len(nums)) else False
```

```py
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        #return not len(nums) == len(set(nums))
        
        nums_count = {}
        for n in nums:
            if n in nums_count:
                return True
            nums_count[n] = 1
        return False
```

```py
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return not (len(set(nums)) == len(nums))
```

```py
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        helper = set(nums)
        return len(helper) != len(nums)
```

The big takeaway here is to use the [set function](https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset) to efficiently reduce a list to its unique elements.

> A _set_ object is an unordered collection of distinct [hashable](https://docs.python.org/3/glossary.html#term-hashable) objects. Common uses include membership testing, removing duplicates from a sequence, and computing mathematical operations such as intersection, union, difference, and symmetric difference. (For other containers see the built-in [`dict`](https://docs.python.org/3/library/stdtypes.html#dict "dict"), [`list`](https://docs.python.org/3/library/stdtypes.html#list "list"), and [`tuple`](https://docs.python.org/3/library/stdtypes.html#tuple "tuple") classes, and the [`collections`](https://docs.python.org/3/library/collections.html#module-collections "collections: Container datatypes") module.)

#### Find the Single Number

Given a **non-empty** array of integers `nums`, every element appears _twice_ except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

    Input: nums = [2,2,1]
    Output: 1   # one is the loneliest number ;)
    Input: nums = [4,1,2,1,2]
    Output: 4

**Submitted Solution:**

_My initial solution beat 95% of other solutions for runtime and 97% of other solutions for memory usage!_

```py
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(0, len(nums)-1, 2):
            if nums[i] != nums[i+1]:
                return nums[i]
            
        return nums[len(nums)-1] 
```

**Other Notable Solutions:**

All faster solutions involved `XOR`-ing the entire array.

```py
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        '''
        [
            1, 001 
            2, 010
            3, 011
            4, 100
            5, 101
        ]
        '''
        res = 0 # n ^ 0 = n
        
        # XOR the entire list
        # everything besides the single number becomes 0 with XOR 
        # we know n ^ 0 = n , so n is the single number 
        
        for n in nums:
            res = n ^ res
        return res
```

```py
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = nums[0]
        for n in nums[1:]:
            ans ^= n
        return ans
```

#### Intersection of Two Arrays II

Given two integer arrays `nums1` and `nums2`, return _an array of their intersection_. Each element in the result must appear as many times as it shows in both arrays and you may return the result in **any order**.

    Input: nums1 = [1,2,2,1], nums2 = [2,2]
    Output: [2,2]
    
    Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    Output: [4,9]
    Explanation: [9,4] is also accepted.

**Submitted Solution:**

This was a dumb first attempt - I'm certain this problem can be solved with far fewer resources.

_Apparently this solution beats 79% of other solutions for speed and 89% for memory use. Ha!_

```py
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        full_set = set(nums1 + nums2)
        count1 = dict.fromkeys(full_set, 0)
        count2 = dict.fromkeys(full_set, 0)
        combined = dict.fromkeys(full_set, 0)
        
        for item in nums1:
            count1[item] += 1
            
        for item in nums2:
            count2[item] += 1
        
        for key in combined.keys():
            if count1[key] or count2[key]:
                combined[key] = min(count1[key], count2[key])
        
        synthesis = []
        for key in combined.keys():
            if combined[key]:
                synthesis += [key] * combined[key]
                
        return synthesis
```

**Other Notable Solutions:**

```py
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = []
        for num1 in nums1:
            for num2 in nums2:
                if num1 == num2:
                    nums2.remove(num2)
                    result.append(num1)
                    break
        return result
```

```py
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        d = dict()
        arr = []
        
        for i in nums1:
            if i not in d:
                d[i] = 1
            else:
                d[i] += 1
                
        for i in nums2:
            if i in d and d[i] != 0:
                arr.append(i)
                d[i] -= 1
        return arr
```

```py
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = []
        for num1 in nums1:
            for num2 in nums2:
                if num1 == num2:
                    nums2.remove(num2)
                    result.append(num1)
                    break
        return result
```

#### Plus One

You are given a **large integer** represented as an integer array `digits`, where each `digits[i]` is the `ith` digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading `0`'s.

Increment the large integer by one and return _the resulting array of digits_.

    Input: digits = [1,2,3]
    Output: [1,2,4]
    Explanation: The array represents the integer 123.
    Incrementing by one gives 123 + 1 = 124.
    Thus, the result should be [1,2,4].

**Submitted Solution:**

Ack, let's take a closer look at this one, my solution is in the lowest 10% for speed, but beats 99.1% of other implementations for memory usage. _Let's go another round before checking other solutions._

```py
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in reversed(range(len(digits))):
            if digits[i] == 9:
                digits[i] = 0
                if i == 0:
                    digits.insert(0,1)
            else:
                digits[i] += 1
                break
                
        return digits
```

Here I converted the list to a number, incremented it, then broke it back into a list of numbers with simple string manipulation. This on beats 40% on runtime and 96.4% on memory usage.

```py
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        num = int("".join(list(map(lambda x: str(x), digits))))
        return map(lambda x: int(x), list(str(num + 1)))
```

**Other Notable Solutions:**

```py
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        # better solution
        n = len(digits)
        for i in range(n-1,-1,-1):
            if digits[i] == 9:
                digits[i] = 0
            else:
                digits[i] += 1
                return digits
        return [1] + digits
```

```py
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        s = ""
        for i in digits:
            s+=str(i)
        s = int(s)
        return list(str(s+1))
```

```py
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        carry  = 1
        for i in range(len(digits)-1, -1, -1):
            if carry + digits[i] >= 10:
                digits[i] = digits[i] + carry  - 10
                carry = 1
            else:
                digits[i] = digits[i] + 1
                return digits
        if carry:
            digits.insert(0, carry)
        return digits
```

#### Move Zeroes

Given an integer array `nums`, move all `0`'s to the end of it while maintaining the relative order of the non-zero elements.

**Note** that you must do this in-place without making a copy of the array.

    Input: nums = [0,1,0,3,12]
    Output: [1,3,12,0,0]

**Submitted Solution:**

```py
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        index = 0
        length = len(nums)
        while index < length:
            if nums[index] == 0:
                del nums[index]
                nums.append(0)
                length -= 1
            else:
                index += 1    
```

**Other Notable Solutions:**

```py
# Fast solution
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        arr = []
        for num in nums:
            if num != 0:
                arr.append(num)
        for i in range(len(arr), len(nums)):
            nums[i] = 0
        for i in range(len(arr)):
            nums[i] = arr[i]
```

```py
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        index = 0
        for n in nums: 
            if(n != 0): 
                nums[index] = n
                index += 1
        for i in range(index, len(nums)): 
            nums[i] = 0
        return nums
```

#### Two Sum

Given an array of integers `nums` and an integer `target`, return _indices of the two numbers such that they add up to `target`_.

You may assume that each input would have **_exactly_ one solution**, and you may not use the _same_ element twice.

You can return the answer in any order.

    Input: nums = [2,7,11,15], target = 9
    Output: [0,1]
    Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
    
    Input: nums = [3,2,4], target = 6
    Output: [1,2]

**Submitted Solution:**

My initial/dumb solution sorted and cropped the possible solution set. It's better than a straight comparison of every pair of numbers, and it passes all the unit tests, but I feel like it would fail if the combination of numbers relied on one of the last few numbers in the set.

```py
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Get some information about the set.
        sorted_nums = sorted(nums)
        last_indice = len(sorted_nums)-1
        lowest_number = sorted_nums[0]
        greatest_possible_number = target - lowest_number
        
        # print(f"Lowest number: {lowest_number}")
        # print(f"Greatest number: {greatest_possible_number}")
        
        # Find indice of greatest number and delete the rest
        greatest_indice = last_indice
        while sorted_nums[greatest_indice] > greatest_possible_number:
            # print(f"Ignoring {sorted_nums[greatest_indice]}")
            greatest_indice -= 1
            
        del sorted_nums[greatest_indice+1:]
        
        # print(sorted_nums)
        
        for i in range(len(sorted_nums)):
            for j in range(len(sorted_nums)-1, i, -1):
                # print(f"Checking {i} and {j}")
                if sorted_nums[i] + sorted_nums[j] == target:
                    # print(f"Found match at indices {i} and {j}")
                    
                    a = nums.index(sorted_nums[i]) 
                    b = nums.index(sorted_nums[j])
                    if a != b:
                        return sorted([a,b])
                    else:
                        a = nums.index(sorted_nums[i], b+1)
                        return sorted([a,b])
```

**Other Notable Solutions:**

ALL of the other notable solutions are variants on this 'enumerate' loop.

```py
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        complement = {}        
        for i, n in enumerate(nums):
            c = target-n
            if c in complement:
                return [complement[c], i]          
            complement[n]=i
```

```py
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        for ix, num in enumerate(nums):
            need = target - num
            if need in seen:
                return [ix, seen[need]]
            seen[num] = ix
```

**Resumbitted Solution:**

This still beats about half of solutions but not the notable ones above.

We convert the entire list to a hashmap first. Surprisingly fast given the size of the operation.

```py
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = dict(map(reversed, enumerate(nums)))
        for i, v in enumerate(nums):
            needed = target - v
            if needed in hashmap:
                ni = hashmap[needed]
                if ni > i:
                    return [i, ni]
```

_Interestingly,_ changing the hashing function kicks us into the **top 95%+** of speed results.

```py
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {key: i for i, key in enumerate(nums)} 
        for i, v in enumerate(nums):
            needed = target - v
            if needed in hashmap:
                ni = hashmap[needed]
                if ni > i:
                    return [i, ni]
```

Note that, for duplicate items, the hashing function ensures that the last instance of a duplicate number will always be stored as `ni`, so checking if the number is greater (`>`) is a valid check, though not equal (`!=`) would do just as well.

#### Valid Sudoku

Determine if a `9 x 9` Sudoku board is valid. Only the filled cells need to be validated **according to the following rules**:

1. Each row must contain the digits `1-9` without repetition.
2. Each column must contain the digits `1-9` without repetition.
3. Each of the nine `3 x 3` sub-boxes of the grid must contain the digits `1-9` without repetition.

**Note:**

* A Sudoku board (partially filled) could be valid but is not necessarily solvable.
* Only the filled cells need to be validated according to the mentioned rules.

![](/uploads/sudoku.png)

    Input: board = 
    [["5","3",".",".","7",".",".",".","."]
    ,["6",".",".","1","9","5",".",".","."]
    ,[".","9","8",".",".",".",".","6","."]
    ,["8",".",".",".","6",".",".",".","3"]
    ,["4",".",".","8",".","3",".",".","1"]
    ,["7",".",".",".","2",".",".",".","6"]
    ,[".","6",".",".",".",".","2","8","."]
    ,[".",".",".","4","1","9",".",".","5"]
    ,[".",".",".",".","8",".",".","7","9"]]
    Output: true

**Submitted Solution:**

Brute force/dumb but fairly elegant.

```py
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        
        def add_counts(hashmap, numlist):
            """Adds elements to a hashmap."""
            for elem in numlist:
                if elem > 0:
                    if elem in hashmap:          
                        hashmap[elem] += 1
                    else:
                        hashmap[elem] = 1
                        
        def bad_counts(hashmap) -> bool:
            """Returns true if counts are bad."""
            vals = hashmap.values()
            if vals:
                return max(hashmap.values()) > 1
            return False

        # Convert board to ints
        for i, row in enumerate(board):
            for j, value in enumerate(row):
                if value == ".":
                    board[i][j] = 0
                else:
                    board[i][j] = int(value)
        
        # Check rows         
        for i, row in enumerate(board):
            row_map = {}
            add_counts(row_map, row)
            if bad_counts(row_map):
                print(f"Found bad row: {i} : {row}")   
                return False
            
        # Check Cols
        for col in range(9):
            col_map = {}
            for row in range(9):
                add_counts(col_map, [board[row][col]])
            if bad_counts(col_map):
                print(f"Found bad col: {col} : {col_map.keys()}")   
                return False
            
        # Check cels
        for i in range(3):
            for j in range(3):
                # Operate on cel i,j
                print(f"Cel {i},{j}")
                cel_map = {}
                for k in range((i*3),((i*3)+3)):
                    run = board[k][(j*3):((j*3)+3)]
                    add_counts(cel_map, run)
                    print(run)
                   
                print(cel_map)
                if bad_counts(cel_map):
                    print(f"Found bad cel: {i},{j} : {cel_map.keys()}")   
                    return False

        return True
```

**Other Notable Solutions:**

Both are fast.

```py
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        N = 9

        # Use an array to record the status
        rows = [[0] * N for _ in range(N)]
        cols = [[0] * N for _ in range(N)]
        boxes = [[0] * N for _ in range(N)]

        for r in range(N):
            for c in range(N):
                # Check if the position is filled with number
                if board[r][c] == ".":
                    continue

                pos = int(board[r][c]) - 1

                # Check the row
                if rows[r][pos] == 1:
                    return False
                rows[r][pos] = 1

                # Check the column
                if cols[c][pos] == 1:
                    return False
                cols[c][pos] = 1

                # Check the box
                idx = (r // 3) * 3 + c // 3
                if boxes[idx][pos] == 1:
                    return False
                boxes[idx][pos] = 1

        return True
```

```py
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        cols = collections.defaultdict(set)
        rows = collections.defaultdict(set)
        squares = collections.defaultdict(set)

        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    continue
                if (board[r][c] in rows[r] or 
                    board[r][c] in cols[c] or
                    board[r][c] in squares[(r // 3, c // 3)]):
                    return False
                cols[c].add(board[r][c])
                rows[r].add(board[r][c])
                squares[(r // 3, c // 3)].add(board[r][c])
        return True
```

#### Rotate Image

You are given an `n x n` 2D `matrix` representing an image, rotate the image by **90** degrees (clockwise).

You have to rotate the image [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm), which means you have to modify the input 2D matrix directly. **DO NOT** allocate another 2D matrix and do the rotation.

![](/uploads/mat1.jpeg)

    Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
    Output: [[7,4,1],[8,5,2],[9,6,3]]

**Submitted Solution:**

Easy mode: makes a deep copy and re-inserts into original matrix.

```py
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        N = len(matrix) - 1  # max indice
        copy = [row[:] for row in matrix]
        for x, row in enumerate(copy):
            for y, value in enumerate(row):
                matrix[y][N-x] = value
```

The first improvement I'd make is holding each layer (4-array set of rows/cols n-deep into the image) in temporary memory and rotating those all at once.

**Other Notable Solutions:**

Like this guy.

```py
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n=len(matrix)
        for i in range(n//2+n%2):
            for j in range(i,len(matrix)-i-1):
                tmp = matrix[i][j]
                tmp2 = matrix[j][len(matrix)-i-1]
                tmp3 = matrix[len(matrix)-j-1][i]
                tmp4 = matrix[len(matrix)-i-1][len(matrix)-j-1]
                matrix[i][j]=matrix[len(matrix)-j-1][i]
                matrix[len(matrix)-j-1][i]=tmp4
                matrix[j][len(matrix)-i-1]=tmp
                matrix[len(matrix)-i-1][len(matrix)-1-j]=tmp2
```

### Strings

Leetcode list [here.](https://leetcode.com/explore/featured/card/top-interview-questions-easy/127/strings/)

#### Reverse String

Write a function that reverses a string. The input string is given as an array of characters `s`.

You must do this by modifying the input array [in-place](https://en.wikipedia.org/wiki/In-place_algorithm) with `O(1)` extra memory.

```py
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s[:] = reversed(s)
```

**Notably:**

```py
class Solution:
    def reverseString(self, s: List[str]) -> None:
        mid = len(s) // 2
        l = len(s) - 1
        for i in range(mid):
            s[i], s[l] = s[l], s[i]
            l -= 1
```

#### Reverse Integer

Given a signed 32-bit integer `x`, return `x` _with its digits reversed_. If reversing `x` causes the value to go outside the signed 32-bit integer range `[-231, 231 - 1]`, then return `0`.

**Assume the environment does not allow you to store 64-bit integers (signed or unsigned).**

    Input: x = 123
    Output: 321

**Submitted Solution:**

```py
# Keep high/low bound as constants.
hi_bound = 2147483647
lo_bound = -2147483648

class Solution:
    def reverse(self, x: int) -> int:
        if x == 0:
            return 0
        
        # Learn a bit about X
        new = 0
        sign_x = (1, -1)[x<0] # get the sign of x
        a = abs(x)
        length = int(math.log(a, 10)) # For use with range.
        base = (10**length)
        
        # Move the bits around
        while length >= 0:
            end = a % 10 
            new += end * base
            base //= 10 
            a //= 10
            length -= 1
            
        # Check if result is out of bounds
        reversed_x = int(new * sign_x)
        if reversed_x > hi_bound or reversed_x < lo_bound:
            return 0
        
        return reversed_x
```

_The other solutions literally just do string transformations._

```py
# Keep high/low bound as constants.
hi_bound = 2147483647
lo_bound = -2147483648

class Solution:
    def reverse(self, x: int) -> int:
        a = list(str(x))[::-1]
        if a[-1] == "-":
            del a[-1]
            a.insert(0,"-")
        
        xr = int("".join(a))
        if xr > hi_bound or xr < lo_bound:
            return 0
        return xr
```

**Other Notable Solutions:**

```py
class Solution:
    def reverse(self, x: int) -> int:
        result = int(str(x)[::-1]) if x > 0 else (int(str(abs(x))[::-1]) * -1)
        return 0 if (result > 2147483647 or result < -2147483647) else result
```

#### First Unique Character in a String

Given a string `s`, _find the first non-repeating character in it and return its index_. If it does not exist, return `-1`.

    Input: s = "leetcode"
    Output: 0
    
    
    Input: s = "loveleetcode"
    Output: 2

**Submitted Solution:**

First submission beats 45% of entries for speed and 67% for mem usage.

```py
class Solution:
    def firstUniqChar(self, s: str) -> int:
        s_list = list(s)
        counts = { x: 0 for x in set(s_list)}
        for val in s_list:
            counts[val] += 1
        for i, val in enumerate(s_list):
            if counts[val] == 1:
                return i
            
        return -1 
```

**Other Notable Solutions:**

```py
class Solution:
    def firstUniqChar(self, s: str) -> int:
        n = len(s)
        res = float('inf')
        for c in 'abcdefghijklmnopqrstuvwxyz':
            i = s.find(c)
            if i != -1 and i == s.rfind(c):
                res = min(res, i)
        if res == float('inf'):
            return -1
        return res
```

```py
class Solution:
    def firstUniqChar(self, s: str) -> int:
        letters = 'abcdefghijklmnopqrstuvwxyz'
        return min([s.index(l) for l in letters if s.count(l) == 1] or [-1])
```

#### Valid Anagram

Given two strings `s` and `t`, return `true` _if_ `t` _is an anagram of_ `s`_, and_ `false` _otherwise_.

An **Anagram** is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

    Input: s = "anagram", t = "nagaram"
    Output: true
    
    Input: s = "rat", t = "car"
    Output: false

**Submitted Solution:**

```py
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s_counts = {x: s.count(x) for x in set(list(s))}
        t_counts = {x: t.count(x) for x in set(list(t))}
        return s_counts == t_counts
```

```py
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        return {x: s.count(x) for x in set(list(s))} == {x: t.count(x) for x in set(list(t))}
```

A two-stage approach beats 2/3 of other results for speed.

```py
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        s_counts = {x: s.count(x) for x in set(list(s))} 
        for x in set(list(t)):
            if x not in s_counts or t.count(x) != s_counts[x]:
                return False 
            
        return True
```

Here's our winner, though.

```py
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return collections.Counter(s) == collections.Counter(t)
```

**Keys:**

* Instantiating a dictionary with zeroes
* Instantiating a dictionary with string character counts.

#### Valid Palindrome

A phrase is a **palindrome** if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string `s`, return `true` _if it is a **palindrome**, or_ `false` _otherwise_.

**Example 1:**

    Input: s = "A man, a plan, a canal: Panama"
    Output: true
    Explanation: "amanaplanacanalpanama" is a palindrome.

**Example 2:**

    Input: s = "race a car"
    Output: false
    Explanation: "raceacar" is not a palindrome.

**Submitted Solutions:**

```py
class Solution:
    def isPalindrome(self, s: str) -> bool:
        alphas = [ ch.lower() for ch in s if ch.isalnum() ]
        length = len(alphas)-1
        halfway = int((length+1)/2)
        if not alphas:
            return True
        for i, val in enumerate(alphas):
            if i >= halfway:
                return True
            if val != alphas[length-i]:
                return False

        return False
```

```py
class Solution:
    def isPalindrome(self, s: str) -> bool:
        sa = "".join([ ch.lower() for ch in s if ch.isalnum() ])
        half = int(len(sa)/2)
        neg_half = len(sa) - half
        return (sa[0:half]) == (sa[neg_half:])[::-1]
```

This beats 85% of other submissions for speed.

```py
class Solution:
    def isPalindrome(self, s: str) -> bool:
        sa = list(filter(lambda x: x in 'abcdefghijklmnopqrstuvwxyz0123456789', list(s.lower())))
        return sa == sa[::-1]
```

```py
class Solution:
    def isPalindrome(self, s: str) -> bool:
        sa = re.sub(r'[^A-Za-z0-9]+', '', s).lower()
        return sa == sa[::-1]
```

**Other Notable Solutions:**

```py
class Solution:
    def isPalindrome(self, s: str) -> bool:
        if s == " ":
            return True
        
        s = "".join(filter(str.isalnum, s)).lower()
        test = s[::-1]
        if test == s:
            return True
        else :
            return False
```

A low memory solution:

```py
class Solution:
    def isPalindrome(self, s: str) -> bool:
        head = 0
        tail = len(s) - 1
        while head < tail and tail > 0:
            if not s[head].isalnum():
                head +=1 
            elif not s[tail].isalnum():
                tail -=1 
            elif s[head].lower() != s[tail].lower():
                return False
            else:
                head +=1 
                tail -= 1
        return True
```

#### String to Integer (atoi)

Implement the `myAtoi(string s)` function, which converts a string to a 32-bit signed integer (similar to C/C++'s `atoi` function).

The algorithm for `myAtoi(string s)` is as follows:

1. Read in and ignore any leading whitespace.
2. Check if the next character (if not already at the end of the string) is `'-'` or `'+'`. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
3. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
4. Convert these digits into an integer (i.e. `"123" -> 123`, `"0032" -> 32`). If no digits were read, then the integer is `0`. Change the sign as necessary (from step 2).
5. If the integer is out of the 32-bit signed integer range `[-231, 231 - 1]`, then clamp the integer so that it remains in the range. Specifically, integers less than `-231` should be clamped to `-231`, and integers greater than `231 - 1` should be clamped to `231 - 1`.
6. Return the integer as the final result.

**Note:**

* Only the space character `' '` is considered a whitespace character.
* **Do not ignore** any characters other than the leading whitespace or the rest of the string after the digits.

**Submitted Solution:**

...I think there's a bug with the _Leetcode_ test cases for this problem.

#### Implement strStr()

Implement [strStr()](http://www.cplusplus.com/reference/cstring/strstr/).

Return the index of the first occurrence of needle in haystack, or `-1` if `needle` is not part of `haystack`.

**Clarification:**

What should we return when `needle` is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when `needle` is an empty string. This is consistent to C's [strstr()](http://www.cplusplus.com/reference/cstring/strstr/) and Java's [indexOf()](https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#indexOf(java.lang.String)).

**Example 1:**

    Input: haystack = "hello", needle = "ll"
    Output: 2

**Example 2:**

    Input: haystack = "aaaaa", needle = "bba"
    Output: -1

**Example 3:**

    Input: haystack = "", needle = ""
    Output: 0

**Submitted Solution:**

```py
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        try:
            return haystack.index(needle)
        except:
            return -1   
```

#### Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string `""`.

**Example 1:**

    Input: strs = ["flower","flow","flight"]
    Output: "fl"

**Example 2:**

    Input: strs = ["dog","racecar","car"]
    Output: ""
    Explanation: There is no common prefix among the input strings.

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

### Linked Lists

Leetcode list [here.](https://leetcode.com/explore/featured/card/top-interview-questions-easy/93/linked-list/)

#### Delete Node in a Linked List

Write a function to **delete a node** in a singly-linked list. You will **not** be given access to the `head` of the list, instead you will be given access to **the node to be deleted** directly.

It is **guaranteed** that the node to be deleted is **not a tail node** in the list.

    Input: head = [4,5,1,9], node = 5
    Output: [4,1,9]
    Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Remove Nth Node From End of List

Given the `head` of a linked list, remove the `nth` node from the end of the list and return its head.

    Input: head = [1,2,3,4,5], n = 2
    Output: [1,2,3,5]

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Reverse Linked List

Given the `head` of a singly linked list, reverse the list, and return _the reversed list_.

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Merge Two Sorted Lists

You are given the heads of two sorted linked lists `list1` and `list2`.

Merge the two lists in a one **sorted** list. The list should be made by splicing together the nodes of the first two lists.

Return _the head of the merged linked list_.

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Palindrome Linked List

Given the `head` of a singly linked list, return `true` if it is a palindrome.

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Linked List Cycle

Given `head`, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next` pointer. Internally, `pos` is used to denote the index of the node that tail's `next` pointer is connected to. **Note that `pos` is not passed as a parameter**.

Return `true` _if there is a cycle in the linked list_. Otherwise, return `false`.

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

### Trees

Leetcode list [here.](https://leetcode.com/explore/featured/card/top-interview-questions-easy/94/trees/)

#### Maximum Depth of Binary Tree

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Validate Binary Search Tree

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Symmetric Tree

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Binary Tree Level Order Traversal

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Convert Sorted Array to Binary Search Tree

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

### Sorting and Searching

Leetcode list [here.](https://leetcode.com/explore/featured/card/top-interview-questions-easy/96/sorting-and-searching/)

#### Merge Sorted Array

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### First Bad Version

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

### Dynamic Programming

Leetcode list [here.](https://leetcode.com/explore/featured/card/top-interview-questions-easy/97/dynamic-programming/)

#### Climbing Stairs

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Best Time to Buy and Sell Stock

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Maximum Subarray

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### House Robber

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

### Design

Leetcode list [here.](https://leetcode.com/explore/featured/card/top-interview-questions-easy/98/design/)

#### Shuffle an Array

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Min Stack

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

### Math

Leetcode list [here.](https://leetcode.com/explore/featured/card/top-interview-questions-easy/102/math/)

#### Fizz Buzz

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Count Primes

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Power of Three

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Roman to Integer

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

### Miscallaneous

Leetcode list [here.](https://leetcode.com/explore/featured/card/top-interview-questions-easy/99/others/)

#### Number of 1 Bits

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Hamming Distance

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Reverse Bits

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Pascal's Triangle

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Valid Parentheses

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

#### Missing Number

**Submitted Solution:**

```py
```

**Other Notable Solutions:**

```py
```

```py
```

## Top Interview Questions: Medium

Leetcode list [here,](https://leetcode.com/explore/interview/card/top-interview-questions-medium/)

### Array and Strings

### Linked List

### Trees and Graphs

### Backtracking

### Sorting and Searching

### Dynamic Programming

### Design

### Math

### Others

## Top Interview Questions: Hard

Leetcode list [here,](https://leetcode.com/explore/interview/card/top-interview-questions-hard/)

### Array and Strings

### Linked List

### Trees and Graphs

### Backtracking

### Sorting and Searching

### Dynamic Programming

### Design

### Math

### Others

## Amazon 2022 SDE-1 List

Leetcode list [here.](https://leetcode.com/list/98u3f9f6/)

### Integer to Roman

### Valid Parentheses

### Merge k Sorted Lists

### First Missing Positive

### Jump Game II

### Insert Interval

### Word Search

### Binary Tree Level Order Traversal

### Binary Tree Zigzag Level Order Traversal

### Best Time to Buy and Sell Stock III

### Binary Tree Maximum Path Sum

### Word Ladder II

### Word Ladder

### Longest Consecutive Sequence

### Copy List with Random Pointer

### Word Break

### Word Break II

### Min Stack

### Binary Tree Right Side View

### Number of Islands

### Word Search II

### Product of Array Except Self

### Integer to English Words

### Find Median from Data Stream

### Best Time to Buy and Sell Stock with Cooldown

### Coin Change

### Russian Doll Envelopes

### Find All Anagrams in a String

### LFU Cache

### Concatenated Words

### Number of Provinces

### Knight Probability in Chessboard

### My Calendar I

### Asteroid Collision

### All Paths From Source to Target

### Rectangle Overlap

### K-Similar Strings

### Reorder Data in Log Files

### Squares of a Sorted Array

### Rotting Oranges

### Stream of Characters

### Longest Happy Prefix

### Making File Names Unique

BUILDMEH



> Thank you for reading!  
> Find more content at <https://ryanfleck.ca/>  
> Source page: <https://ryanfleck.ca/reference/interview-hell-leetcode/>  
> Site index: [llms.txt](https://ryanfleck.ca/llms.txt)