Interview Question Categories

Mth to last element

Mth to last element 


/*Write a program to determine the Mth to last element of a list.   
 * The first argument will be a path to a filename containing a series 
 * of space delimited characters followed by an integer representing a 
 * index into the list (1 based), one per line. 
 * 
 * Print to stdout, the Mth element from the end of the list, one per line. 
 * If the index is larger than the list size, ignore that input. E.g.
 * 
 * E.g. 
 * a b c d 4
 * e f g h 2
 * Output sample:
 * a
 * g
 */

namespace MthToLastElement
{
    class Node
    {
        public char data { get; set; }
        public Node next = null;

        public Node(char ch)
        {
            data = ch;
            next = null;
        }
    }

    class CharLinkedList
    {
        private Node Start;
        private Node CurrentEnd;
        public int Length { get; set; }

        public CharLinkedList()
        {
            Start = null;
            CurrentEnd = null;
            Length = 0;
        }

        public void AddRear(char ch)
        {
            Node newNode = new Node(ch);

            if (Start == null)
            {
                Start = CurrentEnd = newNode;
                Length++;
                return;
            }
            CurrentEnd.next = newNode;
            CurrentEnd = CurrentEnd.next;
            Length++;
        }

        public char GetMthCharFromLast(int M)
        {
            Node first = null;
            Node second = null;

            first = second = Start;

            int i = 0;
            
            //Move the first pointer M positions ahead.
            while (i < M && first != null)  
            {
                first = first.next;
                i++;
            }
            
            //If list end has been reached without moving M positions ahead then no solution.
            if (first == null && i != M) return '\0';   

            // Move both first and second pointers together ahead untill list end is reached.
            while (first != null)       
            {
                first = first.next;
                second = second.next;
            }

            //Return the char pointed by second pointer.
            return second.data;     
        }
    }

    class Program
    {
        const char SPACE = ' ';

        static int PrepareListAndReturnMValue(String inputList, CharLinkedList charList)
        {

            for (int i=0;i<inputList.Length;i++)
            {
                if (char.IsLetter(inputList[i]))
                {
                    charList.AddRear(inputList[i]);
                }
                else if (inputList[i] == SPACE)
                {
                    continue;
                }
                else if (char.IsDigit(inputList[i]))
                {
                    return int.Parse(inputList.Substring(i));
                }
            }
            return 0;
        }

        static void Main(string[] args)
        {
            CharLinkedList charList = null;
            String line = null;
            int M;
            char MthChar = '\0';
           
            try
            {
                FileInfo file = new FileInfo(args[0]);
                StreamReader reader = file.OpenText();      //Open the file

                while ((line = reader.ReadLine()) != null)   //Read each line in the file. 
                {
                    charList = new CharLinkedList();
                    M = PrepareListAndReturnMValue(line, charList);
                    MthChar = charList.GetMthCharFromLast(M);
                    if (MthChar != '\0')
                    {
                        Console.WriteLine(MthChar);
                    }
                }

                reader.Close();         //Close the reader
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
                Console.WriteLine(e.StackTrace);
            }
        }
    }
}

No comments:

Post a Comment