Another Casual Coder

We learn matrix multiplication in school, but it is much simpler with the help of programming. Basically two matrices A[n][k] and B[k][m] can be multiplied in time O(n*k*m). Exemplified by this LC problem:  https://leetcode.com/problems/sparse-matrix-multiplication/ Given two  sparse matrices   A  and  B , return the result of  AB . You may assume that  A 's column number is equal to  B 's row number. Example: Input: A = [ [ 1, 0, 0], [-1, 0, 3] ] B = [ [ 7, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 1 ] ] Output: | 1 0 0 | | 7 0 0 | | 7 0 0 | AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 | | 0 0 1 | The solution is given down below, literally just following the rules of matrices multiplication . Cheers, ACC. public class Solution {     public int[][] Multiply(int[][] A, int[][] B)     {         int[][] result = new int[A.Length][];         f...

Problem is here:  https://leetcode.com/problems/random-pick-with-weight/ Given an array  w  of positive integers, where  w[i]  describes the weight of index  i , write a function  pickIndex  which randomly picks an index in proportion to its weight. Note: 1 <= w.length <= 10000 1 <= w[i] <= 10^5 pickIndex  will be called at most  10000  times. Example 1: Input: ["Solution","pickIndex"] [[[1]],[]] Output: [null,0] Example 2: Input: ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] [[[1,3]],[],[],[],[],[]] Output: [null,0,1,1,1,0] Explanation of Input Syntax: The input is two lists: the subroutines called and their arguments.  Solution 's constructor has one argument, the array  w .  pickIndex  has no arguments. Arguments are always wrapped with a list, even if there aren't any. There must be a...

Here is the problem:  https://leetcode.com/problems/search-suggestions-system/ 1268. Search Suggestions System Medium 63 39 Favorite Share Given an array of strings  products  and a string  searchWord . We want to design a system that suggests at most three product names from  products  after each character of  searchWord  is typed. Suggested products should have common prefix with the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products. Return  list of lists  of the suggested  products  after each character of  searchWord  is typed.  Example 1: Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse" Output: [ ["mobile","moneypot","monitor"], ["mobile","moneypot","monitor"], ["mouse","mousepad"], ["mouse","m...

Here is the problem:  https://leetcode.com/problems/01-matrix/ 542. 01 Matrix Medium 919 92 Favorite Share Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1. Example 1: Input: [[0,0,0], [0,1,0], [0,0,0]] Output: [[0,0,0],  [0,1,0],  [0,0,0]] Example 2: Input: [[0,0,0], [0,1,0], [1,1,1]] Output: [[0,0,0], [0,1,0], [1,2,1]] Note: The number of elements of the given matrix will not exceed 10,000. There are at least one 0 in the given matrix. The cells are adjacent in only four directions: up, down, left and right. The idea will be to do 2-passes: from top to bottom (O(n)) and then from bottom to top (O(n)), using an extra matrix to keep track of the min distance. The first pass you check the min distance comparing with the previous row and the previous col. The second pass you keep track of the min between the current element and the next row, ...

Problem is here:  https://leetcode.com/problems/two-sum-less-than-k/ Given an array  A  of integers and integer  K , return the maximum  S  such that there exists  i < j  with  A[i] + A[j] = S  and  S < K . If no  i, j  exist satisfying this equation, return -1. Example 1: Input: A = [34,23,1,24,75,33,54,8] , K = 60 Output: 58 Explanation: We can use 34 and 24 to sum 58 which is less than 60. Example 2: Input: A = [10,20,30] , K = 15 Output: -1 Explanation: In this case it's not possible to get a pair sum less that 15. Note: 1 <= A.length <= 100 1 <= A[i] <= 1000 1 <= K <= 2000 The approach is to sort the array and implement the "two pointers" technique. Have a left and right pointer. Notice that if the sum surpasses (or equal to) K, the only option is to move right down. If it is less than K, check if it is the max thus far and move the left up. Do this until the poi...

Computer scientists and engineers: use more memory. It is fine. As a matter of fact, if you want to collaborate to ensure that Moore's Law (and the equivalent memory variant) remains true, then you actually have a duty to keep pushing memory (and CPU/GPU) to the next level! Memory these days is cheap - go on, and cache whatever you want. Search uses an absurd amount of caching and pre-computed data in memory. It is necessary. When you want to give the information back to the user in a blink of an eye, you have no choice but to do all the very heavy-lifting processing in the background, and "pre-cook" in memory a lot of what you want to serve the user. This is no cheating. It is technology. In-memory caching makes everyone's life easier - and faster. Here is a problem that exemplifies this concept:  https://leetcode.com/problems/range-sum-query-2d-immutable/ Given a 2D matrix  matrix , find the sum of the elements inside the rectangle defined by its upper lef...

One of the most popular interview questions - brace expansion, here it is:  https://leetcode.com/problems/brace-expansion/ A string  S  represents a list of words. Each letter in the word has 1 or more options.  If there is one option, the letter is represented as is.  If there is more than one option, then curly braces delimit the options.  For example,  "{a,b,c}"  represents options  ["a", "b", "c"] . For example,  "{a,b,c}d{e,f}"  represents the list  ["ade", "adf", "bde", "bdf", "cde", "cdf"] . Return all words that can be formed in this manner, in lexicographical order. Example 1: Input: "{a,b}c{d,e}f" Output: ["acdf","acef","bcdf","bcef"] Example 2: Input: "abcd" Output: ["abcd"] Note: 1 <= S.length <= 50 There are no nested curly brackets. All characters inside a pair...