December 2019 Flashcards Preview

AlgoExpert Notes > December 2019 > Flashcards

Flashcards in December 2019 Deck (32)
Loading flashcards...
1
Q

Difference b/t pass and continue

A

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

2
Q

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

A

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

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

` return False `

3
Q

python equivalent of

indexOf

A

index

myList.index(“a”)

4
Q

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

A

No, you can declare:

nums = {}

for nums in array:

` nums[num] = True`

5
Q

How to iterate in reversed order?

A

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

` print(i)`

6
Q

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

A

visited =

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

7
Q

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

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

A

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

8
Q

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

A

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]

]

9
Q

what are the values for variables

a and b?

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

a = [:2]

b = [2:]

A

a: [1,2]

b: [3,4,5,6]

10
Q

Describe Levenshstein Distance

A

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

11
Q

Whatis Kadane’s Algorithm

A

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

12
Q

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

A

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

13
Q

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

A

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)

14
Q

Describe the two number sum problem.

A

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

15
Q

Describe the three number sum problem

A

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

16
Q

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

A

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)

17
Q

How do you slice an entire list in python?

Does slicing mutate the original array?

A

sliced = arr[:]

No, slicing creates a copied portion.

18
Q

Describe the Max Subsets No Adjacent problem

A

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

19
Q

Describe the number of ways to make change

A

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

20
Q

Describe the “youngest common ancestor”.

A

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

21
Q

Describe the powerset prblem.

A

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.

22
Q

What functions are needed to construct a BST class?

A
  1. contains
  2. insert
  3. remove
  4. getMinValue
23
Q

How to find the min value for a BST?

A

def getMinValue(self):

node = self

while node.left is not None:

node = node.left

return node.value

24
Q

Explain how to remove an element from a BST.

A

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.

25
Q

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

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

What is the conceptual solution for validating a BST?

A

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

27
Q

Reminders on BST construction

A

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
28
Q

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

A

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.

29
Q

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

A

Check that tree is not None

30
Q

How to sort a string?

A

''.join(sorted(testString))

31
Q

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

A

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

32
Q

What are the first 8 fibonacci numbers?

A

0 1 1 2 3 5 8 13