Friday, November 27, 2020

[Google Question][LeetCode] Additive Number

Problem: Additive number is a string whose digits can form additive sequence. A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two. 

Given a string containing only digits, write a method to check if input string is an additive number. Please note that numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Example:

Input: "1235813"
Output: true
Explanation: The digits can form an additive sequence: 1, 2, 3, 5, 8, 13. 
             1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8, 5 + 8 = 13


Approach: The problem can be solved using recursion. Basically what we want to do is choose the starting two numbers which can form additive sequence so we we will choose 2 starting number say num1 and num2 as 1 by 1 of every length possible and see if selecting them as starting numbers are forming additive sequence.

In the method we will see if sum of num1 and num2 is a prefix of rest of the string. If yes, then we can call the method recursively by taking first number as num2 and second number as sum of num1 and num2 and rest of the string as third argument(excluding sum). 

If anywhere we find that current sum is not a prefix of remaining string then we return false. We continue to call the method recursively till we reach to the end that means remaining string become empty.

At any point we find a solution we return true. We can be smart about choosing the numbers as length of sum of two numbers can't be less than any of the operand's (number) length so we can loop till (length of string)/2 for first number and (length of string – first number’s length)/ 2 for second number to ignore invalid result.


Implementation in C#:

        public static bool IsAdditiveNumber(string num)

        {

            if (num?.Length < 3)

            {

                return false;

            }

            int length = num.Length;

            for (int i = 1; i <= length / 2; ++i)

            {

                for (int j = 1; j <= (length - i) / 2; ++j)

                {

                    if (IsAdditiveSequence(num.Substring(0, i), num.Substring(i, j), num.Substring(i + j)))

                    {

                        return true;

                    }

                }

            }

            return false;

        }


        private static bool IsAdditiveSequence(string str1, string str2, string remainingString)

        {

            if (!IsValid(str1) || !IsValid(str2))

            {

                return false;

            }

            if (remainingString == string.Empty)

            {

                return true;

            }

            long num1 = long.Parse(str1);

            long num2 = long.Parse(str2);

            string currSum = (num1 + num2).ToString();

            if (remainingString.Length < currSum.Length || remainingString.Substring(0, currSum.Length) != currSum)

            {

                return false;

            }

            return IsAdditiveSequence(str2, currSum, remainingString.Substring(currSum.Length));

        }


        private static bool IsValid(string str)

        {

            if(str.Length > 1 && str[0] == '0')

            {

                return false;

            }

            return true;

        }


Complexity: O(n^3)

Friday, November 20, 2020

Range Sum Query 2D

Problem: Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). Implement the NumMatrix class:

  1. NumMatrix(int[][] matrix) Initializes the object with the 2D integer array matrix.
  2. int SumRegion(int row1, int col1, int row2, int col2) Return the sum of the elements of the matrix  in the region where (row1, col1) is left top corner and (row2, col2) is the right bottom corner so you can safely assume row1 <= row2 and col1 <= col2.

Example:

Given matrix = [
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12],
  [13, 14, 15, 16]
]

SumRegion(1, 1, 2, 2) -> 34 (6 + 7 + 10 + 11 = 34)
SumRegion(0, 0, 2, 1) -> 33 (1 + 2 + 5 + 6 + 9 + 10 = 33)


Approach: One obvious approach is to save input matrix as is and in SumRegion method we can iterate through every element of the input region and return the sum. This will work but SumRegion will take O(m*n) time. We need to optimize it.

Another approach is we can use the approach of previous problem Range Sum Query (1D array). We can treat each row as separate array. The same precomputation and SumRange method can be applied on each and every row and then we can take the sum of all the rows(arrays) and return. It will take O(n) time which is way better than the brute force approach. Can we optimize it further? Let's see how:

We can precompute a cumulative region sum with respect to the origin at (0, 0). That means we can have a matrix say SumMatrix where SumMatrix[i][j] will have the sum of every element in the region with (0, 0) as left top corner and (i, j) as right bottom corner. In simple language:

SumMatrix[i][j] = Sum of all InputMatrix[x][y] where 0 <= x <= i and 0 <= y <= j

If we use pencil and paper and calculate cumulative sum in this way we will find out that:

SumMatrix[i][j] = SumMatrix[i][j-1] + SumMatrix[i-1][j] + InputMatrix[i][j] - SumMatrix[i-1][j-1]

Let's visualize it using an example. Take the example from the description:


Now let's see how we can calculate SumMatrix[1][1]:


If you see to calculate SumMatrix[1][1] we need sum of region (0,0) to (0, 1) that is SumMatrix[0][1] and region (0, 0) to (1, 0) that is SumMatrix[1][0] and current element. But If you see in this sum SumMatrix[0][0] came 2 times so we need to subtract it. That means:

SumMatrix[1][1] = SumMatrix[1][0] + SumMatrix[0][1] + InputMatrix[1][1] - SumMatrix[0][0]

If you see the above calculation, it matches with the statement I have given to calculate SumMatrix[i][j].

Now Let's see how we can calculate sum of the input region efficiently. Here is the calculated SumMatrix for the given example:


Say we want to calculate sum of the region (1, 1) to (2, 2):


Here is how we can calculate it:

Here is the sum of region (0, 0) to (2, 2) which is SumMatrix[2][2]:


But we don't want this. We actually want the following:


So looking at the picture we can say our target sum will be:

Sum of Region (0, 0) to (2, 2) - Sum of Region (0, 0) to (0, 2) - Sum of Region (0,0) to (2, 0) + Sum of Region (0, 0) to (0, 0) 

= SumMatrix[2][2] - SumMatrix[0][2] - SumMatrix[2][0] + SumMatrix[0][0]

We are adding Sum of region (0, 0) to (0, 0) as if you see we are subtracting it twice with (0, 0) to (0, 2) and (0, 0) to (2, 0). Now let's drive the formula by looking at it

Sum of region (r1, c1) to (r2, c2) = SumMatrix[r2][c2] - SumMatrix[r1-1][c2] - SumMatrix[r2][c1-1] + SumMatrix[r1-1][c1-1]

That's all. Hopefully you could understand the approach easily.


Implementation in C#:

    public class NumMatrix

    {
        public NumMatrix(int[][] matrix)
        {
            if (matrix.Length > 0 && matrix[0].Length > 0)
            {
                this.sumMatrix = new int[matrix.Length + 1, matrix[0].Length + 1];

                for (int i = 1; i < this.sumMatrix.GetLength(0); ++i)
                {
                    for (int j = 1; j < this.sumMatrix.GetLength(1); ++j)
                    {
                        this.sumMatrix[i, j] = this.sumMatrix[i, j - 1] + this.sumMatrix[i - 1, j] + matrix[i - 1][j - 1] - this.sumMatrix[i - 1, j - 1];
                    }
                }
            }
        }

        public int SumRegion(int row1, int col1, int row2, int col2)
        {
            if (this.sumMatrix == null)
            {
                return 0;
            }
            if (row1 == 0 && col1 == 0)
            {
                return this.sumMatrix[row2 + 1, col2 + 1];
            }
            

            return this.sumMatrix[row2 + 1, col2 + 1] - this.sumMatrix[row1, col2 + 1] - this.sumMatrix[row2 + 1, col1] + this.sumMatrix[row1, col1];
        }

        private int[,] sumMatrix;
    }

Complexity: O(m*n) for precomputation and O(1) for SumRegion.

Range Sum Query

Problem: Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. Implement the NumArray class:

  1. NumArray(int[] nums) Initializes the object with the integer array nums.
  2. int sumRange(int i, int j) Return the sum of the elements of the nums array in the range [i, j] inclusive (i.e., sum(nums[i], nums[i + 1], ... , nums[j]))
Example:

Input
Array = [1, 2, 3, 4]
SumRange(1, 2) SumRange(1, 3) Output 5 9 Explanation NumArray numArray = new NumArray([1, 2, 3, 4]); numArray.SumRange(1, 2); // return 5 (2 + 3) numArray.SumRange(1, 3); // return 9 (2 + 3 + 4)

Approach: We can save the input array as it is and then whenever SumRange method is called. We can do the following:
  • sum = 0
  • For itr = i To j
    • sum += array[itr]
  • return sum
But then each SumRange call will take O(n) time. Let's see how we can make it better; Instead of saving the input array as it is what we can do is we can save the cumulative sum. That means we can have a array say "Sums" where Sums[i] will contain the cumulative sum of elements from [0...i] of input array:

Sums[i] = arr[0] + arr[1] + arr[2] + ... + arr[i]

Once we saved this array. SumRange(i, j) will be very simple to implement:
  • IF i == 0 THEN return Sums[j]
  • ELSE return Sums[j] - Sums[i - 1]
That's it!


Implementation in C#:

    public class NumArray
    {
        public NumArray(int[] nums)
        {
            if (nums?.Length > 0)
            {
                this.sums = new int[nums.Length];
                if (nums.Length > 0)
                    this.sums[0] = nums[0];
                for (int i = 1; i < nums.Length; ++i)
                {
                    this.sums[i] = this.sums[i - 1] + nums[i];
                }
            }
        }

        public int SumRange(int i, int j)
        {
            if (this.sums?.Length <= 0)
            {
                return 0;
            }

            return i == 0 ? this.sums[j] : this.sums[j] - this.sums[i - 1];
        }

        private int[] sums;
    }


Complexity: O(n) for constructor and O(1) for SumRange

Thursday, November 19, 2020

Remove Invalid Parentheses

Problem: Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Example(Taken from leetcode):

Input: "()())()"
Output: ["()()()", "(())()"]


Approach: It looks like a backtracking problem(removing 1,2,3....n parenthesis and check if they are valid strings or not).

We can use BFS to optimize it. We can say str1 and str2 are connected if removing one parentheses from str1 forms str2. If we form a graph in this way and while traversing (BFS), at a particular level we find that a valid string is found then we add it to our result and also now we know that we don't need to move to next level as we want to remove minimum number of parenthesis to make string valid. 


Implementation in C#:

        public static IList<string> RemoveInvalidParentheses(string s)

        {

            if (string.IsNullOrWhiteSpace(s))

            {

                return new List<string>();

            }

            List<string> result = new List<string>();

            // BFS

            HashSet<string> visited = new HashSet<string>();

            Queue<string> queue = new Queue<string>();

            queue.Enqueue(s);

            visited.Add(s);

            // If we find valid string, we don't need to go to next level.

            bool goToNextLevel = true;

            while(queue.Count > 0)

            {

                s = queue.Dequeue();

                if (IsStringContainsValidParentheses(s))

                {

                    result.Add(s);

                    goToNextLevel = false;

                }

                if (!goToNextLevel)

                {

                    continue;

                }

                for (int i = 0; i < s.Length; ++i)

                {

                    if (!IsParentheses(s[i]))

                    {

                        continue;

                    }

                    string subStr = s.Substring(0, i) + s.Substring(i + 1);

                    if (!visited.Contains(subStr))

                    {

                        queue.Enqueue(subStr);

                        visited.Add(subStr);

                    }

                }

            }

            return result;

        }


        private static bool IsParentheses(char ch)

        {

            return ch == '(' || ch == ')';

        }


        private static bool IsStringContainsValidParentheses(string s)

        {

            int countParentheses = 0;

            foreach(char ch in s)

            {

                if (ch == '(')

                {

                    ++countParentheses;

                }

                else if (ch == ')')

                {

                    --countParentheses;

                }

                if (countParentheses < 0)

                {

                    return false;

                }

            }

            return countParentheses == 0;

        }


Complexity: O(N * 2 ^ N)

Wednesday, November 11, 2020

Bulls and Cows Game

Problem: Two players are playing the Bulls and Cows game. Game's rules are as follows:

Player 1 write down a secret number and asks Player 2 to guess what the number is. When Player 2 makes a guess, Player 1 provides a hint with the following info:

  1. The number of "bulls", which are digits in the guess that are in the correct position.
  2. The number of "cows", which are digits in the guess that are in your secret number but are located in the wrong position. Specifically, the non-bull digits in the guess that could be rearranged such that they become bulls.

Given the Player 1's secret number and Player 2's guess, return the hint which Player 1 will provide to Player 2. The hint should be formatted as "BullsCountACowsCountB", where BullsCount is the number of bulls and CowsCount is the number of cows. 

Example:

Input: secret = "011", guess = "110"
Output: "1A2B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"011"
  |
"110"


Approach: Using hash it can be solved easily. Approach can be understood by just looking at the code.


Implementation in C#:

        public static string GetHint(string secret, string guess)

        {

            int bulls = 0;

            int cows = 0;

            int[] hash = new int[10];

            for(int i = 0; i < secret.Length; ++i)

            {

                if (i < guess.Length && secret[i] == guess[i])

                {

                    ++bulls;

                }

                ++hash[secret[i] - '0'];

            }

            for (int i = 0; i < guess.Length; ++i)

            {

                if (hash[guess[i] - '0'] > 0)

                {

                    --hash[guess[i] - '0'];

                    ++cows;

                }

            }

            // At this point number of cows will also include number of bulls so subtracting it

            cows -= bulls;

            return $"{bulls}A{cows}B";

        }


Complexity: O(n)

Longest Consecutive Sequence in Binary Tree

Problem: Given a Binary Tree find the length of the longest path which comprises of nodes with consecutive values in increasing order. Every node is considered as a path of length 1.

Example:

Input:
   1
    \
     6
    / \
   2   7
        \
         8
Output:3
Explanation: Longest consecutive sequence path is 6-7-8.


Approach: Using Preorder traversal. Basically we will maintain two parameters in the recursive calls; one current sequence length say current_length and maximum sequence length say maximum_length. The names of the parameters itself tell what they are storing. 

Another parameter is expected_value which will tell what should be the value of current node's value in order to decide whether its consecutive sequence or not so if we find current node's value is expected_value then we will increment current_length otherwise current_length will be assigned back to 1 as this could be start of a new consecutive sequence. Off course if we find current_length is greater than maximum_length then current_length will be assigned to maximum_length.

For each recursive call we will assign expected_value to 1 + value of current node. In the end maximum_length will be our answer.

 

Implementation in C#:

        public int LongestConsecutiveSequence()

        {

            if (this.Root == null)

            {

                return 0;

            }

            int result = 0;

            this.LongestConsecutiveSequence(this.Root, this.Root.Value, 0, ref result);

            return result;

        }


        private void LongestConsecutiveSequence(BinaryTreeNode node, int expectedValue, int currLength, ref int maxLength)

        {

            if (node == null)

            {

                return;

            }

            currLength = node.Value == expectedValue ? currLength + 1 : 1;

            maxLength = Math.Max(currLength, maxLength);

            this.LongestConsecutiveSequence(node.LeftNode, node.Value + 1, currLength, ref maxLength);

            this.LongestConsecutiveSequence(node.RightNode, node.Value + 1, currLength, ref maxLength);

        }


Complexity: O(n)

Serialize and Deserialize Binary Tree

Problem: Design an algorithm to serialize and deserialize a binary tree. Basically we need to ensure that a binary tree can be serialized to a string and this string can be deserialized back to the original tree structure.


Approach: In general we have seen that we can make binary tree using inorder and one of preorder or postorder traversal. A single traversal is not enough to make a tree back so what we can do is we can store both traversals' output (inorder and preorder) in a string while serializing and while deserializing we can use both traversals' output to build the original tree back.

The above approach will surely work but in the end we are going to need 2*N space and we are storing two traversals' output. Let's try to do better. We can use PreOrder traversal with some marker for NULL nodes. Basically while doing preorder traversal if we find a node is null then we store a marker say '$' in the serialization output and while doing deserialization if we see a '$', we can return NULL immediately.  That's all!


Implementation in C#:

        // Serialization of binary tree

        public string Serialize()

        {

            if (this.Root == null)

            {

                return string.Empty;

            }

            List<string> result = this.Serialize(this.Root);

            return string.Join('|', result);

        }


        private List<string> Serialize(BinaryTreeNode node)

        {

            List<string> result = new List<string>();

            if (node == null)

            {

                result.Add("$");

            }

            else

            {

                result.Add(node.Value.ToString());

                result.AddRange(this.Serialize(node.LeftNode));

                result.AddRange(this.Serialize(node.RightNode));

            }

            return result;

        }

        

        // Deserialization of binary tree

        public void Deserialize(string data)

        {

            if (string.IsNullOrWhiteSpace(data))

            {

                this.Root = null;

                return;

            }

            int currIndex = 0;

            this.Root = this.Deserialize(data.Split('|'), ref currIndex);

        }


        private BinaryTreeNode Deserialize(string[] data, ref int currIndex)

        {

            if (data[currIndex] == "$")

            {

                return null;

            }

            BinaryTreeNode node = new BinaryTreeNode(int.Parse(data[currIndex]));

            ++currIndex;

            node.LeftNode = this.Deserialize(data, ref currIndex);

            ++currIndex;

            node.RightNode = this.Deserialize(data, ref currIndex);

            return node;

        }


Complexity: O(n) for both serialize and deserialize operations.

Monday, November 9, 2020

Nim Game

Problem: Two players are playing the following Nim Game:

  • Initially, there is a heap of stones on the table.
  • Both players will alternate taking turns, and Player 1 go first.
  • On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.
  • The one who removes the last stone is the winner.

Given n, the number of stones in the heap, return true if Player (1) who started the game, can win the game assuming both players play optimally, otherwise return false.

Example:

Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. P1 removes 1 stone. P2 removes all the remaining (4 - 1 =) 3 stones. P2 wins.
2. P1 removes 2 stones. P2 removes all the remaining (4 - 2 =) 2 stones. P2 wins.
3. P1 removes 3 stones. P2 removes the last (4 - 3 =) 1 stone. P2 wins.
In all outcomes, P2 wins.


Approach: If you look at the above example closely, you will understand Player 2 will only win if n is a multiple of 4. Otherwise Player 1 can always win as he/she can always leave 4 stones on the table in the second last turn.


Implementation in C#:

        public bool CanWinNim(int n) 

        {

            return n % 4 != 0;

        }


Complexity: O(1)

Given a pattern and a string, find if input string follows the same pattern

Problem: Following the pattern means a full match, such that there is a bijection between a letter in pattern and a non-empty word in the input string.

Example:

Input: pattern = "abba", s = "cat rat rat cat"
Output: true


Approach: We can use hashing here. We can maintain a hash where key is the character is pattern and value is word in s. Whenever a we encounter a new character, we can add it in to the hash as key and corresponding word as value. if we get a character which is already in hash then we can check if the corresponding value in the hash and the current word are same or not, if they are not same then we will return false immediately.

The approach looks good and also works on examples like given in the problem description but It won't work on inputs like [pattern = "abba", s = "cat cat cat cat"].  Here if you see by going with above approach we will return true and the actual answer is false.

What we can do in such cases? We can maintain a reverse hash with key as word and value as character to just reverify if the current word is already a value for a different character in the pattern.  

This will solve our whole problem.


Implementation in C#:

        public bool WordPattern(string pattern, string s)
        {
            string[] words = s.Split(' ');

            if (pattern.Length != words.Length)
            {
                return false;
            }

            Dictionary<char, string> charToWordMap = new Dictionary<char, string>();
            HashSet<string> appearedWordsSet = new HashSet<string>();

            for (int i = 0; i < pattern.Length; ++i)
            {
                if (charToWordMap.ContainsKey(pattern[i]))
                {
                    if (charToWordMap[pattern[i]] != words[i])
                    {
                        return false;
                    }
                }
                else
                {
                    if (appearedWordsSet.Contains(words[i]))
                    {
                        return false;
                    }

                    charToWordMap.Add(pattern[i], words[i]);
                    appearedWordsSet.Add(words[i]);
                }
            }

            return true;
        }


Complexity: O(n)

Friday, November 6, 2020

Find the Duplicate Number

Problem: Given an array of integers containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one duplicate number in the given array, return this duplicate number.

Example:

Input: nums = [3, 1, 3, 4, 2, 3]
Output: 3


Approach: Please note that the duplicate number can appear any number (> 1) of times so if you are thinking of XOR approach, just stop there. Now see what are the other obvious approaches:

  1. Sorting - Will work but the Time complexity will be O(nlogn)
  2. Hash - Will work and solve the problem in O(n) only but will take the space at least O(n).
Both the above approaches can solve this and the complexities are not bad but can we do better? Yes! How? 

Let's look at the problem differently. If you see there is a cycle here because of duplicate number. Just like linked list If I defined node -> next as array[currentValue] then if you traverse in this way, you will see there is a cycle exist in the input array itself. Lets take the above example:

  • currNum = array[0] = 3
  • currNum = array[currNum] = array[3] = 4
  • currNum = array[currNum] = array[4] = 2
  • currNum = array[currNum] = array[2] = 3 (This is the starting point of  cycle)
Now we can use the same approach which we used in finding loop in Linked List to solve this problem. Here is the basic of this algorithm:
  • slow = array[slow]
  • fast = array[array[fast]]
That's all!

Implementation:

        public int FindDuplicate(int[] nums)

        {

            int slow = nums[0];

            int fast = nums[0];

            do

            {

                slow = nums[slow];

                fast = nums[nums[fast]];

            } while (slow != fast);

            slow = nums[0];

            while(slow != fast)

            {

                slow = nums[slow];

                fast = nums[fast];

            }

            return slow;

        }


Complexity: O(n)

Sunday, November 1, 2020

First Bad Version

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

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API. (Question is taken from LeetCode)


Approach: Its like finding an element in a sorted array. We can use binary search here.


Implementation in C#:

        public int FirstBadVersion(int n)

        {

            int start = 1, end = n;

            while (start <= end)

            {

                int mid = start + (end - start) / 2; // To avoid overflow

                if (IsBadVersion(mid) && (mid == 1 || !IsBadVersion(mid - 1)))

                {

                    return mid;

                }

                else if (IsBadVersion(mid))

                {

                    end = mid - 1;

                }

                else

                {

                    start = mid + 1;

                }

            }

            return -1;

        }


Complexity: O(logn)