Creating a power set of a Sequence

http://stackoverflow.com/questions/19890781/creating-a-power-set-of-a-sequence

private static List<string> PowerSet(string input)
{
    int n = input.Length;
    // Power set contains 2^N subsets.
    int powerSetCount = 1 << n;
    var ans = new List<string>();

    for (int setMask = 0; setMask < powerSetCount; setMask++)
    {
        var s = new StringBuilder();
        for (int i = 0; i < n; i++)
        {
            // Checking whether i'th element of input collection should go to the current subset.
            if ((setMask & (1 << i)) > 0)
            {
                s.Append(input[i]);
            }
        }
        ans.Add(s.ToString());
    }

    return ans;
}

[Coding Quiz] get all permutations of a given string

        public IEnumerable<string> getAllPermutationsOfString(string input)
        {
            // given a string as input, print out all possible permutations of that string
            // for example: input of "abc" gives six outputs: abc, acb, bac, bca, cba, cab

            if (input == null) throw new ArgumentNullException();

            if (input.Length == 1)
            {
                yield return input;
            }
            else
            {
                for (int i=0; i<input.Length; i++)
                {
                    var remainder = input.Remove(i, 1);
                    foreach (var permus in getAllPermutationsOfString(remainder))
                    {
                        yield return (input[i] + permus);
                    }
                }
            }

        }

[Coding Quiz] Remove certain elements (or duplicate elements) in an arrary or string

        public static void RemoveZero(int[] arr)
        {
            int index = 0;
            for (int j = 0; j < arr.Length; j++)
            {
                if (arr[j] == 0) continue;
                else
                {
                    arr[index] = arr[j];
                    index++;
                }
            }

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

        }

        public static void RemoveExtraSpace(char[] arr)
        {
            int index = 0;
            bool flag = false;      // ???
            for (int j = 0; j < arr.Length; j++)
            {
                if (arr[j] == ' ')
                {
                    if (!flag)
                    {
                        arr[index++] = arr[j];
                        flag = true;
                    }
                    else
                        continue;
                }
                else
                {
                    flag = false;
                    arr[index] = arr[j];
                    index++;
                }
            }

            for (int i = index; i < arr.Length; i++)
                arr[i] = ' ';

        }    

[Coding Quiz] LRU cache (last recently used)

/*
Amazon interview SDET June 2015

Limited size cache

create a limited size cache (Java LRUMap).

    when set, if there is an existing item with the same key. it overwrite the old value.
    when set, if it already reaches its size limit, it remove the oldest item.
    when get, if it does not hit, should return -1, should NOT throw exception.

http://stackoverflow.com/questions/9916189/hashtable-with-limited-size

http://grepcode.com/file/repository.grepcode.com/java/ext/com.google.android/android/4.0.1_r1/android/util/LruCache.java

http://crunchify.com/how-to-create-a-simple-in-memory-cache-in-java-lightweight-cache/
*/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CT.Hash
{
    class Program
    {
        static void Main(string[] args)
        {
        }
    }

    interface ILimitedHashTable<K, V>
    {
        void Set(K k, V v);
        V Get(K k);
    }

    class LimitedHashTable<K, V> : ILimitedHashTable<K, V>
    {
        Dictionary<K, V> dict = new Dictionary<K, V>();

        Queue<K> queue = new Queue<K>();

        const int MAXSIZE = 100;

        public void Set(K k, V v)
        {
            if (dict.ContainsKey(k))
            {
                dict[k] = v;
                return;
            }

            if (dict.Count() >= MAXSIZE)
            {
                dict.Remove(queue.Dequeue());
            }

            dict.Add(k, v);
            queue.Enqueue(k);

        }

        public V Get(K k)
        {
            if (!dict.ContainsKey(k))
                return default(V);

            return dict[k];
        }
    }
}

Solution hints

Array

• random pickup (load balance) - HashTable does not have the attribute to random pickup
• remove element in non-order-required array - remove element in a array does not have to move the following elements if the order does not matter. One way is to swap the element with the ending element in the array.

HashTable

• From a large collection of data, search for element as fast as possible.

[Coding Quiz] Find count of a repeated value in a sorted array

http://www.geeksforgeeks.org/count-number-of-occurrences-in-a-sorted-array/


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodingTest.SortSearch
{
    class Program
    {

        static int count(int[] arr, int x)
        {
            int i;
            int j;

            /* get the index of first occurrence of x */
            i = first(arr, 0, arr.Length - 1, x, arr.Length);

            /* If x doesn't exist in arr[] then return -1 */
            if (i == -1)
                return i;

            /* Else get the index of last occurrence of x. Note that we
                are only looking in the subarray after first occurrence */
            j = last(arr, i, arr.Length - 1, x, arr.Length);

            /* return count */
            return j - i + 1;
        }

        /* if x is present in arr[] then returns the index of FIRST occurrence
           of x in arr[0..n-1], otherwise returns -1 */
        static int first(int[] arr, int low, int high, int x)
        {
            if (high >= low)
            {
                int mid = (low + high) / 2;  /*low + (high - low)/2;*/
                if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x)
                    return mid;
                else if (x > arr[mid])
                    return first(arr, (mid + 1), high, x, n);
                else
                    return first(arr, low, (mid - 1), x, n);
            }
            return -1;
        }


        /* if x is present in arr[] then returns the index of LAST occurrence
           of x in arr[0..n-1], otherwise returns -1 */
        static int last(int[] arr, int low, int high, int x)
        {
            if (high >= low)
            {
                int mid = (low + high) / 2;  /*low + (high - low)/2;*/
                if ((mid == arr.length - 1 || x < arr[mid + 1]) && arr[mid] == x)
                    return mid;
                else if (x < arr[mid])
                    return last(arr, low, (mid - 1), x, n);
                else
                    return last(arr, (mid + 1), high, x, n);
            }
            return -1;
        }

        static void Main(string[] args)
        {
            int[] arr = { 1, 2, 2, 3, 3, 3, 3 };
            int x = 3;

            int c = count(arr, x);
            Console.WriteLine(" {0} occurs {1} times ", x, c);

            Console.Read();
        }
    }
}

C# syntax, system library functions should be memorized

Try to use them if the interviewer allows to do so.

string

Property

• Length

Method

• ToCharArray()
• Remove(index, length)
• IndexOf(c)

Array

Initialization

• // Single-dimensional array (numbers).
  int[] n1 = new int[4] {2, 4, 6, 8};
  int[] n2 = new int[] {2, 4, 6, 8};
  int[] n3 = {2, 4, 6, 8};
  // Single-dimensional array (strings).
  string[] s1 = new string[3] {"John", "Paul", "Mary"};
  string[] s2 = new string[] {"John", "Paul", "Mary"};
  string[] s3 = {"John", "Paul", "Mary"};
  
  // Multidimensional array.
  int[,] n4 = new int[3, 2] { {1, 2}, {3, 4}, {5, 6} };
  int[,] n5 = new int[,] { {1, 2}, {3, 4}, {5, 6} };
  int[,] n6 = { {1, 2}, {3, 4}, {5, 6} };
  
  // Jagged array.
  int[][] n7 = new int[2][] { new int[] {2,4,6}, new int[] {1,3,5,7,9} };
  int[][] n8 = new int[][] { new int[] {2,4,6}, new int[] {1,3,5,7,9} };
  int[][] n9 = { new int[] {2,4,6}, new int[] {1,3,5,7,9} };

Method

• Array.Reverse(arr)
• Array.Sort(arr)

List

Method

• Add()
• AddRange()

HashTable / Dictionary

Property

• Count
• Keys
• Values

Method

• Contains(K)
• ContainsKey(K) (same as Contains)
• ContainsValue(V)

HastSet

Method

• ToArray()

Stack

Property

• Count

Method

• Push()
• Pop()
• Peek()

Queue

Property

• Count

Method

• Enqueue()
• Dequeue()
• Peek()

File Operation

Read file in steam mode

            using (FileStream contents = File.OpenRead(fileName))
            using (StreamReader reader = new StreamReader(contents))
            {
                while (!reader.EndOfStream)
                {
                    Console.WriteLine(reader.ReadLine());
                }
            }

[algorithm][array/string] Reverse word order in a string and get the word count

http://seesharpconcepts.blogspot.com/2012/07/reverse-words-of-given-string-in-place.html

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace WordOrderChange
{
    class Program
    {
        static char[] separators = { ' ' };

        static void Main(string[] args)
        {
            string[] testCases = {
                                    "It is sunny today",                    // regular
                                    "It  is sunny  today2",                 // mutiple spaces.
                                    "abc",                                  // single word
                                    " ",                                    // single space
                                    "          ",                           // multiple spaces
                                    "   I am Paul   ",                      // begin and end with spaces
                                    "It is sunny today. " + Environment.NewLine + "I like it.",        // string with enter
                                    string.Empty,                        
                                    null
                                 };
         
            // ReverseWordOrder1
            // This implementation uses the string.Split().
            // It removes the redundant spaces.
            Console.WriteLine("================= Implementation 1 =====================");
            foreach (var str in testCases)
            {
                int wordCount = 0;
                Console.WriteLine("Orignial string: {0}", str == null ? "null" : str);
                string changed = ReverseWordOrder1(str, out wordCount);
                Console.WriteLine("After reversed: {0}", changed == null ? "null" : changed );
                Console.WriteLine("Word count: {0}", wordCount);
                Console.WriteLine();
            }

            // ReverseWordOrder2
            // This implementation does not use string library fuctions.
            // It keeps the spaces if there are redundant.
            Console.WriteLine("================= Implementation 2 =====================");
            foreach (var str in testCases)
            {
                int wordCount = 0;
                Console.WriteLine("Orignial string: {0}", str == null ? "null" : str );
                string changed = ReverseWordOrder1(str, out wordCount);
                Console.WriteLine("After reversed: {0}", changed == null ? "null" : changed );
                Console.WriteLine("Word count: {0}", wordCount);
                Console.WriteLine();
            }
        }

        // implementation 1
        public static string ReverseWordOrder1(string str, out int wordCount)
        {
            if (str == null)
            {
                wordCount = -1;
                return str;
            }

            string[] strArr = str.Split(separators, StringSplitOptions.RemoveEmptyEntries);

            string output = string.Empty;
            foreach (var s in strArr)
            {
                output = s + " " + output;
            }

            wordCount = strArr.Length;

            return output;
        }

        // implementation 2
        public static string ReverseWordOrder2(string str, out int wordCount)
        {
            if (str == null)
            {
                wordCount = -1;
                return str;
            }

            string output = PartialReverse(str, 0, str.Length-1);

            int begin = 0, end = 0;
            int count = 0;
            bool wordStartedFlag = false;
            while (end < output.Length)
            {
                if (output[end] != ' ' )
                {
                    if (!wordStartedFlag)
                    {
                        begin = end;
                        wordStartedFlag = true;
                    }

                    end++;
                    continue;

                }

                // current char is a space
                if (wordStartedFlag)
                {
   
                    output = PartialReverse(output, begin, end - 1);
                    count++;
   
   
                }

                wordStartedFlag = false;
                end++;
   
   

            }

            if ((begin < end - 1) && (wordStartedFlag))
            {
                output = PartialReverse(output, begin, end - 1);
                count++;
            }

            wordCount = count;

            return output;
        }


        public static string PartialReverse(string str, int begin, int end)
        {
            char[] charArr = str.ToCharArray();

            char temp;
            while (begin <= end)
            {
                temp = charArr[end];
                charArr[end] = charArr[begin];
                charArr[begin] = temp;
                begin++;
                end--;
            }

            return new string(charArr);
        }
    }
}