Thursday, September 3, 2020

[Microsoft][LeetCode] Next Permutation

Problem: A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

  • For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

  • For example, the next permutation of arr = [1,2,3] is [1,3,2].
  • Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
  • While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Example:

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

Approach: The approach which we are using here is mention on wikipedia. Here are the steps:

  • Find the first number which is not in descending order. say at index i
  • Find the number which is just bigger than the number found at step 1. Say at index j. Swap arr[i] and arr[j].
  • Reverse the array from i + 1 to array's length.


Implementation in C#:

    public void NextPermutation(int[] nums)
    {
        int length = nums?.Length ?? 0;
        if (length <= 1)
        {
            return;
        }
        int i = length - 1;
        while (i > 0 && nums[i] <= nums[i - 1])
        {
            i--;
        }
        if (i > 0)
        {
            int j = length - 1;
            while (j > i - 1 && nums[i - 1] >= nums[j])
            {
                --j;
            }
            this.Swap(nums, i - 1, j);
        }
        this.Reverse(nums, i);
    }

    private void Swap(int[] nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void Reverse(int[] nums, int start)
    {
        int end = nums.Length - 1;
        while (start < end)
        {
            this.Swap(nums, start++, end--);
        }
    }


Complexity: O(n)

You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

 Approach: Use hash


        public IList<int> FindSubstringWithConcatenation(string s, string[] words)

        {

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

            int numOfWords = words.Length;

            int sizeOfWord = words[0].Length;

            int sizeOfWords = sizeOfWord * numOfWords;

            if (s.Length < sizeOfWords)

            {

                return result;

            }

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

            foreach(string word in words)

            {

                if (hash.ContainsKey(word))

                {

                    ++hash[word];

                }

                else

                {

                    hash[word] = 1;

                }

            }


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

            {

                Dictionary<string, int> tempHash = new Dictionary<string, int>(hash);

                int count = numOfWords;

                for(int j = i; j < i + sizeOfWords; j+= sizeOfWord)

                {

                    string str = s.Substring(j, sizeOfWord);

                    if (!tempHash.ContainsKey(str) || tempHash[str] == 0)

                    {

                        break;

                    }

                    --tempHash[str];

                    --count;

                }


                if(count == 0)

                {

                    result.Add(i);

                }

            }


            return result;

        }

Given a linked list, remove the n-th node from the end of list.

Note: Condition was given that n will always be valid.

Approach: Use two pointers.

Implementation in C#:

        public void RemoveNthFromEnd(int n)

        {

            LinkedListNode first = this.Head, second = this.Head;

            for (int i = 1; i <= n; ++i)

            {

                second = second.Next;

                if (second == null)

                {

                    this.Head = this.Head.Next;

                    return;

                }

            }

            while (second.Next != null)

            {

                first = first.Next;

                second = second.Next;

            }

            first.Next = first.Next.Next;

        }

Complexity: O(n)

Wednesday, September 2, 2020

[Uber][LeetCode] Regular Expression Matching

Problem: Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

  • '.' Matches any single character.​​​​
  • '*' Matches zero or more of the preceding element.

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

Example:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".


Approach: Use DP. Have a table [s.Length + 1][p.Length + 1] where table[i][j] indicates s(0..i-1) is a match of pattern p(0...j-1). Once we fill this we need to return table[s.Length][p.Length]. Here is how to fill this table - 

  1. If pattern and string both are null then its a match so table[0][0] is always true.
  2. If pattern is null (p.Length = 0) then its a mismatch so table[i][0] = false for i = 1...s.Length.
  3. If string is null then table[0][j] can be true only if pattern has p[j - 1] = '*' and table[0, j - 2] is true for j = 1...p.Length
  4. table[i][j] = table[i-1][j-1] if current pattern character i.e. p[j - 1] is either . or match with current char of string i.e. s[i-1]
  5. If p[j - 1]  is '*' then
    1.   a. if previous char in pattern match current char of s i.e. p[j - 2] is '.' or s[i-1] then table[i][j] = table[i][j-2] || table[i-1][j]
    2. if not then table[i][j] = table[i][j-2]
  6. table[i][j] = false.


Implementation in C#:

        public bool IsRegexMatch(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] = i - 2 >= 0 ? lookup[0, i - 2] :false;

                }

            }

            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 - 2];

                        if (p[j - 2] == '.' || p[j - 2] == s[i - 1])

                        {

                            lookup[i, j] = lookup[i, j - 2] || 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];

        }


Complexity: O(m * n)

Longest Palindromic Substring

Approach: The idea is to generate all even length and odd length palindromes and keep track of the longest palindrome seen so far.

To generate odd length palindrome, Fix a centre and expand in both directions for longer palindromes, i.e. fix i (index) as center and two indices as i1 = i+1 and i2 = i-1

Compare i1 and i2 if equal then decrease i2 and increase i1 and find the maximum length.

Use a similar technique to find the even length palindrome.

Take two indices i1 = i and i2 = i-1 and compare characters at i1 and i2 and find the maximum length till all pair of compared characters are equal and store the maximum length.


        public string LongestPalindromicSubString(string str)

        {

            if(string.IsNullOrEmpty(str))

            {

                return string.Empty;

            }

            int maxLength = 1;

            int start = 0;

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

            {

                // Find the longest even length palindrome with center points as i-1 and i.

                int low = i - 1;

                int high = i;

                while(low >= 0 && high < str.Length && str[low] == str[high])

                {

                    if (high - low + 1 > maxLength)

                    {

                        start = low;

                        maxLength = high - low + 1;

                    }

                    --low;

                    ++high;

                }

                // Find the longest odd length palindrome with center point as i

                low = i - 1;

                high = i + 1;

                while(low >= 0 && high <str.Length && str[low] == str[high])

                {

                    if (high - low + 1 > maxLength)

                    {

                        start = low;

                        maxLength = high - low + 1;

                    }

                    --low;

                    ++high;

                }

            }

            return str.Substring(start, maxLength);

        }


Complexity: O(n^2)

[LeetCode] Longest Substring Without Repeating Characters

Problem: Given a string s, find the length of the longest substring without repeating characters.

Example:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.


Approach: Clearly it's a sliding window problem. Like in any other sliding window problem we will maintain start and end indices of current window. We can have a hash map but we can use hash set here as the occurrence of  every character in substring can't be more than one. We will keep incrementing end by 1 and for each index 'end', there could be 2 cases:

  1. s[end] is not in current window means it won't be in our hash set too. We can simply add s[end] to hash set i.e. add s[end] to current window. We will also see if the current window length is more than max length then we can assign current length to max length.
  2. s[end] is already in current window means it is already in our hash set. In this case we need to slide our window from the left. Means we will keep increasing start index of window and keep removing s[start] from hash set until s[end] character is removed from the hash set / current window.
In the end we will just return the max length. That's all!


Implementation in C#:

    public int LengthOfLongestSubstring(string s)
    {
        int length = s?.Length ?? 0;
        if (length <= 1)
        {
            return length;
        }
        HashSet<char> charSet = new HashSet<char>();
        int start = 0;
        int end = 0;
        int maxLen = 0;
        for ( ; end < length; ++end)
        {
            if (charSet.Contains(s[end]))
            {
                maxLen = Math.Max(maxLen, end - start);
                while (charSet.Contains(s[end]))
                {
                    charSet.Remove(s[start++]);
                }
            }
            charSet.Add(s[end]);
        }
        return Math.Max(maxLen, end - start);
    }


Complexity: O(n)

Median of 2 sorted arrays

Example: Input : ar1[] = {-5, 3, 6, 12, 15}

        ar2[] = {-12, -10, -6, -3, 4, 10}

        The merged array is :

        ar3[] = {-12, -10, -6, -5 , -3,

                 3, 4, 6, 10, 12, 15}

Output : The median is 3.

Solution: Start partitioning the two arrays into two groups of halves. The first half contains some first elements from the first and the second arrays, and the second half contains the rest elements form both arrays. Reach a condition such that, every element in the first half is less than or equal to every element in the second half.

    public double FindMedianSortedArrays(int[] nums1, int[] nums2)

    {

            if (nums1 == null && nums2 == null)

            {

                return -1;

            }

            if (nums1.Length == 0 && nums2.Length == 0)

            {

                return -1;

            }

            if (nums1.Length <= nums2.Length)

            {

                return this.FindMedianSortedArraysInternal(nums1, nums2);

            }

            else

            {

                return this.FindMedianSortedArraysInternal(nums2, nums1);

            }

        }

        private double FindMedianSortedArraysInternal(int[] nums1, int[] nums2)

        {

            int minIndex = 0, maxIndex = nums1.Length, nums1Index = 0, nums2Index = 0;

            double median = 0;

            while (minIndex <= maxIndex)

            {

                nums1Index = (minIndex + maxIndex) / 2;

                nums2Index = ((nums1.Length + nums2.Length + 1) / 2) - nums1Index;

                if (nums2Index < 0)

                {

                    maxIndex = nums1Index - 1;

                    continue;

                }

                // if num1Index = num1.Length, it means that elements from num1 in the second half is an  

                // empty set. and if num2Index = 0, it means that elements from num2 in the first half is an

                // empty set. so it is necessary to check that, because we compare elements from these two

               // groups. Searching on right  

                if (nums1Index < nums1.Length && nums2Index > 0 && nums2[nums2Index - 1] > nums1[nums1Index])

                {

                    minIndex = nums1Index + 1;

                }

                // if num1Index = 0, it means that Elements from num1 in the first half is an empty set and if 

                // num2Index = num2.Length, it means that Elements from num2 in the second half is an 

                // empty set. so it is necessary to check that, because we compare elements from these two

                // groups. searching on left

                else if (nums1Index > 0 && nums2Index < nums2.Length && nums2[nums2Index] < nums1[nums1Index - 1])

                {

                    maxIndex = nums1Index - 1; 

                }

                // Found the desired halves

                else

                {

                    // this condition happens when we don't have any elements in the first half from num1 so

                    // we returning the last element in num2 from the first half.

                    if (nums1Index == 0)

                    {

                        median = nums2[nums2Index - 1];

                    }

                    // this condition happens when we don't have any elements in the first half from num2 so

                    // we returning the last element in num1 from the first half.

                    else if (nums2Index == 0)

                    {

                        median = nums1[nums1Index - 1];

                    }

                    else

                    {

                        median = Math.Max(nums1[nums1Index - 1], nums2[nums2Index - 1]);

                    }

                    break;

                }

            }

            // If number of elements is odd there is one middle element. 

            if ((nums1.Length + nums2.Length) % 2 == 1)

            {

                return median;

            }

            // Elements from nums1 in the second half is an empty set.

            if (nums1Index == nums1.Length)

            {

                return (median + nums2[nums2Index]) / 2;

            }

            // Elements from nums2 in the second half is an empty set.

            if (nums2Index == nums2.Length)

            {

                return (median + nums1[nums1Index]) / 2;

            }

            return (median + Math.Min(nums1[nums1Index], nums2[nums2Index])) / 2;      

        }