One Stop Interview Preparation: March 2014

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

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

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

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

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);
}
}
}

FIND 0s AND 1s INTERFACE

FIND 0s AND 1s INTERFACE POINT (BINARY SEARCH TECHNIQUE)

namespace Find_0_s_and_1_s_interface

{

class Program

{

static int FindInterface(int[] arr)

{

int l = 0;

int h = arr.Length - 1;

int mid = 0;

while (l < h)

{

mid = (l + h) / 2;

if (arr[mid] == 0 && arr[mid + 1] == 1) return mid;

if (arr[mid] == 1 && arr[mid - 1] == 0) return mid-1;

else if (arr[mid] == 0) l = mid+1;

else h = mid-1;

}

return -1;

}

static void Main(string[] args)

{

int[] A = { 0,0,0,1,1,1,1 };

Console.WriteLine(FindInterface(A));

}

FACTORY DESIGN PATTERN

SIMPLE FACTORY DESIGN PATTERN

namespace Factory_Simple
{
abstract class Aeroplane
{
public String Name { get; protected set; }

abstract public Aeroplane CreateAeroplane();
}

class B747:Aeroplane
{
public static bool Register()
{
return AeroplaneFactory.Register("B747", new B747());
}

public B747()
{
Name = "B747";
}

public override Aeroplane CreateAeroplane()
{
return new B747();
}
}

class A380 : Aeroplane
{
public static bool Register()
{
return AeroplaneFactory.Register("A380", new A380());
}

public A380()
{
Name = "A380";
}

public override Aeroplane CreateAeroplane()
{
return new A380();
}
}

static class AeroplaneFactory
{
static Dictionary<String,Aeroplane> Aeroplanes = new Dictionary<string,Aeroplane>();
public static bool Register(String Name, Aeroplane plane)
{
Aeroplanes.Add(Name, plane);
return true;
}

public static Aeroplane GetAeroplane(String Name)
{
if(Aeroplanes.ContainsKey(Name))
{
return Aeroplanes[Name].CreateAeroplane();
}
return null;
}
}

class Program
{
static void Main(string[] args)
{
A380.Register();
Console.WriteLine(AeroplaneFactory.GetAeroplane("A380").Name);
}
}
}

DNF SORTING

DUTCH NATIONAL FLAG SORTING (DNF SORTING)

namespace DutchFlagAlgo
{
class Program
{
public static void dutchFlagSort(int[] arr, int p, int k)
{
int p_index = 0;
int k_index = arr.Length - 1;
for (int i = 0; i <= k_index; )
{
if (arr[i] < p)
{
swap(arr, i, p_index);
p_index++;
i++;
}
else if (arr[i] >= k)
{
swap(arr, i, k_index);
k_index--;
}
else
{
i++;
}
}
}

public static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static void Main(string[] args)
{
int[] arr = { 3,5,4,2,1};
dutchFlagSort(arr, 2, 4);
foreach (int a in arr) Console.Write(a+" ");
}
}
}

Excel column number to alpha and reverse

namespace ExcelColumnfromNumToAlpha
{
class Program
{

static void Main(string[] args)
{
/*Begin : Column Number to Alphabets*/
//Number to Alphabet, assumption : column A starts at 0.
// if Column A starts from 1 then
//subtract 1 from the input column number.
int ColumnNum = 702;
String ColumnAlpha = "";
int r;

r = ColumnNum % 26;
ColumnAlpha = (char)(r + 65) + ColumnAlpha;
ColumnNum = ColumnNum / 26;

while (ColumnNum > 0)
{
r = ColumnNum % 26;
ColumnAlpha = (char)(r + 64) + ColumnAlpha;
ColumnNum = ColumnNum / 26;
}

Console.WriteLine(ColumnAlpha);
  /*End: Column Number to Alphabets*/

  /*Begin : Column Alphabets to number*/
//Alphabet to number - assumption = Col num starts from 1 i.e A is 1.
//if it starts from 0, then subtract 1 from the final answer.
String ColumninAlpha = "AB";
int ColNum = 0;
for (int i = 0; i < ColumninAlpha.Length; i++)
{
ColNum = ColNum * 26 + (int)(ColumninAlpha[i] - 'A') + 1;
}
Console.WriteLine(ColNum);
  /*End: Column Alphabets to number*/
}
}
}

DETECT DUPLICATE PARENTHESES IN AN EXPRESSION

namespace DuplicateParanthesesInExpression
{
class Program
{
public static Boolean IsDupParanthesesPresent(String Expression)
{
if (Expression == null || Expression.Length == 0)
return false;

Stack<char> S = new Stack<char>();

for (int i = 0; i < Expression.Length; i++)
{
if (Expression[i] == '(') S.Push(Expression[i]);
//If you find '(' in stack when you are find ')' in the input ,
//it means there's a duplicate parantheses in the expression.
else if (Expression[i] == ')')
{
if (!(S.Peek() == '('))
{
while (S.Count > 0 && S.Pop() != '(') ;
}
else return true;
}
else if (!char.IsLetter(Expression[i])) S.Push(Expression[i]);
}

return false;
}

static void Main(string[] args)
{
String Expression = "((a+b)*(c+d))";

Console.WriteLine(IsDupParanthesesPresent(Expression));
}
}
}

What are P, NP-Complete, and NP-Hard?

We start with the idea of a decision problem, a problem for which an algorithm can always answer “yes” or “no.” We also need the idea of two models of computer (Turing machine, really): deterministic and non-deterministic. A deterministic computer is the regular computer we always thinking of; a non-deterministic computer is one that is just like we’re used to except that is has unlimited parallelism, so that any time you come to a branch, you spawn a new “process” and examine both sides. Like Yogi Berra said, when you come to a fork in the road, you should take it.

A decision problem is in P if there is a known polynomial-time algorithm to get that answer. A decision problem is in NP if there is a known polynomial-time algorithm for a non-deterministic machine to get the answer.

Problems known to be in P are trivially in NP — the nondeterministic machine just never troubles itself to fork another process, and acts just like a deterministic one. There are problems that are known to be neither in P nor NP; a simple example is to enumerate all the bit vectors of length n. No matter what, that takes 2ⁿ steps.
(Strictly, a decision problem is in NP if a nondeterministic machine can arrive at an answer in poly-time, and a deterministic machine can verify that the solution is correct in poly time.)

But there are some problems which are known to be in NP for which no poly-time deterministic algorithm is known; in other words, we know they’re in NP, but don’t know if they’re in P. The traditional example is the decision-problem version of the Traveling Salesman Problem (decision-TSP): given the cities and distances, is there a route that covers all the cities, returning to the starting point, in less than x distance? It’s easy in a nondeterministic machine, because every time the nondeterministic traveling salesman comes to a fork in the road, he takes it: his clones head on to the next city they haven’t visited, and at the end they compare notes and see if any of the clones took less than x distance.

(Then, the exponentially many clones get to fight it out for which ones must be killed.)
It’s not known whether decision-TSP is in P: there’s no known poly-time solution, but there’s no proof such a solution doesn’t exist.

Now, one more concept: given decision problems P and Q, if an algorithm can transform a solution for P into a solution for Q in polynomial time, it’s said that Q is poly-time reducible (or just reducible) to P.

A problem is NP-complete if you can prove that (1) it’s in NP, and (2) show that it’s poly-time reducible to a problem already known to be NP-complete. (The hard part of that was proving the first example of an NP-complete problem: that was done by Steve Cook in Cook’s Theorem.)

So really, what it says is that if anyone ever finds a poly-time solution to one NP-complete problem, they’ve automatically got one for all the NP-complete problems; that will also mean that P=NP.

A problem is NP-hard if and only if it’s “at least as” hard as an NP-complete problem. The more conventional Traveling Salesman Problem of finding the shortest route is NP-hard, not strictly NP-complete.

SUM OF PREVIOUS SMALLER NUMBERS IN ARRAY

//For every given element in the array you should return the sum of previous smaller values you //encountered in the array.

//In the solution here basically we are building a BST and every node in the tree would hold
//the sum of all the node values towards its left (i.e. lesser than that node).
//To calculate sum of prev small numbers we add the
//current node's value and current nodes sum to the sum being calculated.
namespace SumOfPrevSmallNumInArr
{
class BST
{
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public int Sum; //for SumOfPrevSmallNumInArr

public TreeNode(int val)
{
this.data = val;
this.left = null;
this.right = null;
this.Sum = 0;
}

public TreeNode(int val, int index)
{
this.data = val;
this.left = null;
this.right = null;
this.Sum = 0;
}

public TreeNode()
{
this.data = 0;
this.left = null;
this.right = null;
this.Sum = 0;
}
}

TreeNode Root;
public BST()
{
Root = null;
}

public int AddNodeAndReturnSumOfPrevSmallNumInArr(int val)
{
TreeNode Node = new TreeNode(val);
if (Root == null)
{
Root = Node;
return 0;
}

TreeNode cur = Root;
TreeNode Prev = null;
int Sum = 0;

while (cur != null)
{
Prev = cur;
//If moving towards right add the current node's value and its
//sum value to the sum being calculated to return.
if (val >= cur.data)
{
Sum += cur.data + cur.Sum;
cur = cur.right;
}
//If moving towards left add the value to current node's sum.
else
{
cur.Sum += val;
cur = cur.left;
}
}
if (val >= Prev.data) Prev.right = Node;
else Prev.left = Node;
return Sum;
}

}
class Program
{
static void Main(string[] args)
{
int[] Arr = { 2, 3, 8, 6, 1 };

//Sum of prev small numbers in arr
BST BinSearchTree = new BST();
for (int i = 0; i < Arr.Length; i++)
{
Console.WriteLine(BinSearchTree.AddNodeAndReturnSumOfPrevSmallNumInArr(Arr[i]));
}

}
}
}

PROBABILITY INTERVIEW QUESTIONS

COUNT MAX NUMBER OF CONNECTED 1s IN A MATRIX

namespace CountMaxNoOfConnected1s
{
//you have a matrix of N x N filled with 1 or 0. you can move
//only 1 step either right or 1 step down. you need to count
//maximum number of "connected 1" in given matrix. for example
//0 0 1 1
//1 1 1 0
//1 0 1 0
//0 1 0 1
//[Start from top left] maximum no. of connected 1s is 4
//[1,0][1,1][1,2][2,2]
class Program
{
static int MaxNoOfConnected1s(int[,] Mat)
{
int[,] ComputeMat = new int[Mat.GetLength(0), Mat.GetLength(1)];
int Max1s = 0;

for (int i = 0; i < Mat.GetLength(0); i++)
{
for (int j = 0; j < Mat.GetLength(1); j++)
{
if (i > 0 || j > 0)
{
if (i > 0 && j > 0)
{
if (Mat[i - 1, j] == 1 || Mat[i, j - 1] == 1)
{
ComputeMat[i, j] = Math.Max(ComputeMat[i - 1, j], ComputeMat[i, j - 1]) + Mat[i, j];
}
else ComputeMat[i, j] = Mat[i, j];
}
else if (i > 0)
{
if (Mat[i - 1, j] == 1)
{
ComputeMat[i, j] = ComputeMat[i - 1, j] + Mat[i, j];
}
else ComputeMat[i, j] = Mat[i, j];
}
else if (j > 0)
{
if (Mat[i, j-1] == 1)
{
ComputeMat[i, j] = ComputeMat[i, j-1] + Mat[i, j];
}
else ComputeMat[i, j] = Mat[i, j];
}

if (ComputeMat[i, j] > Max1s) Max1s = ComputeMat[i, j];
}
}
}
return Max1s;
}

static void Main(string[] args)
{
int[,] Mat = {
{0,0,1,1},
{1,1,1,0},
{1,0,1,0},
{0,1,1,1}
};

Console.WriteLine(MaxNoOfConnected1s(Mat));
}
}
}

Interview Question Categories