Interview Algorithm Problems

 Here are implementations for a few common algorithms in C#:

Reverse a String

Reversing a string is the technique that reverses or changes the order of a given string so that the last character of the string becomes the first character of the string and so on.

static string ReverseString(string s)
{
    char[] charArray = new char[s.Length];
    for (int i = 0; i < s.Length; i++)
    {
        charArray[i] = s[s.Length - 1 - i];
    }
    return new string(charArray);
}

Check for Anagrams

An anagram of a string is another string that contains the same characters, only the order of characters can be different.

static bool AreAnagrams(string s1, string s2)
{
    if (s1.Length != s2.Length)
        return false;

    var charCount = new int[256]; // Assuming ASCII characters

    foreach (char c in s1)
        charCount[c]++;

    foreach (char c in s2)
    {
        if (charCount[c] == 0)
            return false;
        charCount[c]--;
    }

    return true;
}

Remove Duplicates

Remove duplicates from a given string using char frequency.

static string RemoveDuplicates(string s)
{
    var charSet = new HashSet<char>();
    var result = new StringBuilder();

    foreach (char c in s)
    {
        if (!charSet.Contains(c))
        {
            charSet.Add(c);
            result.Append(c);
        }
    }

    return result.ToString();
}

Palindrome Check

A string is said to be palindrome if it remains the same on reading from both ends.

static bool IsPalindrome(string s)
{
    int left = 0;
    int right = s.Length - 1;

    while (left < right)
    {
        if (s[left] != s[right])
            return false;
        left++;
        right--;
    }

    return true;
}

 
 String Compression


static string CompressString(string s)
{
    if (string.IsNullOrEmpty(s))
        return s;

    StringBuilder compressed = new StringBuilder();
    int countConsecutive = 0;

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

        // If next character is different than current, append this char to result
        if (i + 1 >= s.Length || s[i] != s[i + 1])
        {
            compressed.Append(s[i]);
            compressed.Append(countConsecutive);
            countConsecutive = 0;
        }
    }

    // Return the original string if compressed string is not smaller
    return compressed.Length < s.Length ? compressed.ToString() : s;
}

Min Flip Sequence of binary string to completly flip string

static int MinFlips(string s)
{
    if (string.IsNullOrEmpty(s))
        return 0;

    int count0 = 0; // Number of contiguous sequences of '0's
    int count1 = 0; // Number of contiguous sequences of '1's

    // Count the first sequence
    if (s[0] == '0')
        count0++;
    else
        count1++;

    // Iterate through the string and count sequences
    for (int i = 1; i < s.Length; i++)
    {
        if (s[i] != s[i - 1])
        {
            if (s[i] == '0')
                count0++;
            else
                count1++;
        }
    }

    // Return the minimum of the counts
    return Math.Min(count0, count1);
}

Multiply Strings

 int MultiplyStrings(string s1, string s2)
{
    int m = s1.Length;
    int n = s2.Length;

    // Initialize result variable to store the final multiplication result
    int finalResult = 0;

    // Multiply each digit and accumulate results
    for (int i = m - 1; i >= 0; i--)
    {
        for (int j = n - 1; j >= 0; j--)
        {
            int digit1 = s1[i] - '0';
            int digit2 = s2[j] - '0';

            // Calculate the position to add the product
            int position = (m - 1 - i) + (n - 1 - j);

            // Multiply and accumulate into finalResult
            finalResult += digit1 * digit2 * (int)Math.Pow(10, position);
        }
    }

    return finalResult;
}

Print last n lines of a big file or big string.

static void PrintLastLines(string fileName, int n)
{
    LinkedList<string> lines = new LinkedList<string>();
    using (FileStream fs = new FileStream(fileName, FileMode.Open, FileAccess.Read))
    {
        using (StreamReader sr = new StreamReader(fs))
        {
            string line;
            while ((line = sr.ReadLine()) != null)
            {
                lines.AddLast(line);
                if (lines.Count > n)
                    lines.RemoveFirst(); //remove first line.
            }
        }
    }
    foreach (string line in lines)
        Console.WriteLine(line);
}

Valid Parentheses

bool IsValid(string s)
{

    if (s.Length % 2 != 0)
    {
        return false;
    }

    Stack<char> braces = new Stack<char>();
    foreach (char ch in s)
    {

        if (braces.Count == 0)
        {
            braces.Push(ch);
            continue;
        }

        if (ch == ')' && braces.Peek() == '(')
        {
            braces.Pop();
        }
        else if (ch == '}' && braces.Peek() == '{')
        {
            braces.Pop();
        }
        else if (ch == ']' && braces.Peek() == '[')
        {
            braces.Pop();
        }
        else
        {
            braces.Push(ch);
        }

    }

    return braces.Count == 0;
}

Max N numbers string sum

static string FindLargestNumber(int N, int sum)
{
    if (sum == 0 && N == 1)
        return "0";
    if (sum == 0 || sum > 9 * N)
        return "-1"; // Not possible to form such number

    char[] result = new char[N];

    for (int i = 0; i < N; i++)
    {
        if (sum >= 9)
        {
            result[i] = '9';
            sum -= 9;
        }
        else
        {
            result[i] = (char)(sum + '0');
            sum = 0;
        }
    }

    return new string(result);
}

Contains Duplicate

bool ContainsDuplicate(int[] nums)
{
    for (int i = 0; i < nums.Length; i++)
    {
        for (int j = i + 1; j < nums.Length; j++)
        {
            if (nums[i] == nums[j])
            {
                return true;
            }
        }
    }
    return false;
}

Maximum Subarray

int MaxSubArray(int[] nums)
{
    int maxCurrent = nums[0];
    int maxGlobal = nums[0];

    for (int i = 1; i < nums.Length; i++)
    {
        maxCurrent = Math.Max(nums[i], maxCurrent + nums[i]);
        if (maxCurrent > maxGlobal)
        {
            maxGlobal = maxCurrent;
        }
    }
    return maxGlobal;
}

Move Zeroes

void MoveZeroes(int[] nums)
{
    int lastNonZeroFoundAt = 0;
    for (int i = 0; i < nums.Length; i++)
    {
        if (nums[i] != 0)
        {
            nums[lastNonZeroFoundAt++] = nums[i];
        }
    }
    for (int i = lastNonZeroFoundAt; i < nums.Length; i++)
    {
        nums[i] = 0;
    }
}

Remove Duplicates

int RemoveDuplicates(int[] nums)
{
    if (nums.Length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.Length; j++)
    {
        if (nums[j] != nums[i])
        {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

Flatten

static List<object> FlattenList(IEnumerable nestedList)
{
    List<object> result = new List<object>();

    foreach (var item in nestedList)
    {
        if (item is IEnumerable && !(item is string))
        {
            result.AddRange(FlattenList((IEnumerable)item));
        }
        else
        {
            result.Add(item);
        }
    }

    return result;

Number To Text

public class NumberToText
{
    private static string[] unitsMap = { "Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen" };
    private static string[] tensMap = { "Zero", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety" };

    public static string ConvertNumberToText(int number)
    {
        if (number == 0)
            return unitsMap[0];

        if (number < 20)
            return unitsMap[number];

        if (number < 100)
            return tensMap[number / 10] + ((number % 10 > 0) ? " " + ConvertNumberToText(number % 10) : "");

        if (number < 1000)
            return unitsMap[number / 100] + " Hundred" + ((number % 100 > 0) ? " " + ConvertNumberToText(number % 100) : "");

        if (number < 100000)
            return ConvertNumberToText(number / 1000) + " Thousand" + ((number % 1000 > 0) ? " " + ConvertNumberToText(number % 1000) : "");

        return ConvertNumberToText(number / 100000) + " Lac" + ((number % 100000 > 0) ? " " + ConvertNumberToText(number % 100000) : "");
    }
}

Divide Number

static void DivideNumber(int n)
{
    if (n >= 10)
    {
        DivideNumber(n / 10);
    }
    Console.WriteLine(n / 10);
}

If we call above code with input 274 then output would be: 0,2,27

Reverse Number

static int Reverse(int x) {
    long result = 0;
    while (x != 0) {
        result = result * 10 + x % 10;
        x /= 10;
        if (result > Int32.MaxValue || result < Int32.MinValue) {
            return 0;
        }
    }
    return (int)result;
}

Duplicate Characters

static string Duplicates(string s)
{
    var charSet = new char[256];
    var result = new StringBuilder();

    foreach (char c in s)
    {
        charSet[c]++;
    }

    for (int i = 0; i < charSet.Length; i++)
    {
        if (charSet[i] > 1)
        {
            result.Append((char)i);

        }
    }

    return result.ToString();
}

Get String chracters count

["a"," b", "b", "c", "c"," c" ]

["a","1","b","2","c","3"]

static char[] CharactersCount(char[] arr)
{

    var CountArray = new char[256];
    var result = new StringBuilder();
    for (int i = 0; i < arr.Length; i++)
    {
        CountArray[arr[i]]++;
    }

    for (int j = 0; j < CountArray.Length; j++)
    {
        if (CountArray[j] > 0)

        {
            result.Append((char)j); // add character
            result.Append((int)CountArray[j]); // add character count 
        }
    }

    return result.ToString().ToArray();
}

Concatenate two Strings

str1 = "abc" st2="pqr" o/p - apbqcr
str1 = "abcd" st2="pq" o/p - apbqcd
str1 = "ab" st2="pqrs" o/p - apbqrs

static string ConcateStrings(string s1, string s2)
{

    int i = 0;
    int j = 0;
    var result = new StringBuilder(s1.Length + s2.Length);

    while (i < s1.Length && j < s2.Length)
    {
        result.Append(s1[i]);
        result.Append(s2[j]);
        i++;
        j++;
    }

    // Add remaning characters of s1 string if any
    for (; i < s1.Length; i++)
    {
        result.Append(s1[i]);
    }

    // Add remaning characters of s2 string if any
    for (; j < s2.Length; j++)
    {
        result.Append(s2[j]);
    }

    return result.ToString();
}

To be Continued...