December 2019

Question 1

Difference b/t pass and continue

Answer 1

pass is a noop whereas continue skips to the next iteration of the loop

Question 2

What to do to account for potential middle character in palindrome check?

Answer 2

Nothing. The following code will account for the middle value:

if string[i] == string[len(string)-i-1]:

` return False `

Question 3

python equivalent of

indexOf

Answer 3

index

myList.index(“a”)

Question 4

Do you need to perform a cast in order to store an int as a key in a dictionary?

Answer 4

No, you can declare:

nums = {}

for nums in array:

` nums[num] = True`

Question 5

How to iterate in reversed order?

Answer 5

for i in reversed(range(0, len(arr))):

` print(i)`

Question 6

How to make a mirror ‘visited’ matrix based on an input matrix?

Answer 6

visited =

[[False for value in row] for row in matrix]

Question 7

How would you iterate in reverse by two given the following array:

array = [1,2,3,4,5]

Answer 7

for i in reversed(range(0, len(l), 2):

Question 8

In dynamic programming, how do you form the initial grid for something like the Levenshtein Distance algorithm?

Answer 8

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]

]

Question 9

what are the values for variables

a and b?

test = [1,2,3,4,5,6]

a = [:2]

b = [2:]

Answer 9

a: [1,2]

b: [3,4,5,6]

Question 10

Describe Levenshstein Distance

Answer 10

Problem

Find the minimum number of edits required to change one string to another. The following options are available:

1. remove
2. delete
3. insert

Solution

1. create memoization grid based on lengths of input strings
2. seed the first row
3. seed the first column
4. 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

Question 11

Whatis Kadane’s Algorithm

Answer 11

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

Question 12

Describe the branch sums problem. How do you solve for it?

Answer 12

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

Question 13

Describe the 3 largest problem. Why would you not want a sort operation?

Answer 13

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)

Question 14

Describe the two number sum problem.

Answer 14

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

Question 15

Describe the three number sum problem

Answer 15

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–
• return solution array

Analysis

O(n^2) time

O(n) space where n is length of input array

Question 16

How to you wrap for an array given an index which exceeds the length of the array’s length?

Answer 16

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)

Question 17

How do you slice an entire list in python?

Does slicing mutate the original array?

Answer 17

sliced = arr[:]

No, slicing creates a copied portion.

Question 18

Describe the Max Subsets No Adjacent problem

Answer 18

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

Question 19

Describe the number of ways to make change

Answer 19

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

Question 20

Describe the “youngest common ancestor”.

Answer 20

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

Question 21

Describe the powerset prblem.

Answer 21

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.

Question 22

What functions are needed to construct a BST class?

Answer 22

1. contains
2. insert
3. remove
4. getMinValue

Question 23

How to find the min value for a BST?

Answer 23

def getMinValue(self):

node = self

while node.left is not None:

node = node.left

return node.value

Question 24

Explain how to remove an element from a BST.

Answer 24

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

1. Perform setting of value to min value of right tree IFF there are left and right child nodes.
2. If there is no parent, you are dealing with a root node. Manually set this node’s value and the the node.left and node.right values.
3. 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.

Question 25

What are the methods which need to be implented within a doubly linked list class?

Answer 25

1. setHead
2. setTail
3. insertBefore
4. insertAfter
5. insertAtPosition
6. removeNodesWithValue
7. remove
8. containsNodeWithValue
9. removeNodeBindings

Question 26

What is the conceptual solution for validating a BST?

Answer 26

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

Question 27

Reminders on BST construction

Answer 27

Insert

1. Stick to if/else logic not if/elif
2. returns self
3. break after instantiating new BST instance

Remove

1. Remember to add parent parameter
2. Remember to assign parent
3. add break to end of branch logic to avoiding infinite loops
4. Remember to assign node value:node.value = node.left.value

Question 28

What is the trick to implementing a min max stack which has peek, getMin, getMax, push, pop operations which run in constant time?

Answer 28

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.

Question 29

What is condition that must be passed to proceed with logic of inverting a binary tree?

Answer 29

Check that tree is not None

Question 30

How to sort a string?

Answer 30

''.join(sorted(testString))

Question 31

When populating a suffix trie, how do you move from one level of a trie to another during the initial setup?

Answer 31

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

Question 32

What are the first 8 fibonacci numbers?

Answer 32

0 1 1 2 3 5 8 13