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.

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)

Word 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[] sArr = s.Split(' ');

        int length = pattern?.Length ?? 0;

        if (length != sArr.Length)

        {

            return false;

        }

        var map = new Dictionary<char, string>();

        var usedWords = new HashSet<string>();

        for (int i = 0; i < length; ++i)

        {

            if (map.ContainsKey(pattern[i]))

            {

                if (map[pattern[i]] != sArr[i])

                {

                    return false;

                }

            }

            else

            {

                if (usedWords.Contains(sArr[i]))

                {

                    return false;

                }

                map[pattern[i]] = sArr[i];

                usedWords.Add(sArr[i]);

            }

        }

        return true;

    }

Complexity: O(n)

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? 

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 in C#:

    public int FindDuplicate(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length <= 1)

        {

            return -1;

        }

        int slow = nums[0], 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)

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)