Amazon Data Engineer II Interview Questions and Answers

Round duration - 90 minutes
Round difficulty - Hard

This was an online coding round where we were supposed to solve 2 questions under 90 minutes . Both the questions in my set were related to Graphs and were quite tricky and heavy to implement.

Q1. 
Path Counting in Directed Graph
Given a directed graph with a specified number of vertices V and edges E, your task is to calculate the total number of distinct paths from a given source node S to all ot...read more
Ans. 
Calculate the total number of distinct paths from a given source node to all other nodes in a directed graph.
• Use dynamic programming to keep track of the number of paths from the source node to each node in the graph.

• Consider using modular arithmetic to handle large numbers and prevent overflow.

• Start by initializing the number of paths from the source node to itself as 1.

• Iterate through the edges of the graph and updat...read more
Answered by AI
View 2 more answers
Q2. 
Course Schedule II Problem Statement
You are provided with a number of courses 'N', some of which have prerequisites. There is a matrix named 'PREREQUISITES' of size 'M' x 2. This matrix indicates that fo...read more
Ans. 
Given courses with prerequisites, determine a valid order to complete all courses.
• Use topological sorting to find a valid order of courses.

• Create a graph with courses as nodes and prerequisites as edges.

• Start with courses that have no prerequisites and remove them from the graph.

• Continue this process until all courses are taken or there are no valid courses left.

• If there is a cycle in the graph, it is impossible to com...read more
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

This was a Data Structures and Algorithms round with some standard questions . I was expected to come up with an
efficient approach and code it as well .

Q1. 
Merge Intervals Problem Statement
You are provided with 'N' intervals, each containing two integers denoting the start time and end time of the interval.
Your task is to merge all overlapping intervals a...read more
Ans. 
Merge overlapping intervals and return sorted list of merged intervals.
• Sort the intervals based on start times.

• Iterate through intervals and merge overlapping intervals.

• Return the merged intervals in sorted order.
Answered by AI
Add your answer
Q2. 
Longest Route Problem Statement
Given a 2-dimensional binary matrix called Mat of size N x M that consists solely of 0s and 1s, find the length of the longest path from a specified source cell to a destina...read more
Ans. 
Find the length of the longest path from a source cell to a destination cell in a binary matrix.
• Use depth-first search (DFS) to explore all possible paths from source to destination.

• Keep track of visited cells to avoid revisiting them.

• Return the length of the longest path found, or -1 if no path exists.
Answered by AI
Add your answer

Round duration - 50 Minutes
Round difficulty - Medium

This was also a DSA round where I was asked to code only one of the questions but I eventually ended up coding both
as I had some spare time and explained my approches very smoothly to the interviewer . This round went preety well .

Q1. 
Longest Increasing Subsequence Problem Statement
Given an array of integers with 'N' elements, determine the length of the longest subsequence where each element is greater than the previous element. This...read more
Ans. 
Find the length of the longest strictly increasing subsequence in an array of integers.
• Use dynamic programming to solve this problem efficiently.

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

• Iterate through the array and update the length of the longest increasing subsequence for each element.

• Return the maximum value in the array as the result.
Answered by AI
Add your answer
Q2. 
Search In Rotated Sorted Array Problem Statement
Given a rotated sorted array ARR of size 'N' and an integer 'K', determine the index at which 'K' is present in the array.
Note:
1. If 'K' is not present...read more
Ans. 
Given a rotated sorted array, find the index of a given integer 'K'.
• Use binary search to find the pivot point where the array is rotated.

• Then perform binary search on the appropriate half of the array to find 'K'.

• Handle cases where 'K' is not present in the array by returning -1.
Answered by AI
Add your answer

Round duration - 50 Minutes
Round difficulty - Medium

This was also a DSA round with 2 questions of Medium to Hard difficulty . I was expected to follow some clean code and OOPS principles to write the code in this round .

Q1. 
Rank from Stream Problem Statement
Given an array of integers ARR and an integer K, determine the rank of the element ARR[K].
Explanation:
The rank of any element in ARR is defined as the number of elem...read more
Ans. 
Given an array and an index, find the number of elements smaller than the element at that index appearing before it in the array.
• Iterate through the array up to index K and count the number of elements smaller than ARR[K].

• Return the count as the rank of ARR[K].

• Handle edge cases like empty array or invalid index K.
Answered by AI
View 1 more answer
Q2. 
LRU Cache Design Question
Design a data structure for a Least Recently Used (LRU) cache that supports the following operations:
1. get(key) - Return the value of the key if it exists in the cache; otherw...read more
Ans. 
Design a Least Recently Used (LRU) cache data structure that supports get and put operations with capacity constraint.
• Implement a doubly linked list to maintain the order of recently used keys.

• Use a hashmap to store key-value pairs for quick access.

• Update the order of keys in the linked list on get and put operations.

• Evict the least recently used key when the cache reaches its capacity.
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

This was a Data Structures and Algorithms round with preety good questions . I was expected to come up with an efficient approach and code it as well .

Q1. 
K Closest Points to Origin Problem Statement
Your house is located at the origin (0,0) of a 2-D plane. There are N neighbors living at different points on the plane. Your goal is to visit exactly K neighb...read more
Ans. 
Find the K closest points to the origin in a 2-D plane using Euclidean Distance.
• Calculate the Euclidean Distance of each point from the origin

• Sort the points based on their distances

• Return the first K points as the closest neighbors
Answered by AI
Add your answer
Q2. 
Power Set Generation
Given a sorted array of 'N' integers, your task is to generate the power set for this array. Each subset of this power set should be individually sorted.
A power set of a set 'ARR' i...read more
Ans. 
Generate the power set of a sorted array of integers with individually sorted subsets.
• Use recursion to generate all possible subsets by including or excluding each element in the array.

• Sort each subset before adding it to the power set.

• Handle base cases for empty array and single element array.

• Ensure the subsets are unique by using a set data structure.

• Time complexity can be exponential due to the nature of generating ...read more
Answered by AI
Add your answer

Round duration - 50 Minutes
Round difficulty - Hard

This was also a DSA round where I was asked to code only one of the questions but I eventually ended up coding both as I had some spare time and explained my approches very smoothly to the interviewer . This round went preety well .

Q1. 
Roman Numeral to Integer Conversion
Convert a string representing a Roman numeral into its integer equivalent and return the result.
Explanation:
Roman numerals are represented by seven different symbol...read more
Ans. 
Convert a Roman numeral string to its integer equivalent.
• Create a mapping of Roman numeral symbols to their integer values.

• Iterate through the input string and add the corresponding integer values.

• Handle cases where subtraction is needed (e.g., IV = 4, IX = 9).
Answered by AI
Add your answer
Q2. 
Pair Sum Problem Statement
You are given an integer array 'ARR' of size 'N' and an integer 'S'. Your task is to find and return a list of all pairs of elements where each sum of a pair equals 'S'.
Note:
...read more
Ans. 
Find pairs of elements in an array that sum up to a given value, sorted in a specific order.
• Iterate through the array and for each element, check if the complement (S - current element) exists in a hash set.

• If the complement exists, add the pair to the result list.

• Sort the result list based on the criteria mentioned in the question.

• Return the sorted list of pairs.
Answered by AI
Add your answer

Round duration - 50 Minutes
Round difficulty - Medium

This was also a DSA round with 2 questions . One was implementation heavy and the other was related to recursion and so I handled it carefully so that my code does not run into TLE or Segmentation Fault.

Q1. 
Arithmetic Expression Evaluation Problem Statement
You are provided with a string expression consisting of characters '+', '-', '*', '/', '(', ')' and digits '0' to '9', representing an arithmetic express...read more
Ans. 
Evaluate arithmetic expressions in infix notation with given operators and precedence rules.
• Parse the infix expression to postfix using a stack.

• Evaluate the postfix expression using a stack.

• Handle operator precedence and parentheses while evaluating.

• Ensure no division by zero cases and operands fit in 32-bit integer.
Answered by AI
Add your answer
Q2. 
Remove Duplicates from Sorted Array Problem Statement
You are given a sorted integer array ARR of size N. Your task is to remove the duplicates in such a way that each element appears only once. The outpu...read more
Ans. 
Remove duplicates from a sorted array in-place with O(1) extra memory.
• Use two pointers - one for iterating through the array and another for placing unique elements.

• Compare current element with next element to identify duplicates and skip them.

• Update array in-place by moving unique elements to the front.

• Return the length of the array after removal of duplicates.
Answered by AI
Add your answer

Round duration - 50 Minutes
Round difficulty - Medium

This was a typical System Design round where I was asked about the various features of Facebook and what sort of data structures and algorithms are used in implementing them .

Q1. How does Facebook store likes and dislikes?
Ans. 
Facebook stores likes and dislikes using a combination of databases and algorithms.
• Likes and dislikes are stored in databases such as MySQL or Cassandra.

• Algorithms are used to analyze user behavior and recommend content based on likes and dislikes.

• User interactions with posts, pages, and ads are tracked to determine likes and dislikes.

• Likes and dislikes may also be used to personalize the user's feed and target ads mor...read more
Answered by AI
Add your answer
Q2. How does Facebook implement graph search?
Ans. 
Facebook implements graph search using a graph database to efficiently search for connections between users and their interests.
• Facebook uses a graph database to store connections between users, pages, groups, etc.

• The graph search algorithm traverses the graph to find relevant connections based on user queries.

• It takes into account factors like user relationships, interests, and interactions to provide personalized sea...read more
Answered by AI
Add your answer

Round duration - 50 Minutes
Round difficulty - Medium

This was a preety intense round as I was grilled more on my System Design concepts but eventually I was able to asnwers all the questions with some help from the interviewer.

Q1. What is Hadoop and why is it used?
Ans. 
Hadoop is a framework for distributed storage and processing of large data sets.
• Hadoop is used for storing and processing big data across a distributed network of computers.

• It is based on the MapReduce programming model, which allows for parallel processing of data.

• Hadoop consists of HDFS for storage and YARN for resource management.

• It is used for tasks like data warehousing, log processing, recommendation systems, and...read more
Answered by AI
Add your answer
Q2. How does Facebook Chat work?
Ans. 
Facebook Chat works by using a combination of websockets, long polling, and push technology to deliver real-time messaging.
• Facebook Chat uses websockets for real-time communication between the client and server.

• Long polling is used to check for new messages when websockets are not supported.

• Push technology is used to notify users of new messages even when the chat window is not open.

• Messages are stored in a database an...read more
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Easy

In first round they asked me 2 coding questions where he asked me to code as close as possible to the actual one.

Q1. 
Ninja and Sorted Array Merging Problem
Ninja is tasked with merging two given sorted integer arrays ARR1 and ARR2 of sizes 'M' and 'N', respectively, such that the merged result is a single sorted array w...read more
Ans. 
Merge two sorted arrays into one sorted array in place.
• Use two pointers to compare elements from both arrays and place them in the correct position in ARR1.

• Start from the end of ARR1 and compare elements from both arrays, placing the larger element at the end of ARR1.

• Continue this process until all elements from ARR2 are merged into ARR1.
Answered by AI
Add your answer
Q2. 
Word Distance Calculation
Given a document represented as an array/list ARR of words with length N, find the smallest distance between two given words for multiple queries. The distance is defined as the ...read more
Ans. 
Find the smallest distance between two words in a document for multiple queries.
• Iterate through the document array to find the indices of the two words in each query.

• Calculate the absolute difference between the indices to get the distance.

• If a word from the query is not present in the document, return the length of the document array.

• Repeat the process for each query and output the smallest distance for each.
Answered by AI
View 1 more answer

Round duration - 60 minutes
Round difficulty - Easy

Then in the second round they asked a little about tree and told me to code 2 codes.

Q1. 
Level Order Traversal Problem Statement
Given a binary tree of integers, return the level order traversal of the binary tree.
Input:
The first line contains an integer 'T', representing the number of te...read more
Ans. 
The problem requires implementing a function to return the level order traversal of a binary tree.
• Implement a function that takes the root of the binary tree as input and returns the level order traversal of the tree.

• Use a queue data structure to perform level order traversal.

• Process each level of the tree one by one, starting from the root node.

• Print the node values at each level in the order they appear from left to ...read more
Answered by AI
Add your answer
Q2. 
Combination Sum Problem Statement
Given an array of distinct positive integers ARR and a non-negative integer 'B', find all unique combinations in the array where the sum is equal to 'B'. Numbers can be c...read more
Ans. 
Find all unique combinations in an array where the sum is equal to a given target sum, with elements in non-decreasing order.
• Use backtracking to generate all possible combinations.

• Sort the array to ensure elements are in non-decreasing order.

• Track the current combination and sum while backtracking.

• Terminate recursion when the sum equals the target sum.

• Avoid duplicates by skipping elements that have been used in previou...read more
Answered by AI
Add your answer

Round duration - 30 minutes
Round difficulty - Easy

HR round with typical behavioral problems.

Round duration - 60 minutes
Round difficulty - Medium

This was a online test round where I was given 3 DSA questions to be solved in 60 minutes.

Q1. 
Count Ways to Reach the N-th Stair Problem Statement
You are provided with a number of stairs, and initially, you are located at the 0th stair. You need to reach the Nth stair, and you can climb one or tw...read more
Ans. 
The problem involves finding the number of distinct ways to climb to the Nth stair by taking one or two steps at a time.
• Use dynamic programming to solve the problem efficiently.

• The number of ways to reach the Nth stair is the sum of the number of ways to reach the (N-1)th stair and the (N-2)th stair.

• Handle base cases for N=0 and N=1 separately.

• Consider using modulo 10^9+7 to avoid overflow in calculations.
Answered by AI
Add your answer
Q2. 
Optimal Strategy for a Coin Game
You are playing a coin game with your friend Ninjax. There are N coins placed in a straight line.
Here are the rules of the game:
1. Each coin has a value associated wit...read more
Ans. 
The problem involves finding the optimal strategy to accumulate the maximum amount in a coin game with specific rules.
• Start by understanding the rules of the game and how players take turns to choose coins.

• Consider the scenario where both players play optimally to maximize winnings.

• Iterate through different strategies to determine the best approach for selecting coins.

• Keep track of the total winnings accumulated by eac...read more
Answered by AI
Add your answer
Q3. 
Generate All Parentheses Combinations
Given an integer N, your task is to create all possible valid parentheses configurations that are well-formed using N pairs. A sequence of parentheses is considered w...read more
Ans. 
Generate all possible valid parentheses configurations using N pairs.
• Use backtracking to generate all possible combinations of parentheses.

• Keep track of the number of open and close parentheses used.

• Add '(' if there are remaining open parentheses, and add ')' if there are remaining close parentheses.

• Base case: when the length of the generated string is 2*N, add it to the result array.
Answered by AI
Add your answer