SWE Interview preparation

https://leetcode.com/problems/network-delay-time/ There are  N  network nodes, labelled  1  to  N . Given  times , a list of travel times as  directed  edges  times[i] = (u, v, w) , where  u  is the source node,  v  is the target node, and  w  is the time it takes for a signal to travel from source to target. Now, we send a signal from a certain node  K . How long will it take for all nodes to receive the signal? If it is impossible, return  -1 . Example 1: Input: times = [[2,1,1],[2,3,1],[3,4,1]] , N = 4 , K = 2 Output: 2 Note: N  will be in the range  [1, 100] . K  will be in the range  [1, N] . The length of  times  will be in the range  [1, 6000] . All edges  times[i] = (u, v, w)  will have  1 <= u, v <= N  and  0 <= w <= 100 . --- Related problems 787-cheapest-flights-within-k-stops 1514-path-with-maximum-probability ...

https://leetcode.com/problems/merge-k-sorted-lists/ Merge  k  sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [   1->4->5,   1->3->4,   2->6 ] Output: 1->1->2->3->4->4->5->6 --- Time - O(m * log k) - m = length of longest list Space - O(k) --- Related problems kth-largest-element-in-array k-closest-points-to-origin

https://leetcode.com/problems/kth-largest-element-in-a-stream/ Design a class to find the  k th largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element. Your  KthLargest  class will have a constructor which accepts an integer  k  and an integer array  nums , which contains initial elements from the stream. For each call to the method  KthLargest.add , return the element representing the kth largest element in the stream. Example: int k = 3; int[] arr = [4,5,8,2]; KthLargest kthLargest = new KthLargest(3, arr); kthLargest.add(3);   // returns 4 kthLargest.add(5);   // returns 5 kthLargest.add(10);  // returns 5 kthLargest.add(9);   // returns 8 kthLargest.add(4);   // returns 8 Note: You may assume that  nums ' length ≥  k-1  and  k  ≥ 1. ---

https://leetcode.com/problems/kth-largest-element-in-an-array/ Find the  k th largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Example 1: Input: [3,2,1,5,6,4] and k = 2 Output: 5 Example 2: Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 4 Note: You may assume k is always valid, 1 ≤ k ≤ array's length. --- Related problems k-closest-points-to-origin merge-k-sorted-lists

https://leetcode.com/problems/third-maximum-number/ Given a  non-empty  array of integers, return the  third  maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n). Example 1: Input: [3, 2, 1] Output: 1 Explanation: The third maximum is 1. Example 2: Input: [1, 2] Output: 2 Explanation: The third maximum does not exist, so the maximum (2) is returned instead. Example 3: Input: [2, 2, 3, 1] Output: 1 Explanation: Note that the third maximum here means the third maximum distinct number. Both numbers with value 2 are both considered as second maximum. --- Time - O(n log 3) => O(n) Space - O(n) - for Set, PQ also has contains method that can reduce space to O(1)

https://leetcode.com/problems/top-k-frequent-words/ Given a non-empty list of words, return the  k  most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first. Example 1: Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2 Output: ["i", "love"] Explanation: "i" and "love" are the two most frequent words. Note that "i" comes before "love" due to a lower alphabetical order. Example 2: Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4 Output: ["the", "is", "sunny", "day"] Explanation: "the", "is", "sunny" ...

https://leetcode.com/problems/top-k-frequent-elements/ Given a non-empty array of integers, return the  k  most frequent elements. Example 1: Input: nums = [1,1,1,2,2,3] , k = 2 Output: [1,2] Example 2: Input: nums = [1] , k = 1 Output: [1] Note: You may assume  k  is always valid, 1 ≤  k  ≤ number of unique elements. Your algorithm's time complexity  must be  better than O( n  log  n ), where  n  is the array's size. --- Intuition Top K, Max K, Most K => Min Heap Traverse the array We capture the min freq words from 1 upto current element in the min heap If heap size grows beyond k, then top element is least frequent word so far, not a candidate for final solution, so we trash it At the end of array traversal we've trashed out less frequent words, and k remain ---- Time - O(n * log(k)) Space - O(k) ---