SORTING
2. Bubble Sort
3. Topological Sorting
4. Radix Sorting
5. FUZZY SORT
Array related Questions
1. Longest Consecutive sequence of Numbers
2. Stacks using Queues
3. FIND NEXT HIGHER NUMBER WITH SAME DIGITS
4. LONGEST PALINDROME IN A STRING
5. FIND FIRST REPEATED STRING WITH 3 CHARS
6. FIND REPEATED AND MISSING NUMBERS IN AN ARRAY
7. FIND GIVEN PATTERN AND REPLACE IT WITH GIVEN STRING
8. FIND AND ELIMINATE DUPLICATES IN AN ARRAY
9. FIND 4 NUMS IN ARRAY WHOSE SUM EQUALS GIVEN NUM
10. FIND 3 INTS WHOSE PRODUCT IS THE LARGEST IN THE LIST
11. FIND 2 ODD OCCURING INTS IN AN ARRAY
12. FIND 0s AND 1s INTERFACE
13. DETECT DUPLICATE PARENTHESES IN AN EXPRESSION
14. SUM OF PREVIOUS SMALLER NUMBERS IN ARRAY
15. COUNT MAX NUMBER OF CONNECTED 1s IN A MATRIX
16. COUNT 1s in BINARY FORMAT OF A NUMBER
17. Mth to last element
18. CHARACTER COUNTING
19. ROTATE AN ARRAY BY N PLACES IN O(n)
20. STOCK QUOTE PROBLEM
21. PRINT SUB MATRIX WITH EQUAL NUMBER OF 0s AND 1s
22. SUM OF FIBONACCI SEQUENCE
23. B[i] = C[j] - A[k]
24. TRAVERSE THE ARRAY IN SHORTEST NUMBER OF HOPS
22. BITWISE STORAGE
23. CONVERT A NUMBER FROM BASE2 TO BASE4
24. arr[i] = arr[arr[i]] in place
25. GREATEST CONTIGUOUS SUM
26. THREE STRINGS INTERLEAVED PROBLEM
27. MAX APPLES THAT CAN BE COLLECTED IN 2D MATRIX
28. Add 2 Binary Numbers Represented As Strings
29. [a1,a2,a3,b1,b2,b3] to [a1,b1,a2,b2,a3,b3] in Place
2. Stacks using Queues
3. FIND NEXT HIGHER NUMBER WITH SAME DIGITS
4. LONGEST PALINDROME IN A STRING
5. FIND FIRST REPEATED STRING WITH 3 CHARS
6. FIND REPEATED AND MISSING NUMBERS IN AN ARRAY
7. FIND GIVEN PATTERN AND REPLACE IT WITH GIVEN STRING
8. FIND AND ELIMINATE DUPLICATES IN AN ARRAY
9. FIND 4 NUMS IN ARRAY WHOSE SUM EQUALS GIVEN NUM
10. FIND 3 INTS WHOSE PRODUCT IS THE LARGEST IN THE LIST
11. FIND 2 ODD OCCURING INTS IN AN ARRAY
12. FIND 0s AND 1s INTERFACE
13. DETECT DUPLICATE PARENTHESES IN AN EXPRESSION
14. SUM OF PREVIOUS SMALLER NUMBERS IN ARRAY
15. COUNT MAX NUMBER OF CONNECTED 1s IN A MATRIX
16. COUNT 1s in BINARY FORMAT OF A NUMBER
17. Mth to last element
18. CHARACTER COUNTING
19. ROTATE AN ARRAY BY N PLACES IN O(n)
20. STOCK QUOTE PROBLEM
21. PRINT SUB MATRIX WITH EQUAL NUMBER OF 0s AND 1s
22. SUM OF FIBONACCI SEQUENCE
23. B[i] = C[j] - A[k]
24. TRAVERSE THE ARRAY IN SHORTEST NUMBER OF HOPS
22. BITWISE STORAGE
23. CONVERT A NUMBER FROM BASE2 TO BASE4
24. arr[i] = arr[arr[i]] in place
25. GREATEST CONTIGUOUS SUM
26. THREE STRINGS INTERLEAVED PROBLEM
27. MAX APPLES THAT CAN BE COLLECTED IN 2D MATRIX
28. Add 2 Binary Numbers Represented As Strings
29. [a1,a2,a3,b1,b2,b3] to [a1,b1,a2,b2,a3,b3] in Place
Stacks using Queues
Stacks using Queues
namespace StackUsingQueues
{
//Implementation which supports efficient Push and
//innefficient Pop
class StackWithEfficientPush
{
Queue<int> Q1 = null;
Queue<int> Q2 = null;
public StackWithEfficientPush()
{
Q1 = new Queue<int>();
Q2 = new Queue<int>();
}
public void Push(int val)
{
Q1.Enqueue(val);
}
public int Pop()
{
while (Q1.Count > 1)
{
Q2.Enqueue(Q1.Dequeue());
}
int itemToReturn = Q1.Dequeue();
Q1 = Q2;
Q2 = new Queue<int>();
return itemToReturn;
}
}
//Implementation which supports efficient Pop and
//innefficient Push
class StackWithEfficientPop
{
Queue<int> Q1 = null;
Queue<int> Q2 = null;
public StackWithEfficientPop()
{
Q1 = new Queue<int>();
Q2 = new Queue<int>();
}
public void Push(int val)
{
Q1.Enqueue(val);
while (Q2.Count > 0)
{
Q1.Enqueue(Q2.Dequeue());
}
Q2 = Q1;
Q1 = new Queue<int>();
}
public int Pop()
{
return Q2.Dequeue();
}
}
class Program
{
static void Main(string[] args)
{
StackWithEfficientPush S = new StackWithEfficientPush();
S.Push(10);
S.Push(20);
S.Push(30);
S.Push(40);
S.Push(50);
Console.WriteLine(S.Pop());
S.Push(60);
S.Push(70);
S.Push(80);
Console.WriteLine(S.Pop());
Console.WriteLine(S.Pop());
Console.WriteLine(S.Pop());
}
}
}
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));
}
}
}
FIND FIRST REPEATED STRING WITH 3 CHARS
FIND FIRST REPEATED STRING WITH 3 CHARS
namespace FirstRepeatedStringWithMin3Chars
{
//Given a String "abcxrrxabcrr"
//Find the first repeated string with minimum 3 character ?
//Answer is "abc" min 3 characters.
class Program
{
//Here HashSet is being used, we can also do it using Tries.
public static String FindRepeatedString(String Str)
{
HashSet<String> Set = new HashSet<string>();
int index = 0;
String SubString = null;
while (index + 3 < Str.Length)
{
SubString = Str.Substring(index, 3);
if(Set.Contains(SubString))
{
return SubString;
}
Set.Add(SubString);
index++;
}
return null;
}
static void Main(string[] args)
{
String Str = "aaaagfyeueyhgfkeury";
Console.WriteLine(FindRepeatedString(Str));
}
}
}
FIND REPEATED AND MISSING NUMBERS IN AN ARRAY
FIND REPEATED AND MISSING NUMBERS
//you are given a sequence of ints from 1 to n in an array,//the array would contain one repeated element, you need to find
//both the repeated and missing numbers.
namespace FindingRepeatedAndMissinginArray
{
class Program
{
static int fact(int n)
{
if (n == 0) return 1;
return n * fact(n - 1);
}
public static void FindMissingAndRepeatedNum_Method2(int[] arr)
{
int Sum1 = 0;
int Sum2 = 0;
Sum1 = (arr.Length * (arr.Length + 1)) / 2;
Sum2 = ((2 * arr.Length + 1) * (arr.Length + 1) * arr.Length) / 6;
for (int i = 0; i < arr.Length; i++)
{
Sum1 -= arr[i];
Sum2 -= arr[i] * arr[i];
}
/*
sum1 = mis-rep ------------->>1
sum2 = mis2 - rep2 --------->>2
sum2 = (mis+rep)(mis-rep) ----->>2
2/1 ===>>
sum2/sum1 = mis+rep ----------->>3
sum2+sum12 = mis
----------- ---->>(3+1)
2 * sum1
*/
int MissingVal = (Sum2 + Sum1 * Sum1) / (2 * Sum1);
int RepeatedVal = MissingVal - Sum1;
Console.WriteLine(MissingVal + " " + RepeatedVal);
}
public static void FindMissingAndRepeatedNum_Method1(int[] arr)
{
int givensum = 0;
int givenprod = 1;
foreach (int x in arr)
{
givensum = givensum + x;
givenprod = givenprod * x;
}
float acctual_sum = (arr.Length * (arr.Length + 1)) / 2;
float acctual_prod = fact(arr.Length);
float Repeated_val = ((acctual_sum - givensum) / ((acctual_prod / givenprod) - 1));
float Missing_val = (acctual_prod / givenprod) * Repeated_val;
Console.WriteLine("Missing Val = " + Missing_val);
Console.WriteLine("Repeated Val =" + Repeated_val);
}
static void Main(string[] args)
{
int[] arr = { 1, 2, 3, 3};
FindMissingAndRepeatedNum_Method1(arr);
FindMissingAndRepeatedNum_Method2(arr);
}
}
}
FIND GIVEN PATTERN AND REPLACE IT WITH GIVEN STRING
FIND GIVEN PATTERN AND REPLACE IT WITH GIVEN STRING
namespace FindGivenPatternAndReplaceWitStr
{
//Implementation of finding all the occurrence of the given pattern in given String
//and then replacing it with some other given string
class Program
{
public static String FindAndReplace(String GivenString, String Pattern, String ReplaceString)
{
int j = 0;
int tempi;
for (int i = 0; i < GivenString.Length; i++)
{
tempi = i;
j = 0;
while (i<GivenString.Length && j< Pattern.Length && GivenString[i] == Pattern[j])
{
i++;
j++;
}
if (j == Pattern.Length)
{
GivenString = GivenString.Substring(0, tempi) + ReplaceString + GivenString.Substring(i, GivenString.Length - i);
i = tempi + ReplaceString.Length-1;
continue;
}
i = tempi;
}
return GivenString;
}
static void Main(string[] args)
{
String GivenString = "fasdasdkfhawhasdrhasdfasdbygyasgfadfsdkfwerhasdfhpraasd";
String Pattern = "asd";
String ReplaceString = ",";
int tempi;
int i = 0;
int j;
while(i<GivenString.Length)
{
tempi = i;
j = 0;
while (i < GivenString.Length && j < Pattern.Length && GivenString[i] == Pattern[j])
{
i++;
j++;
}
if (j == Pattern.Length)
{
GivenString = GivenString.Substring(0, tempi) + ReplaceString + GivenString.Substring(i, GivenString.Length - i);
i = tempi + ReplaceString.Length;
continue;
}
j = 0;
i = tempi+1;
}
Console.WriteLine(GivenString);
GivenString = "fasdasdkfhawhasdrhasdfasdbygyasgfadfsdkfwerhasdfhpraasd";
Console.WriteLine(FindAndReplace(GivenString, Pattern, ReplaceString));
}
}
}
FIND AND ELIMINATE DUPLICATES IN AN ARRAY
FIND AND ELIMINATE DUPLICATES IN AN ARRAY
namespace FindAndEliminateDuplicate
{
class Program
{
static void Main(string[] args)
{
int[] array = {2,3,5,3,6,8,2,6,6,3};
HashSet<int> holder = new HashSet<int>();
int[] newarray = new int[array.Length];
int j=0;
for (int i = 0; i < array.Length; i++)
{
if(holder.Contains(array[i]))
continue;
newarray[j++] = array[i];
holder.Add(array[i]);
}
for(int k=0;k<j;k++)
Console.WriteLine(newarray[k]);
}
}
}
FIND 4 NUMS IN ARRAY WHOSE SUM EQUALS GIVEN NUM
FIND 4 NUMS IN ARRAY WHOSE SUM EQUALS GIVEN NUM
namespace Find4NumsInArraywhoseSumEqualsGivenNum
{
class pair
{
public int i;
public int j;
public pair(int i, int j)
{
this.i = i;
this.j = j;
}
}
class Program
{
static void Main(string[] args)
{
List<int> li =new List<int>();
li.Add(1);
li.Add(2);
li.Add(3);
li.Add(4);
li.Add(5);
li.Add(6);
li.Add(7);
li.Add(8);
Dictionary<int,pair> Sums = new Dictionary<int,pair>();
int sum = 18;
for (int i = 0; i < li.Count; i++)
{
for (int j = i + 1; j < li.Count; j++)
{
int tempsum = li[i] + li[j];
int remainingsum = sum - tempsum;
if (Sums.ContainsKey(remainingsum))
Console.WriteLine(li[i] + " " + li[j] + " " + li[Sums[remainingsum].i] + " " + li[Sums[remainingsum].j]);
}
for (int k = 0; k < i; k++)
Sums[li[i] + li[k]] = new pair(i, k);
}
}
}
}
FIND 3 INTS WHOSE PRODUCT IS THE LARGEST IN THE LIST
FIND 3 INTS WHOSE PRODUCT IS THE LARGEST IN THE LIST
namespace Find3intsWhoseProdIsTheLargestInArray
{
class Program
{
static void Main(string[] args)
{
List<int> li = new List<int>();
li.Add(1);
li.Add(-3);
li.Add(10);
li.Add(-10);
li.Add(20);
li.Add(5);
li.Add(4);
li.Add(8);
li.Add(-3);
li.Add(-12);
li.Sort();
int prod1 = li[0]*li[1]*li[li.Count-1];
int prod2 = li[li.Count-3]*li[li.Count-1]*li[li.Count-2];
Console.WriteLine((prod1 > prod2)? prod1: prod2);
}
}
}
FIND 2 ODD OCCURING INTS IN AN ARRAY
FIND 2 ODD OCCURING INTS IN AN ARRAY
namespace Find2OddOccuringIntsinanArray
{
class Program
{
public static void Find2OddOccuringInts(int[] Arr)
{
int OddOccurence = 0;
for (int i = 0; i < Arr.Length; i++)
{
OddOccurence ^= Arr[i];
}
//Now variable Oddoccurences will contain
//information about 2 odd occuring numbers.
//In the variable Oddoccurences only those bits
//will be set in which the 2 odd occuring numbers differ.
//Now get the Least significant bit set in the variable OddOccurences.
OddOccurence = OddOccurence & -(OddOccurence);
//Use the above OddOccurences variable to divide
//the array, those with that least significant bit set and those not.
int x=0, y=0;
for (int i = 0; i < Arr.Length; i++)
{
if ((Arr[i] & OddOccurence) > 0)
{
x = x ^ Arr[i];
}
else
{
y = y ^ Arr[i];
}
}
Console.WriteLine(x + " " + y);
}
static void Main(string[] args)
{
int[] Arr = { 1, 3, 4, 5, 1, 5, 6, 6, 7, 8, 7, 8 };
Find2OddOccuringInts(Arr);
}
}
}
namespace Find2OddOccuringIntsinanArray
{
class Program
{
public static void Find2OddOccuringInts(int[] Arr)
{
int OddOccurence = 0;
for (int i = 0; i < Arr.Length; i++)
{
OddOccurence ^= Arr[i];
}
//Now variable Oddoccurences will contain
//information about 2 odd occuring numbers.
//In the variable Oddoccurences only those bits
//will be set in which the 2 odd occuring numbers differ.
//Now get the Least significant bit set in the variable OddOccurences.
OddOccurence = OddOccurence & -(OddOccurence);
//Use the above OddOccurences variable to divide
//the array, those with that least significant bit set and those not.
int x=0, y=0;
for (int i = 0; i < Arr.Length; i++)
{
if ((Arr[i] & OddOccurence) > 0)
{
x = x ^ Arr[i];
}
else
{
y = y ^ Arr[i];
}
}
Console.WriteLine(x + " " + y);
}
static void Main(string[] args)
{
int[] Arr = { 1, 3, 4, 5, 1, 5, 6, 6, 7, 8, 7, 8 };
Find2OddOccuringInts(Arr);
}
}
}
Subscribe to:
Posts (Atom)