Insert Into A Cyclic Sorted List

This question is asked on Programming Praxis. The code in the form of Visual Studio 2010 solution can be downloaded from here.

This is the design of my solution:

While you are looping through the list, these are the various cases (given number refers to the number to be inserted):

1. Current list element <= given number <= next list element : Insert the given number ahead of the current list element
2. Current list element <= next list element <= given number : advance the iterator
3. Current list element <= given number. current list element >= next list element. : Current list element points to list's end and given number is maximum number. Insert the number ahead of the current list element.
4. Current list element >= given number. current list element <= Next list element. iterate till the end of the list
5. Current list element >= next list element. given number <= next list element. Given number is the least number. Insert it after the current list element.
6. Current list element >= given number. Current list element >= next list element. given number > next list element. Advance iterator

Corner cases:
1. pointer to list is null. Make a self referencing node.
2. list has only one elt. Insert the given elt after the list pointer.

Tests:
1. given number > list pointer
 1a. given number belongs to end of list
 1b. given number belongs to a place before end of list

2. given number < list pointer
 2a. given number belongs to start of list
 2b. given number belongs to a place after first element but before current elt

3. All numbers are identical.

*********** SOLUTION CODE ***************************

        /// <summary>
        /// This method adds an int element to a cyclic sorted list of int elements.
        /// </summary>
        /// <param name="element"> Integer element to be inserted </param>
        /// <param name="nodePtr"> Pointer to a node in the cyclic sorted list </param>
        /// <returns>
        /// List of all elements in the list starting from nodePtr.
        /// The return value is really a test hook.
        /// </returns>
        public List<int> AddElementAndGetFullListOfElements(int element, Node nodePtr)
        {
            Node newNode = new Node(element);
            // if list has no node, make newNode the first node and return
            if (null == nodePtr)
            {
                _listPtr = newNode;
                newNode.NextPtr = newNode;
                return GetListOfElements(nodePtr);
            }
            // if list has only one node, insert newNode as the next element
            if (nodePtr.NextPtr.Equals(nodePtr))
            {
                InsertNodeAfterCurrentNode(newNode, nodePtr);
                return GetListOfElements(nodePtr);
            }
            Node currentNode = nodePtr;
            Node nextNode = nodePtr.NextPtr;
            do
            {
                // if currentNode <= newNode <= nextNode : Insert the number
                // ahead of the currentNode
                if (currentNode.Element <= newNode.Element &&
                    newNode.Element <= nextNode.Element)
                {
                    InsertNodeAfterCurrentNode(newNode, currentNode);
                    return GetListOfElements(nodePtr);
                }
                // if currentNode <= newNode. currentNode >= nextNode.
                // currentNode points to list's end.
                // Insert the number ahead of the currentNode.
                if (currentNode.Element >= nextNode.Element &&
                    newNode.Element >= currentNode.Element)
                {
                    InsertNodeAfterCurrentNode(newNode, currentNode);
                    return GetListOfElements(nodePtr);
                }
                // currentNode >= nextNode. newNode <= nextNode.
                // newNode represents the least number. Insert it after the currentNode.
                if (currentNode.Element >= nextNode.Element &&
                    newNode.Element <= nextNode.Element)
                {
                    InsertNodeAfterCurrentNode(newNode, currentNode);
                    return GetListOfElements(nodePtr);
                }
                currentNode = nextNode;
                nextNode = currentNode.NextPtr;
            } while (!currentNode.Equals(nodePtr));
            throw new Exception("Error : Unable to find a place to insert the new element in the list.");
        }
        private void InsertNodeAfterCurrentNode(Node newNode, Node currentNode)
        {
            Node nextNode = currentNode.NextPtr;
            newNode.NextPtr = nextNode;
            currentNode.NextPtr = newNode;
            return;
        }
       
******************* TEST CODE **********************************************
        private static List<int> givenList = new List<int>() { 2, 3, 4, 5, 7 };
       
        /// <summary>
        /// Insert minimum element to the list
        ///</summary>
        [TestMethod()]
        public void AddMinimumElement()
        {           
            CyclicSortedList target = new CyclicSortedList(givenList);
            int elementToInsert = 1;
            Node nodePtr = target.GetXthNode(0);
            List<int> actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);
            List<int> expectedList = new List<int>(givenList);
            expectedList.Add(elementToInsert);
            if (!CheckArrayEquality(expectedList, actualList))
            {
                Assert.Fail("Error : Method returned an unexpected list.");
            }
        }
        /// <summary>
        /// Insert maximum element to the list
        /// </summary>
        [TestMethod]
        public void AddMaximumElement()
        {
            CyclicSortedList target = new CyclicSortedList(givenList);
            int elementToInsert = 10;
            Node nodePtr = target.GetXthNode(0);
            List<int> actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);
            List<int> expectedList = new List<int>(givenList);
            expectedList.Add(elementToInsert);
            if (!CheckArrayEquality(expectedList, actualList))
            {
                Assert.Fail("Error : Method returned an unexpected list.");
            }
        }
        /// <summary>
        /// Insert greater element to the list. Greater element is bigger than the list pointer
        /// but smaller than maximum number in the list.
        /// </summary>
        [TestMethod]
        public void AddGreaterElement()
        {
            CyclicSortedList target = new CyclicSortedList(givenList);
            int elementToInsert = 6;
            Node nodePtr = target.GetXthNode(1);
            List<int> actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);
            List<int> expectedList = new List<int>() { 3, 4, 5, 6, 7, 2 };           
            if (!CheckArrayEquality(expectedList, actualList))
            {
                Assert.Fail("Error : Method returned an unexpected list.");
            }
        }
        /// <summary>
        /// Insert smaller element to the list. Smaller element is smaller than the list pointer
        /// but greater than the smallest number in the list.
        /// </summary>
        [TestMethod]
        public void AddSmallerElement()
        {
            CyclicSortedList target = new CyclicSortedList(givenList);
            int elementToInsert = 6;
            Node nodePtr = target.GetXthNode(4);
            List<int> actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);
            List<int> expectedList = new List<int>() { 7, 2, 3, 4, 5, 6 };
            if (!CheckArrayEquality(expectedList, actualList))
            {
                Assert.Fail("Error : Method returned an unexpected list.");
            }
        }
        /// <summary>
        /// Insert identical element to the list where all elements are identical.        
        /// </summary>
        [TestMethod]
        public void AddIdenticalElement()
        {
            CyclicSortedList target = new CyclicSortedList(new List<int>() { 1, 1, 1, 1, 1 } );
            int elementToInsert = 1;
            Node nodePtr = target.GetXthNode(0);
            List<int> actualList = target.AddElementAndGetFullListOfElements(elementToInsert, nodePtr);
            List<int> expectedList = new List<int>() { 1, 1, 1, 1, 1, 1 };
            if (!CheckArrayEquality(expectedList, actualList))
            {
                Assert.Fail("Error : Method returned an unexpected list.");
            }
        }       

       

Windows cmd script to convert a string to upper case

@echo off
setlocal enableextensions enabledelayedexpansion
set myvar=Jack_and-Jill_went-uP-the_hill.
echo/'myvar' is initially as follows:
echo/[%myvar%]
set UCase=ABCDEFGHIJKLMNOPQRSTUVWXYZ
set LCase=abcdefghijklmnopqrstuvwxyz
for /L %%A in (0,1,24) do Call :ToUpper !LCase:~%%A,1! !UCase:~%%A,1!
echo/
echo/And now that we're done, 'myvar' is as follows:
echo/[%myvar%]
goto :EOF
:ToUpper Low Up
set myvar=!myvar:%1=%2!

C# program to sort number strings

using System;
using System.Collections.Generic;
namespace SortStrings
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] inputArray = {"324", "1", "9001", "-23", "99", "324", "800", "801", "802", "888" };
            Console.WriteLine("Input array is :");
            DisplayArray(ref inputArray);
            QuickSort(ref inputArray, 0, inputArray.Length-1);
            Console.WriteLine("Sorted array is :");
            DisplayArray(ref inputArray);
            Console.ReadKey();
        }
        private static void DisplayArray(ref string[] inputArray)
        {
            foreach (string s in inputArray)
            {
                Console.WriteLine(s);
            }
        }
        private static int Partition(ref string[] inputArray, int startIndex, int endIndex)
        {
            int loopIndex = startIndex;
            int lastIndex = startIndex;
            CompareNumberString c = new CompareNumberString();
            IComparer<string> comparer = (IComparer<string>)c;
            while (loopIndex < endIndex)
            {
                if (comparer.Compare(inputArray[loopIndex], inputArray[endIndex]) < 0)
                {
                    swap(ref inputArray, loopIndex, lastIndex);
                    lastIndex++;
                }
                loopIndex++;
            }
            swap(ref inputArray, endIndex, lastIndex);
            return lastIndex;
        }
        private static void QuickSort(ref string[] inputArray, int startIndex, int endIndex)
        {
            if (startIndex >= endIndex)
            {
                return;
            }       
            int pivotIndex = Partition(ref inputArray, startIndex, endIndex);
            QuickSort(ref inputArray, startIndex, pivotIndex - 1);
            QuickSort(ref inputArray, pivotIndex + 1, endIndex);
            return;
        }
        private static void swap(ref string[] inputArray, int index1, int index2)
        {
            string temp = inputArray[index1];
            inputArray[index1] = inputArray[index2];
            inputArray[index2] = temp;
        }
    }
}

String comparison in C#

Comparing programmatic strings (these are never exposed to the end user)
String.Compare(string1, string2, StringComparison.OrdinalIgnoreCase)

Comparing strings that end user can see:
String.Compare(string1, string2, StringComparison.CurrentCultureIgnoreCase)

Reverse a string in C#

        static void way1(string testString)
        {
            Console.WriteLine("Way 1 ------------>");
            StringBuilder reverseString = new StringBuilder(testString.Length);
            for (int i = testString.Length - 1; i >= 0; i--)
            {
                reverseString.Append(testString[i]);
            }
            Console.WriteLine(reverseString.ToString());
        }

        static void way2(string testString)
        {
            Console.WriteLine("Way 2 ------------>");
            char []temp = testString.ToCharArray();
            Array.Reverse(temp);
            string reverseString = new string(temp);
            Console.WriteLine(reverseString);
        }

        static void way3(string testString)
        {
            Console.WriteLine("Way 3 ------------>");
            String reverseString = String.Empty;
            for (int i = testString.Length - 1; i >= 0; i--)
            {
                reverseString += testString[i];
            }
            Console.WriteLine(reverseString);
        }

DataBase Caching

Recently I went to interview for a Software Developer position. I was asked this interesting question:

Given a database and an API to fetch a record from a database, design a datastructure to implement the cache. Also, design and implement the API used to fetch record from the cache.

My Solution:
Access source code here
You need Visual Studio 2010 to open the solution
The solution is coded in C

Data Structures

All records are stored in a Hash Table for fast access

At any point in time if the cache is full, Least Recently Used record is kicked out to give space to the new record. To keep track of the records in the order of their last access time, the records are also maintained as double linked list.

// represents cache record

struct cacheRec

{

    struct rec * databaseRec;

    struct cacheRec * prevRec;

    struct cacheRec * nextRec;

    bool valid;

};

struct cacheRec HashTable[CACHESIZE];

// pointer to the oldest record in the linked list

struct cacheRec * oldestCacheRec;

// pointer to the newest record in the linked list

struct cacheRec * newestCacheRec;

Time Complexity

Hash table provides lookup in O(1) time. If record is not present in the cache, reading it from database and inserting it in the end of the linked list (thereby making it the newest record) can be done in constant time. If cache is full, deleting record from cache, before inserting the new record, is also achieved in constant time. If record is present in the cache, deleting it from its current location in the linked list and inserting it in the end of the list, can also be done in O(1) time. Thus total time taken by FetchRecord() API is O(1).

Space complexity

If size of cache is n, algorithm takes O(n) space for hash tables and O(n) space for linked list pointers. Thus total space complexity is O(n)

Test Cases

The console app invokes following test cases. Each test case displays PASS/FAIL based on the number of expected Cache and Database hits

1.       Call FetchRecord() with invalid key

2.       Fetch records while re-fetching oldest record in the cache

3.       Fetch records while re-fetching newest record in the cache

4.       Fetch records while re-fetching a record in the middle of the cache linked list

5.       Fetch higher than cache-size number of unique records

6.       Fetch higher than cache-size number of non-unique records