Given two sparse vectors, compute their dot product. Implement class SparseVector: SparseVector(nums) Initializes the object with the vector nums dotProduct(vec) Compute the dot product between the instance of SparseVector and vec A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector. Follow up: What if only one of the vectors is sparse? ...
Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window. Implement the MovingAverage class: MovingAverage(int size) Initializes the object with the size of the window size. double next(int val) Returns the moving average of the last size values of the stream. Example 1: Input ["MovingAverage", "next", "next", "next", "next"] [[3], [1], [10], [3], [5]] Output [null, 1.0, 5.5, 4.66667, 6.0] Explanation MovingAverage movingAverage = new MovingAverage(3); movingAverage.next(1); // return 1.0 = 1 / 1 movingAverage.next(10); // return 5.5 = (1 + 10) / 2 movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3 movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3 Constraints: ...
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements. ...
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. Note: You must not use any built-in BigInteger library or convert the inputs to integer directly. Example 1: Input: num1 = "2", num2 = "3" Output: "6" Example 2: Input: num1 = "123", num2 = "456" Output: "56088" Constraints: 1 <= num1.length, num2.length <= 200 num1 and num2 consist of digits only. Both num1 and num2 do not contain any leading zero, except the number 0 itself. Solution class Solution { public String multiply(String num1, String num2) { int[] products = new int[num1.length() + num2.length()]; for (int i = 0; i < num1.length(); i++) { for (int j = 0; j < num2.length(); j++) { int d1 = num1.charAt(i) - '0'; int d2 = num2.charAt(j) - '0'; products[i + j + 1] += d1 * d2; } } int carry = 0; for (int i = products.length - 1; i >= 0; i--) { int tmp = (products[i] + carry) % 10; carry = (products[i] + carry) / 10; products[i] = tmp; } StringBuilder sb = new StringBuilder(); for (int product: products) { if (product == 0 && sb.length() == 0) { continue; } sb.append(product); } if (sb.length() == 0) { sb.append("0"); } return sb.toString(); } }
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function). The algorithm for myAtoi(string s) is as follows: Read in and ignore any leading whitespace. Check if the next character (if not already at the end of the string) is ‘-’ or ‘+’. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored. Convert these digits into an integer (i.e. “123” -> 123, “0032” -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2). If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1. Return the integer as the final result. Note: ...
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity. 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] Example 3: Input: nums = [], target = 0 Output: [-1,-1] Constraints: ...
Given two strings s and t of length N, find the maximum number of possible matching pairs in strings s and t after swapping exactly two characters within s. A swap is switching s[i] and s[j], where s[i] and s[j] denotes the character that is present at the ith and jth index of s, respectively. The matching pairs of the two strings are defined as the number of indices for which s[i] and t[i] are equal. Note: This means you must swap two characters at different indices. Signature int matchingPairs(String s, String t) Input ...
Pair Sums Given a list of n integers arr[0..(n-1)], determine the number of different pairs of elements within it which sum to k. If an integer appears in the list multiple times, each copy is considered to be different; that is, two pairs are considered different if one pair includes at least one array index which the other doesn’t, even if they include the same values. Signature int numberOfWays(int[] arr, int k) Input n is in the range [1, 100,000]. Each value arr[i] is in the range [1, 1,000,000,000]. k is in the range [1, 1,000,000,000]. Output Return the number of different pairs of elements which sum to k. ...
Given two integer arrays of equal length target and arr. In one step, you can select any non-empty sub-array of arr and reverse it. You are allowed to make any number of steps. Return True if you can make arr equal to target, or False otherwise. Example 1: Input: target = [1,2,3,4], arr = [2,4,1,3] Output: true Explanation: You can follow the next steps to convert arr to target: 1- Reverse sub-array [2,4,1], arr becomes [1,4,2,3] 2- Reverse sub-array [4,2], arr becomes [1,2,4,3] 3- Reverse sub-array [4,3], arr becomes [1,2,3,4] There are multiple ways to convert arr to target, this is not the only way to do so. Example 2: Input: target = [7], arr = [7] Output: true Explanation: arr is equal to target without any reverses. Example 3: Input: target = [1,12], arr = [12,1] Output: true Example 4: Input: target = [3,7,9], arr = [3,7,11] Output: false Explanation: arr doesn't have value 9 and it can never be converted to target. Example 5: Input: target = [1,1,1,1,1], arr = [1,1,1,1,1] Output: true Constraints: ...
Given a file and assume that you can only read the file using a given method read4, implement a method read to read n characters. Your method read may be called multiple times. Method read4: The API read4 reads four consecutive characters from file, then writes those characters into the buffer array buf4. The return value is the number of actual characters read. ...