Amazon Technical Flashcards
Count Unique Characters of All Substrings of a Given String
Time O(N) | Space O(N)
Pattern:
- Create a hash map. If the char is in HM, update its index, if not add -1.
- Loop through HM
- Set a positions to the hashMap’s index
Search Suggestions System
O(NN) Time | O(NN) space
Pattern:
- Sort by lex order
- Loop through searchWord
- Loop through products in products,
- if the index matches for searchWord and product and i < len(product), add it
- Set the products arr to temp
Flip String to Monotone Increasing
O(2 N) Time | O(N) Space
Pattern:
- Calculate the best cost
- Check if there are lower costs
Zombie in Matrix
Reverse Linked List
Time O (N), Space O(1)
Pattern
- Keep next in temp
- Set curr next to prev
- Set prev to current
- Set curr to next
- return prev
Linked List Cycle
Time: O(N) visit every node | Space: Adds every node
Pattern
- Uses memory address as hash
LRU Cache
Time O(1) | Space O(N)
Analyze User Website Visit Pattern
Reorder Data in Log Files
Time O(N log N) | Space O(N)
Notes:
- you can split and check if it digit in one go
- you can split in a lambda function, and specify array location
Sum of Subarray Ranges
Time O(n^2) | Space O(1)
Notes
- Setting a left and right, while incrementing keeps track of the min and max
Count Binary Substrings
Time O(N) | Space O(1)
Notes
- Min of prev keeps track of lesser to ensure balance
Sum of Subarray Minimums
Time O(N^3) | Space O(N)
Minimum Swaps to Group All 1’s Together
Time O(data) | Space O(0s)
Pattern:
- Determine the size of the sliding window by counting the number of 1s,
- Min moves is the number of spaces that are not 1
- Slide window, by iterating from the end of window
- chance the window sum, if it encounters a 1
- Find that window that has the least number of zeros to swap
Minimum Swaps to Group All 1’s Together
Time O(data) | Space O(0s)
Pattern:
- Determine the size of the sliding window by counting the number of 1s,
- Min moves is the number of spaces that are not 1
- Slide window, by iterating from the end of window
- chance the window sum, if it encounters a 1
- Find that window that has the least number of zeros to swap
The kth Factor of n
O(N) Time | O(1) Space
Notes:
- Since we need kth factor, use a count to keep track
Number of Islands
Time O(Rows x Cols) | Space O(Rows x Cols)
Pattern
- Loop through row and col, if there is a 1 call DFS on it
- DFS is used to change all 1s into #
- BC: if smaller than 0 or >= len or != 1 return
- Make all 1s into #
- Call DFS on all four directions
Range Addition
Time O(Updates) | Space O(1)
Notes
- Essentially you create a balance between the first IDX and IDX outside of the window
- And in the second for loop you update all of the sums
Merge Intervals
Time O (N) Time | O(N) Space
Pattern:
- Sort based on lower bound
- Start at next and keep result in arr
- Compare max of currentEnd and nextEnd
- add current case if mutate, else add both
The Maze
Time O(N^2) | Space O(1)
- Create a false map using double list comprehensions
- Check marker if visted or == coordinates
- Set up down left right
- While loop the index to the end and see if it is possible
- return True if it is
Sell Diminishing-Valued Colored Balls
Not optimal
Compare Version Numbers
Time O(2N length + max(Ns) | Space O (2N)
Pattern
- split arr based upon ‘.’
- loop through the largest version
- get the char at location, if it is outside of the index add 0
- int the char so it looses 0s
