Number Operation

Give an array with 1 to N except 1 number. Find the missing number.

public static int FindMissingNumber(int[] a)
{
    if (a == null || a.Length <= 1)
        return 0;

    int sum = 0;
    for (int i = 0; i < a.Length; i++)
        sum = sum ^ a[i] ^ (i+1);

    return sum ^ (a.Length+1);
}

This solution is better:

a ={1,3}   Missing 2

using XOR characteristic when XOR same= number it will become 0 :  A XOR A = 0.

1st pass : 1 XOR 1 = 0

001 XOR 001 = 000

2nd pass : 0 XOR 3 XOR 2 = 1        

000 XOR 011 XOR 010 = 001

Final : 1 XOR 3 = 2

001 XOR 011 = 010

* Avoid using n*(n+1)/2 – sum approach as this will introduce overflow for integer data type.

String Operation

Naive / Brute Force

public static bool NaiveFindString(string text, string pattern)
{
    if (string.IsNullOrEmpty(text)
        || string.IsNullOrEmpty(pattern)
        || text.Length < pattern.Length)
        return false;

    for (int i = 0; i <= text.Length - pattern.Length; i++)
        if (text.Substring(i, pattern.Length) == pattern)
            return true;

    return false;
}

 

public static bool NaiveFindStringV2(string text, string pattern)
{
    if (string.IsNullOrEmpty(text)
        || string.IsNullOrEmpty(pattern)
        || text.Length < pattern.Length)
        return false;

    for (int i = 0; i <= text.Length - pattern.Length; i++)
    {
        int c = 0;

        while (c < pattern.Length && pattern[c] == text[i + c])
            c++;

        if (c == pattern.Length)
            return true;
    }

    return false;
}

Boyer Moore

public static int[] BuildBadChar(string pattern)
{
    int[] badCharMoves = new int[256]; // ASCII

    for (int i = 0; i < badCharMoves.Length; i++)
        badCharMoves[i] = -1;

    for (int i = 0; i < pattern.Length; i++)
        badCharMoves[pattern[i]] = i;

    return badCharMoves;
}

public static bool BoyerMooreFindString(string text, string pattern)
{

    if (string.IsNullOrEmpty(text)
            || string.IsNullOrEmpty(pattern)
            || text.Length < pattern.Length)
        return false;

    int[] badCharMoves = BuildBadChar(pattern);

    for (int i = 0; i <= text.Length - pattern.Length;)
    {
        int count= pattern.Length - 1;
        char ch = char.MinValue;
        while (count >=0 && pattern[count] == (ch=text[i + count]))
            count--;

        if (count < 0)
            return true;

        i = i + Math.Max(count - badCharMoves[ch],1);
    }

    return false;

}

Remove duplicates

public static string RemoveDuplicate(string text)
{
    if (string.IsNullOrEmpty(text) || text.Length == 1)
        return text;

    char[] s = text.ToCharArray();
    int tail = 1;

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

        int m = 0;

        for (; m < tail; m++)
            if (s[m] == s[i])
                break;

        if (tail == m)
        {
            s[tail] = s[i];
            tail++;
        }
    
    }

    StringBuilder sb = new StringBuilder(tail - 1);

    for (int i = 0; i < tail; i++)
        sb.Append(s[i]);

    return sb.ToString();
}

Reverse a string

public static string Reverse(string text)
{
    if (string.IsNullOrEmpty(text) || text.Length == 1)
        return text;

    int first = 0;
    int last = text.Length - 1;

    char[] s = text.ToCharArray();

    while (first < last)
    {
        char c = s[first];
        s[first] = s[last];
        s[last] = c;

        first++;
        last--;
    }

    return new string(s);

}