Amazon Data Structures & Algorithms Interview Questions

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

叶 路. - "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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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