Skip to main content

Amazon Data Structures & Algorithms Interview Questions

Review this list of 39 Amazon Data Structures & Algorithms interview questions and answers verified by hiring managers and candidates.
  • Amazon logoAsked at Amazon 
    1 answer

    "I’d clarify the scope first. I’ll assume they want: Given a root folder and a search text, recursively find all files whose filename contains that text. Code: #include #include #include #include using namespace std; namespace fs = std::filesystem; vector searchFiles(const string& rootPath, const string& target) { vector ans; if(!fs::exists(rootPath)) { return ans; } // recursively go through all folder"

    Alok S. - "I’d clarify the scope first. I’ll assume they want: Given a root folder and a search text, recursively find all files whose filename contains that text. Code: #include #include #include #include using namespace std; namespace fs = std::filesystem; vector searchFiles(const string& rootPath, const string& target) { vector ans; if(!fs::exists(rootPath)) { return ans; } // recursively go through all folder"See full answer

    Software Engineer
    Data Structures & Algorithms
    +1 more
  • Amazon logoAsked at Amazon 
    41 answers
    Video answer for 'Edit distance'
    +33

    "from collections import deque def updateword(words, startword, end_word): if end_word not in words: return None # Early exit if end_word is not in the dictionary queue = deque([(start_word, 0)]) # (word, steps) visited = set([start_word]) # Keep track of visited words while queue: word, steps = queue.popleft() if word == end_word: return steps # Found the target word, return steps for i in range(len(word)): "

    叶 路. - "from collections import deque def updateword(words, startword, end_word): if end_word not in words: return None # Early exit if end_word is not in the dictionary queue = deque([(start_word, 0)]) # (word, steps) visited = set([start_word]) # Keep track of visited words while queue: word, steps = queue.popleft() if word == end_word: return steps # Found the target word, return steps for i in range(len(word)): "See full answer

    Software Engineer
    Data Structures & Algorithms
    +3 more
  • Amazon logoAsked at Amazon 
    31 answers
    +26

    "We can use dictionary to store cache items so that our read / write operations will be O(1). Each time we read or update an existing record, we have to ensure the item is moved to the back of the cache. This will allow us to evict the first item in the cache whenever the cache is full and we need to add new records also making our eviction O(1) Instead of normal dictionary, we will use ordered dictionary to store cache items. This will allow us to efficiently move items to back of the cache a"

    Alfred O. - "We can use dictionary to store cache items so that our read / write operations will be O(1). Each time we read or update an existing record, we have to ensure the item is moved to the back of the cache. This will allow us to evict the first item in the cache whenever the cache is full and we need to add new records also making our eviction O(1) Instead of normal dictionary, we will use ordered dictionary to store cache items. This will allow us to efficiently move items to back of the cache a"See full answer

    Software Engineer
    Data Structures & Algorithms
    +6 more
  • Amazon logoAsked at Amazon 
    2 answers

    "function longestCommonPrefix(arr1, arr2) { const prefixSet = new Set(); for (let num of arr1) { let str = num.toString(); for (let i = 1; i <= str.length; i++) { prefixSet.add(str.substring(0, i)); } } let longestPrefix = ""; for (let num of arr2) { let str = num.toString(); for (let i = 1; i <= str.length; i++) { let prefix = str.substring(0, i); if (prefixSet.has(prefix)) { "

    Maykon henrique D. - "function longestCommonPrefix(arr1, arr2) { const prefixSet = new Set(); for (let num of arr1) { let str = num.toString(); for (let i = 1; i <= str.length; i++) { prefixSet.add(str.substring(0, i)); } } let longestPrefix = ""; for (let num of arr2) { let str = num.toString(); for (let i = 1; i <= str.length; i++) { let prefix = str.substring(0, i); if (prefixSet.has(prefix)) { "See full answer

    Software Engineer
    Data Structures & Algorithms
    +1 more
  • Amazon logoAsked at Amazon 
    13 answers
    +8

    "I firstly discuss the brute force approach in O(n^2) time complexity , than i moved to O(nlogn) tine complexity than i discussed the O(n) time complexity and O(n) space complexity . But interviewer want more optimised solution , in O(n) time complexity without using extra space , The solution wants O(1) space complexity i have to do changes in same array without using any space . This method is something like i have to place positive values to its original position by swapping and rest negativ"

    Anni P. - "I firstly discuss the brute force approach in O(n^2) time complexity , than i moved to O(nlogn) tine complexity than i discussed the O(n) time complexity and O(n) space complexity . But interviewer want more optimised solution , in O(n) time complexity without using extra space , The solution wants O(1) space complexity i have to do changes in same array without using any space . This method is something like i have to place positive values to its original position by swapping and rest negativ"See full answer

    Software Engineer
    Data Structures & Algorithms
    +1 more
  • 🧠 Want an expert answer to a question? Saving questions lets us know what content to make next.

  • Amazon logoAsked at Amazon 
    56 answers
    Video answer for 'Merge Intervals'
    +48

    "const mergeIntervals = (intervals) => { const compare = (a, b) => { if(a[0] b[0]) return 1 else if(a[0] === b[0]) { return a[1] - b[1] } } let current = [] const result = [] const sorted = intervals.sort(compare) for(let i = 0; i = b[0]) current[1] = b[1] els"

    Kofi N. - "const mergeIntervals = (intervals) => { const compare = (a, b) => { if(a[0] b[0]) return 1 else if(a[0] === b[0]) { return a[1] - b[1] } } let current = [] const result = [] const sorted = intervals.sort(compare) for(let i = 0; i = b[0]) current[1] = b[1] els"See full answer

    Software Engineer
    Data Structures & Algorithms
    +6 more
  • Amazon logoAsked at Amazon 
    Add answer
    Software Engineer
    Data Structures & Algorithms
    +1 more
  • Amazon logoAsked at Amazon 
    6 answers
    +3

    "Approach (BFS + Horizontal Distance) Assign a horizontal distance (HD) to each node. Root → HD = 0 Left child → HD = parent HD - 1 Right child → HD = parent HD + 1 Do a BFS (level order traversal). If a node with a given HD is seen for the first time, add it to the result. Ignore later nodes with the same HD (because only the top one is visible). After traversal, sort by HD and print nodes left to righ"

    Firdous A. - "Approach (BFS + Horizontal Distance) Assign a horizontal distance (HD) to each node. Root → HD = 0 Left child → HD = parent HD - 1 Right child → HD = parent HD + 1 Do a BFS (level order traversal). If a node with a given HD is seen for the first time, add it to the result. Ignore later nodes with the same HD (because only the top one is visible). After traversal, sort by HD and print nodes left to righ"See full answer

    Software Engineer
    Data Structures & Algorithms
    +1 more
  • "Batch Packing Problem In Amazon’s massive warehouse inventory, there are different types of products. You are given an array products of size n, where products[i] represents the number of items of product type i. These products need to be packed into batches for shipping. The batch packing must adhere to the following conditions: No two items in the same batch can be of the same product type. The number of items packed in the current batch must be strictly greater than the number pack"

    Anonymous Goat - "Batch Packing Problem In Amazon’s massive warehouse inventory, there are different types of products. You are given an array products of size n, where products[i] represents the number of items of product type i. These products need to be packed into batches for shipping. The batch packing must adhere to the following conditions: No two items in the same batch can be of the same product type. The number of items packed in the current batch must be strictly greater than the number pack"See full answer

    Software Engineer
    Data Structures & Algorithms
    +1 more
  • "i responded using a multi sourced BFS and in place marking, then i checked the final grid to see if any free spots were left unmarked."

    Sh R. - "i responded using a multi sourced BFS and in place marking, then i checked the final grid to see if any free spots were left unmarked."See full answer

    Software Engineer
    Data Structures & Algorithms
    +1 more
  • Amazon logoAsked at Amazon 
    68 answers
    Video answer for 'Move all zeros to the end of an array.'
    +63

    "Initialize left pointer: Set a left pointer left to 0. Iterate through the array: Iterate through the array from left to right. If the current element is not 0, swap it with the element at the left pointer and increment left. Time complexity: O(n). The loop iterates through the entire array once, making it linear time. Space complexity: O(1). The algorithm operates in-place, modifying the input array directly without using additional data structures. "

    Avon T. - "Initialize left pointer: Set a left pointer left to 0. Iterate through the array: Iterate through the array from left to right. If the current element is not 0, swap it with the element at the left pointer and increment left. Time complexity: O(n). The loop iterates through the entire array once, making it linear time. Space complexity: O(1). The algorithm operates in-place, modifying the input array directly without using additional data structures. "See full answer

    Machine Learning Engineer
    Data Structures & Algorithms
    +4 more
  • Amazon logoAsked at Amazon 
    9 answers
    +6

    "DFS with check of an already seen node in the graph would work from collections import deque, defaultdict from typing import List def iscourseloopdfs(idcourse: int, graph: defaultdict[list]) -> bool: stack = deque([(id_course)]) seen_courses = set() while stack: print(stack) curr_course = stack.pop() if currcourse in seencourses: return True seencourses.add(currcourse) for dependency in graph[curr_course]: "

    Gabriele G. - "DFS with check of an already seen node in the graph would work from collections import deque, defaultdict from typing import List def iscourseloopdfs(idcourse: int, graph: defaultdict[list]) -> bool: stack = deque([(id_course)]) seen_courses = set() while stack: print(stack) curr_course = stack.pop() if currcourse in seencourses: return True seencourses.add(currcourse) for dependency in graph[curr_course]: "See full answer

    Software Engineer
    Data Structures & Algorithms
    +4 more
  • Amazon logoAsked at Amazon 
    33 answers
    +25

    " import java.util.*; public class MostCommonWords { public static String mostCommonWords(String text) { // your code goes here Map map = new HashMap(); for(String s : text.replaceAll("[\\p{Punct}]", "").toLowerCase().split(" ")) { if(!s.isEmpty()) { map.merge(s, 1, Integer::sum); } } return map.entrySet().stream().sorted( (e1, e2) -> { "

    Basil A. - " import java.util.*; public class MostCommonWords { public static String mostCommonWords(String text) { // your code goes here Map map = new HashMap(); for(String s : text.replaceAll("[\\p{Punct}]", "").toLowerCase().split(" ")) { if(!s.isEmpty()) { map.merge(s, 1, Integer::sum); } } return map.entrySet().stream().sorted( (e1, e2) -> { "See full answer

    Security Engineer
    Data Structures & Algorithms
    +1 more
  • Amazon logoAsked at Amazon 
    66 answers
    Video answer for 'Product of Array Except Self'
    +60

    "If 0's aren't a concern, couldn't we just multiply all numbers. and then divide product by each number in the list ? if there's more than one zero, then we just return an array of 0s if there's one zero, then we just replace 0 with product and rest 0s. what am i missing?"

    Sachin R. - "If 0's aren't a concern, couldn't we just multiply all numbers. and then divide product by each number in the list ? if there's more than one zero, then we just return an array of 0s if there's one zero, then we just replace 0 with product and rest 0s. what am i missing?"See full answer

    Software Engineer
    Data Structures & Algorithms
    +3 more
  • Amazon logoAsked at Amazon 
    7 answers
    +3

    "General Approach (using Max-Heap) Use a max-heap (priority queue) of size k. For each point: Compute the distance to P. Push it into the heap. If heap size > k, remove the farthest point. The heap will contain the k closest points to P. import java.util.*; public class KClosestPoints { static class Point { int x, y; public Point(int x, int y) { this.x = x; this.y = y; } // Euclidean distance squared (no need to take square root) p"

    Khushbu R. - "General Approach (using Max-Heap) Use a max-heap (priority queue) of size k. For each point: Compute the distance to P. Push it into the heap. If heap size > k, remove the farthest point. The heap will contain the k closest points to P. import java.util.*; public class KClosestPoints { static class Point { int x, y; public Point(int x, int y) { this.x = x; this.y = y; } // Euclidean distance squared (no need to take square root) p"See full answer

    Software Engineer
    Data Structures & Algorithms
    +2 more
  • Amazon logoAsked at Amazon 
    13 answers
    +10

    "Without using a recursive approach, one can perform a post-order traversal by removing the parent nodes from the stack only if children were visited: def diameterOfTree(root): if root is None: return 0 diameter = 0 stack = deque([[root, False]]) # (node, visited) node_heights = {} while stack: curr_node, visited = stack[-1] if visited: heightleft = nodeheights.get(curr_node.left, 0) heightright = nodehe"

    Gabriele G. - "Without using a recursive approach, one can perform a post-order traversal by removing the parent nodes from the stack only if children were visited: def diameterOfTree(root): if root is None: return 0 diameter = 0 stack = deque([[root, False]]) # (node, visited) node_heights = {} while stack: curr_node, visited = stack[-1] if visited: heightleft = nodeheights.get(curr_node.left, 0) heightright = nodehe"See full answer

    Software Engineer
    Data Structures & Algorithms
    +2 more
  • Amazon logoAsked at Amazon 
    3 answers

    "It was like say we have a library A which has a library B as a dependency and so on, how would we determine in the dependency chain that whether there is a circular depedency?"

    Chris R. - "It was like say we have a library A which has a library B as a dependency and so on, how would we determine in the dependency chain that whether there is a circular depedency?"See full answer

    Software Engineer
    Data Structures & Algorithms
    +1 more
  • Amazon logoAsked at Amazon 
    53 answers
    +49

    " from typing import List def two_sum(nums: List[int], target: int) -> List[int]: """ Iterate the list Create a hashmap for tracking seen complements For each element: Check if target - current was seen If so, return the index of the current and the index of the complement If not, add the current number in the hashmap as key, and the index of the current number as value. Return an empty array if the loop e"

    Jorge G. - " from typing import List def two_sum(nums: List[int], target: int) -> List[int]: """ Iterate the list Create a hashmap for tracking seen complements For each element: Check if target - current was seen If so, return the index of the current and the index of the complement If not, add the current number in the hashmap as key, and the index of the current number as value. Return an empty array if the loop e"See full answer

    Software Engineer
    Data Structures & Algorithms
    +5 more
  • Amazon logoAsked at Amazon 
    1 answer

    "class Node: def init(self, value): self.value = value self.children = [] def inorder_traversal(root): if not root: return [] result = [] n = len(root.children) for i in range(n): result.extend(inorder_traversal(root.children[i])) if i == n // 2: result.append(root.value) if n == 0: result.append(root.value) return result Example usage: root = Node(1) child1 = Node(2) chil"

    Teddy Y. - "class Node: def init(self, value): self.value = value self.children = [] def inorder_traversal(root): if not root: return [] result = [] n = len(root.children) for i in range(n): result.extend(inorder_traversal(root.children[i])) if i == n // 2: result.append(root.value) if n == 0: result.append(root.value) return result Example usage: root = Node(1) child1 = Node(2) chil"See full answer

    Software Engineer
    Data Structures & Algorithms
    +1 more
  • Amazon logoAsked at Amazon 
    18 answers
    Video answer for 'Given an nxn grid of 1s and 0s, return the number of islands in the input.'
    +15

    " from typing import List def getnumberof_islands(binaryMatrix: List[List[int]]) -> int: if not binaryMatrix: return 0 rows = len(binaryMatrix) cols = len(binaryMatrix[0]) islands = 0 for r in range(rows): for c in range(cols): if binaryMatrixr == 1: islands += 1 dfs(binaryMatrix, r, c) return islands def dfs(grid, r, c): if ( r = len(grid) "

    Rick E. - " from typing import List def getnumberof_islands(binaryMatrix: List[List[int]]) -> int: if not binaryMatrix: return 0 rows = len(binaryMatrix) cols = len(binaryMatrix[0]) islands = 0 for r in range(rows): for c in range(cols): if binaryMatrixr == 1: islands += 1 dfs(binaryMatrix, r, c) return islands def dfs(grid, r, c): if ( r = len(grid) "See full answer

    Software Engineer
    Data Structures & Algorithms
    +4 more
Showing 1-20 of 39