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
SieveOfEathonse
namespace PrimeNumbersListSieveOfEathonse
{
class Program
{
private static int upperLimit = 10000;
private static Boolean[] flags;
static void Main(string[] args)
{
findPrimes(upperLimit);
displayPrimes();
Console.ReadKey();
}
private static void findPrimes(int number)
{
int upperLimit = number;
flags = new Boolean[upperLimit + 1];
for (int position = 0; position <= upperLimit; position++)
{
flags[position] = false;
}
for (int position = 2; position <= Math.Sqrt(upperLimit); position++)
{
if (!flags[position])
{
int multiple = position * 2;
while (multiple <= upperLimit)
{
flags[multiple] = true;
multiple += position;
}
}
}
}
private static void displayPrimes() {
for (int position = 2; position <= upperLimit; position++) {
if (!flags[position]) {
Console.WriteLine(position + ", ");
}
}
}
}
}
1. add a variable count size(here Size) in tree node
2. Insert each node values and update the Size variable for each node
3.Enter the tree t and k to the KThLargest function .
4.if tree t is null , return null
5. rsize = t.Right.Size(right subtree size)
6.(if k==rsize+1)then a match occurs, returns the node, which is kth largest node
7.else if the k less than the rsize , recursively call function using the right subtree of the t and k.
8. else reduce the k by rsize+1 , and recursively call function using the left subtree of the t and k.
class BinaryTree
{
public Node root = null;
public void AddNode(Int16 value)
{
Node prev, cur, temp;
temp = new Node(value);
if (root == null)
{
root = temp;
return;
}
prev = null;
cur = root;
while (cur != null)
{
prev = cur;
if (value > cur.ID)
{
//count tree size for order statistics
cur.Size++;
cur = cur.Right;
}
else
{
//count tree size for order statistics
cur.Size++;
cur = cur.Left;
}
}
//adding aprent of the temp node
temp.Parent = prev;
if (value < prev.ID)
{
prev.Left = temp;
}
else
prev.Right = temp;
}
public Node KThSmallest(int k,Node t)
{
int lsize = 0;
if (t == null)
return null;
// size of left subtree
if (t.Left != null)
lsize= t.Left.Size;
if (k == lsize + 1)
return t;
if (k <= lsize)
return KThSmallest(k, t.Left);
else
return KThSmallest((k-lsize-1),t.Right);
}
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);
}
}
Please comment on this approach..find the pros and cons of this approach..
Using Suffix array.
1. Use an integer array (Say SuffixIndexArray) to store only the starting index number of the string.
2. Use radix sort to sort the SuffixIndexArray according to the real strings. Here take each index of the string and then take the string using this index. Then sort the real strings. Then store the starting index of the sorted strings on the SuffixIndexArray.
Eg. The original string is “Prepare”
The suffix array Strings are {“ Prepare”,”repare”,”epare”,”pare”,”are”,”re”,”e”}. But I am using the indexes on SuffixIndexArray and it is originally {0,1,2,3,4,5,6}
After sorting the string array, the SuffixIndexArray become {4,6,2,3,0,5,1}
3. LCP method to longest common prefix between two string
4. Select method is used to select the string from the original string.
5. Then use LongestRepeatedString method.
class SuffixArrayCompact
{
public int[] suffixIndexes;
public int N;
public String theOrginalText;
public SuffixArrayCompact(String s)
{
//keeping the theOrginalText
theOrginalText = s;
N = s.Length;
QuickSortCompact qs=new QuickSortCompact();
//this will sort the strings using the indexes but not stores in the string array.
// After sorting the suffixindexes will have the corresponding index of the sorted strings
suffixIndexes = qs.SuffixIndexArrayQsort(s);
}
// size of string
public int length() { return N; }
// ith sorted suffix
public String Select(int i) { return theOrginalText.Substring(suffixIndexes[i], N - suffixIndexes[i]); }
// length of longest common prefix of s and t
public int LCP(String s, String t)
{
int N = Math.Min(s.Length, t.Length);
for (int i = 0; i < N; i++)
if (s[i] != t[i]) return i;
return N;
}
public int LCP(int i)
{
return LCP(theOrginalText.Substring(suffixIndexes[i], N - suffixIndexes[i]), theOrginalText.Substring(suffixIndexes[i-1], N - suffixIndexes[i-1]));
}
}
class LongestRepeatedStringCompact
{
public void LongestRepeatedString()
{
String text = "abcedcedbinuvceddcedsbinuvajosephvbinuvjosephvced";
SuffixArrayCompact sa = new SuffixArrayCompact(text);
int N = sa.length();
String substring = "";
for (int i = 1; i < N; i++)
{
int length = sa.LCP(i);
if (length > substring.Length)
substring = sa.Select(i).Substring(0, length);
}
Console.WriteLine("'" + substring + "'");
}
}
//step 1. dividing whole array into two by applying partition by checking even or odd.Using first=true
//step 2. applying modified quicksort on the two divided arrays.Using first=false
public int Partition(int[] arr, int left, int right,Boolean first)
{
int i = left, j = right;
int tmp;
if (first == true)
{
while (i <= j)
{
while (arr[i] % 2 == 1)
i++;
while (arr[j] % 2 == 0)
j--;
if (i <= j)
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
}
else
{
int pivot = arr[(left + right) / 2];
while (i <= j)
{
if (pivot % 2 == 1)
{
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
}
else
{
while (arr[i] > pivot)
i++;
while (arr[j]< pivot)
j--;
}
if (i <= j)
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
}
return i;
}
public void QuickSort(int[] arr, int left, int right,Boolean first)
{
int index = Partition(arr, left, right,first);
first = false;
if (left < index - 1)
QuickSort(arr, left, index - 1, first);
if (index < right)
QuickSort(arr, index, right, first);
}
//Please add additional changes or feed back
- BVarghese March 10, 2011Algorithm.
//1. find whether the number of digits of the given number is even or odd. if odd , then seperate middle element
//2.convert first half digits and second half digits to different numbers. Middle element is seperated in
//the case of odd number of digits.
//3. if first half number is greater than second half number then, just copy first half number to
//second half number in reverse order. In odd case, keep the middle element without change.
//4. else add 1 to first half number. if it is odd convert first half and middle element to a
//number and then add 1.Then convert it to a different digits list. Then copy first half number except middle element
// to right side in reverse order
public void NextPalindromeNumber(Int32 number)
{
List<int> digitsArray = new List<int>();
List<int> digitsHalfArray = new List<int>();
digitsArray=NumberToDigits(number);
//if even number of digits, then consider middle two numbers as the middle
//convert digits from left to mid and mid-1 to a single number
//convert digits from right to mid to a single number
int count = digitsArray.Count;
int mid = count / 2;
int last = 0, first = 0,middle=0,i=0,j=0;
Boolean odd = false;
//if number of digits is even
if (count % 2 == 0)
{
last = DigitsToNumber(digitsArray, mid, count - 1);
first = DigitsToNumber(digitsArray, 0, mid - 1);
i = mid;
j = mid - 1;
}
else
{
odd=true;
middle = digitsArray[mid];
first = DigitsToNumber(digitsArray, 0, mid - 1);
last = DigitsToNumber(digitsArray, mid + 1, count - 1);
//mid is increased to adjust the midddle number in odd number of digits case
mid++;
i = mid;
j = mid - 2;
}
if (first > last)
{
for (; i < count; ++i, j--)
{
digitsArray.Insert(i,digitsArray[j]);
}
Console.WriteLine(DigitsToNumber(digitsArray,0, count - 1));
}
else
{
//including the middle digit also
first = DigitsToNumber(digitsArray, 0, mid-1);
//adding 1 to middle value
first = first + 1;
digitsHalfArray = NumberToDigits(first);
digitsArray=digitsHalfArray;
int dHalfCount=digitsArray.Count;
//adjustment for number with odd number of digits
if(odd==true)
{
mid--;
odd=false;
}
for (int k = mid-1; k >=0; --k)
{
digitsArray.Insert(dHalfCount++, digitsHalfArray[k]);
}
Console.WriteLine("Nearest Palindrome = " +DigitsToNumber(digitsArray, 0, digitsArray.Count-1));
}
}
private List<int> NumberToDigits(Int32 number)
{
List<int> digitsArray = new List<int>();
int[] tempArray = new int[51];
int tempCount = 0;
while (number > 0)
{
tempArray[tempCount++] = number % 10;
number = number / 10;
}
//reverse the digits and store in a list
for (int i = tempCount-1; i >= 0; --i)
{
digitsArray.Add(tempArray[i]);
}
return digitsArray;
}
public int DigitsToNumber(List<int> digitsArray,int start,int end)
{
int mulFactor = 10;
int num = 1;
int result = 0;
while (start <= end)
{
result += num * digitsArray[end--];
num *= mulFactor;
}
return result;
}
Implementing @fiddler.g's idea
//Time Complexity is O(n).
//Class for finding min and max using divide and conquer method
class MinMaxImpl
{
public int max, min;
int comparisonCount = 0;
public int []array=new int[10000];
static void Main(string[] args)
{
int num = 10000;
MinMaxImpl minMax = new MinMaxImpl();
Random rand = new Random();
for (int i = 0; i < num; i++)
{
minMax.array[i]=rand.Next(1,20000);
}
for (int i = 0; i < num; i++)
{
Console.WriteLine(minMax.array[i]);
}
minMax.max = minMax.array[0];
minMax.min = minMax.array[0];
minMax.MinMax(0, num-1);
Console.WriteLine("min =" + minMax.min + " max " + minMax.max+" comparison count = "+minMax.comparisonCount);
Console.ReadKey();
}
public void MinMax(int i, int j)
{
int max1, min1, mid;
if (i == j)
{
max = min = array[i];
}
else
{
if (i == j - 1)
{
if (array[i] < array[j])
{
comparisonCount++;
max = array[j];
min = array[i];
}
else
{
comparisonCount++;
max = array[i];
min = array[j];
}
}
else
{
mid = (i + j) / 2;
//Divide the array into two parts
MinMax(i, mid);
max1 = max; min1 = min;
MinMax(mid + 1, j);
//Conquer the two parts
if (max < max1)
{
comparisonCount++;
max = max1;
}
if (min > min1)
{
comparisonCount++;
min = min1;
}
}
}
}
}
In this algorithm, I am representing binary heap using an array by assuming that total words count can be found easily. Otherwise 1.a is not efficient. Then we have to use heap tree structure instead of binary heap using an array.
This algorithm using a binary tree and a min binary heap
1.a. Find the count of words .
1.b.Find 10% of the total words and which will be the size of the binary heap array.
1.b. Read each words.
2. Add it to the tree
3.a. If it is a new node, try to insert to the heap.
3.b.If the heap is full, then it will return null
3.c Else it will add the node to the heap and sift up the node.
4.a. if it is not already in the heap but frequency is greater than one, then will
check whether frequency is higher than the ExtractMinimum node from the Heap.
4.b. If the frequency is greater than the minimum node from the heap,then delete the minimum node from the heap and insert the
current node. And sift up the node.
4.c Update the variable 'selected' of node to false.
This will help to select the node to be inserted to the heap during next addnode call ,
if it got its frequency higher than the min node of heap.
5.a. If the word is already in the heap and its frequency will be increased.
5.b. Heapfy it again
Finally the heap will be having 10% mostly occurred words.
Please comment...
public void AddNode(String value,Int16 frequency)
{
HeapNode heapNode = new HeapNode(value,frequency);
Int16 selection = 0;
Node prev, cur, temp;
temp = new Node(value, frequency);
if (root == null)
{ //inserting the first word to the heap
if (Insert(heapNode))
{
temp.Selected = true;
}
root = temp;
return;
}
prev = null;
cur = root;
while (cur != null)
{
prev = cur;
if (value.CompareTo(cur.Word) > 0)
{
cur = cur.Right;
}
else if (value.CompareTo(cur.Word) < 0)
{
cur = cur.Left;
}
else
{
cur.Frequency = (Int16)(cur.Frequency + 1);
selection = 3;
break;
}
}
if (value.CompareTo(prev.Word)<0)
{
prev.Left = temp;
selection = 1;
}
else if (value.CompareTo(prev.Word) > 0)
{
prev.Right = temp;
selection = 2;
}
//section to make the heap.
if (selection == 1 && heapNodeSize<tenPercentOfTotalWords)
{
if (Insert(heapNode))
{
prev.Left.Selected = true;
}
}
else if (selection == 2 && heapNodeSize < tenPercentOfTotalWords)
{
if (Insert(heapNode))
{
prev.Right.Selected = true;
}
}
//frequency is greater than 1
else if (selection == 3 && heapNodeSize < tenPercentOfTotalWords)
{
//already in heap. here we are increasing the frequency and reheapify.
if (cur.Selected == true)
{
int i = 0;
for (i = 0; i < heapNodeSize; ++i)
{
if (array[i].Word.CompareTo(cur.Word) == 0)
{
array[i].Frequency=cur.Frequency;
break;
}
}
BuildMinHeap();
}
else
{
//it is not already in the heap but frequency is greater than one.
//checking whether frequency is higher than the ExtractMinimum node from the Heap
HeapNode min = ExtractMinimum();
if (min.Frequency < cur.Frequency)
{
HeapNode deletedHeapNode= DeleteElement();
SearchAndUpdateNode(deletedHeapNode.Word);
if (Insert(new HeapNode(cur.Word,cur.Frequency)))
{
cur.Selected = true;
}
}
}
}
}
public HeapNode ExtractMinimum()
{
if (heapNodeSize>0)
return array[0];
return null;
}
public void BuildMinHeap()
{
for (int i = 0; i < (heapNodeSize / 2); ++i)
{
MinHeapify(i);
}
}
public Boolean Insert(HeapNode node)
{
if(heapNodeSize < (tenPercentOfTotalWords-1))
{
heapNodeSize++;
array[heapNodeSize] = node;
SiftUp(heapNodeSize);
}
else
{
return false;
}
return true;
}
public void SiftUp(int nodeIndex)
{
int parentIndex = 0;
HeapNode tmp=null;
if (nodeIndex != 0)
{
parentIndex = (nodeIndex-1)/2;
if (array[parentIndex].Frequency > array[nodeIndex].Frequency)
{
//exchange
tmp = array[parentIndex];
array[parentIndex] = array[nodeIndex];
array[nodeIndex] = tmp;
SiftUp(parentIndex);
}
}
}
//if the frequency of a heap node comes haigher than the root node, then remove the root node and insert the coming node
//then set the Selected variable to false in the tree
public HeapNode DeleteElement()
{
HeapNode temp;
temp = array[0];
array[0] = array[heapNodeSize];
heapNodeSize--;
MinHeapify(0);
return temp;
}
//siftdown
public void MinHeapify( int i)
{
int left = 2 * i + 1;
int right = 2 * i + 2;
int min = 0;
//heap size is tenPercentOfTotalWords
if (left <= (tenPercentOfTotalWords-1) && array[left].Frequency < array[i].Frequency)
{
min = left;
}
else
{
min = i;
}
if (right <= (tenPercentOfTotalWords-1) && array[right].Frequency < array[min].Frequency)
{
min = right;
}
if (min != i)
{
HeapNode temp = array[i];
array[i] = array[min];
array[min] = temp;
MinHeapify(min);
}
}
public bool SearchAndUpdateNode(String value)
{
Node curr = root;
while (curr != null)
{
if (value.CompareTo(curr.Word) == 0)
{
curr.Selected = false;
return true;
}
if (value.CompareTo(curr.Word) < 0)
{
curr = curr.Left;
}
else
{
curr = curr.Right;
}
}
return false;
}
- BVarghese May 06, 2011