Math Blog

(Note: Robbing is against the law! 😉 The below is just the actual Leetcode question phrasing reproduced verbatim.)

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

Leetcode Solution (Python)

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        # dp[i] max amount for nums[0:i]
        dp = [-1 for i in range(n+1)]
        
        # Recursive function that returns dp[i]
        def recursive(i):
            if i<=0:
                return 0
            if dp[i]!=-1:
                return dp[i]
            else:
                dp[i] = max(recursive(i-1), nums[i-1]+recursive(i-2))
            #print(dp)
            return dp[i]
        return recursive(n)

Cracking the Coding Interview: 189 Programming Questions and Solutions

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

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Leetcode Python Solution

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        rolling_min = prices[0]
        max_profit = 0
        
        for i in range(0,len(prices)):
            curr_profit = prices[i]-rolling_min
            if curr_profit>max_profit:
                max_profit = curr_profit
            if prices[i]<rolling_min:
                rolling_min = prices[i]
                
        return max_profit

Elements of Programming Interviews in Python: The Insiders’ Guide

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.

Leetcode Solution (Python)

class Solution:
    def myAtoi(self, s: str) -> int:
        # Positive sign
        positive = True
        result_str = ''
        digits = ['0','1','2','3','4','5','6','7','8','9']
        signs = ['+','-']
        
        # Has the first non-space been encountered
        started = False
        
        # Has the first sign been encountered
        signed = False
        
        for i in range(0,len(s)):
            if (signed == True or started == True) and s[i] in signs:
                break
            if s[i]!= ' ':
                started = True
                if s[i] in signs:
                    signed = True
                    if s[i]=='-':
                        positive = False
                elif s[i] in digits:
                    result_str += s[i]
            if started==True and s[i] not in digits and s[i] not in signs:
                break
            
            
        #print(result_str)
        if result_str=='':
            return 0
        else:
            result_int = int(result_str) if positive==True else -int(result_str)
            
        # Clamp Range:
        MIN_INT = -2**31
        MAX_INT = 2**31-1
        if result_int < MIN_INT:
            result_int = MIN_INT
        elif result_int > MAX_INT:
            result_int = MAX_INT
        
        return result_int

Elements of Programming Interviews in Python: The Insiders’ Guide

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.

Leetcode Solution (Python)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # To lower case
        s = s.lower()
        
        # Remove puncutation
        s = s.translate(str.maketrans('', '', string.punctuation))
        
        # Remove space
        s = s.replace(" ", "")
        
        # Two pointers
        l = 0
        r = len(s)-1
        while l<r:
            if s[l]!=s[r]:
                return False
            l+=1
            r-=1
        
        return True

Elements of Programming Interviews in Python: The Insiders’ Guide

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.

Leetcode Solution (Python)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # Set of characters in s,t
        charset_s = set(s)
        charset_t = set(t)
        
        # If the two sets differ, they are not anagrams
        if charset_s!=charset_t:
            return False
        
        for char in charset_s:
            # Count characters in s, t
            count_s = s.count(char)
            count_t = t.count(char)
            # If the counts differ, then they are not anagrams
            if count_s!= count_t:
                return False
        return True

Elements of Programming Interviews in Python: The Insiders’ Guide

Leetcode Question

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).

Python Solution

class Solution:
    def reverse(self, x: int) -> int:
        MAX_INT = 2**31-1
        MIN_INT = -2**31
        result = 0
        while x!=0:
            if result>MAX_INT/10 or result<MIN_INT/10:
                return 0
            digit = x%10 if x>0 else x%-10
            #print('digit:',digit)
            x = math.trunc(x/10)
            #print('x:',x)
            result = result*10 + digit
        return result

Cracking the Coding Interview: 189 Programming Questions and Solutions

Leetcode Question

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 with O(1) extra memory.

Python Solution

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        l = 0
        r = len(s)-1
        while l<r:
            s[l],s[r] = s[r],s[l]
            l+=1
            r-=1

Cracking the Coding Interview: 189 Programming Questions and Solutions

Rotate Image Leetcode

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, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Solution (Python)

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        # Transpose
        for i in range(0,n):
            for j in range(0,i):
                temp = matrix[i][j]
                matrix[i][j] = matrix[j][i]
                matrix[j][i] = temp
        #print(matrix)
        
        # Reflection (left-right, swap columns)
        for i in range(0,n):
            for j in range(0,n//2):
                temp = matrix[i][j]
                matrix[i][j] = matrix[i][n-j-1]
                matrix[i][n-j-1] = temp

Cracking the Coding Interview: 189 Programming Questions and Solutions

Question

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.

Solution (Python)

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        curr_index = len(digits)-1
        while curr_index>0:
            if digits[curr_index]<9:
                digits[curr_index] = digits[curr_index]+1
                return digits
            else:
                digits[curr_index] = 0
                curr_index -=1
        if curr_index==0:
            if digits[0]==9:
                digits[0]=0
                digits = [1] + digits
                return digits
            else:
                digits[0] = 1 + digits[0]
                return digits

Cracking the Coding Interview: 189 Programming Questions and Solutions

Question

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.

Solution (Python)

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        len1 = len(nums1)
        len2 = len(nums2)
        smaller = nums1 if len1<=len2 else nums2
        larger = nums1 if len1>len2 else nums2
        #print(smaller)
        final_list = []
        for num in smaller:
            try:
                idx = larger.index(num)
                larger.pop(idx)
                final_list.append(num)
            except ValueError:
                pass
        return final_list

Cracking the Coding Interview: 189 Programming Questions and Solutions

Question

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.

Solution (Python)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        xor = 0
        for num in nums:
            xor ^= num
        # a^a = 0 (each number a, when xor with itself is 0)
        # 0^b = b (hence, the final output will return the element which appears only once)
        return xor

Cracking the Coding Interview: 189 Programming Questions and Solutions

Question

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.

Solution (Python)

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

Cracking the Coding Interview: 189 Programming Questions and Solutions

Question

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

Python Solution

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if k==0:
            return
        if k>=len(nums):
            k = k % len(nums)
        print('k:',k)
        right_list = nums[-k:] if k>0 else []
        left_list = nums[0:len(nums)-k]
        print('right_list:',right_list)
        print('left_list:',left_list)
        nums[:] = right_list + left_list

Cracking the Coding Interview: 189 Programming Questions and Solutions

Question

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.

Solution (Python)

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

Cracking the Coding Interview: 189 Programming Questions and Solutions