Given an array filled with 'n' random numbers, each number may or may not be repeated again in the array, (mix of duplicates and unique numbers) shift all non-duplicates to the start of the array. for example, if array is {4,2,17,2,56,2,4} output should be {4,2,17,56...} the remaining part of array can be modified to anything, doesnt matter
Tuesday, October 30, 2012
Bit stream has an alternating pattern or not
Write a function that returns true if the bit stream has an alternating pattern.
For example 000000101010 would return true and 0000001010000 would return false. Also write test cases for the function.
Strategy:
bool patternCheck(int a)
{
int b=a>>1;
/*if a=000000101010 then b=0=00000010101,,,,rightshift of a by 1*/
//now xor of a and b
int n=(a^b)+1;//n is in 2^n format if alternate bits are there
if(n & (n-1)) == 0) return true;
return false;
}
For example 000000101010 would return true and 0000001010000 would return false. Also write test cases for the function.
Strategy:
bool patternCheck(int a)
{
int b=a>>1;
/*if a=000000101010 then b=0=00000010101,,,,rightshift of a by 1*/
//now xor of a and b
int n=(a^b)+1;//n is in 2^n format if alternate bits are there
if(n & (n-1)) == 0) return true;
return false;
}
Thursday, October 25, 2012
Draw a circle
Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without making use of any floating point computations at all
Longest substring whose characters are continuous.
Given a string find the longest substring whose characters are continuous.
Input : "owadcbjkl"
Output: "adcb
BST with node equals sum of all greater nodes
Given a BST, convert it so that each node has value equal to sum of all the nodes (including itself) which are greater than that node in the whole tree.
Tuesday, October 23, 2012
Binary Tree in cartesian plane
Assume that a binary tree is drawn over a Cartesian
coordinate system (with X & Y axis) where the leftmost node is
placed at point (0,0). So, we need to traverse the nodes and print in
following manner:
For e.g., for this tree
a
b c
d e f g
Output should be:
d,0,0
b,1,1
e,2,0
a,3,2
f,4,0
c,5,1
g,6,0
the x-coordinate is its cardinal (order) in an inorder traversal; and
the y coordinate is the number of levels in the tree rooted at that node;
Using these 2 pieces you can easily get the output shown above...
For e.g., for this tree
a
b c
d e f g
Output should be:
d,0,0
b,1,1
e,2,0
a,3,2
f,4,0
c,5,1
g,6,0
Strategy:
You can easily note here that for any given node:the x-coordinate is its cardinal (order) in an inorder traversal; and
the y coordinate is the number of levels in the tree rooted at that node;
Using these 2 pieces you can easily get the output shown above...
int print(node* n, int &count) {
if (!n) return -1;
int height = print(n->left, count) + 1;
printf("%d,%d,%d", n->data, count++, height);
print(n->right, count);
return height;
}
print(root, 0);
kth smallest element in a sorted matrix
Assume you have a integer matrix (m x n) sorted over column wise & row wise. WAP to find the kth smallest element from the matrix.
E.g.
int[][] a =
2, 5, 8, 10
4, 7, 9, 12
6, 15, 20, 22
So 5th smallest element is: 7
Binary Tree Traversal-Modified
WAP to print the node values of a binary tree
- Even level starting from right to left
- Odd level starting from left to right
Assume that level of root is 1.
a
b c
d e f g
Output: a c b d e f g
Strategy:
Method 1:Two Stacks
static void print(Node root)
{
Stack<Node> odd = new Stack<Node>();
Stack<Node> even = new Stack<Node>();
odd.Push(root);
while (odd.Count != 0 || even.Count != 0)
{
while (odd.Count != 0)
{
Node node = odd.Pop();
if(node.left!=null)
even.Push(node.left);
if(node.right!=null)
even.Push(node.right);
Console.Write(node.data+" ");
}
Console.WriteLine();
while (even.Count != 0)
{
Node node = even.Pop();
if (node.right != null)
odd.Push(node.right);
if (node.left != null)
odd.Push(node.left);
Console.Write(node.data + " ");
}
Console.WriteLine();
}
}
Method 2:
Breadth First Search with a stack can solve this problem.1. Add the root node to the queue.
2. Get the head node of the queue and add its children to the queue.
3. If the node is in even level, print it. Otherwise, push it into the stack
4. When level of the head node has changed from odd to even,pop the stack and print the node
5. Repeat from 2 until all the node have been scaned
Monday, October 22, 2012
Mirror Puzzle !
Imagine you are standing in front of a mirror, facing it. Raise your left hand. Raise your right hand. Look at your reflection. When you raise your left hand your reflection raises what appears to be his right hand. But when you tilt your head up, your reflection does too, and does not appear to tilt his/her head down. Why is it that the mirror appears to reverse left and right, but not up and down?
Convert unknown base to decimal
Given an integer, write a program that converts the given number to a number (in base 10). The base of the given number is unknown.
Strategy:
The problem statement states that the base of the given number is unknown. Thus to proceed one must need to assume a base for the number. It is practically safe to assume that the digit with the maximum value in the number denotes the maximum that can be accounted in the unknown base. This a number if stated as, 254, it can be assumed that the number system consists of digits 0, 1, 2, 3, 4, 5 - or base 6.
Working on this assumption, it becomes fairly simple to code a function that will return a number for the given string representation of the number. The following JAVA code sample does the same, extending the above assumption to include digits 0 to 9 and characters A to Z, where A represents 10, B represents 11 and so on.
Code:
public Double convertUnknownBaseNumberToBase10(String number) {
// null check
if(number == null || number.length() == 0) {
return null;
}
// turn to upper case - so that our logic below is easy
number = number.toUpperCase();
// scan through the string to find out the maximum number or the character
int maxAscii = 0;
for(int i = 0; i < number.length(); i++) {
int ascii = number.charAt(i);
if(!(((ascii >= '0') && (ascii <= '9')) || ((ascii >= 'A') && (ascii <= 'Z')))) {
System.out.println("Illegal number, can have only digits (0-9) and letters (A-Z)");
return null;
}
maxAscii = Math.max(ascii, maxAscii);
}
// check if the number has letters or not
double finalNumber = 0;
int length = number.length();
if(maxAscii >= 'A') {
int maxNumber = maxAscii - 'A' + 10 + 1;
for(int i = 0; i < length; i++) {
int charCode = number.charAt(i);
if(charCode >= 'A') {
charCode = charCode - 'A' + 10;
}
int num = charCode;
finalNumber = finalNumber + (num * Math.pow(maxNumber, (length - i - 1)));
}
} else {
int maxNumber = maxAscii - '0' + 1;
// just iterate over a normal loop
for(int i = 0; i < length; i++) {
int num = number.charAt(i) - '0';
finalNumber = finalNumber + (num * Math.pow(maxNumber, (length - i - 1)));
}
}
return finalNumber;
}
Strategy:
The problem statement states that the base of the given number is unknown. Thus to proceed one must need to assume a base for the number. It is practically safe to assume that the digit with the maximum value in the number denotes the maximum that can be accounted in the unknown base. This a number if stated as, 254, it can be assumed that the number system consists of digits 0, 1, 2, 3, 4, 5 - or base 6.
Working on this assumption, it becomes fairly simple to code a function that will return a number for the given string representation of the number. The following JAVA code sample does the same, extending the above assumption to include digits 0 to 9 and characters A to Z, where A represents 10, B represents 11 and so on.
Code:
public Double convertUnknownBaseNumberToBase10(String number) {
// null check
if(number == null || number.length() == 0) {
return null;
}
// turn to upper case - so that our logic below is easy
number = number.toUpperCase();
// scan through the string to find out the maximum number or the character
int maxAscii = 0;
for(int i = 0; i < number.length(); i++) {
int ascii = number.charAt(i);
if(!(((ascii >= '0') && (ascii <= '9')) || ((ascii >= 'A') && (ascii <= 'Z')))) {
System.out.println("Illegal number, can have only digits (0-9) and letters (A-Z)");
return null;
}
maxAscii = Math.max(ascii, maxAscii);
}
// check if the number has letters or not
double finalNumber = 0;
int length = number.length();
if(maxAscii >= 'A') {
int maxNumber = maxAscii - 'A' + 10 + 1;
for(int i = 0; i < length; i++) {
int charCode = number.charAt(i);
if(charCode >= 'A') {
charCode = charCode - 'A' + 10;
}
int num = charCode;
finalNumber = finalNumber + (num * Math.pow(maxNumber, (length - i - 1)));
}
} else {
int maxNumber = maxAscii - '0' + 1;
// just iterate over a normal loop
for(int i = 0; i < length; i++) {
int num = number.charAt(i) - '0';
finalNumber = finalNumber + (num * Math.pow(maxNumber, (length - i - 1)));
}
}
return finalNumber;
}
Sunday, October 21, 2012
Pairwise sum
If pairwise sums of 'n' numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1
Example:
i/p:
4
4 5 7 10 12 13
o/p:
1 3 4 9
Strategy:
We will build A up from smallest element to largest. Suppose A and B are integer lists such that B gives the pairwise sums for A, where A[0] < A[1] < A[2] < ... and B[0] <= B[1] <= B[2] <= ... . Given B, we wish to find A. Suppose that we already know A[0]. Then, since P[0] is the smallest element in B, it can only arise as A[0] + A[1]. Similarly, P[1] must equal A[0] + A[2]. Therefore, if we know A[0], we can compute A[1] and A[2].
After that, however, this pattern breaks down. B[2] could either be A[0] + A[3] or A[1] + A[2] and without prior knowledge, we cannot know which one it is.
If we know A[0], we can compute A[1] and A[2] as described above, and then remove A[1] + A[2] from B. The next smallest element is then guaranteed to be A[0] + A[3], which allows us to find A[3].
Similarly, if we know A[0], A[1], A[2], and A[3], we can remove A{i}+A[j], 0 <= i < j <= 3, from B. The next smallest element of B will be A[0]+A[4], which allows us to compute A[4]. Repeating in this way, we can find all of A without ever backtracking.
Thus, once we know A[0], we can compute the rest of A. For this problem, we can now simply try every possibility for A[0]. We are given A contains only distinct non-negative integers, and A[1] > A[0], so A[0] must be an integer between 0 and B[0]/2 - 1 inclusive.
So whatever is the maximum value of B[0], we will have to try B[0]/2 possibilities for A[0].
Occurrence count for each Integer
Given a Integer array, we have to print the occurrence count for each Integer. What will be the optimal solution.
Strategy:
Best solution is to build a binary search tree...if while searching u come across a NULL ...insert that node there....if while searching u find that element increase the count...Then print each element in the tree by traversing it.
Note:
Hash table implementation is suitable when the integers are falling into a certain range say 0 to 100. We can take an array of 100 and the implementation is straight forward.
But say an array which contains only one element 100000. We can not take that much array size. Even if we take a smaller array and implement the hash algo there is always be a chance of collisions.
Strategy:
Best solution is to build a binary search tree...if while searching u come across a NULL ...insert that node there....if while searching u find that element increase the count...Then print each element in the tree by traversing it.
Note:
Hash table implementation is suitable when the integers are falling into a certain range say 0 to 100. We can take an array of 100 and the implementation is straight forward.
But say an array which contains only one element 100000. We can not take that much array size. Even if we take a smaller array and implement the hash algo there is always be a chance of collisions.
Nodes at same depth
Problem is to find print all the nodes at the same levels of a binary tree.Inputs given are root pointer and the pointer to the node (let it be A)whose level elements need to be printed.
Strategy:
Find the depth of the node A.
Then do a depth wise traversal of the tree by tracking the level u are at currently.
Now when u get a node of equal depth as A then print it and do a back traversal from there as other nodes from the current node will result in a higher depth. Thus we can find all the nodes at the current level.
Strategy:
Find the depth of the node A.
Then do a depth wise traversal of the tree by tracking the level u are at currently.
Now when u get a node of equal depth as A then print it and do a back traversal from there as other nodes from the current node will result in a higher depth. Thus we can find all the nodes at the current level.
Java Internals
Java Threading:
Thread, Concurrency, and Synchronization
Java Design Pattern:
http://www.programcreek.com/category/design-patterns/
http://javarevisited.blogspot.in/2012/06/20-design-pattern-and-software-design.html
http://www.programcreek.com/java-design-patterns-in-stories/
Java Memory Model and Memory Leaks:
http://www.programcreek.com/2011/11/what-do-java-objects-look-like-in-memory/
http://www.programcreek.com/2013/04/what-does-a-java-array-look-like-in-memory/
http://www.programcreek.com/2011/10/how-java-compiler-generate-code-for-overloaded-and-overridden-methods/
http://www.programcreek.com/2013/10/the-introduction-of-memory-leak-what-why-and-how/
http://www.programcreek.com/2011/10/java-class-instance-initializers/
Java Garbage Collection:
Thread, Concurrency, and Synchronization
Java Design Pattern:
http://www.programcreek.com/category/design-patterns/
http://javarevisited.blogspot.in/2012/06/20-design-pattern-and-software-design.html
http://www.programcreek.com/java-design-patterns-in-stories/
Java Memory Model and Memory Leaks:
http://www.programcreek.com/2011/11/what-do-java-objects-look-like-in-memory/
http://www.programcreek.com/2013/04/what-does-a-java-array-look-like-in-memory/
http://www.programcreek.com/2011/10/how-java-compiler-generate-code-for-overloaded-and-overridden-methods/
http://www.programcreek.com/2013/10/the-introduction-of-memory-leak-what-why-and-how/
http://www.programcreek.com/2011/10/java-class-instance-initializers/
Java Garbage Collection:
Java Advanced:
Java Framework:
Java Misc:
Thursday, October 18, 2012
Construct BST from preorder traversal
Given preorder traversal of a binary search tree, construct the BST.
For example, if the given traversal is {10, 5, 1, 7, 40, 50}, then the output should be root of following tree.
10
/ \
5 40
/ \ \
1 7 50
http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/
http://algorithms.tutorialhorizon.com/construct-binary-search-tree-from-a-given-preorder-traversal-using-recursion/
http://algorithms.tutorialhorizon.com/construct-binary-search-tree-from-a-given-preorder-traversal-using-stack-without-recursion/
Variation 1:
Given the Pre-order of the BST .check if each non-leaf node has only one child.Linear Time is expected.
Method 1 ( O(n^2) time complexity )
The first element of preorder traversal is always root. We first construct the root. Then we find the index of first element which is greater than root. Let the index be ‘i’. The values between root and ‘i’ will be part of left subtree, and the values between ‘i+1′ and ‘n-1′ will be part of right subtree. Divide given pre[] at index “i” and recur for left and right sub-trees.
For example in {10, 5, 1, 7, 40, 50}, 10 is the first element, so we make it root. Now we look for the first element greater than 10, we find 40. So we know the structure of BST is as following.
10
/ \
/ \
{5, 1, 7} {40, 50}
We recursively follow above steps for subarrays {5, 1, 7} and {40, 50}, and get the complete tree.
Code:
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node* newNode (int data)
{
struct node* temp = (struct node *) malloc( sizeof(struct node) );
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
struct node* constructTreeUtil (int pre[], int* preIndex,
int low, int high, int size)
{
// Base case
if (*preIndex >= size || low > high)
return NULL;
// The first node in preorder traversal is root. So take the node at
// preIndex from pre[] and make it root, and increment preIndex
struct node* root = newNode ( pre[*preIndex] );
*preIndex = *preIndex + 1;
// If the current subarry has only one element, no need to recur
if (low == high)
return root;
// Search for the first element greater than root
int i;
for ( i = low; i <= high; ++i )
if ( pre[ i ] > root->data )
break;
// Use the index of element found in postorder to divide postorder array in
// two parts. Left subtree and right subtree
root->left = constructTreeUtil ( pre, preIndex, *preIndex, i - 1, size );
root->right = constructTreeUtil ( pre, preIndex, i, high, size );
return root;
}
struct node *constructTree (int pre[], int size)
{
int preIndex = 0;
return constructTreeUtil (pre, &preIndex, 0, size - 1, size);
}
void printInorder (struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
int main ()
{
int pre[] = {10, 5, 1, 7, 40, 50};
int size = sizeof( pre ) / sizeof( pre[0] );
struct node *root = constructTree(pre, size);
printf("Inorder traversal of the constructed tree: \n");
printInorder(root);
getchar();
return 0;
}
Time Complexity: O(n^2)
Method 2 ( O(n) time complexity )
The idea used here is inspired from method 3 of this post. The trick is to set a range {min .. max} for every node. Initialize the range as {INT_MIN .. INT_MAX}. The first node will definitely be in range, so create root node. To construct the left subtree, set the range as {INT_MIN …root->data}. If a values is in the range {INT_MIN .. root->data}, the values is part part of left subtree. To construct the right subtree, set the range as {root->data..max .. INT_MAX}.
Code:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node* newNode (int data)
{
struct node* temp = (struct node *) malloc( sizeof(struct node) );
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
struct node* constructTreeUtil( int pre[], int* preIndex, int key,
int min, int max, int size )
{
// Base case
if( *preIndex >= size )
return NULL;
struct node* root = NULL;
// If current element of pre[] is in range, then
// only it is part of current subtree
if( key > min && key < max )
{
// Allocate memory for root of this subtree and increment *preIndex
root = newNode ( key );
*preIndex = *preIndex + 1;
// Contruct the subtree under root
// All nodes which are in range {min .. key} will go in left
// subtree, and first such node will be root of left subtree.
root->left = constructTreeUtil( pre, preIndex, pre[*preIndex],
min, key, size );
// All nodes which are in range {key..max} will go in right
// subtree, and first such node will be root of right subtree.
root->right = constructTreeUtil( pre, preIndex, pre[*preIndex],
key, max, size );
}
return root;
}
struct node *constructTree (int pre[], int size)
{
int preIndex = 0;
return constructTreeUtil ( pre, &preIndex, pre[0], INT_MIN, INT_MAX, size );
}
void printInorder (struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
int main ()
{
int pre[] = {10, 5, 1, 7, 40, 50};
int size = sizeof( pre ) / sizeof( pre[0] );
struct node *root = constructTree(pre, size);
printf("Inorder traversal of the constructed tree: \n");
printInorder(root);
getchar();
return 0;
}
Time Complexity: O(n)
Variation 1:
http://www.careercup.com/question?id=14453690
For example, if the given traversal is {10, 5, 1, 7, 40, 50}, then the output should be root of following tree.
10
/ \
5 40
/ \ \
1 7 50
http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/
http://algorithms.tutorialhorizon.com/construct-binary-search-tree-from-a-given-preorder-traversal-using-recursion/
http://algorithms.tutorialhorizon.com/construct-binary-search-tree-from-a-given-preorder-traversal-using-stack-without-recursion/
Variation 1:
Given the Pre-order of the BST .check if each non-leaf node has only one child.Linear Time is expected.
Method 1 ( O(n^2) time complexity )
The first element of preorder traversal is always root. We first construct the root. Then we find the index of first element which is greater than root. Let the index be ‘i’. The values between root and ‘i’ will be part of left subtree, and the values between ‘i+1′ and ‘n-1′ will be part of right subtree. Divide given pre[] at index “i” and recur for left and right sub-trees.
For example in {10, 5, 1, 7, 40, 50}, 10 is the first element, so we make it root. Now we look for the first element greater than 10, we find 40. So we know the structure of BST is as following.
10
/ \
/ \
{5, 1, 7} {40, 50}
We recursively follow above steps for subarrays {5, 1, 7} and {40, 50}, and get the complete tree.
Code:
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node* newNode (int data)
{
struct node* temp = (struct node *) malloc( sizeof(struct node) );
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
struct node* constructTreeUtil (int pre[], int* preIndex,
int low, int high, int size)
{
// Base case
if (*preIndex >= size || low > high)
return NULL;
// The first node in preorder traversal is root. So take the node at
// preIndex from pre[] and make it root, and increment preIndex
struct node* root = newNode ( pre[*preIndex] );
*preIndex = *preIndex + 1;
// If the current subarry has only one element, no need to recur
if (low == high)
return root;
// Search for the first element greater than root
int i;
for ( i = low; i <= high; ++i )
if ( pre[ i ] > root->data )
break;
// Use the index of element found in postorder to divide postorder array in
// two parts. Left subtree and right subtree
root->left = constructTreeUtil ( pre, preIndex, *preIndex, i - 1, size );
root->right = constructTreeUtil ( pre, preIndex, i, high, size );
return root;
}
struct node *constructTree (int pre[], int size)
{
int preIndex = 0;
return constructTreeUtil (pre, &preIndex, 0, size - 1, size);
}
void printInorder (struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
int main ()
{
int pre[] = {10, 5, 1, 7, 40, 50};
int size = sizeof( pre ) / sizeof( pre[0] );
struct node *root = constructTree(pre, size);
printf("Inorder traversal of the constructed tree: \n");
printInorder(root);
getchar();
return 0;
}
Time Complexity: O(n^2)
Method 2 ( O(n) time complexity )
The idea used here is inspired from method 3 of this post. The trick is to set a range {min .. max} for every node. Initialize the range as {INT_MIN .. INT_MAX}. The first node will definitely be in range, so create root node. To construct the left subtree, set the range as {INT_MIN …root->data}. If a values is in the range {INT_MIN .. root->data}, the values is part part of left subtree. To construct the right subtree, set the range as {root->data..max .. INT_MAX}.
Code:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node* newNode (int data)
{
struct node* temp = (struct node *) malloc( sizeof(struct node) );
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
struct node* constructTreeUtil( int pre[], int* preIndex, int key,
int min, int max, int size )
{
// Base case
if( *preIndex >= size )
return NULL;
struct node* root = NULL;
// If current element of pre[] is in range, then
// only it is part of current subtree
if( key > min && key < max )
{
// Allocate memory for root of this subtree and increment *preIndex
root = newNode ( key );
*preIndex = *preIndex + 1;
// Contruct the subtree under root
// All nodes which are in range {min .. key} will go in left
// subtree, and first such node will be root of left subtree.
root->left = constructTreeUtil( pre, preIndex, pre[*preIndex],
min, key, size );
// All nodes which are in range {key..max} will go in right
// subtree, and first such node will be root of right subtree.
root->right = constructTreeUtil( pre, preIndex, pre[*preIndex],
key, max, size );
}
return root;
}
struct node *constructTree (int pre[], int size)
{
int preIndex = 0;
return constructTreeUtil ( pre, &preIndex, pre[0], INT_MIN, INT_MAX, size );
}
void printInorder (struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
int main ()
{
int pre[] = {10, 5, 1, 7, 40, 50};
int size = sizeof( pre ) / sizeof( pre[0] );
struct node *root = constructTree(pre, size);
printf("Inorder traversal of the constructed tree: \n");
printInorder(root);
getchar();
return 0;
}
Time Complexity: O(n)
Variation 1:
http://www.careercup.com/question?id=14453690
Tuesday, October 16, 2012
String Replacement / String Removal !
Replace all occurrence of the given pattern to ‘X’.
For example, given that the pattern=”abc”, replace “abcdeffdfegabcabc” with “XdeffdfegX”. Note that multiple occurrences of abc’s that are contiguous will be replaced with only one ‘X’.
Variation:
Remove all occurrences of the given pattern/string from another string.
for example:
char str[]="absbdababad";
char pattern[]="ab";
then our function should return "sbdad"
Strategy:
We should take advantage that the replacement is only one character in length. Assume that the pattern is at least one character in length, then the replacement’s length will never exceed the pattern’s length. This means that when we overwrite the existing string with replacement, we would never overwrite characters that would be read next.
Two pointers are also used for an efficient in-place replacement, which traverses the string once without any extra memory.
Code:
bool isMatch(char *str, const char* pattern) {
while (*pattern)
if (*str++ != *pattern++)
return false;
return true;
}
void replace(char str[], const char *pattern) {
if (str == NULL || pattern == NULL) return;
char *pSlow = str, *pFast = str;
int pLen = strlen(pattern);
while (*pFast != '\0') {
bool matched = false;
while (isMatch(pFast, pattern)) {
matched = true;
pFast += pLen;
}
if (matched)
*pSlow++ = 'X';
// tricky case to handle here:
// pFast might be pointing to '\0',
// and you don't want to increment past it
if (*pFast != '\0')
*pSlow++ = *pFast++; // *p++ = (*p)++
}
// don't forget to add a null character at the end!
*pSlow = '\0';
}
Test cases:
Format is string, pattern = answer)
-----------------------------------
a, a = X
aa, aa = X
aa, a = X
aa, aaa = aa
abc, abc = X
abcabc, abc = X
abcabcabc, abc = X
abcaabcaabc, abc = XaXaX
abcaaabcaaabca, abc = XaaXaaXa
abcabcabababcabc, abc = XababX
abcabcabababcabcab, abc = XababXab
aabbaabbaaabbbaabb, aabb = XaXbX
aabbaabbaaabbbaabb, aaabb = aabbaabbXbaabb
aabbaabbaaabbbaaabb, aaabb = aabbaabbXbX
aabbaabbaaabbbaaabc, aaabb = aabbaabbXbaaabc
abcdeffdfegabcabc, abc = XdeffdfegX
abcdeffdfegabcabc, ab = XcdeffdfegXcXc
abcdeffdfegabcabc, a = XbcdeffdfegXbcXbc
abcdeffdfegabcab, abc = XdeffdfegXab
abcdeffdfegabcabcab, abc = XdeffdfegXab
abcdeffdfegabcaabcab, abc = XdeffdfegXaXab
abcdeffdfegabcaaaabcab, abc = XdeffdfegXaaaXab
aaaaaa, a = X
aaaaaa, aa = X
aaaaaa, aaaaaa = X
aaaaaa, aaaaaaa = aaaaaa
aabaababaaab, a = XbXbXbXb
aabaababaaa, a = XbXbXbX
aaaab, a = Xb
baaa, a = bX
aabaaabaab, aaa = aabXbaab
aabaaabaab, aa = XbXabXb
aabaaabaa, aa = XbXabX
Variation:
In the above program we can keep the slow pointer at its place and continue the loop if matched is true
Code:
#include <iostream>
using namespace std;
bool isMatch(char *str, const char* pattern) {
while (*pattern)
if (*str++ != *pattern++)
return false;
return true;
}
void replace(char str[], const char *pattern) {
if (str == NULL || pattern == NULL) return;
char *pSlow = str, *pFast = str;
int pLen = strlen(pattern);
while (*pFast != '\0') {
bool matched = false;
while (isMatch(pFast, pattern)) {
matched = true;
pFast += pLen;
}
if (matched)
continue;
// *pSlow++ = 'X';
// tricky case to handle here:
// pFast might be pointing to '\0',
// and you don't want to increment past it
if (*pFast != '\0')
*pSlow++ = *pFast++; // *p++ = (*p)++
}
// don't forget to add a null character at the end!
*pSlow = '\0';
}
int main()
{
char str[]="absbdababad";
char pattern[]="ab";
replace(str, pattern);
printf("\n%s",str);
getchar();
return 0;
}
For example, given that the pattern=”abc”, replace “abcdeffdfegabcabc” with “XdeffdfegX”. Note that multiple occurrences of abc’s that are contiguous will be replaced with only one ‘X’.
Variation:
Remove all occurrences of the given pattern/string from another string.
for example:
char str[]="absbdababad";
char pattern[]="ab";
then our function should return "sbdad"
Strategy:
We should take advantage that the replacement is only one character in length. Assume that the pattern is at least one character in length, then the replacement’s length will never exceed the pattern’s length. This means that when we overwrite the existing string with replacement, we would never overwrite characters that would be read next.
Two pointers are also used for an efficient in-place replacement, which traverses the string once without any extra memory.
Code:
bool isMatch(char *str, const char* pattern) {
while (*pattern)
if (*str++ != *pattern++)
return false;
return true;
}
void replace(char str[], const char *pattern) {
if (str == NULL || pattern == NULL) return;
char *pSlow = str, *pFast = str;
int pLen = strlen(pattern);
while (*pFast != '\0') {
bool matched = false;
while (isMatch(pFast, pattern)) {
matched = true;
pFast += pLen;
}
if (matched)
*pSlow++ = 'X';
// tricky case to handle here:
// pFast might be pointing to '\0',
// and you don't want to increment past it
if (*pFast != '\0')
*pSlow++ = *pFast++; // *p++ = (*p)++
}
// don't forget to add a null character at the end!
*pSlow = '\0';
}
Test cases:
Format is string, pattern = answer)
-----------------------------------
a, a = X
aa, aa = X
aa, a = X
aa, aaa = aa
abc, abc = X
abcabc, abc = X
abcabcabc, abc = X
abcaabcaabc, abc = XaXaX
abcaaabcaaabca, abc = XaaXaaXa
abcabcabababcabc, abc = XababX
abcabcabababcabcab, abc = XababXab
aabbaabbaaabbbaabb, aabb = XaXbX
aabbaabbaaabbbaabb, aaabb = aabbaabbXbaabb
aabbaabbaaabbbaaabb, aaabb = aabbaabbXbX
aabbaabbaaabbbaaabc, aaabb = aabbaabbXbaaabc
abcdeffdfegabcabc, abc = XdeffdfegX
abcdeffdfegabcabc, ab = XcdeffdfegXcXc
abcdeffdfegabcabc, a = XbcdeffdfegXbcXbc
abcdeffdfegabcab, abc = XdeffdfegXab
abcdeffdfegabcabcab, abc = XdeffdfegXab
abcdeffdfegabcaabcab, abc = XdeffdfegXaXab
abcdeffdfegabcaaaabcab, abc = XdeffdfegXaaaXab
aaaaaa, a = X
aaaaaa, aa = X
aaaaaa, aaaaaa = X
aaaaaa, aaaaaaa = aaaaaa
aabaababaaab, a = XbXbXbXb
aabaababaaa, a = XbXbXbX
aaaab, a = Xb
baaa, a = bX
aabaaabaab, aaa = aabXbaab
aabaaabaab, aa = XbXabXb
aabaaabaa, aa = XbXabX
Variation:
In the above program we can keep the slow pointer at its place and continue the loop if matched is true
Code:
#include <iostream>
using namespace std;
bool isMatch(char *str, const char* pattern) {
while (*pattern)
if (*str++ != *pattern++)
return false;
return true;
}
void replace(char str[], const char *pattern) {
if (str == NULL || pattern == NULL) return;
char *pSlow = str, *pFast = str;
int pLen = strlen(pattern);
while (*pFast != '\0') {
bool matched = false;
while (isMatch(pFast, pattern)) {
matched = true;
pFast += pLen;
}
if (matched)
continue;
// *pSlow++ = 'X';
// tricky case to handle here:
// pFast might be pointing to '\0',
// and you don't want to increment past it
if (*pFast != '\0')
*pSlow++ = *pFast++; // *p++ = (*p)++
}
// don't forget to add a null character at the end!
*pSlow = '\0';
}
int main()
{
char str[]="absbdababad";
char pattern[]="ab";
replace(str, pattern);
printf("\n%s",str);
getchar();
return 0;
}
Thursday, October 11, 2012
Find first occurrence of a string in another
Given two strings s1 and s2, find the first index of s2 in s1 in an efficient manner.
Strategy:
The problem has very typical solution, starting with each character in the source string start looking if the string being searched for, exists or not. However, the implementations may differ on the way they optimize. One good approach is to first look for the starting character of the string being searched for, in the string being searched. If found, then go ahead and look for other matches character by character.
We can optimize above implementation. As strings get longer in length, one may employ various mechanisms to check for equality. One such method being checking for the first character - if that results in a match, compare the last character. If that succeeds as well, go ahead and check the second and then second last character. This way one can zero down to matches to the center of the string being searched for. This particular approach considers that some words are used again and again in a string, but the longer the strings the probability of repetition of the letter at same index zero's down.
Code:
#include<iostream>
#include<string.h>
using namespace std;
int findStringInString(string stringToSearchIn, string stringToSearchFor)
{
int lengthIn = strlen(stringToSearchIn);
int lengthFor = strlen(stringToSearchFor);
if(lengthFor > lengthIn) {
// System.out.println("Sub-string candidate is larger than original string");
return -1;
}
if(lengthFor == lengthIn) {
for(int index = 0; index < lengthIn; index++) {
if(stringToSearchIn[index] != stringToSearchFor[index]) {
// no match found
return -1;
}
}
return 0;
}
// lengthFor < lengthIn
for(int index = 0; index < (lengthIn - lengthFor); index++) {
if(stringToSearchIn[index] == stringToSearchFor[0]) {
boolean found = true;
// first char match found
// check if the string beyond this is equal
for(int subIndex = 0; subIndex < lengthFor; subIndex++) {
if(stringToSearchIn[index + subIndex] != stringToSearchFor[subIndex]) {
// no match
found = false;
break;
}
}
if(found) {
// System.out.println("Match found at index: " + index + " in original string.");
// System.out.println(stringToSearchIn.substring(index, index + lengthFor));
return index;
}
}
}
return -1;
}
int main()
( string str= "abcddercd";
string str2="cd";
int a=findStringInString(str, str2);
getchar();
return 0;
}
Strategy:
The problem has very typical solution, starting with each character in the source string start looking if the string being searched for, exists or not. However, the implementations may differ on the way they optimize. One good approach is to first look for the starting character of the string being searched for, in the string being searched. If found, then go ahead and look for other matches character by character.
We can optimize above implementation. As strings get longer in length, one may employ various mechanisms to check for equality. One such method being checking for the first character - if that results in a match, compare the last character. If that succeeds as well, go ahead and check the second and then second last character. This way one can zero down to matches to the center of the string being searched for. This particular approach considers that some words are used again and again in a string, but the longer the strings the probability of repetition of the letter at same index zero's down.
Code:
#include<iostream>
#include<string.h>
using namespace std;
int findStringInString(string stringToSearchIn, string stringToSearchFor)
{
int lengthIn = strlen(stringToSearchIn);
int lengthFor = strlen(stringToSearchFor);
if(lengthFor > lengthIn) {
// System.out.println("Sub-string candidate is larger than original string");
return -1;
}
if(lengthFor == lengthIn) {
for(int index = 0; index < lengthIn; index++) {
if(stringToSearchIn[index] != stringToSearchFor[index]) {
// no match found
return -1;
}
}
return 0;
}
// lengthFor < lengthIn
for(int index = 0; index < (lengthIn - lengthFor); index++) {
if(stringToSearchIn[index] == stringToSearchFor[0]) {
boolean found = true;
// first char match found
// check if the string beyond this is equal
for(int subIndex = 0; subIndex < lengthFor; subIndex++) {
if(stringToSearchIn[index + subIndex] != stringToSearchFor[subIndex]) {
// no match
found = false;
break;
}
}
if(found) {
// System.out.println("Match found at index: " + index + " in original string.");
// System.out.println(stringToSearchIn.substring(index, index + lengthFor));
return index;
}
}
}
return -1;
}
int main()
( string str= "abcddercd";
string str2="cd";
int a=findStringInString(str, str2);
getchar();
return 0;
}
Concatenate N strings
Concatenate N strings with good optimization
You have n strings with their lengths. You are given an add(string s1,string s2) which would concatenate the string s2 with s1 and return s3. Optimize the cost of concatenation of all these strings into one big string.
Eg: 1,3,2 are the lengths of given strings.
1+3=4
4+2=6
total cost=10
Optimize this total cost?
Strategy:
Make a min heap out of the elements given.
Pop the smallest and the second smallest, add them and again insert that back to the heap.
Finally you will get the minimum cost
OR
you can sort the array on the basis of length...and then just concatenate on the length of the string.
You have n strings with their lengths. You are given an add(string s1,string s2) which would concatenate the string s2 with s1 and return s3. Optimize the cost of concatenation of all these strings into one big string.
Eg: 1,3,2 are the lengths of given strings.
1+3=4
4+2=6
total cost=10
Optimize this total cost?
Strategy:
Make a min heap out of the elements given.
Pop the smallest and the second smallest, add them and again insert that back to the heap.
Finally you will get the minimum cost
OR
you can sort the array on the basis of length...and then just concatenate on the length of the string.
String Concepts
Strings are treated in C/C++ as character arrays terminated by NULL. They can be stored in either statically or dynamically allocated arrays. In either case, a string is represented by a char* pointer that points to the beginning of the string, and the string spans the memory from its beginning to the first NULL. Strings are not an innate data type of C/C++ and the language provides no means to deal with them
Let us consider the below program.
#include<stdio.h>
void swap(char *str1, char *str2)
{
char *temp = str1;
str1 = str2;
str2 = temp;
}
int main()
{
char *str1 = "geeks";
char *str2 = "forgeeks";
swap(str1, str2);
printf("str1 is %s, str2 is %s", str1, str2);
getchar();
return 0;
}
Output of the program is str1 is geeks, str2 is forgeeks. So the above swap() function doesn’t swap strings. The function just changes local pointer variables and the changes are not reflected outside the function.
Let us see the correct ways for swapping strings:
Method 1(Swap Pointers)
If you are using character pointer for strings (not arrays) then change str1 and str2 to point each other’s data. i.e., swap pointers. In a function, if we want to change a pointer (and obviously we want changes to be reflected outside the function) then we need to pass a pointer to the pointer.
#include<stdio.h>
/* Swaps strings by swapping pointers */
void swap1(char **str1_ptr, char **str2_ptr)
{
char *temp = *str1_ptr;
*str1_ptr = *str2_ptr;
*str2_ptr = temp;
}
int main()
{
char *str1 = "geeks";
char *str2 = "forgeeks";
swap1(&str1, &str2);
printf("str1 is %s, str2 is %s", str1, str2);
getchar();
return 0;
}
This method cannot be applied if strings are stored using character arrays.
Method 2(Swap Data)
If you are using character arrays to store strings then preferred way is to swap the data of both arrays.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
/* Swaps strings by swapping data*/
void swap2(char *str1, char *str2)
{
char *temp = (char *)malloc((strlen(str1) + 1) * sizeof(char));
strcpy(temp, str1);
strcpy(str1, str2);
strcpy(str2, temp);
free(temp);
}
int main()
{
char str1[10] = "geeks";
char str2[10] = "forgeeks";
swap2(str1, str2);
printf("str1 is %s, str2 is %s", str1, str2);
getchar();
return 0;
}
This method cannot be applied for strings stored in read only block of memory.
Swapping Strings:
Let us consider the below program.
#include<stdio.h>
void swap(char *str1, char *str2)
{
char *temp = str1;
str1 = str2;
str2 = temp;
}
int main()
{
char *str1 = "geeks";
char *str2 = "forgeeks";
swap(str1, str2);
printf("str1 is %s, str2 is %s", str1, str2);
getchar();
return 0;
}
Output of the program is str1 is geeks, str2 is forgeeks. So the above swap() function doesn’t swap strings. The function just changes local pointer variables and the changes are not reflected outside the function.
Let us see the correct ways for swapping strings:
Method 1(Swap Pointers)
If you are using character pointer for strings (not arrays) then change str1 and str2 to point each other’s data. i.e., swap pointers. In a function, if we want to change a pointer (and obviously we want changes to be reflected outside the function) then we need to pass a pointer to the pointer.
#include<stdio.h>
/* Swaps strings by swapping pointers */
void swap1(char **str1_ptr, char **str2_ptr)
{
char *temp = *str1_ptr;
*str1_ptr = *str2_ptr;
*str2_ptr = temp;
}
int main()
{
char *str1 = "geeks";
char *str2 = "forgeeks";
swap1(&str1, &str2);
printf("str1 is %s, str2 is %s", str1, str2);
getchar();
return 0;
}
This method cannot be applied if strings are stored using character arrays.
Method 2(Swap Data)
If you are using character arrays to store strings then preferred way is to swap the data of both arrays.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
/* Swaps strings by swapping data*/
void swap2(char *str1, char *str2)
{
char *temp = (char *)malloc((strlen(str1) + 1) * sizeof(char));
strcpy(temp, str1);
strcpy(str1, str2);
strcpy(str2, temp);
free(temp);
}
int main()
{
char str1[10] = "geeks";
char str2[10] = "forgeeks";
swap2(str1, str2);
printf("str1 is %s, str2 is %s", str1, str2);
getchar();
return 0;
}
This method cannot be applied for strings stored in read only block of memory.
Count the number of words in a string
Count the number of words in a string, where a word is defined to be a contiguous sequence of non-space characters.
eg, “Hello, my name is John.” -> 5
Strategy:
The key is to note when it is in a word and when it is not; When it changes from not-in-word to in-word, increment wordCount by one.
int countNumWords(const char *str) {
bool inWord = false;
int wordCount = 0;
while (*str) {
if (!inWord && isalpha(*str)) {
inWord = true;
wordCount++;
}
else if (inWord && *str == ' ') {
inWord = false;
}
str++;
}
return wordCount;
}
Tuesday, October 9, 2012
Find sum in stream of numbers
Find first two numbers whose sum equals a given number in infinite length of stream of numbers.
Check whether a given string is an interleaving of two other given strings
Given three strings A, B and C. Write a function that checks whether C is an interleaving of A and B.
C is said to be interleaving A and B, if it contains all characters of A and B and order of all characters in individual strings is preserved.
Strategy:
Pick each character of C one by one and match it with the first character in A. If it doesn’t match then match it with first character of B. If it doesn’t even match first character of B, then return false. If the character matches with first character of A, then repeat the above process from second character of C, second character of A and first character of B. If first character of C matches with the first character of B (and doesn’t match the first character of A), then repeat the above process from the second character of C, first character of A and second character of B. If all characters of C match either with a character of A or a character of B and length of C is sum of lengths of A and B, then C is an interleaving A and B.
#include<stdio.h>
// Returns true if C is an interleaving of A and B, otherwise
// returns false
bool isInterleaved (char *A, char *B, char *C)
{
// Iterate through all characters of C.
while (*C != 0)
{
// Match first character of C with first character of A,
// If matches them move A to next
if (*A == *C)
A++;
// Else Match first character of C with first character of B,
// If matches them move B to next
else if (*B == *C)
B++;
// If doesn't match with either A or B, then return false
else
return false;
// Move C to next for next iteration
C++;
}
// If A or B still have some characters, then length of C is smaller
// than sum of lengths of A and B, so return false
if (*A || *B)
return false;
return true;
}
int main()
{
char *A = "AB";
char *B = "CD";
char *C = "ACBG";
if (isInterleaved(A, B, C) == true)
printf("%s is interleaved of %s and %s", C, A, B);
else
printf("%s is not interleaved of %s and %s", C, A, B);
return 0;
}
Output:
ACBG is not interleaved of AB and CD
Time Complexity: O(m+n) where m and n are the lengths of strings A and B respectively.
Note that the above approach doesn’t work if A and B have some characters in common. For example, if string A = “AAB”, string B = “AAC” and string C = “AACAAB”, then the above method will return false.
C is said to be interleaving A and B, if it contains all characters of A and B and order of all characters in individual strings is preserved.
Strategy:
Pick each character of C one by one and match it with the first character in A. If it doesn’t match then match it with first character of B. If it doesn’t even match first character of B, then return false. If the character matches with first character of A, then repeat the above process from second character of C, second character of A and first character of B. If first character of C matches with the first character of B (and doesn’t match the first character of A), then repeat the above process from the second character of C, first character of A and second character of B. If all characters of C match either with a character of A or a character of B and length of C is sum of lengths of A and B, then C is an interleaving A and B.
#include<stdio.h>
// Returns true if C is an interleaving of A and B, otherwise
// returns false
bool isInterleaved (char *A, char *B, char *C)
{
// Iterate through all characters of C.
while (*C != 0)
{
// Match first character of C with first character of A,
// If matches them move A to next
if (*A == *C)
A++;
// Else Match first character of C with first character of B,
// If matches them move B to next
else if (*B == *C)
B++;
// If doesn't match with either A or B, then return false
else
return false;
// Move C to next for next iteration
C++;
}
// If A or B still have some characters, then length of C is smaller
// than sum of lengths of A and B, so return false
if (*A || *B)
return false;
return true;
}
int main()
{
char *A = "AB";
char *B = "CD";
char *C = "ACBG";
if (isInterleaved(A, B, C) == true)
printf("%s is interleaved of %s and %s", C, A, B);
else
printf("%s is not interleaved of %s and %s", C, A, B);
return 0;
}
Output:
ACBG is not interleaved of AB and CD
Time Complexity: O(m+n) where m and n are the lengths of strings A and B respectively.
Note that the above approach doesn’t work if A and B have some characters in common. For example, if string A = “AAB”, string B = “AAC” and string C = “AACAAB”, then the above method will return false.
Monday, October 8, 2012
Permutations of BST
Given an array of integers arr = [5,6,1].
When we construct a BST with this input in the same order, we will have "5" as root, "6" as the right child and "1" as left child.
Now if our input is changed to [5,1,6], still our BST structure will be identical.
So given an array of integers, how to find the number of different permutations of the input array that results in the identical BST as the BST formed on the original array order?
Startegy:
Your question is equivalent to the question of counting the number of topological orderings for the given BST.
For example, for the BST
10
/ \
5 20
\7 | \
15 30
the set of topological orderings can be counted by hand like this: 10 starts every ordering. The number of topological orderings for the subtree starting with 20 is two: (20, 15, 30) and (20, 30, 15). The subtree starting with 5 has only one ordering: (5, 7). These two sequence can be interleaved in an arbitrary manner, leading to 2 x 10 interleavings, thus producing twenty inputs which produce the same BST. The first 10 are enumerated below for the case (20, 15, 30):
10 5 7 20 15 30
10 5 20 7 15 30
10 5 20 15 7 30
10 5 20 15 30 7
10 20 5 7 15 30
10 20 5 15 7 30
10 20 5 15 30 7
10 20 15 5 7 30
10 20 15 5 30 7
10 20 15 30 5 7
The case (20, 30, 15) is analogous --- you can check that any one of the following inputs produces the same BST.
This examples also provides a recursive rule to calculate the number of the orderings. For a leaf, the number is 1. For a non-leaf node with one child, the number equals to the number of topological orderings for the child. For a non-leaf node with two children with subtree sizes |L| and |R|, both having l and r orderings, resp., the number equals to
l x r x INT(|L|, |R|)
Where INT is the number of possible interleavings of |L| and |R| elements. This can be calculated easily by (|L| + |R|)! / (|L|! x |R|!). For the example above, we get the following recursive computation:
Ord(15) = 1
Ord(30) = 1
Ord(20) = 1 x 1 x INT(1, 1) = 2 ; INT(1, 1) = 2! / 1 = 2
Ord(7) = 1
Ord(5) = 1
Ord(10) = 1 x 2 x INT(2, 3) = 2 x 5! / (2! x 3!) = 2 x 120 / 12 = 2 x 10 = 20Useful Link:http://stackoverflow.com/questions/1701612/permutations-of-bst?rq=1Sunday, October 7, 2012
Print Ancestors of a node in a Binary Tree:
Print Ancestors of a node in a Binary Tree
Strategy:
Strategy:
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
int isAncestor(struct node* root, int n)
{
if(root == NULL)
return 0;
if(root->data == n)
return 1;
if(isAncestor(root->left, n) || isAncestor(root->right, n))
{
printf("%d\n", root->data);
return 1;
}
return 0;
}
struct node* newnode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
// node->nextRight = NULL;
return(node);
}
int main()
{
/* Constructed binary tree is
10
/ \
8 2
/ \
3 90 \ 14
*/
struct node *root = newnode(10);
root->left = newnode(8);
root->right = newnode(2);
root->left->left = newnode(3);
root->right->right = newnode(90);
root->right->right->left = newnode(14);
isAncestor(root, 14);
getchar();
return 0;
}
Time Complexity: O(n) where n is the number of nodes in the given Binary Tree
Find the First Duplicated Integer in an Array Without Using Extra Memory
There is a size-N array of integers whose values range from 1 to N. Some integers are duplicated. Find the first duplicate and its index without using any extra memory.
Strategy:
To solve this problem, we must keep track of elements in order to figure out which one is duplicate. However, regardless of method, we must not use any extra memory. Here is where we must depend on the information given by the problem.
We know that each element's value is between 1 and N, so if we increase that value by (N + 1), the modulus of that value and N + 1 is still the same. For example, modulus of 2 and (N + 1) is 2 and modulus of 2 + N + 1 is still 2. Thus, we can mark a visited element by adding N + 1 into its value or any element's value in the array because that doesn't change its modulus with N + 1 at all!
Furthermore, we know that each element's value is between 1 and N. Hence, we can use each element's value as a key and the element at array[key] as the mark. For example, if the current element is 4 then we can check if its value has been visited, and thus a duplicate, by looking at the value of the element at index 4 in the array, if the current element is 2 the we check the value of the element at index 2 in the array, and so on.
One final point, we need to traverse the array and check each element, so we need a loop that run till we find the duplicate or till we reach the end of the array. The problem with such loop is that it needs additional counter / sentinel value as the loop's termination condition! That requires memory allocation. Fortunately, we know that the first element is not a duplicate because there is no other element in front of it. Thus, we can use the first element in the array as our counter.
Example:
Lets take the given array as 1 3 2 1 1 3
Alternative Method:
Keep one pointer at first index and swap the value at first index with the value at index=value at first position.That means 1 will be swapped with 1 only.If a[i]==i then move the pointer forward.Then at index 2 we get the value as 3.So swap 3 with 2.Now again a[2]=2 So move the pointer forward.In this manner if an elemnt i is already there at a[i] then that is first duplicate.
Strategy:
To solve this problem, we must keep track of elements in order to figure out which one is duplicate. However, regardless of method, we must not use any extra memory. Here is where we must depend on the information given by the problem.
We know that each element's value is between 1 and N, so if we increase that value by (N + 1), the modulus of that value and N + 1 is still the same. For example, modulus of 2 and (N + 1) is 2 and modulus of 2 + N + 1 is still 2. Thus, we can mark a visited element by adding N + 1 into its value or any element's value in the array because that doesn't change its modulus with N + 1 at all!
Furthermore, we know that each element's value is between 1 and N. Hence, we can use each element's value as a key and the element at array[key] as the mark. For example, if the current element is 4 then we can check if its value has been visited, and thus a duplicate, by looking at the value of the element at index 4 in the array, if the current element is 2 the we check the value of the element at index 2 in the array, and so on.
One final point, we need to traverse the array and check each element, so we need a loop that run till we find the duplicate or till we reach the end of the array. The problem with such loop is that it needs additional counter / sentinel value as the loop's termination condition! That requires memory allocation. Fortunately, we know that the first element is not a duplicate because there is no other element in front of it. Thus, we can use the first element in the array as our counter.
Example:
Lets take the given array as 1 3 2 1 1 3
Alternative Method:
Keep one pointer at first index and swap the value at first index with the value at index=value at first position.That means 1 will be swapped with 1 only.If a[i]==i then move the pointer forward.Then at index 2 we get the value as 3.So swap 3 with 2.Now again a[2]=2 So move the pointer forward.In this manner if an elemnt i is already there at a[i] then that is first duplicate.
Find minimum trees to cut
Find minimum trees to cut so that we will be getting at least k units of wood
Given array contains heights of trees in ascending order
2 5 7 8 11 13 17
If we cut a tree of height x then all the trees above height x will be cut and will add to the total units of wood.So for each tree of height say y we will get y-x units of wood.We need to find minimum number of trees to cut to make k units of wood
Strategy:
In the given array lets say we want to make 18 units
We will start from 13.So sum=17-13=4 units only <18
So we move left to 11 and find again sum as sum= previuos sum+ difference between current & next element * number of elements after curent element
So sum= 4+ (13-11) * 2=8 units <18
Again we move to 8 & find sum as sum= 8+ (11-8) * 3 [ as 11,13,17 --3 elements are there towards right]
=17 <18
So we move to 7 and sum= 17 + 1*4=21>18 So 7 is my answer
Given array contains heights of trees in ascending order
2 5 7 8 11 13 17
If we cut a tree of height x then all the trees above height x will be cut and will add to the total units of wood.So for each tree of height say y we will get y-x units of wood.We need to find minimum number of trees to cut to make k units of wood
Strategy:
In the given array lets say we want to make 18 units
We will start from 13.So sum=17-13=4 units only <18
So we move left to 11 and find again sum as sum= previuos sum+ difference between current & next element * number of elements after curent element
So sum= 4+ (13-11) * 2=8 units <18
Again we move to 8 & find sum as sum= 8+ (11-8) * 3 [ as 11,13,17 --3 elements are there towards right]
=17 <18
So we move to 7 and sum= 17 + 1*4=21>18 So 7 is my answer
Saturday, October 6, 2012
Minimum path sum from top to bottom in a Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
http://www.programcreek.com/2013/01/leetcode-triangle-java/
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
http://www.programcreek.com/2013/01/leetcode-triangle-java/
Maximum number divisible by 2,3 and 5
An array of size n is given. The array contains digits from 0 to 9. I had to generate the maximum number using the digits in the array such that it is divisible by 2, 3 and 5
Clock Teasers
Question 1:
Find the angle between the hands of a clock.
Question 2:
The hour and minute hands are at equal distance from the 6 hour, what time will it be exactly?
Question 3:
Find out how many times the minute hand and hour hand exactly match over a 12-hour cycle.How often the second hand and minute hand match each other exactly
Solution 1:
Minutes Angle = (360 * m) / 60 = 6m where m is the minutes.Hour Angle = ((360 * h) / 12) + (360 * m / 12 * 60)
Hour Angle - Minutes Angle = 30h - 11m/2
Solution 2:
Say answer is "8 hour X minute". According as proposition, the angle between the minute hand and "mark 4" of the watch is equal to the angle between the hour hand and "mark 8" of the watch.
We know in 60 minutes the minute hand makes 360 degrees (360/60=6 degrees per minute) and the hour hand makes 360/12=30 degrees (30/60=1/2 degrees per minute).
Therefore, (20-X) minutes corresponds to 6(20-X) degrees (this is the angle between the minute hand and "mark 4").
And in X minutes the hour hand makes X/2 degrees with "mark 8".
Thus, X/2=6(20-X) gives X=18 minutes 27 and 9/13 second.
So, the answer is 8 hour, 18 minutes, 27 9/13 second.
Solution 3:
Between 12:00 and 1:00, the minute hand is always ahead of the hour hand. Then somewhere slightly past 5 minutes after 1:00, the hour and minute hands are in the exact same position. If you have a clock or watch on which you can manipulate the time, try this for yourself.
In this way, the minute hand will pass over the hour hand ten more times, once each hour between 1 and 2, 3 and 4, and so on, until the hour between 10 and 11. Between 11 and 12, the minute hand never catches up to the hour hand until exactly 12:00, when the hands line up again. The hands match up 12 times in a complete cycle, including both the starting and ending positions.
Wednesday, October 3, 2012
Find max sub-square whose border values are all 1
Imagine you have a square matrix, where each cell is filled with either black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.
Maximum sub-matrix sum in a matrix
Given an NxN matrix of positive and negative integers, write code to find the sub- matrix with the largest possible sum.
http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/
Useful Links:
http://ronzii.wordpress.com/2012/03/16/kadanes-algorithm-2d/
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=385650#385650
http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/
Useful Links:
http://ronzii.wordpress.com/2012/03/16/kadanes-algorithm-2d/
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=385650#385650
Tuesday, October 2, 2012
50 Trucks with Payload
Given a fleet of 50 trucks, each with a full fuel tank and a range of 100 miles, how far can you deliver a payload? You can transfer the payload from truck to truck, and you can transfer fuel from truck to truck. Assume all the payload will fit in one truck.
Monday, October 1, 2012
Binary Tree to BST Conversion
Given a Binary Tree, convert it to a Binary Search Tree. The conversion must be done in such a way that keeps the original structure of Binary Tree.
Example 1--------------
Input:
10
/ \
2 7
/ \
8 4
Output:
8
/ \
4 10
/ \
2 7
Example 2---------------
Input:
10
/ \
30 15
/ \
20 5
Output:
15
/ \
10 20
/ \
5 30
http://www.geeksforgeeks.org/binary-tree-to-binary-search-tree-conversion/
Correct the BST !
Two nodes of a BST are swapped, correct the BST
September 14, 2012
Two of the nodes of a Binary Search Tree (BST) are swapped. Fix (or correct) the BST.
Input Tree:
10
/ \
5 8
/ \
2 20
In the above tree, nodes 20 and 8 must be swapped to fix the tree.
Following is the output tree
10
/ \
5 20
/ \
2 8
Strategy:
The inorder traversal of a BST produces a sorted array. So a simple method is to store inorder traversal of the input tree in an auxiliary array. Sort the auxiliary array. Finally, insert the auxiilary array elements back to the BST, keeping the structure of the BST same. Time complexity of this method is O(nLogn) and auxiliary space needed is O(n).
We can solve this in O(n) time and with a single traversal of the given BST. Since inorder traversal of BST is always a sorted array, the problem can be reduced to a problem where two elements of a sorted array are swapped. There are two cases that we need to handle:
1. The swapped nodes are not adjacent in the inorder traversal of the BST.
For example, Nodes 5 and 25 are swapped in {3 5 7 8 10 15 20 25}.
The inorder traversal of the given tree is 3 25 7 8 10 15 20 5
If we observe carefully, during inorder traversal, we find node 7 is smaller than the previous visited node 25. Here save the context of node 25 (previous node). Again, we find that node 5 is smaller than the previous node 20. This time, we save the context of node 5 ( current node ). Finally swap the two node’s values.
2. The swapped nodes are adjacent in the inorder traversal of BST.
For example, Nodes 7 and 8 are swapped in {3 5 7 8 10 15 20 25}.
The inorder traversal of the given tree is 3 5 8 7 10 15 20 25
Unlike case #1, here only one point exists where a node value is smaller than previous node value. e.g. node 7 is smaller than node 8.
How to Solve? We will maintain three pointers, first, middle and last. When we find the first point where current node value is smaller than previous node value, we update the first with the previous node & middle with the current node. When we find the second point where current node value is smaller than previous node value, we update the last with the current node. In case #2, we will never find the second point. So, last pointer will not be updated. After processing, if the last node value is null, then two swapped nodes of BST are adjacent.
Code:
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *left, *right;
};
void swap( int* a, int* b )
{
int t = *a;
*a = *b;
*b = t;
}
struct node* newNode(int data)
{
struct node* node = (struct node *)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
// This function does inorder traversal to find out the two swapped nodes.
// It sets three pointers, first, middle and last. If the swapped nodes are
// adjacent to each other, then first and middle contain the resultant nodes
// Else, first and last contain the resultant nodes
void correctBSTUtil( struct node* root, struct node** first,
struct node** middle, struct node** last,
struct node** prev )
{
if( root )
{
// Recur for the left subtree
correctBSTUtil( root->left, first, middle, last, prev );
// If this node is smaller than the previous node, it's violating
// the BST rule.
if (*prev && root->data < (*prev)->data)
{
// If this is first violation, mark these two nodes as
// 'first' and 'middle'
if ( !*first )
{
*first = *prev;
*middle = root;
}
// If this is second violation, mark this node as last
else
*last = root;
}
// Mark this node as previous
*prev = root;
// Recur for the right subtree
correctBSTUtil( root->right, first, middle, last, prev );
}
}
// A function to fix a given BST where two nodes are swapped. This
// function uses correctBSTUtil() to find out two nodes and swaps the
// nodes to fix the BST
void correctBST( struct node* root )
{
// Initialize pointers needed for correctBSTUtil()
struct node *first, *middle, *last, *prev;
first = middle = last = prev = NULL;
// Set the poiters to find out two nodes
correctBSTUtil( root, &first, &middle, &last, &prev );
// Fix (or correct) the tree
if( first && last )
swap( &(first->data), &(last->data) );
else if( first && middle ) // Adjacent nodes swapped
swap( &(first->data), &(middle->data) );
// else nodes have not been swapped, passed tree is really BST.
}
void printInorder(struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
int main()
{
/* 6
/ \
10 2
/ \ / \
1 3 7 12
10 and 2 are swapped
*/
struct node *root = newNode(6);
root->left = newNode(10);
root->right = newNode(2);
root->left->left = newNode(1);
root->left->right = newNode(3);
root->right->right = newNode(12);
root->right->left = newNode(7);
printf("Inorder Traversal of the original tree \n");
printInorder(root);
correctBST(root);
printf("\nInorder Traversal of the fixed tree \n");
printInorder(root);
return 0;
}
Output:
Inorder Traversal of the original tree
1 10 3 6 7 2 12
Inorder Traversal of the fixed tree
1 2 3 6 7 10 12
Time Complexity: O(n)
http://www.geeksforgeeks.org/fix-two-swapped-nodes-of-bst/
Subscribe to:
Posts (Atom)