White Board Coding

White Board coding is a standard part of technical interviews these days. This is a one stop destination for most popular interview problem categories: Linked Lists, Trees, Stacks, Queues, Strings, Arrays, Graphs, Back Tracking, Math, Stats and Dynamic Programming. We aim to provide a platform to discuss the most commonly asked interview questions and provide a solution with detailed analysis of runtime complexity and space complexity.

3 SUM

Problem Statement

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Source: https://leetcode.com/problems/3sum/
Programming Language: C#
Run Time Complexity: O(n^2)

After sorting the input array, 3 three pointers are initialized.
The first pointer goes from index 0 to index end-2.
The 2nd pointers goes from the current element(1st pointer) index + 1
The 3rd pointers goes from the last element in a reverse order.

Two iterations:
1. 1st pointer from 0 to index end-2
2. while (2nd<3rd)

Conditions:
1. if (array[1st]+array[2nd]+array[3rd]==0), get one result
2. if (array[1st]+array[2nd]+array[3rd]>0), 3rd -1
3. if (array[1st]+array[2nd]+array[3rd]<0), 2nd +1

Solution

public IList<IList<int>> ThreeSum(int[] num)
{
    IList<IList<int>> Resultset3Sum = new List<IList<int>>();

    if ((num == null) || (num.Length < 3))
        return Resultset3Sum;

    // sort array
    List<int> numList = num.ToList();
    numList.Sort();

    for (int i = 0; i < numList.Count - 2; i++)
    {
        // //avoid duplicate solutions
        if (i == 0 || numList[i] > numList[i - 1])
        {

            int start = i + 1;
            int end = numList.Count - 1;

            while (start < end)
            {
                //case 1
                if (numList[i] + numList[start] + numList[end] == 0)
                {
                    List<int> temp = new List<int>();
                    temp.Add(numList[i]);
                    temp.Add(numList[start]);
                    temp.Add(numList[end]);

                    Resultset3Sum.Add(temp);
                    start++;
                    end--;
                    
                    //avoid duplicate solutions
                    while (start < end && numList[end] == numList[end + 1])
                        end--;

                    while (start < end && numList[start] == numList[start - 1])
                        start++;                    
                }
                //case 2
                else if (numList[i] + numList[start] + numList[end] < 0)
                {
                    start++;                    
                }
                //case 3
                else
                {
                    end--;
                }
            }
        }
    }
    return Resultset3Sum;
}

Longest Common Prefix

Problem Statement

Write a function to find the longest common prefix string amongst an array of strings.

Source: https://leetcode.com/problems/longest-common-prefix/

Programming Language: C#
Run Time Complexity: if n is the length of shortest string in array of strings and there are m strings in the array. Run time complexity would be O(m*n)

Space Complexity: Constant space

Solution

public string LongestCommonPrefix(string[] strs)
{
    // Input Validation
    if ((strs == null) || (strs.Length <= 0))
        return "";

    // First string in the array of Strings
    string firstString = strs[0];

    // If the length of array of strings is 1 you can return the first string
    if (strs.Length == 1)
        return firstString;
    
    // For all characters in the first string
    for (int index = 0; index < firstString.Length; index++)
    {
        // Index for the string array
        for (int strsIndex = 1; strsIndex < strs.Length; strsIndex++)
        {
            // Condition 1: index should be less than the current string in the array
            // Condition 2: character at index should match with the character of the current string
            if ((index > strs[strsIndex].Length - 1) || (strs[strsIndex][index] != firstString[index]))
                return firstString.Substring(0, index);
        }
    }

    // If first string is ended that is the common prefix 
    return firstString;
}

Roman To Integer

Problem Statement

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999

Programming Language: C#
Run Time Complexity: O(N)
Space Complexity: Constant space
Resources: http://en.wikipedia.org/wiki/Roman_numerals
Source: https://leetcode.com/problems/roman-to-integer/
Solution

public int RomanToInt(string s)
{
    // Input validation
    if (string.IsNullOrEmpty(s))
        return 0;

    // 4:IV, 9:IX, 40:XL, 90:XC, 400:CD, 900:CM,
    // 1:I, 10:X, 100:C, 1000:M
    int output = 0;
    // Prev is previous character in the input string
    char pre = ' ';

    for (int i = 0; i < s.Length; i++)
    {
        if (s[i] == 'M' && pre != 'C') { output += 1000; }
        if (s[i] == 'C' && pre != 'X') { output += 100; }
        if (s[i] == 'X' && pre != 'I') { output += 10; }

        if (s[i] == 'M' && pre == 'C') { output += 800; }
        if (s[i] == 'C' && pre == 'X') { output += 80; }
        if (s[i] == 'X' && pre == 'I') { output += 8; }

        if (s[i] == 'I') { output += 1; }

        if (s[i] == 'V' && pre != 'I') { output += 5; }
        if (s[i] == 'L' && pre != 'X') { output += 50; }
        if (s[i] == 'D' && pre != 'C') { output += 500; }

        if (s[i] == 'V' && pre == 'I') { output += 3; }
        if (s[i] == 'L' && pre == 'X') { output += 30; }
        if (s[i] == 'D' && pre == 'C') { output += 300; }

        pre = s[i];

    }

    // Return output
    return output;
}

Integer to Roman

Problem Statement

Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.

Programming Language: C#
Run Time Complexity: O(N)
Space Complexity: Constant space
Resources: http://en.wikipedia.org/wiki/Roman_numerals
Source: https://leetcode.com/problems/integer-to-roman/

Solution

public string IntToRoman(int num)
{
    // Maintain a mapping of numbers to roman numerals staring from highest numeral
    int[] integer = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
    String[] roman = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
    
    // Output 
    string output = "";

    // Input validation (Num should be in the range of 1-3999)
    if (num <= 0)
        return output;

    for (int index = 0; index < integer.Length; index++)
    {
        int result = num / integer[index];

        // Append the roman numeral equal to the result 
        while (result > 0)
        {
            output += roman[index];
            result--;
        }

        // Continue the processing with the remainder
        num = num % integer[index];
    }

    // return output
    return output;
}

Container With Most Water

Problem Statement

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

Source: https://leetcode.com/problems/container-with-most-water/
Programming Language: C#
Run Time Complexity: O(N)
Space Complexity: Constant space

Analysis:
In order to maximize the area we need to find out the farthest points with maximum possible.

Solution

public int MaxArea(IList<int> height)
{
    // Input validation
    if ((height == null) || (height.Count <= 1))
        return 0;

    // Track maxArea found so far
    int maxArea = Int32.MinValue;
    // Start index 
    int low = 0;
    // End Index
    int high = height.Count - 1;

    // While low is less than high
    while (low < high)
    {
        // Area equal to difference of high and low and min of heigh at that index
        int area = (high - low) * Math.Min(height[low], height[high]);

        // If area is greater than maxArea update
        maxArea = Math.Max(area, maxArea);

        // in an attemt to maximize the area 
        // increment the low if height at low is less than height at high
        if (height[low] < height[high])
            low = low + 1;
        // else decrement high
        else
            high = high - 1;
    }
    return maxArea;
}

Palindrome Number

Problem Statement

Determine whether an integer is a palindrome. Do this without extra space.

Source: https://leetcode.com/problems/palindrome-number/

Programming Language: C#
Run Time Complexity: O(N)(Number of digits in the input)
Space Complexity: Constant space for divider

public bool IsPalindrome(int x)
{
    // Input validation -ve number is not palindrome number
    if (x < 0)    
        return false;    

    // Set divider to 1 
    int divider = 1;

    // While the number of digits in divider is eual to the number of digits of input
    while (x / divider >= 10)
    {
        divider *= 10;
    }

    // While input is not equal to 0
    while (x != 0)
    {
        // Take the right most digit
        int right = x % 10;

        // Take the left most digit
        int left = x / divider;
        
        // Not a palindrome number if left and right digit not match
        if (right != left)        
            return false;
        
        // input equal to mod of divider to get the number skipping left most digit
        x %= divider;
        
        // input divide by 10 to skip the right most digit
        x /= 10;
        
        // divider should be reduced by factor of 100 since right and left most digits are processed
        divider /= 100;
    }

    // Input validated and is palindrome number return true
    return true;
}