This is a list of most frequently asked coding questions for Amazon SDE roles.
Let's get started.
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
"""
Logic:
1.Create heap to store the val and index of every first element of each ListNode in the lists.
2.Pop the minimum element from the heap and assign the val and node to its next.
3.Iterate until your heap is empty
"""
# Empty heap list
temp_list = []
# Create the output Node and assign it to result
output = ListNode(0)
result = output
# create a heap with all the first elements val and index in the lists nodes.
for index,node in enumerate(lists):
if node:
heapq.heappush(temp_list, (node.val, index))
''' If lists are empty temp_list will also be empty'''
# Until the heap is empty append the minimum values to Output Node
while temp_list:
m = heapq.heappop(temp_list)
output.next = ListNode(m[0])
# Update heap with new elements
if lists[m[1]].next != None:
lists[m[1]] = lists[m[1]].next
heapq.heappush(temp_list, (lists[m[1]].val,m[1]))
output = output.next
# return the result
return result.nextdef partitionLabels(self, S: str) -> List[int]:
"""
Greedy Approach:
1.Create a dictionary with the char and their last indices
2.create start and end of each partition and update them by iterating through the String 'S'
"""
last_indices = {char:index for index, char in enumerate(S)}
# to track start and end of each partition
start = end = 0
result = []
for curr_ind,curr_char in enumerate(S):
'''Update end to its maximum value for every char
so that same elements doesn't fall in diff partitions'''
end = max(end, last_indices[curr_char])
if curr_ind == end:
result.append(end - start + 1) # length of the current partition
start = end + 1 # update start
return resultdef topKFrequent(self, words: List[str], k: int) -> List[str]:
"""
Heap object creates a tree from a list which contains the smallest
element from the list at root, So it always pops the smallest element from the list.
(-count) helps to push the elements in reverse order.
"""
# Count the frequency of each word
word_dict = collections.Counter(words)
# Intialize a heap list
heap = []
for word,count in word_dict.items():
# Push elements into heap based on their count
heapq.heappush(heap, (-count, word))
# return the k largest elements from the heap
return [heapq.heappop(heap)[1] for _ in range(k)]def minMeetingRooms(self, intervals: List[List[int]]) -> int:
"""
Input: [[0, 30],[5, 10],[15, 20]]
Output: 2
Input: [[7,10],[2,4]]
Output: 1
"""
l = len(intervals) # length of intervals
# Basic Edge cases
if l == 0:
return 0
elif l == 1:
return 1
''' Create a heap and store values based on their end time '''
heap = []
intervals.sort(key=lambda x:x[0])
heapq.heappush(heap, intervals[0][1])
for i in range(1, l):
if intervals[i][0] < heap[0]:
''' If current start time is less than the end time
of the meeting that is going to complete is first then update heap'''
heapq.heappush(heap, intervals[i][1])
else:
heapq.heappop(heap) # remove the completed meeting that doesn't clash with new one.
heapq.heappush(heap, intervals[i][1])
return len(heap) # No:of meeting roomsdef wordBreak(self, s: str, wordDict: List[str]) -> bool:
"""
Input: "catsandog", ["cats", "dog", "sand", "and", "cat"]
Output: false
"""
# Convert word list to Dictionary:
worddict = {w:1 for w in wordDict}
# Empty dict for memorization:
memory = {}
# Recurvise wordBreak with Memorization parameter
def recursion_with_mem(s, wordDict, mem):
# Base Condition
if s == "" or s in wordDict:
return True
# Check in Memory
if s in mem:
return mem[s]
# Recursive Traversal of the string
for i in range(1, len(s)):
if s[:i] in wordDict and recursion_with_mem(s[i:], wordDict, mem):
mem[s] = True
return True
mem[s] = False
return False
return recursion_with_mem(s, worddict, memory)