Daily

Question 1

What is a catalan number, equation, time complexity that uses it?

Answer 1

1, 2, 5, 14

C0 = 1
C n = (2 * n)! / (n + 1)! * (n!)

C 3 (1 indexed) = 6 * 5 * 4 * 3 * 2 * 1 / ( 4 * 3 * 2 * 1 ) * 3 * 2 * 1 = 6 * 5 / 3 * 2 = 5

Equation only shows it as n^2, BUT the catalan grows as 4^n / n^(3/2), so that would be the time complexity, exponential

Question 2

the equation for a permutation and combination

Answer 2

permutation = n! / (n - r)!
n is the choices, r is the length of our final result

combinations = n! / (k!(n-k)!
n is the choices, k is the length of the result

Question 3

Exponential search? What is it used for?

Answer 3

Use exponential search for divide 2 ints

class Solution:

• —def divide(self, dividend: int, divisor: int) -[greater than] int:
• ——-max_int = 2**31 -1
• ——-min_int = -2**31
• ——-half = -1073741824 # can’t use division
• ——-if dividend == min_int and divisor == -1:
• ———–return max_int
• ——-negatives = 2
• ——-if dividend [greater than] 0:
• ———–negatives -= 1
• ———–dividend = -dividend
• ——-if divisor [greater than] 0:
• ———–negatives -= 1
• ———–divisor = -divisor
• ——-if dividend [greater than] divisor:
• ———–return 0
• ——-quotient = 0
• ——-power = -1
• ——-value = divisor
• ——-# negative values
• ——-while value [greater than]= half and value + value [greater than]= dividend:
• ———–value += value
• ———–power += power
• ——-while divisor [greater than]= dividend:
• ———–if value [greater than]= dividend:
• —————quotient += power
• —————dividend -= value
• ———–power = (power [greater than][greater than] 1)
• ———–value = (value [greater than][greater than] 1)
• ——-return quotient if negatives is 1 else -quotient

Question 4

Add 2 ints without using + or -

Answer 4

class SumOfTwoBinary(object):

• —def answer1(self, a, b):
• ——-x, y = abs(a), abs(b)
• ——-if x[less than]y:
• ———–x,y = y, x
• ———–a,b = b, a
• ——-# sign = 1 if a[greater than]0 else -1
• ——-if a[greater than]0:
• ———–sign=1
• ——-else:
• ———–sign=-1
• ——-if a*b[greater than]=0:
• ———–while y:
• —————answer=x^y
• —————borrow = (x&y)[less than][less than]1
• —————x,y = answer, borrow
• ——-else:
• ———–while y:
• —————answer = x^y
• —————carry = ((~x)&y)[less than][less than]1
• —————x, y = answer, carry
• ——-return x*sign

Question 5

What is an adjacency list?

Answer 5

An unordered list in which the values represent edges of the graph at that index. Usually 1-indexed

[ [2, 3], [1,3], [1, 2] ] means that index 0 (node 1) has an edge to 2 and 3, and node 2 has an edge to 1 and 3

Question 6

Substring/subarray, subset, subsequence, how do you calculate each of them?

Answer 6

think contiguous!

Subarray
a subarray is a contiguous subsequence (they share a border)
if given {1, 2, 3, 4}, subarray can be

{1, 2, 3}
{2, 3, 4}

n^2 to get all subarrays/substrings

def displaysublist(str_list):
   response = [""]
   for i in range(len(str_list)):
----  for j in range(i + 1, len(str_list) + 1):
-------- sub = str_list[i:j]
-------- response.append(sub)
   return response

subsequence
order matters, but not contiguous
{1, 3}
{1, 4}

it takes 2^n to find all subsequences (same as subsets apparently)

from itertools import combinations

• —def all_subsequences(self, s):
• ——-out = set()
• ——-for r in range(1, len(s) + 1):
• ———–for c in combinations(s, r):
• —————out.add(‘‘.join(c))
• ——-return out

subset
subset is neither ordered nor contiguous

{1}
{2, 1}
{4, 3}
{1, 2, 3}

Question 7

3 things to do before you start coding in an interview

Answer 7

1. Ask about edge cases, should we expect null inputs? Will the input always be [integer, string, array, ect] and not any other type of input? If it is an integer, can we expect the number to be negative, string to be empty, array to be populated?Should we expect this to fit in 32 bits? Do we expect a large amount of edge inputs (so we can check in the beginning instead of the middle)
2. come up with 2 solutions, 1 that is really bad and brute force and say that is bad and expensive
3. write out what you plan to do before you start coding, give your interviewer an idea of what is to come, this will help

Say a lot that comes to mind, they have a rubric that says “if they mention X, add 1 point” this usually is in reference to multiple ways to solve a problem, BFS vs DFS and such, recursive or iterative, it all counts.

Question 8

time/space complexity of merge, quick, heap sort

Answer 8

all time complexity is N log N

quick: log n, bc we cut the list in half for each new call
heap: constant, we re-arrange the array from a heap perspective
merge: N, need the entire N space for left/right on the first one, then half the second, 3rd, 4th, which gives us N total, N + logN to be exact (https://stackoverflow.com/questions/10342890/merge-sort-time-and-space-complexity)

Question 9

squares of a sorted array

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Answer 9

brute is NlogN time, and logN space if you use quick sort. standard python sorting actually takes N time (I think)

class Solution:

• —def brute(self, nums):
• ——-return sorted([x * x for x in nums])

time: O(n), making the new list and iterating through the old one
space: O(n), we make a new list

• —def sortedSquares(self, nums):
• ——-response = [0] * len(nums)
• ——-left, right = 0, len(nums) - 1
• ——-for i in range(len(nums) - 1, -1, -1):
• ———–if abs(nums[right]) >= abs(nums[left]):
• —————current = nums[right]
• —————right -= 1
• ———–else:
• —————current = nums[left]
• —————left += 1
• ———–response[i] = current * current
• ——-return response

Question 10

1089. Duplicate Zeros

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything. THIS MEANS WE WILL REMOVE ELEMENTS FROM THE ARRAY IF THEY ARE PUSHED OUT

Example 1:

Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Answer 10

1. edge case if the last element in the while loop is 0, we can’t duplicate the zero, but the last element in the array will definitely be zero (if it is not already), so make the last element zero
2. duplicating the zeros is hard. similar to rotating array/linked list, we know elements that have 2 zeros infront will be moved back that many indexes. We know that if we find a zero, we move 1 zero up that many zeros we have found and 1 zero is moved up 1 less than that. Tricky but draw it out!

time: O(n), we do 2 loops, once to find the zeros, once to move them
space: constant, we cannot make a new array

class Solution:

• —def duplicateZeros(self, arr):
• ——-zeros = 0
• ——-left, right = 0, len(arr) - 1
• ——-while left <= right:
• ———–if left == right and arr[left] == 0:
• —————right -= 1
• —————arr[-1] = 0
• —————break
• ———–elif arr[left] == 0:
• —————zeros += 1
• —————right -= 1
• ———–left += 1
• ——-for i in range(right, -1, -1):
• ———–if arr[i] == 0:
• —————arr[i + zeros] = 0
• —————zeros -= 1
• —————arr[i + zeros] = 0
• ———–else:
• —————arr[i + zeros] = arr[i