How to measure 45 minutes using two wires

Problem: How do we measure forty-five minutes using two identical wires, each of which takes an hour to burn. We have matchsticks with us. The wires burn non-uniformly. So, for example, the two halves of a wire might burn in 10 minute and 50 minutes respectively.

Solution: We know that the wires are not uniform so we can't say that after 30 minutes half of the wire would have burnt but what we can guarantee is if we burn the wire from both sides then the wire will be burnt in 30 minutes (60 / 2). With this approach we can solve this puzzle easily. Here is how:

1. Burn the Wire-1 from both side and Wire-2 from single side.
2. Once the Wire-1 is completely burnt means 30 minutes we burn the Wire-2 from the other side too.
3. Now the Wire-2 will be completely burnt in next 15 minutes as for 30 minutes it is already burnt from single side and 30 minutes were remaining. As we have started fire from the other end too it will take only 15 (30 / 2) minutes to be fully burnt. 

Given a list of non-negative integers, arrange them such that they form the largest number.

Example:

Input: nums = [4,40,44,6,92]
Output: "92644440"

Approach: Before moving to solution, lets consider one thing -

• The result may be very large, so we need to return a string instead of an integer.

At first look we came up with following two approaches immediately -

1. Sort integers in descending order: Won't work at all. Take an example - {2, 10}. With this approach it will produce 102 which is not correct.
2. Convert integers to string and then sort in descending order: It will initially look like the right approach and solve many cases like {2, 10} but take an example say {3, 31}. With this approach the result will be 313 where it should be 331 so it won't work too.

Now we can see that none of the inbuilt comparator will work for us. That means we need to write our own comparator while sorting these numbers. What should be our comparator? This is easy, if you see we are forming number by appending these numbers to each other so we just have to apply the same logic to our comparator. Here is how it can be done:

Say we need to compare two numbers NUM1 and NUM2, in our comparator we will actually be comparing numbers first formed by NUM2 appending at the end of NUM1 say NUM1NUM2 and second formed by NUM1 appending at the end of NUM2 say NUM2NUM1.

And that's all! Is it, Almost yes but we have a boundary condition here to handle. Say the input array is {0, 0}, in this case we will return "00" instead of "0"? How to handle this condition? Let's see, we know that the final array will be in descending order so we can check if first element of sorted array is 0 then the result is "0". Now that's all.

Implementation in C#:

        public static string LargestNumber(int[] nums)

        {

            Array.Sort(nums, LargeNumberComare);

            return nums[0] == 0 ? "0" : string.Join(string.Empty, nums);

        }

        private static int LargeNumberComare(int num1, int num2)

        {

            string num1num2 = $"{num1}{num2}";

            string num2num1 = $"{num2}{num1}";

            return num1num2.CompareTo(num2num1) > 0 ? -1 : 1;

        }

Complexity: O(nlogn)

[Microsoft][LeetCode] Dungeon Game

Problem: The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess. Here are few points to be considered -

• The knight's health has no upper bound.
• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Example: given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2 (K)	-3	3
-5	-10	1
10	30	-5 (P)

Approach: Use DP. We can maintain a 2D table where Table[i][j] will tell the minimum health points required to reach (m - 1, n - 1), where m is number of rows and n is number of columns, from (i, j). Obviously our answer will be Table[0][0]. Here is how we will fill the table:

1. Table[m - 1][n - 1] = Max (1 - Matrix[m - 1][n - 1], 1) // At least1 is required
2. Foreach i from m - 1 to 0 and j from n - 1 to 0: 

            Table[i][j] = Max ( Min (Table[i + 1][j], Table[i][j + 1]) - Matrix[i][j], 1)

Please note that in above statement, you have to take care of boundary conditions.

Implementation in C#:

        public int CalculateMinimumHP(int[][] dungeon)

        {

            int[,] minHealthHP = new int[dungeon.Length, dungeon[0].Length];

            minHealthHP[dungeon.Length - 1, dungeon[0].Length - 1] = Math.Max(1 - dungeon[dungeon.Length - 1][dungeon[0].Length - 1], 1);

            for (int i = dungeon.Length - 2; i >= 0; --i)

            {

                minHealthHP[i, dungeon[0].Length - 1] = Math.Max(minHealthHP[i + 1, dungeon[0].Length - 1] - dungeon[i][dungeon[0].Length - 1], 1);

            }

            for (int i = dungeon[0].Length - 2; i >= 0; --i)

            {

                minHealthHP[dungeon.Length - 1, i] = Math.Max(minHealthHP[dungeon.Length - 1, i + 1] - dungeon[dungeon.Length -1][i], 1);

            }

            for (int i = dungeon.Length - 2; i >= 0; --i)

            {

                for (int j = dungeon[0].Length - 2; j >= 0; --j)

                {

                    minHealthHP[i, j] = Math.Max(Math.Min(minHealthHP[i + 1, j], minHealthHP[i, j + 1]) - dungeon[i][j], 1);

                }

            }

            return minHealthHP[0, 0];

        }

Complexity: O(m * n) => O(n^2)

Binary Search Tree Iterator

Problem: Implement an iterator over a binary search tree (BST). Your iterator should perform following operations -

1. Next - Return the next smallest number in the BST.
2. HasNext - Check if there is any element.

Approach: We can see that we need a inorder traversal here. What we can do is we can store all the nodes in an array using inorder traversal but that will increase the space a lot. If we want to reduce space then we can actually have a member say k and can return kth smallest node by doing inorder traversal every time when somebody calls Next.

Now if we go with recursion approach of inorder traversal, we always have to start from root but if we use the stack approach, we can do little better both in terms of time and space.

    public class BSTIterator

    {

        public BSTIterator(BinaryTreeNode root)

        {

            this.stack = new Stack<BinaryTreeNode>();

            this.PushTillLeftMost(root);

        }

        public int Next()

        {

            BinaryTreeNode node = stack.Pop();

            if (node.RightNode!= null)

            {

                this.PushTillLeftMost(node.RightNode);

            }

            return node.Value;

        }

        public bool HasNext()

        {

            return stack.Count > 0;

        }

        private void PushTillLeftMost(BinaryTreeNode node)

        {

            while (node != null)

            {

                stack.Push(node);

                node = node.LeftNode;

            }

        }

        private Stack<BinaryTreeNode> stack;

    }

Given an integer n, return the number of trailing zeroes in n!

Approach: Let's take example say !5 = 5 x 4 x 3 x 2 x 1 = 120, it has 1 zero. If we see trailing zeros are equals to number of 10s in the factorial which we can say is equal to number of 5s (5 x 2) right. See it yourself that number of 5s are always less than number of 2s in factorial by definition.

Here is how we can count 5s -

         public int TrailingZeroes(int n)

        {

            int numsOfFives = 0;

            while (n >= 5)

            {

                numsOfFives += n / 5;

                n = n / 5;

            }

            return numsOfFives;

        }

Complexity: O(logn)

Majority Element

Problem: Given an array of size n, find the majority element. The majority element is the element that appears more than n/2 times.

Example:

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

Approach: Using Boyer–Moore majority vote algorithm. We can do it by sorting the array or using hash but majority vote algorithm do it most efficiently in terms of time and space.

Implementation in C#:

    public int MajorityElement(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return int.MinValue;

        }

        int count = 1;

        int majElement = nums[0];

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

        {

            majElement = count == 0 ? nums[i] : majElement;

            count = majElement == nums[i] ? count + 1 : count - 1;

        }

        count = 0;

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

        {

            if (majElement == nums[i])

            {

                ++count;

            }

        }

        return count > length / 2 ? majElement : int.MinValue;

    }

Complexity: O(n)

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

Example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 
    ...

Approach: Not much to explain. Its a straight forward case -

        public static string ConvertToTitle(int n)

        {

            string result = string.Empty;        

            while(n > 0)

            {

                --n;

                int remainder = n % 26;

                result = (char)('A' + remainder) + result;

                n = n / 26;

            }

            return result;

        }

[LeetCode] Fraction to Recurring Decimal

Problem: Given two integers representing the numerator and denominator of a fraction, return the fraction in string format. If the fractional part is repeating, enclose the repeating part in parentheses.

Example: 

Input: numerator = 1, denominator = 5
Output: "0.2"

Input: numerator = 18, denominator = 3
Output: "6"

Input: numerator = 10, denominator = 3
Output: "0.(3)"

Input: numerator = 3, denominator = 333
Output: "0.(012)"

Input: numerator = 1, denominator = 6
Output: "0.1(6)"

Input: numerator = -50, denominator = 8
Output: "-6.25"

Approach: If you see, I have given many examples here specially to cover many scenarios. The approach is not complex, its straight forward. The only problem is to detect if there is recurrence in division. We can detect it using hash of remainders. The points here which we need to be careful of -

1. What is the sign of the result.
2. Check for denominator if it is 0.
3. Deal with int.MinValue as abs(int.MinValue) will throw exception. We can use long instead of int to deal with it.

That's all!

Implementation in C#:

        public static string FractionToDecimal(int numerator, int denominator)

        {

            if (numerator == 0)

            {

                return "0";

            }

            if (denominator == 0)

            {

                throw new DivideByZeroException();

            }

            string sign = (numerator < 0 && denominator > 0) || (numerator > 0 && denominator < 0) ? "-" : string.Empty;

            long numer = Math.Abs((long)numerator);

            long deno = Math.Abs((long)denominator);

            string result = string.Empty;

            result += (numer / deno).ToString();

            if (numer % denominator == 0)

            {

                return sign + result;

            }

            result += ".";

            long remainder = numer % deno;

            Dictionary<long, int> remainders = new Dictionary<long, int>();

            while(remainder != 0 && !remainders.ContainsKey(remainder))

            {

                remainders.Add(remainder, result.Length); // storing length to see from where we need to put (

                result += ((remainder * 10) / deno).ToString();

                remainder = ((remainder * 10) % deno);

            }

            if (remainder != 0)

            {

                result = result.Insert(remainders[remainder], "(");  

                result += ")";

            }

            return  sign + result;

        }

Compare Version Numbers

Problem: Given two version numbers, version1 and version2, compare them. Version numbers consist of one or more revisions joined by a dot '.'. Each revision consists of digits and may contain leading zeros. Every revision contains at least one character. Revisions are 0-indexed from left to right, with the leftmost revision being revision 0, the next revision being revision 1, and so on. For example 2.2.35 and 0.7 are valid version numbers.

To compare version numbers, compare their revisions in left-to-right order. Revisions are compared using their integer value ignoring any leading zeros. This means that revisions 1 and 001 are considered equal. If a version number does not specify a revision at an index, then treat the revision as 0. For example, version 1.0 is less than version 1.1 because their revision 0s are the same, but their revision 1s are 0 and 1 respectively, and 0 < 1.

Return the following:

• If version1 < version2, return -1.
• If version1 > version2, return 1.
• Otherwise, return 0.

Example: (Taken from leetcode)

Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: Ignoring leading zeroes, both "01" and "001" represent the same integer "1".

Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: version1 does not specify revision 2, which means it is treated as "0".

Input: version1 = "0.1", version2 = "1.1"
Output: -1
Explanation: version1's revision 0 is "0", while version2's revision 0 is "1". 0 < 1, so version1 < version2.

Implementation in C#:

        public int CompareVersion(string version1, string version2)

        {

            string[] version1Array = version1.Split('.');

            string[] version2Array = version2.Split('.');

            

            int maxLength = Math.Max(version1Array.Length, version2Array.Length);

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

            {

                int num1 = i >= version1Array.Length ? 0 : int.Parse(version1Array[i]);

                int num2 = i >= version2Array.Length ? 0 : int.Parse(version2Array[i]);

                if (num1 < num2)

                {

                    return -1;

                }

                else if (num1 > num2)

                {

                    return 1;

                }

            }

            return 0;

        }

Complexity: O(m+n) where m is the length of largest version number and n are number of revisions.

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

 Example:

Input: [12,3,9,1,17]
Output: 6
Explanation: The sorted form of the array is [1,3,9,12,17], (3,9) has the maximum difference 3.

Approach: We can sort the array and then in one traversal we can get the answer but this will take O(nlogn) time. Let's see how we can do better. Here is the problem we are trying to solve -

"Sorting requires comparing each element with every other element. Can we do it without it? It's possible if we somehow divide the elements in buckets and then just compare these buckets."

We can use Pigeonhole Sort technique to get it in Linear time. Remember here we are not trying to sort the array so we can reduce the number of buckets that means one bucket may contain more than one element. Here are few clarifications or pre-calculations before jumping to algorithm -

1. Gaps between the elements: Best case where all elements of the array are sorted and have a uniform gap between them. This means every adjacent pair of elements differ by the same constant. So for n elements, there are n-1 gaps.
2. Size of bucket: With n - 1 gaps and the range of numbers as max(array) -  min(array), we can say the size of bucket will be (max(array) -  min(array)) / n - 1 (approximately, could be ceil of the division).
3. No comparison among the elements in the bucket: We just can't compare each and every element in the bucket otherwise the time complexity will be high so what we can do? We only compare among buckets as the buckets can be already ordered but if we only compare buckets then we need to ensure that the gap between the buckets itself represent the maximal gap in the input array. 
• See the bucket size is (max - min)/(n-1) (point 2). Since the gaps within the same bucket would only be <= bucket size, we can say that the maximal gap would indeed occur only between two adjacent buckets.
4. How to compare two adjacent buckets: By comparing buckets' boundaries. We compare the minimum element of the next bucket to the maximum element of the current bucket.

Now let's talk about the algorithm, after discussing the above points, it is fairly straight forward -

We choose a bucket size b such that 1 < b ≤(max−min)/(n−1). Let's just choose b = Ceil((max - min)/(n-1)).
Thus all the n elements would be divided among numBuckets = (max - min)/b.
Hence the ith bucket would hold the range of values: (min + (i - 1) * b) to  (min + i * b).
Index of the bucket to which a particular element num belongs is given by (num - min) / b.
Once all n elements have been distributed, we compare numBuckets - 1 adjacent bucket pairs to find the maximum gap.

Here is the implementation in C# -

        public int MaximumGap(int[] nums)

        {

            if (nums?.Length < 2)

            {

                return 0;

            }

            int min = Enumerable.Min(nums);

            int max = Enumerable.Max(nums);

            int gap = (int)Math.Ceiling(((double)(max - min)) / ((double)nums.Length - 1));

            int[] bucketMax = new int[nums.Length - 1];

            Array.Fill(bucketMax, int.MinValue);

            int[] bucketMin = new int[nums.Length - 1];

            Array.Fill(bucketMin, int.MaxValue);

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

            {

                if (nums[i] == min || nums[i] == max)

                {

                    continue;

                }

                int index = (nums[i] - min) / gap;

                bucketMax[index] = Math.Max(bucketMax[index], nums[i]);

                bucketMin[index] = Math.Min(bucketMin[index], nums[i]);

            }

            int maxGap = 0, prevMax = min;

            for (int i = 0; i < nums.Length - 1; ++i)

            {

                if (bucketMax[i] == int.MinValue)

                {

                    continue;

                }

                maxGap = Math.Max(maxGap, bucketMin[i] - prevMax);

                prevMax = bucketMax[i];

            }

            return Math.Max(maxGap, max - prevMax);

        }

Complexity: O(n)

Pigeonhole Sort

This is an example of the non-comparison sorting technique. It is used where the number of items and the range of possible key values is approximately the same.

To perform this sort, we need to make some holes. The number of holes needed is decided by the range of numbers. In each hole, items are inserted. Finally deleted from the hole and stored into an array for sorted order.

Here is the algorithm:

Begin
   find max and min from the array list
   holeRange := max – min +1
   define holeRange number of Lists

   for i := 0 to n-1 do
      hole[array[i]-min].append(array[i])
   done

   count := 0
   for j := 0 to holeRange-1 do
      while hole[j] is not empty do
         array[count] := get first node of hole[j] and delete it
         count := count +1
      done
   done
End

Here is the implementation:

        public static void PigeonHoleSort(int[] arr)

        {

            int max = Enumerable.Max(arr);

            int min = Enumerable.Min(arr);

            int holeRange = max - min + 1;

            int[] pigeonHoles = new int[holeRange];

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

            {

                pigeonHoles[arr[i] - min]++;

            }

            int writeIndex = 0;

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

            {

                while(pigeonHoles[i]-- > 0)

                {

                    arr[writeIndex++] = i + min;

                }

            }

        }

Complexity: Time: O (n + (max - min)), Space: O(max - min)

Find Peak Element

Problem: A peak element is an element that is greater than its neighbors. Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

Example:

Input: nums = [2,4,2,3,4,9,8]
Output: 1 or 5 
Explanation: Either index 1 where the peak element is 4 or index 5 where the peak element is 9.

Approach: Straightforward solution is to traverse each element just check the condition arr[i - 1] < arr[i] > arr[i + 1] and we are done but it will take O(n) time. We can do it in O(logn) using the binary search approach:

1. IF arr[mid] > arr[mid + 1] then we know that we need to look at the left array partition including mid.
2. ELSE we need to look at right subarray. 

Implementation in C#:

        public int FindPeakElement(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return -1;

        }

        if (length == 1 || nums[0] > nums[1])

        {

            return 0;

        }

        if (nums[length - 1] > nums[length - 2])

        {

            return length - 1;

        }

        int start = 1, end = length - 2;

        while (start <= end)

        {

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

            if (nums[mid] > nums[mid - 1] &&

                nums[mid] > nums[mid + 1])

            {

                return mid;

            }

            else if (nums[mid] <= nums[mid + 1])

            {

                start = mid + 1;

            }

            else

            {

                end = mid - 1;

            }

        }

        return -1;

    }

Complexity: O(logn)

Find Minimum in Rotated Sorted Array with duplicates

Problem: It is same as previous Find Minimum in Rotated Sorted Array but here the array contains duplicates. 

Approach: We just need one additional check to make it work in this case which is - if arr[mid] is equals to arr[high] then we just reduce high by 1.

        public int FindMinInRotatedArray(int[] nums)

        {

            if (nums?.Length == 0)

            {

                return -1;

            }

            int low = 0, high = nums.Length - 1;

            while(low < high)

            {

                int mid = (low + high) / 2;

                if (nums[mid] == nums[high]) // Additional check

                {

                    --high;

                }

                else if (nums[mid] > nums[high])

                {

                    low = mid + 1;   

                }

                else

                {

                    high = mid;

                }

            }

            return nums[high];

        }

[LeetCode] Find Minimum in Rotated Sorted Array

Problem: Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

Example:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 

Approach: We are going to use binary search. While comparing the mid element, we would have these three conditions -

1. arr[mid - 1] > arr [mid] < arr[mid + 1]. Got the minimum just return arr[mid]. We need to take care of boundary conditions here.
2. arr[mid] > arr[high]. That's the only condition where the min element is on the right side. It happened because of rotation.
3. Otherwise the min element is on left side.

Implementation in C#:

Using Recursion:

        public int FindMinInRotatedArray(int[] nums)

        {

            if (nums?.Length == 0)

            {

                return -1;

            }

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

        }

        private int FindMinInRotatedArray(int[] nums, int low, int high)

        {

            if (low == high)

            {

                return nums[low];

            }

            int mid = (low + high) / 2;

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

                (mid == 0 || nums[mid] < nums[mid - 1]))

            {

                return nums[mid];

            }

            if (nums[mid] > nums[high]) // Go to right side

            {

                return FindMinInRotatedArray(nums, mid + 1, high);

            }

            else // Go to left side otherwise

            {

                return FindMinInRotatedArray(nums, low, mid - 1);

            }

        }

Without recursion:

        public int FindMinInRotatedArray(int[] nums)

        {

            if (nums?.Length == 0)

            {

                return -1;

            }

            int low = 0, high = nums.Length - 1;

            while(low < high)

            {

                int mid = (low + high) / 2;

                if (nums[mid] > nums[high])

                {

                    low = mid + 1;   

                }

                else

                {

                    high = mid;

                }

            }

            return nums[high];

        }

Complexity: O(logn)

Reverse Words in a String - 2

Problem: This is similar to Reverse words in a sentence but with some extra conditions. Here is what is more -

1. Reversed string should not contain leading or trailing spaces.
2. Reduce multiple spaces between two words to a single space in the reversed string.

Example:

Input: "  Nishant Saxena   examples   "
Output: "examples Saxena Nishant"

Approach: Same as the original problem. We just need to take care of leading, trailing and multiple continuous spaces. Using Trim() and one self written method we can make the string which can be processed successfully by original ReverseWords method.

Implementation in C#:

        public string ReverseWords(string s)

    {

        if (string.IsNullOrEmpty(s))

        {

            return s;

        }

        char[] sArr = s.Trim().ToCharArray();

        int end = this.RemoveDupSpaces(sArr);

        this.Reverse(sArr, 0, end - 1);

        int i = 0, j = 0;

        while(j < end)

        {

            while(j < end && sArr[j] != ' ')

            {

                ++j;

            }

            this.Reverse(sArr, i, j - 1);

            j = j + 1;

            i = j;

        }      

        return new string(sArr, 0, end);

    }

    private void Reverse(char[] sArr, int start, int end)

    {

        while (start < end)

        {

            char temp = sArr[start];

            sArr[start++] = sArr[end];

            sArr[end--] = temp;

        }

    }

    private int RemoveDupSpaces(char[] sArr)

    {

        int j = 0;

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

        {

            if (sArr[i] != ' ' || sArr[i  - 1] != ' ')

            {

                sArr[j++] = sArr[i];

            }

        }

        return j;

    }

Complexity: O(n)

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Example: 

Input: ["6", "3", "-", "3", "/"]
Output: 1
Explanation: ((6 - 3) / 3) = 1

Approach: Use stack. Whenever an operator comes, pop 2 values from stack and apply the operation and push the result back to stack. Please note that for "-" operator a single operand will also be enough. 

        public static int EvalRPN(string[] tokens)

        {

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

            foreach(string token in tokens)

            {

                if (IsOperator(token))

                {

                    if (stack.Count >= 2)

                    {

                        int operand2 = stack.Pop();

                        int operand1 = stack.Pop();

                        int operationResult = ExecuteOperation(token, operand1, operand2);

                        stack.Push(operationResult);

                    }

                    else if (stack.Count == 1 && token == "-") // special handling of "-"

                    {

                        int num = stack.Pop();

                        stack.Push(-num);

                    }

                }

                else

                {

                    stack.Push(int.Parse(token));

                }

            }

            return stack.Pop(); 

        }

        private static int ExecuteOperation(string operatorStr, int operand1, int operand2)

        {

            switch (operatorStr)

            {

                case "+": return operand1 + operand2;

                case "-": return operand1 - operand2;

                case "*": return operand1 * operand2;

                default: return operand1 / operand2;

            }

        }

        private static bool IsOperator(string str)

        {

            return str == "+" || str == "-" || str == "*" || str == "/";

        }

Implement insertion sort for linked list

        public void InsertionSort()

        {

            if (this.Head == null || this.Head.Next == null)

            {

                return;

            }

            LinkedListNode curr = this.Head.Next;

            LinkedListNode prev = this.Head;

            while(curr != null)

            {

                LinkedListNode next = curr.Next;

                this.SortedInsert(curr);

                if (curr.Next == next)

                {

                    prev.Next = curr;

                    prev = curr;

                }

                else

                {

                    prev.Next = next;

                }

                curr = next;

            }

        }

        public void SortedInsert(LinkedListNode node)

        {

            if (this.Head == null || this.Head.Value >= node.Value)

            {

                node.Next = this.Head;

                this.Head = node;

            }

            else

            {

                LinkedListNode curr = this.Head;

                while(curr.Next != null && curr.Next != node && curr.Next.Value < node.Value)

                {

                    curr = curr.Next;

                }

                if (curr.Next != node)

                {

                    node.Next = curr.Next;

                    curr.Next = node;

                }

            } 

        }

Reorder List

Problem: Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

Example:

Given 1->2->3->4, reorder it to 1->4->2->3.

Approach: We can maintain a stack to get the nodes in the reverse order and we can have a iterator starting from head. We can keep merging these nodes till the iterator and top of stack are same or iterator's next and top of stack are same. Here is the code -

        public void ReorderList1()

        {

            if (this.Head == null || this.Head.Next == null)

            {

                return;

            }

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

            LinkedListNode itr = this.Head;

            while (itr != null)

            {

                stack.Push(itr);

                itr = itr.Next;

            }

            itr = this.Head;

            LinkedListNode itrEnd = stack.Pop();

            while(itr != itrEnd && itr.Next != itrEnd)

            {

                LinkedListNode tempNext = itr.Next;

                itr.Next = itrEnd;

                itrEnd.Next = tempNext;

                itr = tempNext;

                itrEnd = stack.Pop();

            }

            if (itr == itrEnd)

            {

                itr.Next = null;

            }

            else 

            {

                itrEnd.Next = null;

            }

        }

Complexity: O(n)

Even the above approach runs in O(n) but it has the space complexity of O(n). Can we do better? If we look at the approach closely, we can see we are reversing the second half of the list and merging. So we can do it without stack now. Here is the optimized solution -

        public void ReorderList()

        {

            if (this.Head == null || this.Head.Next == null)

            {

                return;

            }

            LinkedListNode slow = this.Head, fast = this.Head.Next;

            // Getting the mid element

            while (fast != null)

            {

                slow = slow.Next;

                fast = fast.Next;

                if (fast != null)

                {

                    fast = fast.Next;

                }

            }

            // Reversing the second half

            fast =  this.ReverseFromNode(slow.Next);

            slow.Next = null;

            slow = this.Head;

            // Merging now

            while(fast != null) // second half will be less than or equal to the first half

            {

                LinkedListNode tempNext = slow.Next;

                LinkedListNode tempFastNext = fast.Next;

                slow.Next = fast;

                fast.Next = tempNext;

                fast = tempFastNext;

                slow = tempNext;

            }

        } 

Complexity: O(n)

Given a linked list, check if a cycle exist and return the node where the cycle begins. If there is no cycle, return null.

Approach: Using Floyd’s Cycle-Finding Algorithm.

        public LinkedListNode HasCycle()

        {

            if (this.Head == null)

            {

                return null;

            }

            LinkedListNode slow = this.Head, fast = this.Head;

            while (fast != null)

            {

                slow = slow.Next;

                fast = fast.Next;

                if (fast != null)

                {

                    fast = fast.Next;

                }

                if (slow == fast)

                {

                    break;

                }

            }

            if (fast == null) // No cycle

            {

                return null;

            }

            slow = this.Head;

            while(slow != fast)

            {

                slow = slow.Next;

                fast = fast.Next;

            }

            return slow;

        }

Word break: Get all the possible sentences

Problem: Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Example: (Taken from leetcode)

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Approach: Recursion with memorization. Memorization is introduced just for more efficient solution then usual backtracking.

        public static IList<string> WordBreakAllPatitions(string s, IList<string> wordDict)

        {

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

            return WordBreakAllPatitionsDP(s, wordDict, resultsHash);

        }

        private static List<string> WordBreakAllPatitionsDP(string s, IList<string> wordDict, Dictionary<string, List<string>> resultsHash)

        {

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

            if (resultsHash.ContainsKey(s))

            {

                return resultsHash[s];

            }

            if (s.Length == 0)

            {

                return new List<string> { string.Empty };

            }

            foreach (string word in wordDict)

            {

                if (s.StartsWith(word))

                {

                    List<string> currResult = WordBreakAllPatitionsDP(s.Substring(word.Length), wordDict, resultsHash);

                    foreach(string str in currResult)

                    {

                        string mid = (str == "") ? "" : " ";

                        result.Add(word + mid + str);

                    }

                }

            }

            resultsHash.Add(s, result);

            return result;

        }

[Uber][LeetCode] Word Break

Problem: Given a non-empty string and a dictionary containing a list of non-empty words, determine if given string can be segmented into a space-separated sequence of one or more dictionary words. 

Example:

Input: s = "Iamace", wordDict = ["I", "a", "am" "ace"]
Output: true
Explanation: Return true because "Iamace" can be segmented as "I am ace".

Approach: The immediate approach which comes to mind is DP with a 2D table where its element T[i][j] tells if sub string [i...j] can be partitioned into dictionary words or not. Obviously T[0][n-1] will be our answer. Table T can be filled in following way -

FOREACH length = 1 to string.Length:

FOREACH i = 0 to i = string.Length - length

• If S[i...i + length - 1] is a dictionary word then T[i][i + length - 1] = true.
• ELSE 
• FOREACH j = i to i + length - 2 // checking for each partition
• IF T[i][j] && T[j+1][i + length -1] is true then T[i][i + length - 1] = true // Got a partition
• T[i][i + length - 1] = false

Now this solution will work fine and is obviously is way better than the brute force approach but still its time complexity is O(n^3) ignoring the string comparison and finding word in dictionary with O (n^2) space complexity. 

Can we do better? Let's see it closely. There are following points to be considered -

1. We always need to check S[0...i] as we want result from the first character only.
2. Do we need to look at each index? I think not, we just need to consider indexes which tells us that from 0...index, you can partition the string into valid words i.e. sub-string S[0...i] can be partitioned into dictionary words so now we just need to check whether sub-string S[i+1... S.Length - 1]  can be partitioned into dictionary words or not.
3. Considering above 2 points, we can see that we don't need 2D table to store data. We can just have 1D array T where T[i] is true if S[0...i] can be broken into dictionary words. Right? It looks correct but if we see, we just need the end index result i.e. T[S.Length -1] that means we can ignore the other values in T. It tells us we can use a bool variable which can tell us result at current index and we can return it.

Implementation in C#:

        public static bool WordBreak1(string s, IList<string> wordDict)

        {

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

            validIndexes.Add(-1);

            bool isValidonCurrentIndex = false;

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

            {

                isValidonCurrentIndex = false;

                for (int j = validIndexes.Count - 1; j >= 0; --j) // only check for valid indexes

                {

                    if (wordDict.Contains(s.Substring(validIndexes[j] + 1, i - validIndexes[j])))

                    {

                        isValidonCurrentIndex = true;

                        validIndexes.Add(i);

                        break;

                    }

                }

            }

            return isValidonCurrentIndex;

        }

Complexity: O(n^2)  

  

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Approach: Lets have a look at the solution first and then I will explain what exactly this is doing. Here is the pseudo code -

ones = 0
twos = 0
notThrees = 0
FOREACH elem in array
twos = twos OR (ones AND elem)
ones = ones XOR elem
notThrees = NOT (twos AND ones)
ones = ones AND notThrees
twos = twos and notThrees
return ones;

Now let's understand what this is doing. This works in similar line with the question of  "finding the element which appears once in an array - containing other elements each appearing twice". Solution is to XOR all the elements and you get the answer. Basically, it makes use of the fact that x^x = 0 or I would say if "bit1" and "bit2" are same then bit1 ^ bit2 will become 0 so using XOR we actually cancel all the set bits appearing even times and remaining are set bits occurred odd times. Obviously these set bits give the number appears only once in an array.

Now, coming to our original question just XORing will not work as we will end up getting XOR of all unique elements. To make it work the solution uses 2 variables -

1. ones - At any point of time, this variable holds XOR of all the set bits which have appeared only once.
2. twos - At any point of time, this variable holds XOR of all the bits which have appeared only twice.

So here is the flow. I am using number instead of set bit just for make it more understandable (even though it is not true) -

1. A new number appears - It gets XOR'd to "ones"
2. A number appears twice - It is removed from "ones" and XOR'd to "twos"
3. A number appears for the third time - It gets removed from both "ones" and "twice"

Finally variable ones obviously will be our answer so if we can prove that above code is doing exactly these three steps we are done. The last three lines -

1. not_threes = NOT (ones & twos)
2. ones = ones AND not_threes
3. twos = twos AND not_threes

All it does is, common set bits between "ones" and "twos" are converted to zero because if a number comes ones and twice i.e. it appears three times and we don't want to include it in our answer. I simplify it just to make it more understandable.

Let's take an example array = [x, x, x, y] and run our code and see what it is doing -

For array[0] i.e. x -

1. twos = twos OR (ones AND x) - Since bit representation of "x" is not present in "ones", AND condition yields nothing. So "twos" does not get bit representation of "x" i.e. twos remain 0.
2. ones = ones XOR x - "ones" ends up adding bits of x
3. Last 3 lines will not do anything as there are no common set bits between ones and twos (x appears only once) so ones has x and twos is 0.

For array[1] i.e. x -

1. twos = twos OR (ones AND x) - twos will get bit representation of x and it should as x appears twice now.
2. ones = ones XOR x - "ones" ends up being 0 that is removing x's bit representation and it should as x is appeared twice now.
3. Last 3 lines will not do anything as there are no common set bits between ones and twos so twos will have x and ones will be 0.

For array[2] i.e. x -

1. twos = twos OR (ones AND x) - twos will get bit representation of x as ones(currently 0) & x will be 0 only.
2. ones = ones XOR x - ones will get get bit representation of x. (0 ^ x = x)
3. Here is problem as x is in twos and also in ones that's where last 3 lines of code do the magic as x's set bits are the common set bits in twos and ones so both of them will loose bit representation of x i.e. in our case ones and twos will become 0 and that's exactly we want. 

For array[2] i.e. y - Same as step 1 here ones will get the y and will be our answer. 

Hopefully it will make the solution understandable. Ultimately like XOR (in case of 2 element), we wanted an operation "op" which does the same thing, which XOR does on 2 elements, on 3 elements. Something like -

• x op x op x = 0
• 0 op x = x

which is exactly what we have achieved here. 

        public int SingleNumber2(int[] nums)

        {

            int ones = 0;

            int twos = 0;

            foreach(int num in nums)

            {

                twos |= ones & num;

                ones ^= num;

                int notThree = ~(ones & twos);

                ones &= notThree;

                twos &= notThree;

            }

            return ones;

        }