tag:blogger.com,1999:blog-82361609943594935262024-03-23T15:44:03.592+05:30Interview questions on Algorithms, Programmingtnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.comBlogger51125tag:blogger.com,1999:blog-8236160994359493526.post-42726429876840922982018-10-29T12:12:00.001+05:302018-10-29T12:12:52.702+05:30Explode the Active BombsGiven a matrix of dimension M*N, where each cell in the matrix can have values 0, 1 or 2 which has the following meaning:<br />
<br />
0: Empty cell<br />
1: Cells have bombs, not activated yet.<br />
2: Cells have activated bombs<br />
<br />
And you have a trigger. After pressing the trigger all activated bomb at index [i,j] will explode in one second and will activate other bombs at indexes [i-1,j], [i+1,j], [i,j-1], [i,j+1] (up, down, left and right), which<br />
will inturn explode in the next second and this continues. So we have to determine what is the time taken for all the bombs to explode, once the trigger is pressed. If it is impossible to explode every bomb, then simply return -1.<br />
<br />
Sample Input : 2 X 2<br />
<br />
2 1<br />
1 0<br />
<br />
Output: 2<br />
<br />
Sample Input: 3 X 3<br />
<br />
2 1 1<br />
0 0 0<br />
2 0 1<br />
<br />
Output: -1<br />
<br />
Sample Input:10 X 10<br />
<br />
2 2 2 2 2 2 2 2 2 0<br />
2 2 2 2 2 2 2 2 2 0<br />
2 2 2 2 2 2 2 2 2 0<br />
2 2 2 2 2 2 2 2 2 0<br />
2 2 2 2 2 2 2 2 2 0<br />
1 0 1 0 1 0 1 0 1 0<br />
0 1 0 1 0 1 0 1 0 1<br />
2 2 2 2 2 2 2 2 2 2<br />
1 1 0 0 1 1 0 0 1 1<br />
1 1 1 1 0 0 1 1 1 1<br />
<br />
Output: 5<br />
<br />
<pre>#include<stdio.h>
int explode(int a[][100], int n)
{
int count = 0;
int c;
do {
c = 0;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(a[i][j] == 2) {
if(i>0 && a[i-1][j]==1) {
a[i-1][j]=3;
c++;
}
if(j>0 && a[i][j-1]==1) {
a[i][j-1]=3;
c++;
}
if(i<n-1 && a[i+1][j]==1) {
a[i+1][j]=3;
c++;
}
if(j<n-1 && a[i][j+1]==1) {
a[i][j+1]=3;
c++;
}
}
}
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(a[i][j]==3)
a[i][j]=2;
}
}
count++;
}while(c!=0);
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(a[i][j] == 1)
return -1;
}
}
return count;
}
main()
{
int n;
int a[100][100];
printf("Enter the size of the matrix: ");
scanf("%d", &n);
printf("Enter the matrix\n");
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
scanf("%d", &a[i][j]);
}
}
int ex = explode(a, n);
printf("%d", ex);
return 0;
}
</pre>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com1tag:blogger.com,1999:blog-8236160994359493526.post-13649276242342784022018-10-26T17:46:00.000+05:302018-10-26T17:46:44.767+05:30How will you trap rain water?<div dir="ltr" style="text-align: left;" trbidi="on">Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_oUgS7s1OO_vfo3d4BmrkVsgNz7ot3NS3lDFgw9CMR1-FyJpd7mCdOSkUQZylJ096NWhA5ij27I98ow_K3HIMmuvKyIPkfbEJoSGOBINnuQwSMCFpB99ov-karMgUcTD_hhN0fBm17cc/s1600/watertrap.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="600" data-original-width="482" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_oUgS7s1OO_vfo3d4BmrkVsgNz7ot3NS3lDFgw9CMR1-FyJpd7mCdOSkUQZylJ096NWhA5ij27I98ow_K3HIMmuvKyIPkfbEJoSGOBINnuQwSMCFpB99ov-karMgUcTD_hhN0fBm17cc/s1600/watertrap.png" /></a></div><br />
<br />
Example:<br />
<br />
Input: [0,1,0,2,1,0,1,3,2,1,2,1]<br />
Output: 6<br />
<br />
Input: [3, 0, 0, 2, 0, 4]<br />
Output: 10<br />
<br />
<pre>
#include<stdio.h>
calculate(int a[], int n)
{
int f = a[0];
int fi = 0;
int sum = 0;
for(int i=0; i<n; i++) {
int next = getNextGENumber(a, a[i], i, n);
if(next != -1) {
for(int j=i+1; j<next; j++) {
sum += (a[i]-a[j]);
}
i = next - 1;
}
}
return sum;
}
int getNextGENumber(int a[], int value, int start, int n)
{
for(int i=start+1; i<n; i++) {
if(value <= a[i]) {
return i;
}
}
return -1;
}
main()
{
int n;
int a[1000];
printf("Enter number of blocks: ");
scanf("%d", &n);
printf("Enter the blocks\n");
for(int i=0; i<n && i<1000; i++) {
scanf("%d", a+i);
}
printf("%d\n", calculate(a, n));
}
</pre><br />
</div>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-84291928599153559042015-03-01T10:28:00.000+05:302015-03-01T10:28:00.642+05:30Remove one Recursion in Inorder Traversal<pre>function inorder(Node root)
{
if(root == NULL)
return;
inorder(root->left);
print root->node;
inorder(root->right);
}
After removing one recursion
function inorder(Node root)
{
if(root == NULL)
return;
while(root->right != NULL) {
inorder(root->left);
print root->node;
root = root->right;
}
}
</pre>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-51795324471805308532014-04-28T23:30:00.000+05:302014-04-28T23:30:02.279+05:30Petrol Bunks in Circle<p align="justify">There is a circular road, and there are n petrol bunks at different places on that road. The petrol bunk i has enough fuel by which one can travel f_i distance. The distance from the petrol bunk i to i+1 is d_i. <br />
<br />
You have a car with empty fuel tank, and you need to find a place from where you can start and travel by that road and reach the same place. <br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<b>Solution:</b><br />
<br />
The distance from first bunk to second is D1, and second to third is D2 and so on.<br />
The distance that can be travelled by the fuel in the first bunk is F1, and from the second bunk, it is F2 and so on.<br />
<br />
If F1 < D1, then we cannot start from the first bunk.<br />
If F1 + F2 < D1 + D2, then we cannot start from the first or second bunks.<br />
Similarly, if F1 + F2 + F3 < D1 + D2 + D3, then we cannot start from the first, second or third bunks.<br />
<br />
Wherever we reach the fuel to be less than the distance, we have to skip all those bunks, and have to move to the next bunk and repeat the same thing.<br />
<br />
<br />
<b>Code:</b><br />
</p><pre>#include<<stdio.h>
int findStart(int distance[], int capacity[], int n)
{
int c=0, d=0, st=0, i;
for(i=0; i<n; i++) {
c+=capacity[i];
d+=distance[i];
if(c<d) {
st = i+1;
c=0;
d=0;
}
}
if(st != 0) {
for(i=0; i<st; i++) {
c+=capacity[i];
d+=distance[i];
if(c<d) {
return -1;
}
}
}
return st;
}
main()
{
int distance[] = {10,20,30,40,50,60};
int capacity[] = {11,21,10,50,51,71};
int result = findStart(distance, capacity, 6);
printf("%d \n", result);
}
</pre>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-7848431711679703392014-04-27T23:28:00.000+05:302014-04-27T23:28:00.260+05:30Finding Odd Coin<div dir="ltr" style="text-align: left;" trbidi="on"><div align="justify"><b>Simple Problem</b><br />
<br />
There are 12 coins, and one coin has less weight. We have to find the odd coin by measuring only three times.<br />
<br />
<b>Complex Problem</b><br />
<br />
There are 12 coins, and one coin is of different weight (more or less). We have to find the odd coin by measuring only three times.<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<b>Solutions</b><br />
<br />
<b>Simple Problem</b><br />
<br />
Put 6 coins on one side and other 6 coins on another side. <br />
Take the 6 coins of less weight, and put 3 coins on one side and another 3 coins on another side.<br />
Take the 3 coins of less weight. Put one coin on one side and another coin on another side.<br />
<br />
Whichever is of less weight, that is the odd coin. If both are equal, the third coin is of odd coin.<br />
<br />
<br />
<b>Complex Problem</b><br />
<br />
<b>Incomplete Solution</b><br />
<br />
Split the 12 coins into three parts, A, B and C, and name them like A1, A2, A3, A4, B1, B2, B3, B4, C1, C2, C3 and C4.<br />
</div><ul><li>Put 4 coins of A and 4 coins of B.<br />
<ul><li>If they are equal, put 2 coins of A on one side, and put C1 and C2 on the other side, and measure the weight.<br />
<ul><li>If they are not equal, Put A1 and C1 and measure the weight. <br />
<ul><li>If they are not equal, C1 is the odd coin. Otherwise, C2 is the odd coin. </li>
</ul></li>
</ul><ul><li>If they are equal, put 1 coin of A and C3 and measure the weight.<br />
<ul><li>If they are equal, C4 is the odd coin. Otherwise, C3 is the odd coin.</li>
</ul></li>
</ul></li>
</ul><ul><li>If they are not equal, remember which one is of less weight. Put C1, C2, C3, C4 on one side and A1, A2, B1, B2 on another side.<br />
<ul><li>If they are not equal, check whether AB is of more weight or less weight. If it is more weight, then in the previous step, whichever one has more weight that has the odd coin. Same thing applies, if it is of less weight. Let's say, set A has the odd coin. Measure C1 and A1.<br />
<ul><li>If they are equal, A2 is the odd coin. Otherwise, A1 is the odd coin.</li>
</ul></li>
</ul><ul><li>If they are equal, <span style="color: #800000;"><b>Cannot find the solution</b></span></li>
</ul></li>
</ul></li>
</ul></div><br />
<b>Complete Solution</b><br />
<br />
Split the 12 coins into three parts, A, B and C, and name them like A1, A2, A3, A4, B1, B2, B3, B4, C1, C2, C3 and C4.<br />
<ul><li>Put A1, A2, A3 and A4 on one side and B1, B2, B3 and B4 on the other side.<br />
<ul><li>If both are equal, put A1, A2, A3 on one side and C1, C2 and C3 on another side.<br />
<ul><li>If both are equal, C4 is the odd coin. By weighing with any other coin, we can find whether it is heavier or lighter.<br />
<li>If A is heavier, it means one of C1, C2 and C3 is the lighter odd coin. Weigh C1 and C2. Whichever is of less weight, that is the odd coin. If both are equal, C3 is the lighter odd coin.<br />
<li>If C is heavier, it means one of C1, C2 and C3 is the heavier odd coin. Weigh C1 and C2. Whichever is of more weight, that is the odd coin. If both are equal, C3 is the heavier odd coin. <br />
</ul><li>If A is heavier, put B1, B2, B3 and A4 on one side and C1, C2, C3 and B4 on another side.<br />
<ul><li>If both are equal, One of A1, A2, A3 is heavier. Weigh A1 and A2. Whichever is heavier, that is the odd coin. If both are equal, A3 is the odd coin.<br />
<li>If B1, B2, B3 and A4 is still heavier. It means, either A4 is heavier or B4 is lighter. Weigh A4 with any other coin (other than B4). If it is equal, then B4 is the odd coin of less weight. Otherwise, A4 is the odd coin of more weight.<br />
<li>If B1, B2, B3 and A4 is lighter, then one of B1, B2 and B3 is the lighter odd coin. Weigh B1 and B2. Whichever is lighter, that is the odd coin. If both are equal, B3 is the lighter odd coin. <br />
</ul><li>If B is heavier, do same as above. Put C1, C2, C3 and A4 on one side and A1, A2, A3 and B4 on another side and proceed the same way.<br />
</ul></ul>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-53766273334476266352014-04-26T23:27:00.000+05:302014-04-26T23:27:00.721+05:30No Child After a Girl ChildGovernment introduced a rule saying, once a couple gets a girl child, they should not have any more children. What would be the ratio of boys to girls after n years?<br />
<br />
<br />
<br />
<br />
It would be 1:1 only [If we assume, for any birth the ratio of boy to girl is 1:1]. <br />
<br />
Let's suppose, if there 1000 couples. If we take 1:1 in the births, then 500 would give birth to boys and 500 would give birth to girls. <br />
<br />
The couple who gave birth to girls will not conceive anymore. The 500 couple who gave birth to boys would give birth to 250 boys and 250 girls in the next delivery.<br />
<br />
The couple who gave birth to 250 girls would stop conceiving, and the remaining 250 couple would try again.<br />
<br />
They would give birth to 125 boys and 125 girls.<br />
<br />
The same thing is repeated and the ratio would be 1:1 at the end.<br />
tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-4302972988043224542014-04-25T23:27:00.000+05:302014-04-25T23:27:00.356+05:30Converting a Tree into an Array<pre>Call traverse(root, array, 0);
int traverse(Node root, int[] a, int index)
{
if(node == NULL)
return index;
int x = traverse(root->left, a, index);
a[x] = root->data;
x = traverse(root->right, a, x+1);
}
</pre>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-2087884735871536602014-04-24T23:27:00.000+05:302014-04-24T23:27:00.641+05:30Copy a Linked List in C<pre>Node Copy(Node first)
{
if(first == NULL)
return NULL;
Node copy = (Node)malloc(sizeof(Node));
Node temp = copy;
while(first->next != NULL) {
temp->data = first->data;
temp->next = (Node)malloc(sizeof(Node));
temp = temp->next;
first = first->next;
}
temp->data = first->data;
return copy;
}
</pre>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-22824438081022510712014-04-23T23:26:00.000+05:302014-04-23T23:26:00.068+05:30No.of Nodes in a Tree<pre>int Count(Node root)
{
if(root == NULL)
return 0;
return 1 + Count(root->left) + Count(root->right);
}
</pre>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-63787685655035240332014-04-22T23:26:00.000+05:302014-04-22T23:26:00.098+05:30Delete all the nodes in a Tree in C<p align="justify"><br />
<pre>void Clear(Node root)
{
if(root == NULL)
return;
Clear(root->left);
Clear(root->right);
free(root);
}
</pre></p>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-12127637884297847222014-04-21T23:25:00.000+05:302014-04-21T23:25:00.879+05:30Find Colored CouplesIn an array of colors, we need to find out the no.of colored couples of the same color that are next to each other. If you find a colored couple, then you can remove that couple, and check whether any more couples can be formed by that or not. <br />
<br />
<b>Example</b><br />
<br />
R G B B G R Y W Y<br />
<br />
In the above, there are two B's next to each other. That is one couple, and we can remove that. After removing both the B's, the colors would be like <br />
<br />
R G G R Y W Y<br />
<br />
Now, there is another pair of G's in this. After removing that, the colors would be like below.<br />
<br />
R R Y W Y<br />
<br />
after removing R, it would be like below.<br />
<br />
Y W Y.<br />
<br />
At this time, there are no colored couples that are next to each other. In this case, there are three couples in the given array.<br />
<br />
<br />
<b>Answer:</b><br />
<br />
<b>Stack:</b><br />
<br />
Stack is the simplest approach to solve this problem. If we can modify the input array, then we can use the input array itself as stack to solve this problem. <br />
<br />
We take the first element, and push it to the stack. <br />
<br />
If the stack contains any elements, then we take the top element and take the next element in the input array and compare the elements. If both are same, then we found one couple. We pop the element, and we move forward.<br />
<br />
If the elements are not same, then we just push that element to the stack and proceed.<br />
<br />
With this, by the time we reach the end, we would find the total no. of paired couples.<br />
<br />
<br />
<b>Doubly Linked List:</b><br />
<br />
If the input elements is given in the form of Doubly Linked List, and if we can modify the input, then from that also, we can easily find the count. <br />
<br />
We will have two pointers. Initially, first pointer would point to first element, and second pointer would point to second element. If both are different, then both pointers would move one step forward. If they are same, then the first pointer would move backward, and second pointer would move forward. We also would clear the two colors, and adjust the pointers in the doubly linked list. We repeat the loop.<br />
<br />
<br />
<b>Code for Stack:</b><br />
<br />
<pre>#include<stdio.h>
#include<string.h>
#include<stdlib.h>
class color
{
private:
char *array;
int length;
public:
void init(char *c)
{
array = c;
length = 0;
};
void push(char x)
{
array[length] = x;
length++;
};
char pop() { return array[--length]; };
char top() { return array[length-1]; };
int exists() { return length; };
};
main(int argc, char **argv)
{
char a[1000];
int n, i, j, c=0;
if(argc != 2) {
printf("Usage: colorpairs colorstring\n");
return -1;
}
strcpy(a, argv[1]);
n = strlen(a);
class color clr;
clr.init(a);
clr.push(a[0]);
for(int k=1; k<n; k++) {
if(clr.exists() && clr.top() == a[k]) {
clr.pop();
c++;
} else {
clr.push(a[k]);
}
}
printf("Count: %d\n", c);
return 0;
}
</pre><br />
<b>Code for Doubly Linked List:</b><br />
<br />
<pre>findCount(Node *head)
{
if(head == NULL || head->next == NULL)
return 0;
Node *first = head;
Node *second = head->next;
Node *free1, *free2;
int count = 0;
while(second != NULL) {
if(first->value == second->value) {
count++;
free1 = first;
free2 = second;
if(second->next == NULL)
break;
if(first->prev == NULL) {
first = second->next;
second = second->next->next;
} else {
first = first->prev;
second = second->next;
}
first->next = second;
second->prev = first;
free(free1);
free(free2);
} else {
first = first->next;
second = second->next;
}
}
return count;
}
</pre>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-76960798313275429542014-04-20T23:25:00.000+05:302014-04-20T23:25:00.711+05:30Check Whether the tree is Balanced Tree or Not<p align="justify">A tree is a balanced tree, if the heights of the left and right sub trees differ by at max 1 at all the nodes.<br />
<br />
<b>The code which checks only at the root level</b><br />
<pre>bool IsTreeBalanced(Node root)
{
if(root == NULL)
return true;
int lh = GetDepth(root -> left);
int rh = GetDepth(root -> right);
if(lh - rh > 1 || rh - lh > 1)
return false;
return true;
}
int GetDepth(Node root)
{
if(root == NULL)
return 0;
int lh = GetDepth(root->left);
int rh = GetDepth(root->right);
return (lh > rh ? lh + 1 : rh + 1);
}
</pre><br />
<br />
<b>The code which checks at all the levels, but, not optimized</b><br />
<pre>bool IsTreeBalanced(Node root)
{
if(root == NULL)
return true;
int lh = GetDepth(root -> left);
int rh = GetDepth(root -> right);
if(lh - rh > 1 || rh - lh > 1 || ! IsTreeBalanced(root->left) || ! IsTreeBalanced(root->right))
return false;
return true;
}
int GetDepth(Node root)
{
if(root == NULL)
return 0;
int lh = GetDepth(root->left);
int rh = GetDepth(root->right);
return (lh > rh ? lh + 1 : rh + 1);
}
</pre><br />
<b>The code which checks at all the levels, and optimized little</b><br />
<br />
This code does not give the accurate height. If at few levels itself, if it finds that, it is not balanced, it would just return. <br />
<br />
In C#, we can use out parameters. In C, C++, we can use pointers, and in java, we need to have some kind of holder class. <br />
<br />
<pre>bool IsTreeBalanced(Node root, out int height)
{
if(root == NULL) {
height = 0;
return true;
}
int lh, rh;
if(! IsTreeBalanced(root -> left, out lh)) {
height = lh + 1;
return false;
}
if(! IsTreeBalanced(root -> right, out rh)) {
height = (lh > rh ? lh + 1 : rh + 1);
return false;
}
height = (lh > rh ? lh + 1 : rh + 1);
if(lh - rh > 1 || rh - lh > 1)
return false;
return true;
}
</pre><br />
<b>Very strict Balanced Tree: (In practice, not advisable)</b><br />
<br />
Where the the path length of the nearest empty child is within one from the path to the farthest empty child.<br />
<br />
<pre>bool IsTreeBalanced(Node root)
{
int max = GetMaxMinDepth(root, min);
if(max - min > 1)
return false;
return true;
}
int GetMaxMinDepth(Node root, out int minDepth)
{
if(root == NULL) {
minDepth = 0;
return 0;
}
int lmin, rmin;
int lmax = GetMaxMinDepth(root->left, out lmin);
int rmax = GetMaxMinDepth(root->right, out rmin);
minDepth = lmin < rmin ? lmin + 1 : rmin + 1;
return (lmax > rmax ? lmax + 1 : rmax + 1);
}
</pre></p>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-67053698859672942502014-04-19T23:24:00.000+05:302014-04-19T23:24:00.596+05:30In Binary Tree, Find Sum of Nodes of Alternate Levels<div dir="ltr" style="text-align: left;" trbidi="on">Given a binary tree, find sum of all the nodes of alternate levels. <br />
<br />
Root is at level 0.<br />
All the children of root are at level 1.<br />
All the grand children of root are at level 2.<br />
and so on.<br />
<br />
Given a level n, find some of all the nodes that are at alternate levels 0, 2, 4, and so on.<br />
<br />
<pre>int Sum(Node root, level n)
{
if(root==NULL)
return 0;
int d = (n%2 == 0 ? root->data : 0);
return d + Sum(root->left, n+1) + Sum(root->right, n+1);
}
</pre></div>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-88686914767760421252014-04-17T10:29:00.000+05:302014-04-17T10:29:02.006+05:30In a Binary Tree, find sum of all the nodes below certain levelGiven a binary tree, find sum of all the nodes below certain level. <br />
<br />
Root is at level 0.<br />
All the children of root are at level 1.<br />
All the grand children of root are at level 2.<br />
and so on.<br />
<br />
Given a level n, find some of all the nodes that are at level n or more.<br />
<br />
<pre>int Sum(Node root, level n)
{
if(root==NULL)
return 0;
if(n>0)
return Sum(root->left, n-1) + Sum(root->right, n-1);
return root->data + Sum(root->left, n-1) + Sum(root->right, n-1);
}
</pre>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-63343084833297020422014-04-16T10:23:00.000+05:302014-04-16T10:23:00.278+05:30In A Binary Tree, Find sum of all nodes upto certain levelGiven a binary tree, find sum of all the nodes upto certain level. <br />
<br />
Root is at level 0.<br />
All the children of root are at level 1.<br />
All the grand children of root are at level 2.<br />
and so on.<br />
<br />
Given a level n, find some of all the nodes that are at level n or less.<br />
<br />
<pre>int Sum(Node root, level n)
{
if(root==NULL)
return 0;
if(n==0)
return root->data;
return root->data + Sum(root->left, n-1) + Sum(root->right, n-1);
}
</pre>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com1tag:blogger.com,1999:blog-8236160994359493526.post-49333986896651769182014-04-15T18:10:00.005+05:302014-04-15T18:10:00.392+05:30In a Binary Tree, Find Sum of all the nodesGiven a binary tree, find the sum of all the nodes.<br />
<br />
<pre>int SumOfNodes(Node root)
{
if(root==NULL)
return 0;
return root->data + SumOfNodes(root->left) + SumOfNodes(root->right);
}
</pre>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-15165653212364634302014-04-14T17:42:00.000+05:302014-04-14T17:42:00.814+05:30Find whether two strings are anagrams of each other or not<p align="justify">Given a two strings, find whether they are anagrams of each other or not.<br />
<br />
Anagram means, rearranging of the characters in the string.<br />
<br />
Ex: <br />
mary and army are anagrams.<br />
abba and abab are anagrams<br />
abba and abbb are not anagrams<br />
<br />
<br />
<br />
<b>Answer:</b><br />
<br />
Assumption: The characters are ASCII characters<br />
<br />
<pre>AreAnagrams(char a[], char b[])
{
int count[128];
int n=strlen(a);
if(n!=strlen(b))
return false;
for(int i=0; i<127; i++)
count[i]=0;
for(int i=0; i<n; i++)
count[a[i]]++;
for(int i=0; i<n; i++)
count[b[i]]--;
for(int i=0; i<127; i++)
if(count[i]!=0)
return false;
return true;
}
</pre></p>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-60045433380317874072014-04-13T16:18:00.001+05:302014-04-13T16:18:00.796+05:30Efficiently Right Shift a String<p align="justify">You are given a string and a number k. You need to right shift the string k times. What is the efficient way to solve this?<br />
<br />
Example:<br />
the string is "Democracy".<br />
If k is 2, then the output should be "cyDemocra".<br />
If k is 3, then the output should be "acyDemocr"<br />
<br />
<br />
<br />
<br />
<br />
<br />
<b>Answer 1:</b><br />
<br />
O(nk) time complexity, O(1) space complexity.<br />
<br />
where n is the length of the string.<br />
<br />
Right shift the string k times.<br />
<br />
<pre>main()
{
char s[] = "Some string ....";
int n = streln(s);
for(int i=0; i<k; i++)
rightShift(s, n);
}
rightShift(char s[], int length)
{
char temp = s[length-1];
for(int i=length-1; i>0; i--)
s[i]=s[i-1];
s[0] = temp;
}
</pre><br />
<b>Answer 2:</b><br />
<br />
O(n) time complexity, and O(k) space complexity<br />
<br />
<pre>char s[] = "Some string ....";
int n = streln(s);
char *exsp = (char*)calloc(k, sizeof(char));
for(int i=0; i<k; i++)
exsp[i]=s[n-k+i];
for(int i=n-1; i>=k; i--)
s[i]=s[i-k];
for(int i=0; i<k; i++)
s[i]=exsp[i];
</pre><br />
<b>Answer 3:</b><br />
<br />
O(n) time complexity, O(1) space complexity<br />
<br />
Reverse the entire array.<br />
Reverse the array from 0 to k-1, and from k-1 to n-1.<br />
<br />
<pre>Reverse(char s[], int start, int end)
{
for(int i=start, j=end; i<j; i++, j--)
{
int t=s[i];
s[i]=s[j];
s[j]=t;
}
}
Reverse(s, 0, n-1);
Reverse(s, 0, k-1);
Reverse(s, k, n-1);
</pre></p>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com2tag:blogger.com,1999:blog-8236160994359493526.post-82027473372777780272011-09-28T11:13:00.000+05:302011-09-28T11:13:02.734+05:30Constructing Tree From Inorder and PreorderConstructTree(preorder, 0, preOrder.Length-1, inorder, 0, inorder.Length-1);
<pre>
Node ConstructTree(int[] preorder, int ps, int pe, int[] inorder, int is, int ie)
{
if(ps < pe || is < ie)
return NULL;
Node root = new Node();
root->data = preorder[ps];
int mid = is;
while(inorder[mid] != preorder[ps])
mid++;
root->left = ConstructTree(preorder, ps+1, ps+mid-is, inorder, is, mid-1);
root->right = ConstructTree(preorder, ps+mid-is+1, pe, inorder, mid+1, ie);
return root;
}
</pre>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-21928572999669069302011-04-27T21:50:00.000+05:302011-04-27T21:50:13.925+05:30Princess, Flowers and Snake With Incorrect Name Plates<p align="justify">There are three rooms, and there are Princess, Flowers and Snake in those rooms. The doors of all the rooms have incorrect nameplates. i.e., the nameplate for the princess' room is not Princess. Similarly, the nameplate for the Flowers' room is not Flowers. You need to find the room of the Princess without going to the room of Snake. How do you find?<br />
<br />
<br />
<br />
<b>Answer:</b><br />
<br />
Go to the room which has the nameplate Snake. That will not have Snake. If the room has princess, you are done. If the room has flowers, then go to the room which has nameplate flowers. Princess would be there in that room. [Since, Princess cannot be there in the room which has nameplate Princess.]<br />
</p>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com2tag:blogger.com,1999:blog-8236160994359493526.post-12197170412944061642011-04-27T21:37:00.000+05:302011-04-27T21:37:43.765+05:30One Person Always Lies, Another always Tells Truth<p align="justify">You have to go to a place and there are two paths. You don't know which path leads to your destination. There are two watchmen at the entrance. One person always tells truth, and another one always tells lies. You can ask only one question to one person. What question would you ask to find the way to your destination?<br />
<br />
<br />
<br />
<b>Answer:</b><br />
If I ask the other person, the way to the destination, what would he tell?<br />
<br />
Whatever he says, that is not the correct path. Take the other path. <br />
<br />
</p>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com1tag:blogger.com,1999:blog-8236160994359493526.post-72506660742928145722011-04-27T21:30:00.000+05:302011-04-27T21:30:10.231+05:30Four People crossing the river with different speeds<p align="justify">There is a dark tunnel and four people wants to cross the tunnel. In the tunnel, only two people can travel at a time, and there is only one torch light. Without the torch light, they cannot travel through the tunnel. The four people can travel with different speeds. The first person takes 1 hour to travel through the tunnel. Second person takes 2 hours, third person takes 5 hours, and fourth person takes 10 hours. How can they travel in the least amount of time?<br />
<br />
<br />
<br />
<b>Solution:</b><br />
<br />
1 & 2 cross the tunnel<br />
<br />
1 returns<br />
<br />
5 & 10 cross the tunnel<br />
<br />
2 returns<br />
<br />
1 & 2 cross the tunnel<br />
<br />
Total Time: 17 hours<br />
</p>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-45383973185303875282011-02-13T12:55:00.000+05:302011-02-13T12:55:23.907+05:30Three Cannibals and Three Humans Crossing River<p align="justify">There is a small river. On one side of the river, there are three cannibals, and on another side three humans are there. Boat is with the cannibals. If there are more no.of cannibals than the humans, then the cannibals will eat the humans. If the no.of cannibals is equal or less than the no.of humans, then they cannot do anything. How do the humans move to the other side of the river safely?<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<b>Answer:</b><br />
<br />
3 Cannibals - 3 Humans<br />
<br />
One Cannibal crosses the river<br />
<br />
2 Cannibals - 3 Humans, 1 Cannibal<br />
<br />
2 Humans cross the river<br />
<br />
2 Cannibals, 2 Humans - 1 Human, 1 Cannibal<br />
<br />
1 Human and 1 Cannibal cross the river.<br />
<br />
1 Cannibal, 1 Human - 2 Humans, 2 Cannibals<br />
<br />
2 Humans cross the river<br />
<br />
1 Cannibal, 3 Humans - 2 Cannibals<br />
<br />
1 Cannibal crosses the river<br />
<br />
3 Humans - 3 Cannibals.<br />
</p>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-64148611788202063022011-02-13T12:43:00.000+05:302011-02-13T12:43:35.035+05:30Find the Distance Travelled By the Prince<p align="justify">A Prince is going to a temple in a forest by his horse which travels at a speed of 60 km per hour. When he reached the entrance of the forest, he saw a girl who is going to the temple at a speed of 6 kms per hour. He visits the temple and returns to see the girl immediately. After he sees the girl, he goes again to the temple. He roams between the temple and girl, till the girl reaches the temple after one hour. How much distance the prince travelled by roaming between the girl and the temple?<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<b>Answer:</b><br />
<br />
If we try to calculate how many no.of times, the prince has visited the temple or girl etc., the problem becomes complicated. The simple to way to solve the problem is, how long the prince has travelled, and from that calculate the distance. The prince has travelled as long as the girl was walking towards the temple. The girl took one hour to reach the temple. For that one hour, the prince was travelling. So, he travelled total 60 kms.<br />
</p>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com0tag:blogger.com,1999:blog-8236160994359493526.post-12471209571307179832011-02-13T12:20:00.000+05:302011-02-13T12:20:20.065+05:30Finding the Poison Bottle<p align="justify">A king has arranged a celebration with many visitors to his kingdom. In the celebration, they arranged drinks in 1000 bottles. Just one hour before the celebration, he came to know that, one person has included a poison drink of the same color in a bottle of the same shape. If anyone drinks poison, then nothing happens to that person for one hour. After one hour, suddenly that person would die.<br />
<br />
The king has few criminals who are going to be hanged the next day. With the help of them, he can find which bottle has poison. How many minimum no.of criminals he needs to find out the poisoned bottle in one hour.<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<b>Answer:</b><br />
He needs 10 criminals.<br />
<br />
Every bottle is given a no from 0 to 1000. Convert each number to binary. The binary number would contain 10 bits. For the first criminal, give little drink from all the bottles for which the first bit is 1. Similarly, for the second criminal, give drink from all the bottle for which the second bit is 1. Do the same thing for all the ten criminals. <br />
<br />
After one hour, form a binary number with the criminals. If the first criminal dies, then make the first bit 1. If the second criminal does not die, then make the second bit 0. Do the same for all the criminals. Convert the binary number to the corresponding decimal number. That bottle has the poison. <br />
</p>tnsatishhttp://www.blogger.com/profile/11487701501347042727noreply@blogger.com1