Amazon Senior Data Engineer Interview Questions and Answers

Function to return mutual friends given two ids and getFriends(id) function

• Call getFriends(id) for both ids to get their respective friend lists

• Iterate through both lists and compare to find mutual friends

• Return the list of mutual friends

Function to return list of friends of friends in decreasing order of mutual friends

• Use a set to store all friends of friends

• Iterate through the list of friends of the given id

• For each friend, iterate through their list of friends and count mutual friends

• Sort the set of friends of friends by decreasing number of mutual friends

Given time slots, find a specific time with maximum overlap. Prove solution.

• Create a list of all start and end times

• Sort the list in ascending order

• Iterate through the list and keep track of the number of overlaps at each time

• Return the time with the maximum number of overlaps

• Prove solution by testing with different input sizes and edge cases

Find the longest sub-array with increasing order of integers.

• Iterate through the array and keep track of the current sub-array's start and end indices.

• Update the start index whenever the current element is smaller than the previous element.

• Update the end index whenever the current element is greater than or equal to the next element.

• Calculate the length of the sub-array and compare it with the longest sub-array found s

Find the length of longest increasing subsequence and print the sequence from an array of integers.

• Use dynamic programming to solve the problem

• Create an array to store the length of longest increasing subsequence ending at each index

• Traverse the array and update the length of longest increasing subsequence for each index

• Print the sequence by backtracking from the index with the maximum length

• Time complexity: O(n^2)

• Exam...read more

Code to find a given integer in a rotated sorted array.

• Use binary search to find the pivot point where the array is rotated.

• Divide the array into two subarrays and perform binary search on the appropriate subarray.

• Handle edge cases such as the target integer not being present in the array.

Use a min-heap to keep track of the largest K numbers seen so far.

• Create a min-heap of size K.

• For each incoming integer, add it to the heap if it's larger than the smallest element in the heap.

• If the heap size exceeds K, remove the smallest element.

• At the end, the heap will contain the largest K numbers in the input.

LRU Cache is a data structure that stores the most recently used items and discards the least recently used items.

• Use a doubly linked list to keep track of the order of items in the cache

• Use a hash map to store the key-value pairs for fast access

• When an item is accessed, move it to the front of the linked list

• When the cache is full, remove the least recently used item from the back of the linked list and the hash map

Solution to performing operations on a large array of bits.

• Use bitwise operators to perform operations on individual bits

• Use a loop to iterate through the array and perform the operations

• Ensure that the array is large enough to accommodate all the bits

• Consider using a data structure like a bitset for efficient bit manipulation

Given a 2D matrix with doors and walls, fill distance matrix with minimum distance to the nearest door.

• Iterate through the matrix and find the doors

• Use Breadth-First Search (BFS) to calculate the minimum distance from each cell to the nearest door

• Update the distance matrix with the minimum distances

Find kth smallest element in unordered array with O(1) space

• Use the QuickSelect algorithm to partition the array and find the kth smallest element

• Choose a pivot element and partition the array into two subarrays

• Recursively partition the subarray that contains the kth smallest element

• Repeat until the pivot element is the kth smallest element

• Time complexity: O(n) average case, O(n^2) worst case

To find friends of friends who are not already friends with you, we can first find your friends and then their friends excluding yourself and your friends.

• Get your list of friends

• For each friend, get their list of friends

• Exclude yourself and your friends from the final list of friends of friends