Cutting Binary Search Tree - Amazon Top Interview Questions
Given a binary search tree root, an integer lo, and another an integer hi, remove all nodes that are not between [lo, hi] inclusive. Constraints n ≤ 100,000 where n is the number of nodes in root Example 1 Input root = [2, [1, [0, null, null], null], [4, [3, null, null], null]] lo = 3 hi = 4 Output [4, [3, null, null], null] Example 2 Input root = [5, [1, null, null], [9, [7, [6, null, null], [8, null, null]], [10, null, null]]] lo = 7 hi = 10 Output [9, [
View Solution →Swap Kth Node Values - Amazon Top Interview Questions
You are given a singly linked list node and an integer k. Swap the value of the k-th (0-indexed) node from the end with the k-th node from the beginning. Constraints 1 ≤ n ≤ 100,000 where n is the number of nodes in node 0 ≤ k < n Example 1 Input node = [1, 2, 3, 4, 5, 6] k = 1 Output [1, 5, 3, 4, 2, 6] Explanation We swap 2 and 5. Example 2 Input node = [0, 6, 8, 2, 9] k = 2 Output [0, 6, 8, 2, 9] Explanation We swap 8 with 8.
View Solution →Sum of Nodes with Even Grandparent Values - Amazon Top Interview Questions
Given a binary tree root, return the sum of all node values whose grandparents have an even value. Constraints 0 ≤ n ≤ 100,000 where n is the number of nodes in root Example 1 Input root = [8, [4, [6, null, null], [7, null, [2, null, null]]], [3, null, null]] Output 15 Explanation Nodes 6, 7, and 2 have an even value grandparent.
View Solution →Least Recently Used Cache - Amazon Top Interview Questions
Implement a least recently used cache with the following methods: LRUCache(int capacity) constructs a new instance of a LRU cache with the given capacity. get(int key) retrieves the value associated with the key key. If it does not exist, return -1. As a side effect, this key now becomes the most recently used key. set(int key, int val) updates the key key with value val. If updating this key-value pair exceeds capacity, then evicts the least recently used key-value pair. Each method shoul
View Solution →Flight Itinerary Sequel - Amazon Top Interview Questions
You are given a list of flights that were taken, represented as origin to destination airport pairs. Given that this list was shuffled, find all the airports that were visited in the correct order. If there's more than one valid itinerary, return the lexicographically smallest ones first. Note: airports may be visited twice. Example 1 Input flights = [ ["YYZ", "SEA"], ["JFK", "YYZ"], ["SEA", "JFK"] ] Output ["JFK", "YYZ", "SEA", "JFK"] Explanation The thre
View Solution →