Interview Question Categories

Longest Consecutive sequence of Numbers

Longest Consecutive sequence


//Longest Consecutive sequence
//Ex: If arr = {1, 5, 2, 6, 7, 9, 10, 4 }
//Longest Consecutive sequence = {4,5,6,7}
namespace longestConsecutiveSequence
{
    class Program
    {
        static int[] longestConsecutiveSequence(int[] arr)
        {
            Dictionary<int, int> table = new Dictionary<int, int>();
            int length = 0;
            int first = int.MaxValue;

            foreach (int i in arr)
            {
                //If i has already been encountered and is in table
                //then continue with next number
                if (!table.ContainsKey(i))
                {
                    int start = i;
                    int end = i;
                    //Checking if i+1 has already been encountered
                    //If so add i to the existing range in the table.
                    if (table.ContainsKey(i + 1) && table[i + 1] >= i + 1)
                    {
                        end = table[i + 1];
                        table.Remove(i + 1);
                        table.Remove(end);
                    }
                    //Checking if i-1 has already been encountered
                    //If so add i to the existing range in the table.
                    if (table.ContainsKey(i - 1) && table[i - 1] <= i - 1)
                    {
                        start = table[i - 1];
                        table.Remove(i - 1);
                        table.Remove(start);
                    }
                    //Update the table with newly found range
                    table[start] = end;
                    table[end] = start;

                    //Update the longest range found so far.
                    if (end - start + 1 > length)
                    {
                        first = start;
                        length = end - start + 1;
                    }
                }
            }

            int[] s = new int[length];
            for (int i = 0; i < length; i++) s[i] = first + i;
            return s;
        }

        static void Main(string[] args)
        {
            int[] arr = { 1, 5, 2, 6, 7, 9, 10, 4 };

            int[] longestSeq = longestConsecutiveSequence(arr);
        }
    }
}

FIND NEXT HIGHER NUMBER WITH SAME DIGITS

FIND NEXT HIGHER NUMBER WITH SAME DIGITS


namespace FindNextHigherNumWitSameDigits
{
    class Program
    {
        public static int[] IntToIntArr(int Num)
        {
            int r = 0;
            List<int> li = new List<int>();
            while (Num > 0)
            {
                r = Num % 10;
                li.Add(r);
                Num = Num / 10;
            }
            li.Reverse();
            return li.ToArray();
        }

        public static int IntArrToInt(int[] NumArr)
        {
            int Num = 0;
            for (int i = 0; i< NumArr.Length; i++)
            {
                Num = Num * 10 + NumArr[i];
            }
            return Num;
        }

        public static int GetNextHigherNumWitSameDigits(int Num)
        {
            if (Num < 10) return Num;

            int[] NumArr = IntToIntArr(Num);
            int prev = NumArr[NumArr.Length - 1];

            int i = NumArr.Length - 2;

            //Find the first number which is smaller than the prev 
            //number travelling from rear end
            for (; i >= 0; i--)
            {
                if (prev > NumArr[i]) 
                {
                    break;
                }
                prev = NumArr[i];
            }

            if (i == -1) return Num;

            int smallIndex = i+1;

            //Find the smallest number greater than 'NumArr[i]' towards 
            //right of 'NumArr[i]'.
            for (int j = i+2; j < NumArr.Length; j++)
            {
                if (NumArr[j] > NumArr[i] && NumArr[j] < NumArr[smallIndex])
                    smallIndex = j;
            }
            
            int temp = NumArr[smallIndex];
            NumArr[smallIndex] = NumArr[i];
            NumArr[i] = temp;
            Array.Sort(NumArr, i + 1, NumArr.Length - i - 1);
            return IntArrToInt(NumArr);
            
        }

        static void Main(string[] args)
        {
            Console.WriteLine(GetNextHigherNumWitSameDigits(12354));
        }
    }
}

LONGEST PALINDROME IN A STRING

LONGEST PALINDROME IN A STRING

//Idea : Start from a character and explore the chars 
//towards left and right simultaneously.
//Complexiety : O(n2)

namespace LongestPalindrome
{
    class Program
    {
        static string LongestPalindromeImproved(String Str)
        {
            char[] strchr = Str.ToCharArray();
            int left;
            int right;
            int LongestStart = 0;
            int LongestEnd = 0;

            for (int mid = 1; mid < strchr.Length; mid++)
            {
                //To find palindrome of odd length
                left = mid;
                right = mid;

                while (left >= 0 && right < strchr.Length)
                {
                    if (strchr[left] == strchr[right])
                    {
                        if (right - left > LongestEnd - LongestStart)
                        {
                            LongestStart = left;
                            LongestEnd = right;
                        }
                        left--;
                        right++;
                    }
                    else break; 
                }

                //To find palindrome of Even length
                left = mid-1;
                right = mid;

                while (left >= 0 && right < strchr.Length)
                {
                    if (strchr[left] == strchr[right])
                    {
                        if (right - left > LongestEnd - LongestStart)
                        {
                            LongestStart = left;
                            LongestEnd = right;
                        }
                        left--;
                        right++;
                    }
                    else break; 
                }
            }

            if (LongestEnd - LongestStart > 0)
                return new string(strchr, LongestStart, LongestEnd - LongestStart + 1);
            else return "";
        }

        
        static void Main(string[] args)
        {
            String str = "qweert";
            Console.WriteLine(LongestPalindromeImproved(str));
        }
    }
}