Communication Towers - Amazon Top Interview Questions
You are given a two dimensional list of integers matrix where a 1 represents a communication tower, and 0 represents an empty cell. Towers can communicate in the following ways: If tower a, and tower b are either on the same row or column, they can talk with each other. If tower a can talk with tower b and b can talk with c, then a can talk to c. Return the total number of tower groups there are (a group is a list of towers that can talk with each other). Constraints n ≤ 250 where n i
View Solution →Number of Unique Binary Search Trees - Amazon Top Interview Questions
Given an integer n, return the number of unique binary search trees you can form with integers from [0, n). Mod the result by 10 ** 9 + 7. Constraints n ≤ 1,000 Example 1 Input n = 3 Output 5 Explanation There are 5 unique trees. 0 \ 1 \ 2 0 \ 2 / 1 2 / 1 / 0 2 / 0 \ 1 1 / \ 0 2
View Solution →Kth Smallest Element - Amazon Top Interview Questions
Given a list of unsorted integers nums, and an integer k, return the kth (0-indexed) smallest element in the list. This should be done in \mathcal{O}(n)O(n) time on average. Constraints 0 ≤ k < n ≤ 100,000 where n is the length of nums Example 1 Input nums = [5, 3, 8, 2, 0] k = 2 Output 3 Explanation When sorted the numbers are [0, 2, 3, 5, 8] and index 2's value is 3.
View Solution →Longest Increasing Subsequence - Amazon Top Interview Questions
Given an unsorted list of integers nums, return the longest strictly increasing subsequence of the array. Bonus: Can you solve it in \mathcal{O}(n \log n)O(nlogn) time? Constraints n ≤ 1,000 where n is the length of nums Example 1 Input nums = [6, 1, 7, 2, 8, 3, 4, 5] Output 5 Explanation Longest increasing subsequence would be [1, 2, 3, 4, 5] Example 2 Input nums = [12, 5, 6, 25, 8, 11, 10] Output 4 Explanation One longest increasing subseque
View Solution →Make Target List with Increment and Double Operations - Amazon Top Interview Questions
You are given a list of non-negative integers target. Consider a list A of the same length as target containing all zeros initially. In one operation, you can increment one number in A, or double every number in A. Return the minimum number of operations required to turn A into target. Constraints 0 ≤ n ≤ 100,000 where n is the length of target Example 1 Input target = [3, 2, 2] Output 5 Explanation First, we start with A = [0, 0, 0] We increment A[0] and get [1, 0,
View Solution →