Boris Coding Blog

Here is the problem:  https://leetcode.com/problems/grid-illumination/ On a  N x N  grid of cells, each cell  (x, y)  with  0 <= x < N  and  0 <= y < N  has a lamp. Initially, some number of lamps are on.   lamps[i]  tells us the location of the  i -th lamp that is on.  Each lamp that is on illuminates every square on its x-axis, y-axis, and both diagonals ( similar to a Queen in chess ). For the i-th query  queries[i] = (x, y) , the answer to the query is 1 if the cell (x, y) is illuminated, else 0. After each query  (x, y)  [in the order given by  queries ], we turn off any lamps that are at cell  (x, y)  or are adjacent 8-directionally (ie., share a corner or edge with cell  (x, y) .) Return an array of answers.  Each value  answer[i]  should be equal to the answer of the  i -th query  queries[i] . Example 1: Input: N = 5 , lamps = [[0,0],[4,4]] , queries = [[1,1],[1,0]] Output: [1,0] Explanation: Before performing the first query we have both lamps [0

Here is a hard Leetcode problem:  https://leetcode.com/problems/number-of-squareful-arrays/description/ Given an array  A  of non-negative integers, the array is  squareful  if for every pair of adjacent elements, their sum is a perfect square. Return the number of permutations of A that are squareful.  Two permutations  A1  and  A2  differ if and only if there is some index  i such that  A1[i] != A2[i] . Example 1: Input: [1,17,8] Output: 2 Explanation: [1,8,17] and [17,8,1] are the valid permutations. Example 2: Input: [2,2,2] Output: 1 Note: 1 <= A.length <= 12 0 <= A[i] <= 1e9 The array length is very small (12), which allows us to think about a brute-force solution, which is what's done on the post, but I'm sure there is a DP solution too. The brute-force solution goes like this: Pre-compute a hash table with the A[i]+A[j] that are perfect square. Do this in 144 steps (fast) Do a DFS but only calling recursively when the conditi

Here is the problem, powered by Daily Coding Problem : This problem was asked by Square. Given a list of words, return the shortest unique prefix of each word. For example, given the list: dog cat apple apricot fish Return the list: d c app apr f The solution can be done in linear time by using a Trie  using the following strategy: Create a trie using Hash Tables but each element has a count of how many times it has been seen Add all the words to the trie When you're done, parse the trie looking for the nodes that have count equals to 1. It means that it is a unique prefix. Print it Code is below and also on Github, right here:  https://github.com/BorisVasilenko/dailycodingproblem/blob/master/DailyCodingProblem02232019.cs . Cheers, ACC. using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Collections; namespace DailyCodingProblem { class DailyCodingProblem02232019 { pu

Diophantine Equations (DE) are polynomial equations with only integer solutions, in particular there is the linear Diophantine Equations:  https://www.bing.com/search?q=linear%20diophantine%20equation Related to DE, a nice programming problem is the following: suppose that you're given four numbers {N, A, B, C}, where all these numbers are non-zero positive integers. You can build a DE in the following way: c1*A + c2*B + c3*C = N Where the coefficients c1, c2 and c3 are all integers greater than or equal to zero. Now there may exist zero or more solutions to this problem. For example, for {N, A, B, C} = {22, 2, 3, 5}, two solutions would be: 11*2 + 0*3 + 0*5 = 22 1*2 + 0*3 + 4*5 = 22 If you add up the coefficients of the first solution you get 11. The sum of the coefficients for the second solution is 5. What the problem will be asking is the following: "For all the possible solution to this DE, find the one where the sum of its coefficients is minimi

What does Facebook, Lagrange and Dynamic Programming have in common? Well, they come up together in a technical interview question, by Daily Coding Problem : Good morning! Here's your coding interview problem for today. This problem was asked by Facebook . Given a positive integer  n , find the smallest number of squared integers which sum to  n . For example, given  n  = 13, return 2 since 13 = 3 2  + 2 2  = 9 + 4. Given  n  = 27, return 3 since 27 = 3 2  + 3 2  + 3 2  = 9 + 9 + 9. There is actually a theorem about this problem: any positive number can be expressed as the sum of four integer squares - it is called the Lagrange's Four-Square Theorem : Lagrange's four-square theorem Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number can be represented as the sum of four integer squares. But we can go one step beyond that and try to solve the problem not only for the power of two (square),

It is believed that 0^0 is undefined. One way to think about it is that whenever you have X^0, you'll get 1, but 0^X and you'' get 0, hence as you can see the function kind of “alternates” with no clear convergence.  What if we write a simple program to show that? We’ll have a function F(X) = X^X, and we can vary X from say 0.9 all the way to smaller numbers in decrements of 0.001. At each step we’ll calculate F(X). We’ll take, say, 900 of those points.  What we’re doing is simulating Lim(x->0) x^x . If X^X converges, we should see a straight line, either approaching zero, or approaching one. The chart, however, is intriguing: It starts by coming down nicely towards zero (hence we might have guessed that 0^0 goes to 0), however and intriguingly it eventually takes off in the opposite direction towards 1!  By no means this is any proof that 0^0 won’t converge, but computationally it is not looking promising that 0^0 reaches the end of the t

Problem:  https://leetcode.com/problems/random-pick-index/description/ Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array. Note: The array size can be very large. Solution that uses too much extra space will not pass the judge. Example: int[] nums = new int[] {1,2,3,3,3}; Solution solution = new Solution(nums); // pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning. solution.pick(3); // pick(1) should return 0. Since in the array only nums[0] is equal to 1. solution.pick(1); The solution uses the same idea as presented few years back on how to retrieve a random line from a file (which btw, this is a technique that sometimes I still use at work, whenever dealing with massive files, which is usually the norm around here), check out the post:  https://dreaktor.com/2014/09/a-random

Problem:  https://leetcode.com/problems/add-to-array-form-of-integer/description/ For a non-negative integer  X , the  array-form of  X  is an array of its digits in left to right order.  For example, if  X = 1231 , then the array form is  [1,2,3,1] . Given the array-form  A  of a non-negative integer  X , return the array-form of the integer  X+K . Example 1: Input: A = [1,2,0,0] , K = 34 Output: [1,2,3,4] Explanation: 1200 + 34 = 1234 Example 2: Input: A = [2,7,4] , K = 181 Output: [4,5,5] Explanation: 274 + 181 = 455 Example 3: Input: A = [2,1,5] , K = 806 Output: [1,0,2,1] Explanation: 215 + 806 = 1021 Example 4: Input: A = [9,9,9,9,9,9,9,9,9,9] , K = 1 Output: [1,0,0,0,0,0,0,0,0,0,0] Explanation: 9999999999 + 1 = 10000000000 Note： 1 <= A.length <= 10000 0 <= A[i] <= 9 0 <= K <= 10000 If  A.length > 1 , then  A[0] != 0 Key is to use list manipulations in your preferred language, in my case, C#. Below, thx, ACC.

Simple problem:  https://leetcode.com/problems/powerful-integers/description/ Given two non-negative integers  x  and  y , an integer is  powerful  if it is equal to  x^i + y^j  for some integers  i >= 0  and  j >= 0 . Return a list of all  powerful  integers that have value less than or equal to  bound . You may return the answer in any order.  In your answer, each value should occur at most once. Example 1: Input: x = 2 , y = 3 , bound = 10 Output: [2,3,4,5,7,9,10] Explanation: 2 = 2^0 + 3^0 3 = 2^1 + 3^0 4 = 2^0 + 3^1 5 = 2^1 + 3^1 7 = 2^2 + 3^1 9 = 2^3 + 3^0 10 = 2^0 + 3^2 Example 2: Input: x = 3 , y = 5 , bound = 15 Output: [2,4,6,8,10,14] Note: 1 <= x <= 100 1 <= y <= 100 0 <= bound <= 10^6 Code will run in up to 10^6, which is fine. Do a sieves-style, avoid Math.Pow, hash-table the solution to avoid dupes, handle cases when the input is 1 (special), other than that, two nested loops ought to do it. Thanks, ACC. publ

Love this kind of tree problem:  https://leetcode.com/problems/binary-tree-pruning/description/ We are given the head node  root  of a binary tree, where additionally every node's value is either a 0 or a 1. Return the same tree where every subtree (of the given tree) not containing a 1 has been removed. (Recall that the subtree of a node X is X, plus every node that is a descendant of X.) Example 1: Input: [1,null,0,0,1] Output: [1,null,0,null,1] Explanation: Only the red nodes satisfy the property "every subtree not containing a 1". The diagram on the right represents the answer. Example 2: Input: [1,0,1,0,0,0,1] Output: [1,null,1,null,1] Example 3: Input: [1,1,0,1,1,0,1,0] Output: [1,1,0,1,1,null,1] Note: The binary tree will have at most  100 nodes . The value of each node will only be  0  or  1 . Simple recursion: Use post-order traversal (either left-right-parent or right-left-parent) Use a ref variable t o indicate whether the

Loved this question!  https://leetcode.com/problems/sort-list/description/ Sort a linked list in  O ( n  log  n ) time using constant space complexity. Example 1: Input: 4->2->1->3 Output: 1->2->3->4 Example 2: Input: -1->5->3->4->0 Output: -1->0->3->4->5 It requires a little fundamentals of Sorting: if you use QuickSort , which is the best sorting algorithm on average, you won't be able to guarantee O(NLogN) for all the cases since in the worst case scenario QuickSort performs in O(N^2)-time. If you want to guarantee O(NLogN), you'll need to select a different method. One that is guaranteed O(NLogN) for all the cases is MergeSort , although it comes with a stack overhead hence not preferred in real applications. But that's what I'm going to use here: MergeSort. The approach for MergeSort in a nutshell is the following: Handle the base cases when the list has zero, one or two elements Split the list into 2.

Problem:  https://leetcode.com/problems/binary-tree-right-side-view/description/ Given a binary tree, imagine yourself standing on the  right  side of it, return the values of the nodes you can see ordered from top to bottom. Example: Input:  [1,2,3,null,5,null,4] Output:  [1, 3, 4] Explanation: 1 <--- / \ 2 3 <--- \ \ 5 4 <--- Problem is interesting since you can't really do a DFS otherwise you'll miss some of the far left nodes that need to be in the result list. Notice that all the problem is asking is return the last element for each level of the tree . Level by level: BFS using a queue. Solution is below, thanks, ACC. public class Solution { public IList RightSideView(TreeNode root) { if (root == null) return new List (); QueueItem qi = new QueueItem(root, 0); Queue queue = new Queue(); queue.Enqueue(qi); int lastLevel = -1; int lastVal = root.val; List retVal = new List (); whil

https://leetcode.com/problems/word-search/description/ Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. Example: board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] Given word = " ABCCED ", return true . Given word = " SEE ", return true . Given word = " ABCB ", return false . DFS should do it, below, cheers, ACC. public class Solution { public bool Exist(char[,] board, string word) { if (String.IsNullOrEmpty(word)) return true; for (int r = 0; r < board.GetLength(0); r++) { for (int c = 0; c < board.GetLength(1); c++) { if (board[r, c] == word[0]) { Hashtable visited =

Problem is here:  https://leetcode.com/problems/longest-valid-parentheses/description/ Given a string containing just the characters  '('  and  ')' , find the length of the longest valid (well-formed) parentheses substring. Example 1: Input: "(()" Output: 2 Explanation: The longest valid parentheses substring is "()" Example 2: Input: " )()()) " Output: 4 Explanation: The longest valid parentheses substring is "()()" My solution isn't the best, but it passes with an N^2-time complexity: two tested loops, looking for the best solution starting at the outer-loop index, optimizing whenever we end up at an invalid substring. If you look at the official solution, you'll find very lean and elegant DP solutions for this problem. Sometimes if you can't find the best solution, at least find a better solution than the worst-case (in our case, N^3). Cheers, ACC. public class Solution { public int LongestVal