Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred. Example 1 Input: [1,2,3,4,5], k=4, x=3 Output: [1,2,3,4] Example 2 Input: [1,2,3,4,5], k=4, x=-1 Output: [1,2,3,4] Note The value k is positive and will always be smaller than the length of the sorted array.
Given an array arr[0 .. n-1] of distinct integers, the task is to find a local minima in it. We say that an element arr[x] is a local minimum if it is less than or equal to both its neighbors. For corner elements, we need to consider only one neighbor for comparison. There can be more than one local minima in an array, we need to find any one of them.
Given two arrays, write a function to compute their intersection. Example 1 Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2] Example 2 Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [9,4] Note Each element in the result must be unique. The result can be in any order. Solution Use binary search when one of the lists is very long and the other is short class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: if len(nums1) < len(nums2): return self.
Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned. Example 1 Input: 4 Output: 2 Example 2 Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842…, and since the decimal part is truncated, 2 is returned.
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. Example 1 Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 Output: true Example 2 Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 Output: false Solution # Treat the 2-d matrix as a 1-d list of length rows * cols.
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. Example 1 Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Example 2 Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1] Solution Time: O(logN)
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Your algorithm’s runtime complexity must be in the order of O(log n). Example 1 Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 Example 2 Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1 Solution (binary search) Java
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). Find the minimum element. You may assume no duplicate exists in the array. Example 1 Input: [3,4,5,1,2] Output: 1 Example 2 Input: [4,5,6,7,0,1,2] Output: 0 Solution class Solution: def findMin(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) == 1: return nums[0] if len(nums) == 2: return min(nums[0], nums[1]) if nums[0] < nums[len(nums)-1]: return nums[0] if nums[len(nums)-2] > nums[len(nums)-1]: return nums[len(nums)-1] for i in range(1, len(nums)-1): if nums[i] < nums[i-1] and nums[i] < nums[i+1]: return nums[i] def bsFindMin(self, nums): l, r = 0, len(nums) - 1 while l < r: m = (l + r) // 2 if nums[m] > nums[m - 1] and nums[m] > nums[m + 1]: return nums[m + 1] if nums[m] < nums[m - 1] and nums[m] < nums[m + 1]: return nums[m] if nums[m] >= nums[r]: l = m else: r = m return nums[0]
There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty. Example 1 nums1 = [1, 3] nums2 = [2] The median is 2.0 Example 2 nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.