Friday, September 4, 2020

[Uber] Group Anagrams

Problem: Given an array of strings strs, group the anagrams together. You can return the answer in any order. It is given that these strings have only lower case characters (a...z).

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example:

Input: strs = ["cat","tac","ten","act","net"]
Output: [["net","ten"],["act","cat","tac"]]


Approach: We can use hashing here where key is the sorted string and value is the list of corresponding words so basically we will have a loop for the strings in strs in which we will sort the string ans use it as a key and then we add this string in the list which is value of the hash. In the end all the values (lists) of the hash is our answer.

The above approach will work but it will take O (n * klogk) time where n is the number of strings in strs and k is the length of largest string in strs as we sort every string in strs. Let's try to do better; if we look at the definition anagram, we will find out that two words are anagram if they have the same characters with same number of occurrences, right?

That means if we can count the characters count efficiently, we can solve this question faster than the first approach. We will still use the hash and we will have almost same approach except the key generation of hash. We can use an array of 26 integers and then based on character count we can modify the arrays values, like in case of string "act", we will have following array:

1 | 0 | 1 | ... | 1 | 0 | ... 

0.  1  2  ...   19  (Indices)

Now the key will be as follows:

1-0-1-0-0...-1-0-0... 

So basically key will be concatenation of all the values in the above integer array separated by a '-'. That's all as all the other things will remain same.


Implementation in C#:

Approach 1 (Key generation using sorting):

        public static IList<IList<string>> GroupAnagrams(string[] strs)

        {

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

            Dictionary<string, List<string>> hash = new Dictionary<string, List<string>>();

            foreach(string str in strs)

            {

                char[] tempKey = str.ToCharArray();

                Array.Sort(tempKey);

                string key = new string(tempKey);

                if (!hash.ContainsKey(key))

                {

                    hash.Add(key, new List<string>());

                }

                hash[key].Add(str);

            }

            foreach(string key in hash.Keys)

            {

                result.Add(hash[key]);               

            }

            return result;

        }


Approach 2 (Key generation using counting):

    public IList<IList<string>> GroupAnagrams(string[] strs) 

    {

        Dictionary<string, List<string>> freqMap = new Dictionary<string, List<string>>();

        foreach (string str in strs)

        {

            string freqStr = this.GetKey(str);

            if (!freqMap.ContainsKey(freqStr))

            {

                freqMap[freqStr] = new List<string>();

            }  

            freqMap[freqStr].Add(str);  

        }

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

        foreach (string key in freqMap.Keys)

        {

            result.Add(freqMap[key]);

        }    

        return result;

    }

    

    private string GetKey(string str)

    {

        int[] freq = new int[26];        

        foreach (char ch in str)

        {

            ++freq[ch - 'a'];

        }

        StringBuilder sb = new StringBuilder();

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

        {

            sb.Append(freq[i]);

            sb.Append('-');

        }

        return sb.ToString();

    }


Complexity: Approach 1: O (n * klogk)

                     Approach 2: O (n * k)

                     Here n is the number of strings in strs and k is the length of the largest string in strs.

[LeetCode] Jump Game

Problem: You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.


Approach: We will start from the last index (length -1) and see if there is an index i from length - 2 to 0 where nums[i] + i is equal to the length - 1. That means can we reach from any index to length - 1. Once we find such good_index, now our task is to check if we can reach from any index (good_index - 1 to 0) to good_index or not. 


Implementation in C#:

    public bool CanJump(int[] nums)
    {
        int length = nums?.Length ?? 0;
        if (length <= 1)
        {
            return true;
        }
        int lastGoodPos = length - 1;
        for (int i = length - 2; i >= 0; --i)
        {
            if (i + nums[i] >= lastGoodPos)
            {
                lastGoodPos = i;
            }
        }
        return lastGoodPos == 0;
    }


Complexity: O(n)

Wildcard Matching

Problem: Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.

'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).


Approach: Use DP


        public bool IsWildCardMatch(string s, string p)

        {

            bool[,] lookup = new bool[s.Length + 1, p.Length + 1];

            lookup[0, 0] = true;

            for (int i = 1; i <= p.Length; ++i)

            {

                if (p[i - 1] == '*')

                {

                    lookup[0, i] = lookup[0, i - 1];

                }

            }

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

            {

                for (int j = 1; j <= p.Length; ++j)

                {

                    if (p[j - 1] == '*')

                    {

                        lookup[i, j] = lookup[i, j - 1] || lookup[i - 1, j];

                    }

                    else if (p[j -1] == '?' || s[i - 1] == p[j - 1])

                    {

                        lookup[i, j] = lookup[i - 1, j - 1];

                    }

                    else

                    {

                        lookup[i, j] = false;

                    }

                }

            }

            return lookup[s.Length, p.Length];

        }

[AirBnb] Combination Sum

Problem: Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Example:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.


Approach: Use backtracking.


Implementation in C#:

        public IList<IList<int>> CombinationSum(int[] candidates, int target)

        {

            IList<IList<int>> result = new List<IList<int>>();

            if (candidates == null || candidates.Length == 0)

            {

                return result;

            }

            Array.Sort(candidates);

            List<int> currResult = new List<int>();

            this.FindCombinationSumCandidates(candidates, target, result, currResult, 0);

            return result;

        }

        private void FindCombinationSumCandidates(int[] candidates, int target, IList<IList<int>> result, List<int> currResult, int currIndex)

        {

            if (target < 0)

            {

                return;

            }

            if (target == 0)

            {

                result.Add(new List<int>(currResult));

                return;

            }

            while(currIndex < candidates.Length && target - candidates[currIndex] >= 0)

            {

                currResult.Add(candidates[currIndex]);

                this.FindCombinationSumCandidates(candidates, target - candidates[currIndex], result, currResult, currIndex);

                ++currIndex;

                currResult.RemoveAt(currResult.Count - 1);

            }

        }


Complexity: O(2 ^ k) where k is is the sum of target / candidates[i] for all i = 0 to length of candidates.

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

 Approach: Use binary search 

        public int SearchInsert(int[] nums, int target)

        {

            if (nums == null)

            {

                return -1;

            }

            if (nums.Length == 0 || target < nums[0])

            {

                return 0;

            }

            else if (target > nums[nums.Length - 1])

            {

                return nums.Length;

            }

            return this.SearchInsert(nums, 0, nums.Length - 1, target);

        }


        private int SearchInsert(int[] nums, int low, int high, int target)

        {

            if (low > high)

            {

                return -1;

            }

            int mid = (low + high) / 2;

            if (nums[mid] == target || (nums[mid] > target && nums[mid - 1] < target))

            {

                return mid;

            }

            else if (nums[mid] < target)

            {

                return this.SearchInsert(nums, mid + 1, high, target);

            }

            else

            {

                return this.SearchInsert(nums, low, mid - 1, target);

            }

        }


Thursday, September 3, 2020

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

 Approach: Use binary search

        public int[] SearchRange(int[] nums, int target)

        {

            if (nums == null || nums.Length <= 0)

            {

                return new int[] { -1, -1 };

            }

            if (nums.Length == 1)

            {

                return nums[0] == target ? new int[] { 0, 0 } : new int[] { -1, -1 };

            }

            int first = this.GetFirstOccurance(nums, 0, nums.Length - 1, target);

            if (first == -1)

            {

                return new int[] { -1, -1 };

            }

            int last = this.GetLastOccurance(nums, 0, nums.Length - 1, target);

            return new int[] { first, last };

        }


        private int GetFirstOccurance(int[] nums, int low, int high, int target)

        {

            if (low > high)

            {

                return -1;

            }

            int mid = (low + high) / 2;

            if ((nums[mid] == target) && (mid == 0 || nums[mid] > nums[mid - 1]))

            {

                return mid;

            }

            else if (nums[mid] < target)

            {

                return this.GetFirstOccurance(nums, mid + 1, high, target);

            }

            else

            {

                return this.GetFirstOccurance(nums, low, mid - 1, target);

            }

        }


        private int GetLastOccurance(int[] nums, int low, int high, int target)

        {

            if (low > high)

            {

                return -1;

            }

            int mid = (low + high) / 2;

            if ((nums[mid] == target) && (mid == nums.Length - 1 || nums[mid] < nums[mid + 1]))

            {

                return mid;

            }

            else if (nums[mid] > target)

            {

                return this.GetLastOccurance(nums, low, mid - 1, target);

            }

            else

            {

                return this.GetLastOccurance(nums, mid + 1, high, target);

            }

        }

Longest Valid Parentheses

Problem: Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Solution:

        public static int LongestValidParentheses(string s)

        {

            Stack<int> stack = new Stack<int>();

            stack.Push(-1);

            int result = 0;

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

            {

                if (s[i] == '(')

                {

                    stack.Push(i);

                }

                else

                {

                    stack.Pop();

                    if (stack.Count > 0)

                    {

                        result = Math.Max(result, i - stack.Peek());

                    }

                    else

                    {

                        stack.Push(i);

                    }

                }

            }


            return result;

        }