Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Algorithm > LC-Meta > Flashcards

LC-Meta Flashcards

1
Q

Binary tree vertical order traversal

A

You know it

Add tuple to dictionary;
Pop left from queue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Valid word abbreviation

A
  1. Make sure index2 is in range while getting the count
  2. Check if enough remaining chars in word and early return
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Nested list weight sum

A

Be careful about updating primitive variables with inner function.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

lowest common ancestor iii - with parent pointer

A

Two pointers that can merge, making sure they go through the same distance and eventually merge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

lowest common ancestor ii - nodes may or may not exist

A

Post order
Return (none, 0) as default after checking left and right

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Minimum remove to make valid parentheses - return just one valid string

A

Two pass; maintain balance.

T - N
S - N

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Valid Palindrome I

A

Get lower case of letter lower()
Check if letter is alphanumeric isalnum()
Reverse a string or list

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Valid palindrome II - remove at most one letter

A

Start from head and tail; whenever no match found, try remove either side

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Dot product of two sparse vectors

A
  1. Get both index and element by using enumerate func
  2. Get both key and value by items func
  3. Consider using array instead of hashmap!
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Validate palindrome - remove at most K letters

A

Think about base cases
Memorization
How to infer current from child cases

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Random pick with weight

A

Prefix sum the same length as array
Binary search - if low < target; else; then check both low and high
Random function - random.randint(start, stop) both inclusive

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Basic calculator II

A
  1. Track current operation
  2. How to truncate towards 0 when doing division for negative values
  3. isdigit()
  4. isspace()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Basic calculator - with parentheses and only addition and subtraction

A
  1. In place update result, we still need a stack though - why?
  2. When operator found, finish previous calculation and reset the sign and operand
  3. When open parenthesis found, cache the current sign and result in stack. Reset the result and sign
  4. When closing parenthesis found, finish previous calculation first, pop from stack and complete the calculation outside of the parenthesis. Reset operator.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Lowest common ancestor - two nodes must exist

A

Do preorder and early return

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Lowest common ancestor of binary search tree

A

Check the root value against p and a value and move to subproblem on either right or left subtree

What’s the stop case?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Basic calculator III - with positive number s only, parentheses and all operators

A
  1. We anyway need to use a stack.
  2. Check if an variable is integer - isinstance(e, int)
  3. Use while loop instead of for loop
  4. How to truncate towards 0 when negative division
  5. What to do when open and closing parentheses encountered
  6. Reset current operation when dealing with open parentheses
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Building with ocean view

A

Monotonic stack.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Kth largest element in an array

A
  1. initialize heap as list
  2. heapq.heappush
  3. heapq.heappop
  4. heap[0]
  5. Why do we use minimum heap here? Why do we pop when heap size is larger than k
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Range sum of BST

A

In order traversal - try recursion

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Moving average from data stream

A

Deque
Initialize sum as float(0)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Simplify path

A
  1. For dots, check if dots are between slashes
  2. When dealing with current directly or previous directly, make exception for root directory
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Convert binary search tree to sorted doubly linked list

A

In order traversal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Sum root to leaf numbers

A

DFS

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Simplify path

A

Remember to verify dots are only between slashes before moving on checking dots numbers

Remember to make exceptions for root directory slash

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Insert into sorted circular linked list

A
  1. No node
  2. Single node
  3. Use two pointers and while loop
  4. Insert value between max and min
  5. Find the tail, check if insert value is beyond and min and max range
  6. When back to the head, just insert
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Custom sort string

A

Frequency dictionary

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

3 sum closest

A

Sort.
Enumerate the start
Binary search and try to get closer and maintain the absolute diff.
Return target + diff

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

K closet points to origin

A

Heap
Tuple in heap

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Interval list intersections

A
  1. Two pointers
  2. Get the start and end first
  3. Check if the interval is valid
  4. Move pointers by comparing end of the two intervals

https://leetcode.com/problems/interval-list-intersections/

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Sticker to spell word

A
  1. DFS on subsequence
  2. For each subsequence, check which sticker to start with and exhaust the sticker by making a deep copy of it, then DFS on the remaining subsequence
  3. When starting with different stickers, get what’s the minimum result
  4. Eventually cache the minimum result for the subsequence
  5. Apply the DFS on entire subsequence
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Word break - check if break is true or false

A

Start with each word and DFS and see if possible

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Word break II - return all sentences that can be formed

A

Start with word and do DFS, if a solution is found the append to global result;
Pop from current sentence after moving to next word

https://leetcode.com/problems/word-break-ii/description/

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Pow(x, n)

A

Binary expression

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Two sum - sorted array, avoid duplicates

A

Low and high pointers.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

3 Sum; K Sum

A

Enumerate the start and skip duplicates.

Recursively call K-1 sum or 2 sum.

Iterate through the result from K - 1 sum or 2 sum and add to result.

36
Q

Make a large island

A

Union find;

Get the maximum size during first pass for building the parent dictionary.
We can return early for some edge cases.

Remember to use a dictionary to record how many islands we can connect given a cell of water.

37
Q

Number of islands

A

BSF from each island and add to visited set
Increment the result after BFS is done with the island.
Use set instead of list to store visited islands, because set provides constant search time

38
Q

Word Ladder

A
  1. Get all words combinations
  2. BSF and maintain number of steps

https://leetcode.com/problems/word-ladder/description/

39
Q

Min stack

A

Use one stack. Maintain the minimum value separately

40
Q

Valid number

A
  1. Three variables
  2. enumerate the string
  3. e should be after digits and not seen before; e can be right after dots! Reset digit seen because we expect integer after e
  4. dots can no be seen twice or after e
41
Q

Shortest path in binary matrix - 8 directional

A
  1. BFS
  2. Edge case
  3. How to maintain distance for each node?
42
Q

Subarray sum equals K - total number of subarrays;
Negative number in the array

A

Prefix sum + dictionary
Sum to to a set of indexes - why?
We actually don’t need to store the set of indexes, we can just have a frequency table.

43
Q

Continuous subarray sum that is always a multiple of K

A

Dictionary of residue

44
Q

Subarray product less than K - all positive numbers

A

Same direction two pointers;
Enumerate the start; end start from 0.

Remember to check the end - out of range or not, it impacts how we calculate the range.

https://leetcode.com/problems/subarray-product-less-than-k/description/

45
Q

Group shifted strings

A

Do mod operation and take the residue and build hash key. In Python it’s guaranteed to return a nonnegative residue.

Python ord(c) to return a number representing the char.

46
Q

Find Peak Item

A

Binary search

47
Q

LRU cache

A

Double linked list to efficiently perform remove and insert.

  1. Store the key with the node, so we can remove from the dictionary
  2. del dictionary[key]
  3. Define new node class and constructor. Val and key initialized as None
48
Q

Maximum swap

A

Digit to highest index

49
Q

Random pick index

A

Number to indexes dictionary
Random.randint(start, end) both inclusive

50
Q

Toeplitz matrix

A

Optimize the space.

51
Q

Diameter of binary tree

A

DFS

52
Q

Closest binary search tree value

A

Recursion version, no need to return result from the DFS function. Update the result in place.

53
Q

Binary tree right side view

A

https://leetcode.com/problems/binary-tree-right-side-view/description/

BFS by layer

54
Q

Copy list with random pointer

A

Dictionary from old to new nodes;
Recursion;
If old in dictionary, directly return the new nodes

55
Q

Clone graph

A

Old to new nodes dictionary at class level
Recursion

56
Q

Product of two run-length encoded arrays

A

Two pointer
Remember to check if two intervals can be merged in result
Update original two inputs in place

57
Q

Top K frequent elements

A

Frequency map and convert to tuple list

Heap sort on the tuple and keep heap size as K

58
Q

Exclusive time of functions

A

https://leetcode.com/problems/exclusive-time-of-functions/description/

Maintain current running Id and current time.
Update the current time.
Pop from stack when a function ends

59
Q

Missing ranges

A

Edge case when input is empty

60
Q

Diagonal traversal

A

Maintain a flag of direction;
Change the head when reaching the boundary
Flip the head
If at the corner, just return

61
Q

Merge intervals

A
  1. Use just one pointer.
  2. Maintain current start and end
  3. Iterate through the input and compare with current start and end.
  4. Pop from result if needed.
62
Q

Check if an original string exists given two encoded string

A
  1. Analysis first character of both strings and recursively solve the problem
  2. how many possible number combinations? Enumerate them and solve iteratively
  3. Use memo

https://leetcode.com/problems/check-if-an-original-string-exists-given-two-encoded-strings/

63
Q

Account merge

A

BFS
Email to name
Unique emails

64
Q

Merge K sorted lists

A
  1. Merge two sorted
  2. Override original list1
65
Q

Merge sorted array

A

Start from the end - m + n - 1

66
Q

Meeting room II - how many meeting rooms needed

A

Maintain a heap of meeting room end time
Return the length of heap

67
Q

Design tic tax toe

A

Maintain arrays of the marked blocks for each row and col and diagonal or anti-diagonal.

Set player to either 1 or -1

Each move should update all arrays

68
Q

Remove invalid parentheses - return all unique valid strings with minimum number of removals

A

DFS, pass a new str into recursive call

69
Q

Convert sorted linked into binary search tree 109

A

Converted linked list to array and the divide and conquer

70
Q

Maximum consecutive ones

A

Two window
Be super careful with moving end
After while loop, check both cases - if end is out of bound or not

71
Q

Kth missing positive number

A

Index to missing number? Binary search. Follow the standard binary search pattern.

72
Q

Verifying an alien dictionary

A
  1. Use zip
  2. No need to compare more if first different char is sorted
    3 check edge case - all letters the same

class Solution(object):
def isAlienSorted(self, words, order):
“””
:type words: List[str]
:type order: str
:rtype: bool
“””
letter_order = {}
for index, letter in enumerate(order):
letter_order[letter] = index

    # apple app
    for word1, word2 in zip(words, words[1:]):
        for letter1, letter2 in zip(word1, word2):
            if letter1 != letter2:
                if letter_order[letter1] > letter_order[letter2]:
                    return False
                # if we find the first different character and they are sorted,
                # then there's no need to check remaining letters
                break
        else:
            if len(word1) > len(word2):
                return False

    return True
73
Q

Populate next right pointer in each node

A

Make use of perfect binary to optimize the efficient, use while loop to check leftmost pointer at each letter

74
Q

Add Strings

A

Pointers from last element and cache carry

75
Q

All nodes distance K in binary tree

A

Two rounds of DFS

Build parent pointer

76
Q

Unique path I and II

A

Memorization

77
Q

Merge two BSTs

A

Use two stacks to do in-order traversal as the same time

https://favtutor.com/blogs/merge-binary-search-trees

78
Q

Remove Nth node from end of list

A

Two pointers. Use dummy head!

79
Q

Check completeness of binary tree

A

Get total nodes count.

DFS on indexes

80
Q

Swapping nodes in a single linked list - kth from the beginning and kth from the end

A

3 pointers.
Front pointer
End pointer
Another current pointer that goes to end

81
Q

Expression add operators

A

DFS and backtracking

Index, cur num, pre num, total, string

https://leetcode.com/problems/expression-add-operators/submissions/1285559171/

82
Q

Next permutation

A

Find the first non-increasing digit from the last, swap it with the first digit larger than it to its right, and then reverse the sub list to its right

83
Q

Validate IP address

A

Validate v4 and v6 separately by checking the number of dots

84
Q

K smallest elements from n sorted array

A

Use heap, first push all first elements to heap.

85
Q

Reverse integer

A

Keeping dividing and mod
Check against integer range

86
Q

Minimum add to make parentheses valid

A

Maintain balance. One pass.

Algorithm (14 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions