Implement Two stacks using one array

Problem: How to implement/code two stacks using one array.

Solution: The obvious solution is to have the two stacks at the two ends of the array. The stacks will grow in opposite direction. When the two stacks collide and there is no more room in the array the stacks will over flow. This problem is probably one of the easier problems and targeted towards exercising your array index manipulation skills. See the figure below for a visual representation of the two stacks in the array.



Code (C#):

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

namespace Array2Stacks
{
    /// 

    /// DualStack class implements 2 stacks in a single array.
    /// Stack A starts on the right and increases towards the left
    /// Stack B starts on the left and increases towards the right
    /// When both stacks meet there is no more room for adding items
    /// The cool thing about the dual stack is that both stacks share the
    /// same array with built in collision detection. If one stack was empty
    /// the other stack can potentially use the entire array.
    /// 
    public class DualStack
    {
        int size = 50; //default array size
        int stackATop = -1;
        int stackBTop = 50;

        public DualStack(int size)
        {
            this.size = size;
            array = new object[this.size];
            stackBTop = size;
        }

        //one array to hold the two stacks
        object[] array = null;
 
        //pushes an item on stack A
        public bool PushStackA(object obj)
        {
            if (stackATop < stackBTop - 1) //we have at least one empty slot in the array
            {
                array[++stackATop] = obj;
                return true;
            }
            else
            {
                //return false if stack is full
                return false;   
            }
        }

        //pops an item from stack A
        public object PopStackA()
        {
            if (stackATop >= 0 && stackATop < stackBTop)
            {
                //take the element at the top of the stack
                object obj = array[stackATop]; 
                stackATop--;//decrement stack top pointer
                return obj;
            }
            return null;
        }

        /// pushes an item on stack B
        public bool PushStackB(object obj)
        {
            if (stackBTop > stackATop + 1) //we have at least one empty slot between the stacks
            {
                array[--stackBTop] = obj;
                return true;
            }
            else
            {
                //stack is full
                return false;
            }
        }

        public object PopStackB()
        {

            if (stackBTop < this.size && stackBTop > stackATop) //stack is not empty
            {
                object obj = array[stackBTop];
                stackBTop++;
                return obj;
            }
            else
            {   //stack is empty
                return null;
            }
        }
    }
}

Determine and display all anagrams in a string array

Question: Given an array of strings (string[] inputStrings). Devise a way and write the code to determine and display all the anagrams in the array.

Solution: With any interview question one should get the specifics of the problem and the input data before designing the solution. In this particular case, we should ask about the approximate number of strings in the array, average length of each string, memory constraints, CPU usage constraints, etc. Each factor can influence the design and selection of algorithm and the data structures used.

The solution I am presenting here optimizes for speed at the cost of extra memory. The basic idea is to come up with simple hash or signature for each string in the input string array. This signature is nothing but the characters in the string sorted alphabetically. So, the signature for "cat" will be "act" and for "tac" it will be "act" too. As you can see the signature is the same for 2 strings that are anagrams. We can use this property to identify and collect the anagrams in the inputString array together. We can use a hash table for fast insert and retrieve these anagrams, but will cost us extra memory.

Note: There are other solutions that don't use a hashtable, but involves CPU cost is higher and involves sorting of the signature. I will post this alternative solution soon. If you have a better method, please write a comment.

Pseudo-Code:

Loop for each string (S) in the array:

1. Get signature (K) for S (sort the characters of S to get its signature (K))
2. Insert S in hash table with signature K as the key and append S to the array list contained in the value of the hash table key.
3. If K already exists, don't add a new key (since it will cause collision), but just append S to the end of the list in that hash table slot.
4. Goto step 1 with next available string.
5. In the end just print all the keys in the hash table along with the list of strings in each slot.

Code (C#): I am avoiding use of generics here for convenience of users of other languages.

using System;
using System.Text;
using System.Collections;

namespace anagram_problem
{
   class Program
   {
       static void Main(string[] args)
       {
           string[] inputStrings = new string[] { "cat", "tac", "army", "pam", "act", "map", "mary", "self" };
           PrintAnagrams(inputStrings);
       }

       //
       // given a set of strings group all the strings that are anagrams
       // "cat", "tac", "army", "pam", "act", "map", "mary", "self"
       // "act": "act", "cat", "tac"
       // "army": "army", "mary"
       // "map": "map", "pam"
       // "self": "self"
       
       static void PrintAnagrams(string[] inputStrings)
       {
           Hashtable hashTable = new Hashtable();
           foreach (string str in inputStrings)
           {
               string signature = GetAnagramSignature(str);
               if (!hashTable.ContainsKey(signature))
               {
                   // this will be used to store our anagrams for this particular signature
                   ArrayList newStringList = new ArrayList();
                   newStringList.Add(str);

                   hashTable.Add(signature, newStringList);
               }
               else
               {
                   // we have already encountered this signature so we just
                   // need to append the current str to the list
                   ArrayList list = (ArrayList)hashTable[signature];
                   list.Add(str);
               }
           }

           // now we print all the anagrams for each hash key
           foreach (string key in hashTable.Keys)
           {
               Console.Write("{0}: ", key);
             
               ArrayList list = (ArrayList)hashTable[key];
               foreach (string str in list)
               {
                   Console.Write("{0},", str);
               }
               Console.Write(Environment.NewLine);
           }
       }

       //
       // this method will sort the characters in the input string alphabetically
       // this sorted string will be out hash key
       //
       static string GetAnagramSignature(string input)
       {
           char[] charArray = input.ToLower().ToCharArray();
           Array.Sort<char>(charArray, new Comparison<char>(CompareCharacters));
           return new string(charArray);
       }

       static int CompareCharacters(char a, char b)
       {
           if (a > b)
               return 1;
           else if (b > a)
               return -1;
           else
               return 0;
       }
   }
}