December 2019 Flashcards
Difference b/t pass and continue
pass is a noop whereas continue skips to the next iteration of the loop
What to do to account for potential middle character in palindrome check?
Nothing. The following code will account for the middle value:
if string[i] == string[len(string)-i-1]:
` return False `
python equivalent of
indexOf
index
myList.index(“a”)
Do you need to perform a cast in order to store an int as a key in a dictionary?
No, you can declare:
nums = {}
for nums in array:
` nums[num] = True`
How to iterate in reversed order?
for i in reversed(range(0, len(arr))):
` print(i)`
How to make a mirror ‘visited’ matrix based on an input matrix?
visited =
[[False for value in row] for row in matrix]
How would you iterate in reverse by two given the following array:
array = [1,2,3,4,5]
for i in reversed(range(0, len(l), 2):
In dynamic programming, how do you form the initial grid for something like the Levenshtein Distance algorithm?
str1 = "abc"
str2 = "yabd"
edits = [[x for x in range(len(str1)+1)] for row in range(len(str2)+1)]
result:
[
[0, 1, 2, 3],
[0, 1, 2, 3],
[0, 1, 2, 3],
[0, 1, 2, 3],
[0, 1, 2, 3]
]
what are the values for variables
a and b?
test = [1,2,3,4,5,6]
a = [:2]
b = [2:]
a: [1,2]
b: [3,4,5,6]
Describe Levenshstein Distance
Problem
Find the minimum number of edits required to change one string to another. The following options are available:
- remove
- delete
- insert
Solution
- create memoization grid based on lengths of input strings
- seed the first row
- seed the first column
- iterate through nested loop (str1, str2)
- if char of str2 == char of str1 memo value = diagonal (top left)
- else memo value = 1 + memo of top, left, topleft
Analysis
O(mn) time
O(m,n) space but O(min(m,n)) possible
Whatis Kadane’s Algorithm
Problem
The input is a non empty array of numbers. The target output is the greatest sum found within a subarray of the input array.
Solution
The key variables to track and initialize are
maxEndingHere = array[0]
maxSoFar = array[0]
You iterate through the array and update the variables. The key concept is to realize that you are update the values based on the largest subarray which ends at a given index.
Analysis
O(n) time
O(1) space
Describe the branch sums problem. How do you solve for it?
Problem
The question asks that you populate an array of sums based on the branches of a given binary search tree.
Solution
Create a helper method which takes a node, solution array, and ‘runningSum’.
- Return if node is null.
- Otherwise calculate new runningSum based on node value.
- If there is no left child and no right child, append updated runningSum to array.
- Else, recurse on child left and recurse on child right
Analysis
O(n) time
O(n) space
Describe the 3 largest problem. Why would you not want a sort operation?
Problem
Given an array, find the three largest values.
Solution
You initialize a three item solution array threeLargest in which each item is negative infinity.
Analysis
O(n) time
O(1) space
Then, create a helper function which takes inthreeLargest and a number. For each item inthreeLargest , see if the number is greater than the current item. If it is, adjust threeLargest so that its values are shifted appropriately and the new value is placed at the correct position. You can implement a shiftArrAndPlaceNum(arr, val, index) function to achieve this end.
The reason you don’t want to use a sorting operation is that the aforementioned implementation has a O(n) time complexity whereas sorting means at least O(nlog n)
Describe the two number sum problem.
Problem
Given an array of numbers and a target sum, return an array of the two numbers from the input array which add up to the target sum.
Solution
- sort array
- initialize left and right pointers for ends of the array
- while left < right:
- candidate = sum of left and right pointers
- if candidate == target, return [left, right]
- elif candidate < target: left += 1
- elif candidate > target: right -= 1
Analysis
O(n) time
O(n) space
Describe the three number sum problem
Problem
Given an array and a target sum, find all triplets which will equal the target sum.
Solution
- sort array
- for num in array
- create pointers left and right based on num position
- while left < right
- find sum of all three values
- if sum == target, left++ right++ and append into solution array
- if sum < target, left ++
- if sum > target, right–
- while left < right
- create pointers left and right based on num position
- return solution array
Analysis
O(n^2) time
O(n) space where n is length of input array
How to you wrap for an array given an index which exceeds the length of the array’s length?
3
You use the mod operator with the length of the array.
example 1:
arr = ['a','b','c',d','e']
wrapIndex = -12
newIndex = wrapIndex % len(arr)
example 2:
arr = [1,2,3]
wrapIndex = 10
newIndex = wrapIndex % len(arr)
How do you slice an entire list in python?
Does slicing mutate the original array?
sliced = arr[:]
No, slicing creates a copied portion.
Describe the Max Subsets No Adjacent problem
Problem
Given an array of positive integers, return the max sum created by adding non-adjacent values within the array
Solution
Dynamic Programming. You are memoizing parallel array which indicates the maxsubset at each index. Key lemma is to seed the first two values of the memo:
maxSubsets[0] = arr[0]
maxSubsets[1] = max(arr[0], arr[1]
Analysis
O(n) time
O(n) space
(or constant space if you remove memo and simply track two variables ‘first’ and ‘second’)
Describe the number of ways to make change
Problem
The question asks that you return the number of ways to make change given a target amount and list of denominations (6, [1,4,2])
Solution
Dynamic programming. Initialize memo array with length of n+1 (to account for initial zero value). Initialize each value within array to 0. Seed memo[0] = 1 because there is only one way to create target 0 with 0 denomination (do nothing).
For each denomination, iterate through amounts 1 to n+1. If denom <= amount, ways[amount] += way[amount-denom]
return ways[-1]
Analysis
O(nd) time where d is length of denominations arg
O(n) space
Describe the “youngest common ancestor”.
Problem
An ancestral tree is a tree in which the root node is the top ancestor and sub nodes are descendants. Given the top ancestor and two descendants, find the youngest common ancestor for the two given nodes. Each node has an ‘ancestor’ property.
Solution
Realize that you only need to get the nodes to the same depth in the tree. Then, you can backtrack ancestors simultaneouly until both nodes hit the same ancestor (the solution).
Analysis
O(d) time where d is depth of longest descendant
O(1) space
Describe the powerset prblem.
Problem
You are given an array of integers. Return the powerset for the given array. A powerset if the set of all subsets.
Solution
Initialize a subsets variable to an empty array with one empty subset. Then iterate through the array Within each iteration, iterate through the subsets array and create a new subset which contains subsets[i] + [num]. Push this subset to the subsets array.
Analysis
O(2^n * n)
O(2^n * n)
The reason is that the final powerset always has 2^n items. Also, the average number of items in each subset of the powerset is n/2, which converges to n.
What functions are needed to construct a BST class?
- contains
- insert
- remove
- getMinValue
How to find the min value for a BST?
def getMinValue(self):
node = self
while node.left is not None:
node = node.left
return node.value
Explain how to remove an element from a BST.
You first add a parent param if none is available (algoexpert). Then you traverse tree until you get to the target element. Follow the following branch logic (if, elif, elif):
- Perform setting of value to min value of right tree IFF there are left and right child nodes.
- If there is no parent, you are dealing with a root node. Manually set this node’s value and the the
node.leftandnode.rightvalues. - Reset the parent.left or parent.right pointers to the left child of the deleted node if possible; otherwise point to the right node of the deleted node. Break
Return self.
What are the methods which need to be implented within a doubly linked list class?
- setHead
- setTail
- insertBefore
- insertAfter
- insertAtPosition
- removeNodesWithValue
- remove
- containsNodeWithValue
- removeNodeBindings
What is the conceptual solution for validating a BST?
You validate a given node based on a min and max value. If the node is validated, then you recurse on the left and right branches with assignments to:
leftValidated
rightValidated
Key concept: the base case for the function is
if not node.left and not node.right:
return True
Reminders on BST construction
Insert
- Stick to if/else logic not if/elif
- returns self
- break after instantiating new BST instance
Remove
- Remember to add
parentparameter - Remember to assign
parent - add
breakto end of branch logic to avoiding infinite loops - Remember to assign node value:
node.value = node.left.value
What is the trick to implementing a min max stack which has peek, getMin, getMax, push, pop operations which run in constant time?
The trick is to maintain both a normal array and a parallel “minMax” array which contains items that indicate the min and max at a given index of the normal array.
You can simply use a dictionary with “min” and “max” values for each item in the minMax array.
What is condition that must be passed to proceed with logic of inverting a binary tree?
Check that tree is not None
How to sort a string?
''.join(sorted(testString))
When populating a suffix trie, how do you move from one level of a trie to another during the initial setup?
You treat each level (hashmap) as a node within the tree.
You can traverse the trie by initially setting node to self.root and then, after assigning values to the node, updating node to equal node[letter] at each iteration.
At the end of the iteration, you assign node[self.endSymbol] = True
What are the first 8 fibonacci numbers?
0 1 1 2 3 5 8 13
