150

The problem Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums, return this repeated number. You must solve the problem without modifying the array nums and using only constant extra space. Examples Input: nums = [1,3,4,2,2] Output: 2 Input: nums = [3,1,3,4,2] Output: 3 Input: nums = [3,3,3,3,3] Output: 3 Constraints 1 <= n <= 10^5 nums.length == n + 1 1 <= nums[i] <= n All the integers in nums appear only once except for precisely one integer which appears two or more times. Follow up: ...

The problem You are given two non‑empty linked lists representing two non‑negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Examples Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807. Input: l1 = [0], l2 = [0] Output: [0] Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1] Constraints The number of nodes in each linked list is in the range [1, 100]. 0 ≤ Node.val ≤ 9 It is guaranteed that the list represents a number that does not have leading zeros. Explanation When we add two numbers, we need to remember the carry value when it’s necessary. The main caveat in this problem is the edge cases; we will discuss them later. From the description of the problem, we know that we are given two non‑empty linked lists without negative integers, and the digits are stored in reverse order; we will see later that this reverse order will help us solve the problem. ...

The problem A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null. Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointers of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list. ...

The problem Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Examples Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2. Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5. Constraints nums1.length == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -10^6 <= nums1[i], nums2[i] <= 10^6 Explanation From our given examples we can learn that we could potentially have an even or odd number of total elements after we merge two input arrays. If we just try to merge both inputs and find the median, it will take us O(m + n) time, but we know that is not what we were asked to do. ...

The problem Design a time-based key-value data structure that can store multiple values for the same key at different timestamps and retrieve the key’s value at a certain timestamp. Implement the TimeMap class: TimeMap() Initializes the object of the data structure. void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp. String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "". Examples Input ["TimeMap", "set", "get", "get", "set", "get", "get"] [[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]] Output [null, null, "bar", "bar", null, "bar2", "bar2"] Explanation TimeMap timeMap = new TimeMap(); timeMap.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1. timeMap.get("foo", 1); // return "bar" timeMap.get("foo", 3); // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar". timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4. timeMap.get("foo", 4); // return "bar2" timeMap.get("foo", 5); // return "bar2" Constraints 1 <= key.length, value.length <= 100 key and value consist of lowercase English letters and digits. 1 <= timestamp <= 10^7 All the timestamps of set are strictly increasing. At most 2 * 10^5 calls will be made to set and get. Explanation Our objective for this task is to design a key-value store. We are going to have a key, and a list of values associated with that key, and each value is going to have a timestamp associated with it. As for operations, we are going to support only set and get operations. Now, let’s look at our example ...