BVarghese
BAN USER- 0of 0 votes
AnswersRegular expression- String matching. Find as many as patterns found in the given text.
- BVarghese in United States
Pattern is "abcd\\d*abcd". Here the regular expression part is ‘\\d*’. Search for this pattern in a text like follows.
text = "KABabcd123abcsdjhsdh". Using above regular expression pattern, we can match a string 'abcd123abcd 'in the text.
More explanation: In the pattern, if it is a '*',then digits can be repeated. If it is a '+', then only one digit.
There is a function which will return whether it is a digit or Char.
public static Boolean IsThisADigitChar(char input). Use this function to find whether the input character is Digit or not.
example: abcd\\d*abcd==> abcd123456abcd is matched
abcd\\d*abcd==> abcd12abcd is matched
abcd\\d*abcd==> abcd1abcd is matched
abcd\\d*abcd==> abcd123456bcd is not matched
abcd\\d+abcd==> abcd1abcd is matched
abcd\\d+abcd==> abcd2abcd is matched
abcd\\d+abcd==> abcd7abcd is matched
abcd\\d+abcd==> abcd123456abcd is not matched| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWrite a program to find whether two lines are intersecting.
- BVarghese in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
Answers
- BVarghese in United StatesSearch for an element in a matrix. Rows and columns of the matrix are sorted in ascending order. eg. matrix [1 14 25 35] [2 16 28 38] [5 20 28 40] [16 22 38 41] search for 38. The interviewer was looking for a solution better than O(n+m). He didn't want a solution which starts searching from the left bottom and go to right or above according to the key value to search. That solution has O(n+m) worst complexity, where n is row count and m is column count.
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersPairwise swap elements of a given doubly linkedlist.
- BVarghese in United States
Node has prev and next pointers.| Report Duplicate | Flag | PURGE
Adobe SDE-2 Algorithm
My suggestion is modified KMP algorithm. This will give solution with O(n) complexity.
namespace KMPForRegularExpressionDFA
{
class Program
{
public static int[] b;
public static String p;
public static String t;
public static int m;
public static int n;
static void Main(string[] args)
{
p = "aba\\d+a";
t = "aaaba1aaaaba123111caba123ac";
b = new int[p.Length + 1];
m = p.Length;
n = t.Length;
KmpPreprocess();
KmpSearchRegularExp();
Console.ReadKey();
}
public static void KmpPreprocess()
{
int i = 0, j = -1;
b[i] = j;
while (i < m)
{
while (j >= 0 && p[i] != p[j])
{
j = b[j];
}
i++; j++;
b[i] = j;
}
}
public static void KmpSearchRegularExp()
{
int i = 0, j = 0;
while (i < n)
{
Boolean flag=false;
if ((p[j] != '*' && IsThisADigitChar(t[i]) == false) || (p[j] != '*' && IsThisADigitChar(t[i]) == true))
{
flag=true;
}
while (j >= 0 && j < m && t[i] != p[j] && flag == true)
{
j = b[j];
}
if (j < m && j >= 0 && p[j] == '*' && IsThisADigitChar(t[i]) == true)
{
j++;
if (IsThisADigitChar(t[i]) == true)
{
i++;
}
if (j < m && j >= 0 && p[j] == '+')
{
j++;
while (IsThisADigitChar(t[i]) == true)
{
i++;
}
}
}
else
{
i++;
j++;
}
if (j == m)
{
report(i - j);
j = b[j];
}
}
private static Boolean IsThisADigitChar(char input)
{
if (input >= '0' && input <= '9')
{
return true;
}
else return false;
}
//print the string
Private static void Report(int l)
{
}
}
My answer suggestion :
Equations of two lines:
A1x + B1y = C1
A2x + B2y = C2
To find the point at which the two lines intersect, we simply need to solve the two equations for the two unknowns, x and y.
double det = A1*B2 - A2*B1
if(det == 0){
//Lines are parallel
}else{
double x = (B2*C1 - B1*C2)/det
double y = (A1*C2 - A2*C1)/det
}
Normally, Quick Sort is considered to better sorting algorithm than Merge sort. But , to explain why Merge sort is good for Linked List, we have to look into disadvantage of Quick sort when we use it for Linked List.
Quick sort has locality of reference, where the computer hardware is optimized so that accessing memory locations that are near one another tends to be faster than accessing memory locations scattered throughout memory. The partitioning step in quick sort typically has excellent locality, since it accesses consecutive array elements near the front and the back.
But when working with linked lists, this advantage necessarily will not apply. Because linked list cells are often scattered throughout memory, there is no locality bonus to accessing adjacent linked list cells. Also, since merge sort's linked list algorithm doesn't need any extra auxiliary storage space and it more evenly splits the lists in half and does less work per iteration to do a merge than to do the partitioning step like quick sort, merge sort is going to be better for linked list.
namespace CommonElementsOfTwoLinkedList
{
class Program
{
static void Main(string[] args)
{
List l1 = new List();
l1.Add(1);
l1.Add(2);
l1.Add(6);
l1.Add(12);
l1.Add(14);
l1.Add(18);
l1.Print();
Node result = SortList.MergeSort(l1);
}
}
class SortList
{
public Node Merge(Node list1, Node list2)
{
Node result = null;
if (list1 == null)
return list2;
if (list2 == null)
return list1;
if (list1.ID <= list2.ID)
{
result = list1;
result.Front = Merge(list1.Front, list2);
}
else
{
result = list2;
result.Front = Merge(list1, list2.Front);
}
return result;
}
public Node MergeSort(Node list1)
{
if (list1 == null || list1.Front == null)
{
return list1;
}
Node head_one = list1, head_two;
head_two = list1.Front;
while (head_two != null && head_two.Front != null)
{
list1 = list1.Front;
head_two = head_two.Front.Front;
}
head_two = list1.Front;
list1.Front = null;
return Merge(MergeSort(head_one), MergeSort(head_two));
}
}
}
Sorry, I am adding a generalised approach. This approach will help both on exact one string matching or any number of same string matching. If it is exact one string matching, this idea is not efficient. Please ignore this.
Idea:Modified KMP can be used like follows. complexity o(n)
static void Main(string[] args)
{
p = "*ba*a";
t = "abafa";
b = new int[p.Length + 1];
m = p.Length;
n = t.Length;
KmpPreprocess();
KmpSearchRegularExp();
Console.ReadKey();
}
public static void KmpPreprocess()
{
int i = 0, j = -1;
b[i] = j;
while (i < m)
{
while (j >= 0 && p[i] != p[j])
{
j = b[j];
}
i++; j++;
b[i] = j;
}
}
public static bool report(int n)
{
//do what ever here once found a match
return true;
}
public static void KmpSearchRegularExp()
{
int i = 0, j = 0;
while (i < n)
{
if (j < m && j >= 0 && p[j] == '*')
{
j++; i++;
}
while (j >= 0 && j < m && t[i] != p[j] )
{
j = b[j];
}
++i;
j++;
if (j == m)
{
report(i - j);
j = b[j];
}
}
}
My answer suggestion: Please give comments
This idea will take extra space for index and original array. But time complexity will be less than square of n.
step 1: store the indices of the array and elements into 'index' and 'array'.
step 2: sort the elements using quick sort and store the indices of the element into the index array during the swap method. We will have the index with elements sorted.
step 3: use the following Find method to get the maximum element.
Idea of the Find method.
Start from end of the original array. Start from beginning of the sorted array. If the element of the sorted array is less than original array, get the max separation by subtracting indices of the sorted array from present indices of the original array.(please see the find method)
Exit both for loops if the max separation is greater than the iterator of the first for loop.
namespace LargestSeperationBetweenAiLessAj
{
class Program
{
public static float[] main = { 34, 8, 10, 3, 2, 80, 30, 33, 1 };
public static int[] index;
public static float[] orginal;
static void Main(string[] args)
{
index=new int[main.Length];
orginal = new float[main.Length];
//sort the numbers.
//store the index of the sorted numbers
//use quicksort
//go from last till the max <array.lenth-max
for (int i = 0; i < main.Length; ++i)
{
index[i] = i;
orginal[i] = main[i];
Console.Write(index[i] + "=" + main[i] + "\t");
}
Console.WriteLine();
Quicksort();
for (int i = 0; i < main.Length; ++i)
Console.Write(index[i] +"="+main[i] + "\t");
Console.WriteLine("max=" + Find());
Console.Read();
}
public static int Find()
{
int max = 0;
for (int i = orginal.Length - 1; i >= max; --i)
{
for (int j = 0; j <main.Length; ++j)
{
if (main[j] < orginal[i])
{
if (max < (i - index[j]))
{
max = i - index[j];
}
}
else
{
break;
}
}
}
return max;
}
public static void Quicksort()
{
quicksort( 0, index.Length - 1);
}
// quicksort a[left] to a[right]
private static void quicksort( int left, int right)
{
if (right <= left) return;
int i = partition(left, right);
quicksort( left, i - 1);
quicksort( i + 1, right);
}
// partition a[left] to a[right], assumes left < right
private static int partition(
int left, int right)
{
int i = left - 1;
int j = right;
while (true)
{
while (less(main[++i], main[right])) // find item on left to swap
; // a[right] acts as sentinel
while (less(main[right], main[--j])) // find item on right to swap
if (j == left) break; // don't go out-of-bounds
if (i >= j) break; // check if pointers cross
exchange(i, j); // swap two elements into place
}
exchange(i, right); // swap with partition element
return i;
}
// is x < y ?
private static bool less(float x, float y)
{
return (x < y);
}
// exchange a[i] and a[j]
private static void exchange(int i, int j)
{
float swap = main[i];
main[i] = main[j];
main[j] = swap;
int b = index[i];
index[i] = index[j];
index[j] = b;
}
}
}
Two answer suggestions.
answer1. Sort the array asc order, get the n-2th element.
Answer2. Two variables: largest and secondlargest. Assign them with 1st element and 2nd element of the array respectively if 1st element is greater than 2nd else vice versa.
Now loop from 3rd element onwards till end of the array.
For each element, Case 1:If current element is greater than largest, then replace secondlargest element with largest and replace largest by current element.
Case2: If current element is greater than secondlargest but less than largest, then replace secondlargest with current element.
O(n) complexity.
Since range k is given and they said that k is much lesser than n, we will try for count sort and a linear search approach like other answers here explains. But count sort has got o(n) space complexity and time complexity. So,in this case, hashset approach is much efficient since range k is much smaller.
- BVarghese April 25, 2013Step: declare a min heap,say minheap, of 10 string items and each of its node contains a variable -count. This count is used to keep the heap property. Declare another hashmap,say hmap, with string as its key and count of string as its value. Declare a 256 int array,say chCount, if the strings are only contains ascci characters else declare 16 bit int array.
Step 2: scan each characters from the file, update chCount for each of them, when a word occurs, insert/update(update hmap if this word already in hmap) into hmap and increment its value by one.Then compare this word with top element of minheap. If the count variable of top element of minheap is less than value of hmap's present word , then if it is not in minheap replace the min element with new element from the hmap.If this element is already in minheap, then just increment its count and re-adjust heap property.
Finally we will get minheap with 10 elements and character count in chCount array.
Step 1: if the linked lists are not empty, find the length of each linked list. Since they have a common end point, we will get length of common area of the linked lists too.
Step 2: find the difference between the length of both list. Start traverse the biggest list till the difference in length between them, provided one of them is bigger than the other.
Step 3: now they are at the same remaining length. Traverse both of the together till both are pointing to the same next node.That node is the common node which is the merging point. If there is no such point, then they are not merged.
public Node Delete(Node list, int data)
{
if (list == null)
return null;
Node llist = list,pre=null;
while (llist != null)
{
if (llist.Data == data)
{
if (pre == null)
{
list = list.Next;
llist = list;
continue;
}
else
{
pre.Next = llist.Next;
llist = pre;
}
}
pre = llist;
llist = llist.Next;
}
return list;
}
- BVarghese February 01, 2012//sort the numbers . Since it would n digits only, so we could use count sort,
//then use the permutation and avoid if the number is repeating.
class Program
{
static void Main(string[] args)
{
int[] digits = { 1, 2, 4, 5, 7, 8};
bool[] used = new bool[digits.Length];
Permutation(digits, used, 0, digits.Length-2, "",-10);
Console.Read();
}
public static void Permutation(int[] digits, bool[] used, int count, int length, string result,int pre)
{
if (count == length && result != " ")
{
Console.WriteLine(result);
return;
}
for (int i = 0; i < digits.Length; ++i)
{
if (used[i]||pre > digits[i])
continue;
pre = digits[i];
used[i] = true;
Permutation(digits, used, count + 1, length, result +" "+ digits[i],pre);
used[i] = false;
}
}
}
Thanks @Shishivicto! I forget to add the following line. Thanks for pointing it.
For case 1 and 3( if first half is less than second half) reverse first half number and convert to a number, and then check whether it is bigger than second half. If bigger, then just reverse and paste it at right side and we don't need of adding 1 with it. Otherwise, for both cases add one and do as wrote above.
eg:
126 521==> we can just reverse first half and paste it at right side
126 1 521 ==> we can just reverse first half and paste at right side
We can write a simple program for the following 4 cases, which will be answer for this question.
There are two main cases. 1. Number of digits is odd. 2. Number of digits is even.
In odd case, it has to be separated into three groups. 1. First half 2. Middle digit 3. Second half.
In even case, it has to be separated into two groups. 1. First half 2. Second half.
Now consider following different cases.
1. Case 1: Even number of digits and first half is less than second half.
123 456 124 421
Add 1 to first half, reverse first half and paste it at right side.
2. Case 2: Even number of digits and first half is greater than second half.
456 123 456 654
Just reverse it and paste it at right side.
3. Case 3: If odd number of digits and first half is less than second half.
123 1 234 123 2 321
Add 1 to combined first half and middle one (here 1231+1). Then separate middle one and reverse first half and paste it on right side
Another example: 123 9 234 124 0 421 (here 1239 +1= 1240).
4. Case 4: If odd number of digits and second half is less than second half.
445 9 123 445 9 544
Reverse first half and paste it on right side
Yes, as wei said, this will not work for a different combination. I think we have to find all permutation of the digits first and use this check function for each permutation.
Anyway Gayathiri's check function is excellent. I tried it with permutation and found all correctly printed.
Any further solutions?
This program works all cases. please comment
//step 1. start from left .
//step 2. if it is a # or end of the input string or a new integer , just decode the previous integer.if the pre integer repeated and more than the length of the corresponding code string from the 'codes' string array, then print the number itself.
//step 3.if the previous intger same as present one, and if the repeated more than the length of total charecters in that group, just start again from beginning (cycle must wrap around)
//step 4. else simply continue the loop and index incremented
public static void Decrypt(String input)
{
if (input == " " || input == "#")
{
Console.WriteLine(" nothing to decrypt ");
return;
}
String[] codes = { "", null, "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ" };
char pre = ' ';
int index = -1, i = 0; char inputCh = ' ';
while (input.Length + 1 > i)
{
if (input.Length > i)
{
inputCh = input[i];
}
else
{
inputCh = ' ';
}
//printing the decoded charecter first if it an end(three different end points are there).
if (inputCh == '#' || inputCh == ' ' || pre != ' ' && pre != inputCh)
{
if (index >= 0 && codes[input[i - 1] - '0'].Length > index)
{
Console.Write(codes[input[i - 1] - '0'][index]);
}
else if(pre != ' ')
Console.Write(pre);
//adjusting for '#'. (# breaks the cycle)
if(inputCh == '#')
index = -1;
else index = 0;
pre = ' ';
}
//(cycle must wrap around)
else if (codes[input[i] - '0'].Length <= index )
{
index = 0;
pre = inputCh;
}
else
{
index++;
pre = inputCh;
}
i++;
}
}
// considering i/p: 1->2->3->4->a->b->c->d->5->6->e->f
//step 1: start from left. scan till first char occurs. It is
//keep start node(where the first int occured),prevToStart(previous to start node.First time
//it is present node itself).also count number of non-chars before the current char.
//step 2: loop till the count. detach each node from start position , attach it to the left of the current node.
//increment the start node to next position.Keep the prevToStart=start.
public static void Rearrange(Node list)
{
if (list == null)
return;
Node prevToStart = null, start = list, prevToCurrent = null, current = list;
int i = 0, count = 0;
while (current != null)
{
//finding till first char occurs
if (current.Ch >= '0' && current.Ch <= '9')
{
//count of integers before first char
count++;
current = current.Front;
}
else
{
//loop till count
while (i < count )
{
Node nextToStart = start.Front;
if (prevToStart != null)
{
// here we are taking the Front link right from the char node in the previous case
//eg. 1->a->. prevToStart at 1 and taking Front link from 'a'
//and storing address of present start node '2'. so 1->a->2.
prevToStart.Front.Front = start;
//then pointing prevToStart to '2'
prevToStart = start;
}
else
{
prevToStart = start;
}
start.Front = current;
start = nextToStart;
i++;
prevToCurrent = current;
//if there is no suffient nodes avaialable for sawpping, just return
if (current.Front != null)
current = current.Front;
else return;
}
prevToStart = prevToCurrent;
start = prevToCurrent.Front;
count = 0;
i = 0;
}
}
}
- BVarghese December 20, 2011Another method. O(n) complexity.
Algorithm
1. Find whether the element to be inserted is less than the refernceNode. If it is less, then find the inflexion point where the order is changing
2. then find the position where the element to be inserted from the next loop.
3. If element is greater than the reference node, then go to second loop where we are finding the node which is first bigger than the element and tempList is pointing to the previous node.
4. Last: Previous is the present node in the tempList. tempList is moving one more postion.
5. Then add the element at that position
class CircularSortedList
{
public static Node head = null;
public static Node Insert(Node list,int value, Node referenceNode)
{
if(referenceNode==null)
return null;
Node newNode = new Node(value);
if(list==null)
{
newNode=newNode.Next;
return newNode;
}
Node tempList=referenceNode;
Node endNode=referenceNode;
Node previous= referenceNode;
//here finding point where the newNode should be added
//if value is less than the reference node
if(endNode.Data>value)
{
while(tempList.Next!=endNode && tempList.Next.Data >= value)
{
//finding the inflexion point
if (tempList.Data > tempList.Next.Data)
{
break;
}
tempList=tempList.Next;
}
}
while (tempList.Next != endNode )
{
//Starting from the lowest element now.
if (tempList.Next.Data > value || tempList.Next.Data < tempList.Data && tempList.Data < value)
{
break;
}
tempList=tempList.Next;
}
previous = tempList;
tempList = tempList.Next;
previous.Next=newNode;
newNode.Next=tempList;
return newNode;
}
Assume that arrays are sorted. Otherwise sort the arrays first
namespace MinDistanceBetweenWordsIn2Docs
{
class Program
{
//use binary search in second array
static void Main(string[] args)
{
int[] ar1 = { 2, 3, 5, 10, 12, 16, 19, 20 };
int[] ar2 = { 8, 13, 27, 29 };
Console.WriteLine(MinimumDistance(ar1,ar2));
Console.Read();
}
public static int MinimumDistance(int[] arr1, int[] arr2)
{
int min = int.MaxValue;
for (int i = 0; i < arr1.Length; ++i)
{
int left = 0, right = arr2.Length - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (Math.Abs(arr1[i] - arr2[mid])<min)
{
min = Math.Abs(arr1[i] - arr2[mid]);
}
if (mid > left && Math.Abs(arr1[i] - arr2[mid - 1]) < min)
{
min = Math.Abs(arr1[i] - arr2[mid - 1]);
right = mid - 1;
}
else if (mid < right && Math.Abs(arr1[i] - arr2[mid + 1]) < min)
{
min = Math.Abs(arr1[i] - arr2[mid + 1]);
left = mid + 1;
}
//mid element distance is the least
else break;
}
}
return min;
}
}
}
namespace InfixToPostfixString
{
class Program
{
public static Stack<char> opStack = new Stack<char>();
static void Main(string[] args)
{
Console.WriteLine(InfixToPostFix("(((A+B)+E)+(F*C))-D"));
Console.Read();
}
//little bit tricky
private static Boolean Precedence(char stackTop,char infix)
{
//here we are trying to find that if the stacktop is equal to preced[] value
char[] prec = { '(','/', '*', '+', '-',')' };
for (int i = 0; i < prec.Length; ++i)
{
if (prec[i] == stackTop)
return true;
if (prec[i] == infix)
return false;
}
return false;
}
public static StringBuilder InfixToPostFix(String infix)
{
StringBuilder postFix = new StringBuilder(); int i=0,j=0;
while (i < infix.Length)
{
if (IsThisAOperandChar(infix[i]))
{
postFix.Append(infix[i]);
}
else if(IsThisAOperatorChar(infix[i]))
{
while (opStack.Count != 0 && Precedence(opStack.Peek(), infix[i]))
{
if (opStack.Peek() == '(')
{
opStack.Pop();
break;
}
else postFix.Append(opStack.Pop());
}
if(infix[i]!=')')
opStack.Push(infix[i]);
}
else return null;
i++;
}
while (opStack.Count != 0)
{
if (opStack.Peek() == '(')
opStack.Pop();
else
postFix.Append(opStack.Pop());
}
return postFix;
}
public static bool IsThisAOperandChar(char input)
{
var asciiValue = Convert.ToInt16(input);
return ((asciiValue >= 65) && (asciiValue <= 90) || (asciiValue >= 97) && (asciiValue <= 122));
}
public static bool IsThisAOperatorChar(char input)
{
var asciiValue = Convert.ToInt16(input);
return ((asciiValue == 42) || (asciiValue == 43) || (asciiValue == 45) || (asciiValue == 47) || (asciiValue == 40) || (asciiValue == 41));
}
}
}
Complexity is O(n).
public static void SortZeroAndOne(int[] arr, int n)
{
int i=0,j=n-1;
while (i < j)
{
if (arr[i] == 1)
{
while (arr[j] != 0&& i < j)
{
j--;
}
if(i==j) break;
if (arr[i] != arr[j] )
{
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
++i;
}
}
This algorithm works in worst case logn+n-2 comaprisons
public static void MinAndSecondMin(int[] arr, ref int min, ref int min2)
{
if (arr.Length <= 2)
{
return;
}
if (arr[0] < arr[1])
{
min = arr[0];
min2 = arr[1];
}
else
{
min = arr[1];
min2 = arr[0];
}
for (int i = 2; i < arr.Length; ++i)
{
if (arr[i] < min)
{
min2 = min;
min = arr[i];
}
else if (arr[i] < min2)
{
min2 = arr[i];
}
}
}
class MatrixFromTree
{
public static int[,] matrix;
public static void Matrix(Node root, List<Node> list)
{
if (root == null)
return;
list.Add(root);
Matrix(root.Left, list);
Matrix(root.Right, list);
list.Remove(list[list.Count-1]);
for (int i = 0; i < list.Count; ++i)
{
Node parent = list[i];
matrix[(int)(root.ID - 65), (int)(parent.ID - 65)] = 1;
}
}
public static void Matrix(Node root, int row, int col)
{
List<Node> list=new List<Node>();
matrix = new int[row, col];
Matrix(root, list);
}
}
Morris In-order Traversal is used here
or
threaded binary tree
public static void MorrisTraversal(Node root)
{
Node current, pre;
if (root == null)
return;
current = root;
while (current != null)
{
if (current.Left == null)
{
if (head1 == null)
{
head1 = current;
tail1 = current;
}
else
{
tail1.Next = current;
tail1 = current;
}
Console.WriteLine(current.ID);
current = current.Right;
}
else
{
/* Find the inorder predecessor of current */
pre = current.Left;
while (pre.Right != null && pre.Right != current)
pre = pre.Right;
/* Make current as right child of its inorder predecessor */
if (pre.Right == null)
{
pre.Right = current;
current = current.Left;
}
/* Revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else
{
pre.Right = null;
if (head1 == null)
{
head1 = current;
tail1 = current;
}
else
{
tail1.Next = current;
tail1 = current;
}
Console.WriteLine(current.ID);
current = current.Right;
}
}
}
}
}
I just tried somebody else's idea and found answer correctly.
Just pasting here for your references.
namespace SubsequenceIncreasingNonContigious
{
class Program
{
static void Main(string[] args)
{
int[] input = { -2, 37, -5, -71, 57, -1, 4, 4, 12,10, -7, -191, 231 };
SubseqenceIncreasingOrderNonContigous(input, input.Length);
Console.Read();
}
public static int[] dp;
public static int[] previous;
public static void SubseqenceIncreasingOrderNonContigous(int[] array, int N)
{
int maxLength = 1, bestEnd = 0;
dp = new int[N];
previous = new int[N];
dp[0] = 1;
previous[0] = -1;
for (int i = 1; i < N; i++)
{
dp[i] = 1;
previous[i] = -1;
for (int j = i - 1; j >= 0; j--)
if (dp[j] + 1 > dp[i] && array[j] < array[i])
{
dp[i] = dp[j] + 1;
previous[i] = j;
}
if (dp[i] > maxLength)
{
bestEnd = i;
maxLength = dp[i];
}
}
Console.WriteLine(" best end " + bestEnd + " maxlength " + maxLength);
Print(array, bestEnd);
}
public static void Print(int[] array, int bestEnd)
{
//printing the best endvalue
Console.WriteLine(array[bestEnd]);
int i = bestEnd;
//now taking from best end value to backward
while (previous[i] != -1)
{
Console.WriteLine(array[previous[i]]);
i = previous[i];
}
}
}
}
I hope this will work.
Next- linkedlist ponter
Right and Left - tree pointers
class LinkedListOfSameLevelsOrAllSiblings
{
public static void LinkedListConnect(Node node, int depth, List<Node> linkedLists)
{
if (node == null)
return;
if (linkedLists.Count <= depth)
linkedLists.Add(node);
else
{
linkedLists[depth].Next = node;
linkedLists[depth] = node;
}
LinkedListConnect(node.Left, depth + 1, linkedLists);
LinkedListConnect(node.Right, depth + 1, linkedLists);
}
//printing the linked list
public static void PrintLinkedList(Node root)
{
if (root == null)
return;
Node temp = root;
while (temp != null)
{
Console.Write(temp.ID + " - > ");
temp = temp.Next;
}
if (temp == null)
Console.WriteLine();
if (root.Left != null)
{
PrintLinkedList(root.Left);
}
else
PrintLinkedList(root.Right);
}
}
call the functions like this
List<Node> prev = new List<Node>();
LinkedListConnect(treeRoot, 0, prev);
PrintLinkedList(prev[0]);
This is finding the LCA and simultaneously searching for the Y node.
Step 1: Starting from the X and finding the height of the tree from X.
Step 2:Starting from the Z and finding the height of the tree from Z.
Step 3: finding diff between the height of the X and Z.
Step 4: Again starting from X and Z, till difference of number of nodes between X and Y, and setting the variable found if Y found as any of the parents.Now X and Z are at same height
Step 5: Start from same height same traversal starts upward and set the found variable. if both X and Z becomes null and not found any LCA, then found=false.
class YbetweenXandZ
{
public static Boolean YbetweenXnZ(Node nd1, Node nd2, Node Y)
{
Node cur1 = nd1;
Node cur2 = nd2;
Boolean found = false;
// calculate nd1 height
int nd1Height = 0;
while (cur1.Parent != null)
{
nd1Height++;
cur1 = cur1.Parent;
}
// calculate nd2 height
int nd2Height = 0;
while (cur2.Parent != null)
{
nd2Height++;
cur2 = cur2.Parent;
}
int diff = nd1Height - nd2Height;
cur1 = nd1;
cur2 = nd2;
if (diff > 0)
{
while (diff-- != 0)
{
if (Y == cur1.Parent)
found = true;
cur1 = cur1.Parent;
}
}
else
{
diff = -diff;
while (diff-- != 0)
{
if (Y == cur2.Parent)
found = true;
cur2 = cur2.Parent;
}
}
while (true)
{
//if not equal found, returns and found=false since not Y inside the path
if (cur1 == null || cur2 == null)
{
//not Y inside the path
found = false;
break;
}
if (cur1 == cur2)
{
return found;
}
cur1 = cur1.Parent;
cur2 = cur2.Parent;
if (Y == cur1 || Y == cur2)
found = true;
}
return found;
}
}
- BVarghese July 13, 2011using the bit sets logic for printing all combinations
Step 1: finding first m-1 bits to avoid and start from there.
step 2: finding the bits set in next number onward. Then set a BitArray for the same bits. Then counting total bits set in the BitArray.
step 3: if the count of bits set is m, then start printing them , else reset the
BitArray and start step 2.
public static void CombinationsOfMoutOfN(char []set,int m)
{
int n = set.Length;
int powerSet = (int)Math.Pow(2, n);
int skippingFirstMminusbits = (int)Math.Pow(2, m) - 1;
BitArray bitArray = new BitArray(n, false );
for (int i = skippingFirstMminusbits; i < powerSet; ++i)
{
int count = 0;
for (int j = 0; j < n; ++j)
{
//this is the logic
if ((i & (1 << j)) > 0)
{
count++;
bitArray[j] = true;
}
else
bitArray[j] = false;
}
if (count == m)
{
for (int j = 0; j < n; ++j)
{
if (bitArray[j] == true)
{
Console.Write(set[j]);
bitArray[j] = false;
}
}
}
count = 0;
Console.WriteLine("");
}
Please tell me if I am wrong. This work o(n) complexity. It needs a hash table for storing the missing elements.
This will print all missing numbers and all repeated numbers.
class Program
{
public static int[] arr;
public static Hashtable missingKArr=new Hashtable();
static void Main(string[] args)
{
arr = new int[30] { 29,29,29,8, 3, 1, 9, 10, 8, 9, 12, 2, 13, 13, 14, 11, 12, 0, 15, 16, 19, 21, 25, 26, 2, 13, 14, 11, 12, 0 };
//missing numbers 4,5,6,7,17,18,20,22,23,24,27,28,
MissingKElements(30);
Console.Read();
}
public static void MissingKElements(int n)
{
for (int i = 0; i < n; ++i)
{
if (arr[i] != i)
{
Swap(i);
}
}
for (int i = 0; i < n; ++i)
{
if (arr[i] != i)
{
//if the missing number found, then replace it to the position.
//then remove from hashtable
if (missingKArr.ContainsKey(i))
{
arr[i] = i;
missingKArr.Remove(i);
}
else
{
//this is missing
missingKArr.Add(i, 1);
}
if (arr[arr[i]] != arr[i])
{
Swap(i);
if (missingKArr.ContainsKey(i))
{
arr[arr[i]] = arr[i];
missingKArr.Remove(i);
}
}
}
}
//here prints all missing numbers and repeated numbers
for (int i = 0; i < n; ++i)
{
if (arr[i] != i)
{
Console.Write(i+" "+'\n');
Console.Write(" repeated number " + arr[i]);
}
Console.WriteLine();
}
}
private static void Swap(int i)
{
int temp1 = arr[i];
int temp2 = arr[temp1];
arr[temp1] = temp1;
arr[i] = temp2;
}
}
}
LList ll = new LList();
LLNode[] llArr = new LLNode[10] { null, null, null, null, null, null, null, null, null, null };
public void levelSumToList(Node root, int level)
{
Node[] queue = new Node[100];// Important to initialize!
int size = 0;
int queue_pointer = 0;
if (root != null)
{
//making the linkedlist and summing the list value each time
if (llArr[level] == null)
{
LLNode newNode = new LLNode(root.ID);
ll.Add(newNode);
llArr[level++] = newNode;
}
else
{
llArr[level++].ID += root.ID;
}
Console.Write(root.ID + "- > ");
levelSumToList (root.Left, level);
levelSumToList (root.Right, level);
}
}
public static void RandomUniqueNumbers(int n)
{
nArr = new int[n];
for (int i = 0; i < n; ++i)
{
nArr[i] = i + 1;
}
Random rand = new Random();
for (int i = n; i >0; --i)
{
int nextNum = rand.Next(0, i);
Console.WriteLine(nArr[nextNum]);
nArr[nextNum] = nArr[i-1];
}
}
Order Statistics of Tree for Median of a BST
Step 1: Add another ‘size’ variable which is to store the size of the nodes in the sub trees.
Step 2: Create the tree and find the size. When completion of tree, return the size stored at Root, which will be the total number of nodes in the tree.
Step 3: If the total number of nodes is n and it is an odd number, then n/2th number is the median, else (n/2 th number +(n/2+1) th number )/2 is the median
Step 4: Use order statistics to find the n/2 the largest number for odd, n/2 and (n/2+(n/2+1) )/2 for even.
After creating the Tree with size variable, use the following to find the largest number.
public Node KThLargest(int k, Node t)
{
int rsize = 0;
if (t == null)
return null;
// size of right subtree
if (t.Right != null)
rsize = t.Right.Size;
if (k == rsize + 1)
return t;
if (k <= rsize)
return KThLargest(k, t.Right);
else
return KThLargest((k - rsize - 1), t.Left);
}
O(n) is the complexity.
I am using @sugarbear idea and implementing it.
Please correct me if something went wrong.
//Step 1.take the first element from the preorder. It is the root
//step 2. check whether it is there in inorder and postorder. These are roots.
// set status=false and returns, if any where a mismatch occurs during.
// if it is there then
// find the PostorderSeperationIndex and PreorderSeperationIndex
// seperate the root and divide array into two sub arrays by using the above indexes -left side sub(tree) array and right side sub(tree) array
// step 3. Call the CheckTree function recursively with these indexes
public void CheckTree(int frI,int tI,int frPr,int tPr,int frPo,int tPo)
{
// Console.WriteLine( frPr + " <-from preo to ->" + tPr + " and " + frPo + " <-from posto to ->" + tPo+ " and "+frI + " <-from Ino to ->" + tI );
int rootInroder, rootPostorder, rootPreorder, postOrderIndex, preOrderIndex, temp3;
if ((frI == tI) && (frPr == tPr) && (frPo == tPo))
{
Boolean result = CheckRoot(frI, frPr, frPo);
if (result == false)
{
status = false;
return;
}
}
//sending the preorder root to inorder seperation function to divide it into two sub arrays and get the root position,if it exists
rootInroder = InorderSeperationIndex(preorder[frPr], frI, tI);
if (preorder[frPr] == postorder[tPo]&&rootInroder >= 0)
{
rootPostorder = tPo; rootPreorder = frPr;
postOrderIndex = PostorderSeperationIndex(postorder[tPo], frPo, tPo);
preOrderIndex = PreorderSeperationIndex(preorder[frPr], frPr, tPr);
if ((((rootInroder - 1) - frI) >= 0) && ((preOrderIndex - (frPr + 1)) >= 0) && ((postOrderIndex - frPo) >= 0))
{
CheckTree(frI, rootInroder - 1, frPr + 1, preOrderIndex, frPo, postOrderIndex);
}
if (((tI - (rootInroder + 1)) >= 0) && ((tPr - (preOrderIndex + 1)) >= 0) && ((tPo - 1 - (postOrderIndex + 1)) >= 0))
{
CheckTree(rootInroder + 1, tI, preOrderIndex + 1, tPr, postOrderIndex + 1, tPo - 1);
}
}
else
{
status = false;
return;
}
}
public Boolean CheckRoot(int rI, int rPr,int rPo)
{
if ((preorder[rPr] == postorder[rPo]) && (preorder[rPr] == inorder[rI]))
{
return true;
}
else
return false;
}
//returns the seperation index.
public int PreorderSeperationIndex(char root,int from,int to)
{
for (int i = from; i <= to; ++i)
{
if (preorder[i] > root)
{
return --i;
}
}
return -1;
}
//this will check till root and return the root
// so the root is i and right subtree starts from i+1
public int InorderSeperationIndex(char root, int from, int to)
{
for (int i = from; i <= to; ++i)
{
if (inorder[i] == root)
{
return i;
}
}
return -1;
}
//returns the seperation index.
public int PostorderSeperationIndex(char root,int from,int to)
{
for (int i = from; i <= to; ++i)
{
if (postorder[i] > root)
{
return --i;
}
}
return -1;
}
}
}
But interviewer was asking about the equation for the line and solve with that. I was trying to tell a similar idea like in the normal line segment problem like @Apostle is pointing to.
- BVarghese July 29, 2013