Given
a large number with many digits, propose a method or data structure to
efficiently store them. Addition, subtraction, mult, division should be
supported by your design.
Thursday, November 1, 2012
Test type of triangle based on side lengths
Develop strategy and test type of triangle based on side lengths.
Strategy:
you're given sides a, b, and c.
let a <= b <= c.
for a = b = c, it's an equilateral tri.
for a = b < c or a < b = c, it's an isosceles tri.
for a < b < c, it's a scalene tri.
since we already said that a and b are the smallest 2 sides,
for a^2 + b^2 > c^2, it's an acute tri.
for a^2 + b^2 = c^2, it's a right tri.
for a^2 + b^2 < c^2, it's an obtuse tri.
equilateral triangle is always acute.
for a = b < c isosceles triangle, it IS an obtuse isosceles.
for a < b = c isosceles triangle, it IS an acute isosceles.
Also,
In an equilateral triangle, all three sides are the same length. An equilateral triangle is always equiangular.
In an isosceles triangle, two sides are the same length. An isosceles triangle may be right, obtuse, or acute.
In a scalene triangle, none of the sides are the same length. A scalene triangle may be right, obtuse, or acute.
In a right triangle, one of the angles is a right angle—an angle of 90 degrees. A right triangle may be isosceles or scalene.
In an obtuse triangle, one angle is greater than a right angle—it is more than 90 degrees. An obtuse triangle may be isosceles or scalene.
In an acute triangle, all angles are less than right angles—each one is less than 90 degrees. An acute triangle may be equilateral, isosceles, or scalene.
Writing Test Cases:
Strategy:
you're given sides a, b, and c.
let a <= b <= c.
for a = b = c, it's an equilateral tri.
for a = b < c or a < b = c, it's an isosceles tri.
for a < b < c, it's a scalene tri.
since we already said that a and b are the smallest 2 sides,
for a^2 + b^2 > c^2, it's an acute tri.
for a^2 + b^2 = c^2, it's a right tri.
for a^2 + b^2 < c^2, it's an obtuse tri.
equilateral triangle is always acute.
for a = b < c isosceles triangle, it IS an obtuse isosceles.
for a < b = c isosceles triangle, it IS an acute isosceles.
Also,
In an equilateral triangle, all three sides are the same length. An equilateral triangle is always equiangular.
In an isosceles triangle, two sides are the same length. An isosceles triangle may be right, obtuse, or acute.
In a scalene triangle, none of the sides are the same length. A scalene triangle may be right, obtuse, or acute.
In a right triangle, one of the angles is a right angle—an angle of 90 degrees. A right triangle may be isosceles or scalene.
In an obtuse triangle, one angle is greater than a right angle—it is more than 90 degrees. An obtuse triangle may be isosceles or scalene.
In an acute triangle, all angles are less than right angles—each one is less than 90 degrees. An acute triangle may be equilateral, isosceles, or scalene.
Writing Test Cases:
| S.No. | Test case Name | Description | Expected Result |
| 1 | Check Scalene triangle | Enter input as A=8, B=5 and C=7 | Output should be scalene triangle |
| 2 | Check Scalene triangle | Enter input as A=200, B=400 and C=900 | Output should be scalene triangle |
| 3 | Check isosceles triangle | Enter input as A=8, B=10 and C=10 | Output should be isosceles triangle |
| 4 | Check isosceles triangle | Enter input as A=800, B=700 and C=700 | Output should be isosceles triangle |
| 5 | Check equilateral triangle | Enter input as A=15, B=15 and C=15 | Output should be equilateral triangle |
| 6 | Check equilateral triangle | Enter input as A=190, B=190 and C=190 | Output should be equilateral triangle |
| 7 | Check Negative values | Enter input as A= -6, B=-15 and C=-14 |
Error message should be displayed
|
| 8 | Check Negative values | Enter input as A= 6, B=15 and C=-15 |
Error message should be displayed
|
| 9 | Check Negative values | Enter input as A= 6, B=-16 and C=-15 |
Error message should be displayed
|
| 10 | Check Zero values | Enter input as A= 6, B=16 and C=0 | Error message should be displayed |
Test a program that outputs factorial of a number
Given a simple program designed to take inputs of integers from 1-1000 and to
output the factorial value of that number, how would you test this program?
You do not have access to the code
Strategy:
This is a standard testing question. In professional world when you are testing anything, you are expected to automate the entire process. So in this case they do not expect you to check the factorial value returned each time. Rather first you have to write a routine that gives the correct factorial value for numbers between 1-1000. (There are no efficiency constraints)
2) Then you must check what it gives for values out of the range and if it crashes or not.
3) You should also check for negative numbers and floating point. In all the cases the code should reject the input and not crash.
Try to think of as many as possible such test cases. Testing questions are an integral part of interviews because even if you are being selected for a Dev profile, you need to test your code thoroughly.
While answering testing questions you should be imaginative and speak out whatever weird condition/check that comes to your mind. They are testing you for your thoroughness and the understanding of what actually that code does.
Strategy:
This is a standard testing question. In professional world when you are testing anything, you are expected to automate the entire process. So in this case they do not expect you to check the factorial value returned each time. Rather first you have to write a routine that gives the correct factorial value for numbers between 1-1000. (There are no efficiency constraints)
Now you need to check for different test cases such as1) It must return the correct value for the numbers in the range. You do not need to check for each number but can randomly pick 100 numbers (or whatever with the interviewer would be satisfied) from 1-1000 and check for them.
2) Then you must check what it gives for values out of the range and if it crashes or not.
3) You should also check for negative numbers and floating point. In all the cases the code should reject the input and not crash.
Try to think of as many as possible such test cases. Testing questions are an integral part of interviews because even if you are being selected for a Dev profile, you need to test your code thoroughly.
While answering testing questions you should be imaginative and speak out whatever weird condition/check that comes to your mind. They are testing you for your thoroughness and the understanding of what actually that code does.
Match two board configurations of tic-tac-toe problem
How will you match two board configurations of tic-tac-toe problem?
Strategy:
This is a quite unexpected interview question as it has nothing to do with your programming skills or algorithms. This is a plain simple question designed to check your problem solving skills.
The trick in this question is that any board configuration is rotation invariant and what we mean by that is
all three the configurations shown above are similar and must match in the logic we use for checking board configurations.
Rotation of the elements of a matrix can be done in multiple ways and we are going to discuss two methods here.
Method 1: Given a matrix we can take it's transpose and to rotate it left exchange the rows and to rotate right, exchange the columns.
Strategy:
This is a quite unexpected interview question as it has nothing to do with your programming skills or algorithms. This is a plain simple question designed to check your problem solving skills.
The trick in this question is that any board configuration is rotation invariant and what we mean by that is
all three the configurations shown above are similar and must match in the logic we use for checking board configurations.
Any given configuration of the board can have 7 other configurations which will be identical to it in terms of rotation invariance. These can be obtained by rotating the matrix either left or right 4 times. And then taking the mirror image of the matrix and again rotating it.So the entire problem breaks down to reducing the first board configuration to matrix and then rotating it one by one and matching it with the other configuration.
Rotation of the elements of a matrix can be done in multiple ways and we are going to discuss two methods here.
Method 1: Given a matrix we can take it's transpose and to rotate it left exchange the rows and to rotate right, exchange the columns.
1) original matrix
1 2 3
4 5 6
7 8 9
2) transpose
1 4 7
2 5 8
3 6 9
3-a) change rows to rotate left
3 6 9
2 5 8
1 4 7
3-b) or change columns to rotate right
7 4 1
8 5 2
9 6 3
Method 2: We can use the following pesudo-code which directly does the work
which is being done while taking transpose and exchanging columns. This works
for a given square matrix A of dimension NxN for n = 0 to N - 2
for m = n + 1 to N - 1
swap A(n,m) with A(m,n)Test cases for overlap of rectangles
Given a function, func( rect a, rect b), which takes two rectangles as
argument and tells if two rectangles overlap or not. Write all possible test cases
for this.
Strategy:
This is a testing profile question asked by Microsoft in 2011. If you are being hired for testing profile you will face many such questions which aim at testing your ability to come up with interesting and unique test cases. You should think out of the box to suggest situations which can cause the function or a component to fail. If function responds correctly to all the cases, it is considered fit to be used.
Coming back to the question at hand, let's write all the test cases:
Strategy:
This is a testing profile question asked by Microsoft in 2011. If you are being hired for testing profile you will face many such questions which aim at testing your ability to come up with interesting and unique test cases. You should think out of the box to suggest situations which can cause the function or a component to fail. If function responds correctly to all the cases, it is considered fit to be used.
Coming back to the question at hand, let's write all the test cases:
- Begin with the base cases i.e. putting NULL in place of either a, b or both. That means function must not fail if either of the arguments is empty. This is generally the case, since developers sometimes forget to keep check for this.
These are few test cases, there can be many more to this. But keep in mind to give the base or initial test case. That is from where interviewer judges your understanding and method you tackle the problem.
Tuesday, October 30, 2012
Shift all non-duplicates to the start of the array
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
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;
}
Subscribe to:
Posts (Atom)