## Max Sum Partitioning - Amazon Top Interview Questions

You are given a list of integers nums and an integer k. You must partition nums into contiguous groups of size at most k each, and then set each element in nums to the maximum value of its group. Return the maximum possible sum of the resulting list after partitioning. Constraints n ≤ 1,000 where n is the length of nums 1 ≤ k ≤ n Example 1 Input nums = [1, 6, 3, 2, 2, 5, 1] k = 3 Output 35 Explanation We can partition the list into [1, 6, 3] + [2] + [2, 5, 1] to

## Binary Search Tree Validation - Amazon Top Interview Questions

Given a binary tree root, return whether it's a binary search tree. A binary tree node is a binary search tree if : All nodes on its left subtree are smaller than node.val All nodes on its right subtree are bigger than node.val All nodes hold the these properties. Constraint n ≤ 100,000 where n is the number of nodes in root Example 1 Input root = [3, [2, null, null], [9, [7, [4, null, null], [8, null, null]], [12, null, null]]] Output True Example 2 Input root =

## 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

## 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

## 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.