Interview Question Categories
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
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
//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));
}
}
}
