Posts

Hard Leetcode Problem: Grid Illumination

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 ...

Hard Leetcode Problem: Number of Squareful Arrays

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 ...

Shortest Unique Prefixes, by Square

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/marcelodebarros/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 {...

Diophantine Equation and Dynamic Programming

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...

Facebook, Lagrange and Dynamic Programming

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 o...

Is 0^0 a number?

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...

Random Pick Index

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://anothercasualcoder.blogspot.com/2014/09...