gauravk.18
BAN USER- 0of 0 votes
AnswersLets say A is a friend of B and B is a friend of C then A and C are two degree friends. So we have to implement a function that takes two friends and return true if they are 2 degree friends. How will you implement this function efficiently.
- gauravk.18| Report Duplicate | Flag | PURGE
Hi5 Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWhat is stack. How do you implement it. Now lets say we want to add a new function called min which return the min element on the stack along with push and pop. Like push and pop this min function should also be a constant time operation how will u do it.
- gauravk.18| Report Duplicate | Flag | PURGE
Hi5 Software Engineer / Developer Algorithm - 1of 0 votes
AnswersBackground:
- gauravk.18
For any perimeter of a rectangle, there may be multiple different dimensions that result in that specific
perimeter. When there are multiple dimensions for the same perimeter, there may also be multiple areas. In other words, any one perimeter can result in different areas depending on the possible combinations of dimensions that can make that perimeter.
Definition:
A dimension or instance of dimensions for a rectangle is a pair of length and width values. A dimension with length 5 and width 4 is considered the same as a dimension with length 4 and width 5. The area of a rectangle is the length multiplied by the width. The perimeter of a rectangle is equal to the sum of the lengths of all 4 sides or the sum of 2 multiplied by the width and 2 multiplied by the length.
Requirement:
A finite set of possible perimeters of a rectangle exist given a maximum perimeter, minimum length of any side, and the constraint that all sides are whole numbers; we will call this set U. Find the subset of perimeters in set U where all of the possible dimensions for a perimeter in the subset have areas common with the areas of one or more other perimeters in set U. Your program should take the minimum length of any side and the maximum perimeter, respectively, as command line arguments and output a comma separated list of the perimeters that meet the criteria explained above, sorted from lowest to highest. The program should be submitted in a single Java class with an implemented main function that provides the correct output given the two input arguments.
Example:
javac YourClass.java
java YourClass 1 64
10,14,18,20,22,26,30,34
Please make sure your program can be run with the exact syntax above. You can name the class anything you like, but the class name will be passed to a program that will compile it and then run a set of tests on the resulting program. It is important that your class will compile and run from within a local directory, not a package directory.| Report Duplicate | Flag | PURGE
Hi5 Software Engineer / Developer Coding Algorithm - 0of 0 votes
AnswersImplement Run Length Encoding.
- gauravk.18| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Coding - 0of 0 votes
AnswerGiven n cities with their populations, suggest an algorithm to pick up one of the cities randomly such that more the population of city is more chance it stands to be picked. Assume you can use an inbuilt random generator function from the language library.
- gauravk.18| Report Duplicate | Flag | PURGE
Hi5 Software Engineer / Developer Algorithm - 0of 0 votes
AnswersImplement Strtok function.
- gauravk.18| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Coding
Will take only 2 shots. First shot compare pair of 3 balls 1233 with 456. If they are not same lets say 123 is heavier then way 1 and 2 if they are same 3 is heavier. If 123 and 456 are same then weight 7 and 8 and find out which one is heavier. So total trial required only 2.
- gauravk.18 April 01, 2008XOR is the way to go. XOR all the numbers and the output will be the no missing. Take just 3 nos. 2,2,3 when u XOR 2 with itself it will give 0 and XOR of a no with 0 is the number itself. Hence XORing all the nos. will give the missing no.
- gauravk.18 March 31, 2008You solution takes more than 2 measurements wheras this can be easily done in just 2 measurements.
- gauravk.18 March 31, 2008So, you have to assign 3 bit number to each corner of the cube. Consider the geometry of the cube and represent each binary digit as one of the three axis x,y,z and choose value as 0 or 1 depending on the alignment of the cube in that direction. In this way you can assign binary digits to the cube. Now the beauty of this is that if you travel through the cube covering each corner at most one it will generate a 3 bit Gray code.
- gauravk.18 March 31, 2008Bring a dog and show him how you greet him and that way alien will know how to greet a dog.
- gauravk.18 March 21, 2008I guess the first solution given is the best....I don't understand why people are talking about linked list when the ques says to use an array. With dividing the array in 3 parts makes it easier to add and delete elements by maintaining three pointers each one of them pointing to the top of the one of the three stacks....
- gauravk.18 March 13, 2008Here is the code..
#include<stdio.h>
void main()
{
int a,b,c,count=0;
printf("Enter the two numbers \n");
scanf("%d", &a);
scanf("%d", &b);
c = a^b;
//Counting the no. of ON bits in c
while(c)
{
count++;
c = c & (c-1);
}
printf("The total no. of transformations required is %d\n",count);
}
void merge(int * a, int na, int *b, int nb, int *c)
{
int i, aindex = 0, bindex = 0;
for(i = 0; i<na+nb;i++)
{
if(aindex<na && bindex < nb)
{
if(a[aindex] < b[bindex])
c[i] = a[aindex++];
else
c[i] = b[bindex++];
}
else
break;
}
if(aindex == na)
for(int j = i; j<na+nb;j++)
c[j] = b[bindex++];
else
for(int j = i; j<na+nb;j++)
c[j] = a[aindex++];
}
I am using additional memory but we can do it without using additional memory in that case we will have to scan through the entire array twice..In that case in first scan we replace all zeroes in the array by a special character and in the second scan we replace each row and column containing that special character to Zero..
#include<stdio.h>
#include<stdlib.h>
void main()
{
int a[100][100];
int n;
printf("Enter the number of elements of the array in one dimension\n");
scanf("%d", &n);
printf("Enter the elements of the array \n");
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d", &a[i][j]);
int * i_index = (int *) malloc(sizeof(int) * n);
int * j_index = (int *) malloc(sizeof(int) * n);
for(int i=0;i<n;i++)
{
i_index[i] = -1;
j_index[i] = -1;
}
for(int i =0; i< n;i++)
for(int j=0;j<n;j++)
{
if(a[i][j] == 0)
{
i_index[i] = 0;
j_index[j] = 0;
}
}
for(int i=0;i<n;i++)
{
if(i_index[i] == 0)
for(int j=0;j<n;j++)
a[i][j] = 0;
if(j_index[i] == 0)
for(int j=0;j<n;j++)
a[j][i] = 0;
}
printf("The new elements of the array are \n");
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
printf("%d", a[i][j]);
printf("\n");
}
}
Can be done in linear time using Boyer's Moore algorithm. If preprocessing is allowed we can build a hash table and keep a count of all the words seen in the book but that will be expensive. We can also use suffix tree which can be constructed in O(n) time and will require the same amount of space and then the search for the pattern can be carried out in O(length of pattern). But this will also take a lot of space. Can anyone think of a better solution????
- gauravk.18 March 01, 2008Hey, I think it should work...Should not be a problem in this case....
- gauravk.18 March 01, 2008Here is my code...
#include<stdio.h>
void main()
{
char str[100];
char * ptr;
printf("Enter the string \n");
ptr = gets(str);
int i =0;
int val = 0;
while(str[i]!='\0' && (str[i] >='0' && str[i] <='9' || str[i] == '-'))
{
if(str[i] == '-')
{
i++;
continue;
}
val = str[i]-'0' + val*10;
i++;
}
if(str[0] == '-')
printf("The value is %d \n",0- val);
else
printf("The value is %d \n", val);
}
#include<stdio.h>
void main()
{
int n, no = 0, x = 5, i =1;
printf("Enter the number\n");
scanf("%d", &n);
while(n/x != 0)
{
no = no + n/(5*i);
i = i+5;
x = x *5;
}
printf("The total no. of trailing zeros in the number is %d \n", no);
}
void reverse(struct nodes *head)
{
struct nodes *prev, *now, *future;
prev = head;
now = prev->next;
while(now)
{
future = now->next;
now->next = prev;
prev = now;
now = future;
}
head->next = NULL;
head = prev;
display_list(head);
}
Here is the code without recursion. I tried for couple of inputs and it seems to work. Plz let me know if someone finds a bug in it..
#include<stdio.h>
void main()
{
int i, a[100],n,start,mid,end,count=0;
printf("Enter the total no. of elements in the array \n");
scanf("%d", &n);
printf("Enter the elements in the rotated array \n");
for(i=0;i<n;i++)
scanf("%d", &a[i]);
start = 0;
end = n-1;
while(start != end)
{
mid = start+(end-start+1)/2;
if(a[start] < a[mid])
start = mid;
else
{
count = mid;
end = mid-1;
}
}
printf("The rotation count is %d \n", (count)?n-count:0);
}
Here is the code...
#include<stdio.h>
void combinations(int * result, int start, int prev);
const char * getcode(int digit);
void main()
{
int result[7];
for(int i = 0; i < 9; i++)
{
result[0] = i;
combinations(result, 1 ,i);
}
}
void combinations(int * result, int start, int prev)
{
const char *code;
int i,k=0;
if(start == 7)
{
printf("\nCombination: ");
for(i=0;i<7;i++)
printf("%d ", result[i]);
return;
}
code = getcode(prev);
k=0;
while(code[k] != '\0')
{
result[start] = code[k++] - '0';
combinations(result, start+1, result[start]);
}
}
const char * getcode(int digit)
{
char *code;
switch(digit)
{
case 0: code = "46";
break;
case 1: code = "68";
break;
case 2: code = "79";
break;
case 3: code = "48";
break;
case 4: code = "39";
break;
case 5: code = "5";
break;
case 6: code = "17";
break;
case 7: code = "26";
break;
case 8: code = "13";
break;
case 9: code = "24";
break;
}
return code;
}
We can't apply binary search as we don't know the size of the array and I guess there is no better solution that what's posted by Anonymous.
- gauravk.18 February 29, 2008My messy solution to this problem..
#include<stdio.h>
void main()
{
int i, n, sum=0, prev_sum = 0, a[100], smallest_negative, start_index, end_index, prev_start_index, prev_end_index,smallest_index;
printf("Enter the number of elements in the array \n");
scanf("%d", &n);
printf("Enter the elements of the array \n");
for(i = 0;i<n;i++)
scanf("%d", &a[i]);
smallest_negative = a[0];
start_index = 0;
end_index = 0;
prev_start_index = 0;
prev_end_index = 0;
smallest_index = 0;
for(i=0;i<n;i++)
{
if(smallest_negative < a[i])
{
smallest_negative = a[i];
smallest_index = i;
}
if(sum + a[i] < sum && prev_sum < sum)
{
prev_end_index = i-1;
prev_start_index = start_index;
prev_sum = sum;
}
sum = sum + a[i];
if(sum < 0)
{
sum = 0;
start_index = i+1;
}
else
end_index = i;
}
if(sum < prev_sum)
{
start_index = prev_start_index;
end_index = prev_end_index;
}
sum = (sum > prev_sum)?sum:prev_sum;
if(!sum)
{
sum = smallest_negative;
start_index = end_index = smallest_index;
}
printf("The maximum sum in the array is %d ", sum);
printf("The elements are \n");
for(i=start_index;i<=end_index;i++)
printf("%d ", a[i]);
}
Consider all the words as nodes of a graph and draw an edge between those nodes(words) that are synonyms. Now if you have to find the synonym of a word start from that word(node) and run BFS. That will give all the words that are connected to this word and hence synonyms to the word. Once you are ready with the graph of all the words, listing down the synonyms will only take O(m+n) time.
- gauravk.18 February 29, 2008Its not completely O(n) as you are using strcmp function which in itself take O(k) time assuming k to be the average length of each word and so the efficiency will become O(nk). I am not sure if we need to consider k or not. I guess that depends on what the interviewer wants.
- gauravk.18 February 29, 2008Here is the code..
#include<stdio.h>
#include<stdlib.h>
void main()
{
int a[100],n,start,end,i;
printf("Enter the no. of elements in the array \n");
scanf("%d", &n);
printf("Enter the elements of the array \n");
for(i=0;i<n;i++)
{
scanf("%d", &a[i]);
if(a[i] != 0 || a[i] != 1)
printf("Wrong Input \n");
exit(0);
}
start = 0;
end = n-1;
while(start < end)
{
if(a[start] == 1 && a[end] == 0)
{
a[start++] = 0;
a[end--] = 1;
}
else if(a[start] == 1 && a[end] == 1)
end--;
else
start++;
}//End of while
printf("The sorted array is \n");
for(i=0;i<n;i++)
printf("%d ", a[i]);
}
int maxdepth(tree_node * root)
{
int d1=0, d2=0;
if (root == NULL)
return 0;
d1 = maxdepth(root->left);
d2 = maxdepth(root->right);
if(d1>d2)
return d1+1;
else
return d2+1;
}
Here is my version..
#include<stdio.h>
void main()
{
int i, n, sum=0, prev_sum = 0, a[100], smallest_negative, start_index, end_index, prev_start_index, prev_end_index,smallest_index;
printf("Enter the number of elements in the array \n");
scanf("%d", &n);
printf("Enter the elements of the array \n");
for(i = 0;i<n;i++)
scanf("%d", &a[i]);
smallest_negative = a[0];
start_index = 0;
end_index = 0;
prev_start_index = 0;
prev_end_index = 0;
smallest_index = 0;
for(i=0;i<n;i++)
{
if(smallest_negative < a[i])
{
smallest_negative = a[i];
smallest_index = i;
}
if(sum + a[i] < sum && prev_sum < sum)
{
prev_end_index = i-1;
prev_start_index = start_index;
prev_sum = sum;
}
sum = sum + a[i];
if(sum < 0)
{
sum = 0;
start_index = i+1;
}
else
end_index = i;
}
if(sum < prev_sum)
{
start_index = prev_start_index;
end_index = prev_end_index;
}
sum = (sum > prev_sum)?sum:prev_sum;
if(!sum)
{
sum = smallest_negative;
start_index = end_index = smallest_index;
}
printf("The maximum sum in the array is %d ", sum);
printf("The elements are \n");
for(i=start_index;i<=end_index;i++)
printf("%d ", a[i]);
Here is the code for part1..
#include<stdio.h>
int find(int * a, int n, int largest, int second);
void main()
{
int n, i, a[100],largest = 0 ,second = 0;
printf("Enter the no. of elements of the array\n");
scanf("%d", &n);
printf("Enter the elements of the array\n");
for(i = 0 ;i<n; i++)
scanf("%d", &a[i]);
if(n == 1)
printf("No Second largest element exist");
else
{
largest = a[0];
second = a[1];
second = find(a,n,largest,second);
if(second == -1)
printf("No Second largest element exist");
else
printf("The second largest element is %d\n", second);
}
}
int find(int * a, int n, int largest, int second)
{
int temp;
static int start = 0;
if(start == n)
{
if(second == largest)
return -1;
else
return second;
}
if(a[start] > largest)
{
temp = largest;
largest = a[start];
second = temp;
}
start++;
second = find(a,n,largest,second);
}
Adjacency List as we need to know the neighbors of nodes which can be obtained more efficiently in adjacency list representation. In case of adjacency matrix we need to scan through all the n nodes to check if u,v has a edge.
- gauravk.18 February 29, 2008Use Adjacency List to represent the graph and run DFS or BFS to find out if there is a path between two nodes.
- gauravk.18 February 26, 2008O(n) in worst case when all the keys get mapped to the same slot.
- gauravk.18 February 26, 2008O(n)
- gauravk.18 February 26, 2008void reverse(struct nodes *head)
{
struct nodes *prev, *now, *future;
prev = head;
now = prev->next;
while(now)
{
future = now->next;
now->next = prev;
prev = now;
now = future;
}
head->next = NULL;
head = prev;
display_list(head);
}
A naive implementation is as follows:
#include <stdio.h>
char * strstr(char *, char *);
void main()
{
char str1[1000];
char str2[100];
char *s = 0;
printf("Enter the input string \n");
gets(str1);
printf("Enter the string to be matched \n");
gets(str2);
s = strstr(str1,str2);
if(s==0)
printf("SORRY NO MATCH\n");
else
printf("The output is %s \n", s);
}
char * strstr(char * str1, char * str2)
{
char *s = 0;
int len1 = 0, len2 = 0;
while(str1[len1] != '\0')
len1++;
while(str2[len2] != '\0')
len2++;
if(len1<len2)
return 0;
else
{
for(int i = 0; i<len1-len2+1; i++)
{
int j = 0;
while(str2[j] != '\0')
if(str1[i+j] == str2[j])
j++;
else
break;
if(j==len2)
{
s = str1+i;
break;
}
}
return s;
}
}
Here is My Code...
#include<stdio.h>
char getcode(int start, int index);
void word(int *, int , char * );
void main()
{
int n[7];
char result[8];
printf("Enter the 7 digit phomne number \n");
for(int i=0;i<7;i++)
{
scanf("%d", &n[i]);
//result[i] = ' ';
}
result[7] = '\0';
word(n,0,result);
}
void word(int *n, int start, char * result)
{
if(start==7)
{
printf("\n");
printf("%s", result);
return;
}
for(int i=0;i<3;i++)
{
result[start] = getcode(n[start],i);
word(n, start+1,result);
}
}
char getcode(int start, int index)
{
switch(start)
{
case 0: return '0';
case 1: return '1';
case 2:switch(index){
case 0: return 'a';
case 1: return 'b';
case 2: return 'c'; }
case 3:switch(index){
case 0: return 'd';
case 1: return 'e';
case 2: return 'f'; }
case 4:switch(index){
case 0: return 'g';
case 1: return 'h';
case 2: return 'i'; }
case 5:switch(index){
case 0: return 'j';
case 1: return 'k';
case 2: return 'l'; }
case 6:switch(index){
case 0: return 'm';
case 1: return 'n';
case 2: return 'o'; }
case 7:switch(index){
case 0: return 'p';
case 1: return 'q';
case 2: return 'r'; }
case 8:switch(index){
case 0: return 's';
case 1: return 't';
case 2: return 'u'; }
case 9:switch(index){
case 0: return 'v';
case 1: return 'w';
case 2: return 'x'; }
}
}
Here is my Code...
#include<stdio.h>
char getcode(int start, int index);
void word(int *, int , char * );
void main()
{
int n[7];
char result[8];
printf("Enter the 7 digit phomne number \n");
for(int i=0;i<7;i++)
{
scanf("%d", &n[i]);
//result[i] = ' ';
}
result[7] = '\0';
word(n,0,result);
}
void word(int *n, int start, char * result)
{
if(start==7)
{
printf("\n");
printf("%s", result);
return;
}
for(int i=0;i<3;i++)
{
result[start] = getcode(n[start],i);
word(n, start+1,result);
}
}
char getcode(int start, int index)
{
switch(start)
{
case 0: return '0';
case 1: return '1';
case 2:switch(index){
case 0: return 'a';
case 1: return 'b';
case 2: return 'c'; }
case 3:switch(index){
case 0: return 'd';
case 1: return 'e';
case 2: return 'f'; }
case 4:switch(index){
case 0: return 'g';
case 1: return 'h';
case 2: return 'i'; }
case 5:switch(index){
case 0: return 'j';
case 1: return 'k';
case 2: return 'l'; }
case 6:switch(index){
case 0: return 'm';
case 1: return 'n';
case 2: return 'o'; }
case 7:switch(index){
case 0: return 'p';
case 1: return 'q';
case 2: return 'r'; }
case 8:switch(index){
case 0: return 's';
case 1: return 't';
case 2: return 'u'; }
case 9:switch(index){
case 0: return 'v';
case 1: return 'w';
case 2: return 'x'; }
}
}
I didn't get this question. Can anyone clarify please?
If the change needs to be done on all the pages on internet then its not possible as we won't have access to modify the pages. In case, we do have the access, then I guess we need to search for the hyperlink using some fast algo like Boyer's Moore Algorithm for string matching and replace it.
However I guess better would have been to keep amazon.com and when the request comes to the default page on amazon simply redirect it to amazon.com?id=123 but I know thats not what's being asked here.
1. Demand Forecasting
2. Price Optimization
Here is the code....
#include<stdio.h>
#include<stdlib.h>
struct node
{
int value;
node * next;
};
void deletenode(node *);
void main()
{
int i, n=0,k=0,val = 0;
node *temp, *head, *prev;
printf("Enter the no. of nodes in the link list\n");
scanf("%d", &n);
printf("Enter the values of the link list in order\n");
scanf("%d", &val);
head = (node *) malloc(sizeof(node));
head->value = val;
head->next = NULL;
prev= head;
for(i=1;i<n;i++)
{
scanf("%d", &val);
temp = (node *) malloc(sizeof(node));
temp->value = val;
temp->next = NULL;
prev->next = temp;
prev = temp;
}
printf("Enter the node you wish to delete\n");
scanf("%d",&k);
temp = head;
k = k-1;
while(k--)
temp = temp->next;
//Taking care of the boundary condition where you only have one node in the list
if(temp->next == NULL && temp == head) // If the linklist only has one node
head = NULL;
else if(temp->next == NULL && temp != head) //If last node in the list needs to be deleted
{
printf("Can't delete the last node\n");
exit(0);
}
else if((temp->next != NULL && temp == head)) //If head needs to be deleted
head = head->next;
else
deletenode(temp);
temp = head;
while(temp)
{
printf("%d ",temp->value);
temp = temp->next;
}
}
void deletenode(node *head)
{
int i;
node *first, *temp, *future;
temp = head;
first = head;
//If Head is NULL return
if(head)
{
head->value = head->next->value;
future = head->next->next;
delete(head->next);
head->next = future;
}
}
Here is the solution in one pass
#include<stdio.h>
#include<stdlib.h>
struct node
{
int value;
node * next;
};
node * delete_kth(node *, int);
void main()
{
int i, n1=0,n2=0,k=0,val = 0;
node *temp, *head, *prev;
printf("Enter the no. of nodes in the link list\n");
scanf("%d", &n1);
printf("Enter the values of the link list in order\n");
scanf("%d", &val);
head = (node *) malloc(sizeof(node));
head->value = val;
head->next = NULL;
prev= head;
for(i=1;i<n1;i++)
{
scanf("%d", &val);
temp = (node *) malloc(sizeof(node));
temp->value = val;
temp->next = NULL;
prev->next = temp;
prev = temp;
}
printf("Enter the value of the kth node from last that u wanna delete\n");
scanf("%d",&k);
if(k>n1 || k<=0)
printf("Wong input\n");
//Taking care of the boundary condition where you only have one node in the list
else if(head->next == NULL)
head = NULL;
else
head = delete_kth(head,k);
temp = head;
while(temp)
{
printf("%d ",temp->value);
temp = temp->next;
}
}
node * delete_kth(node *head, int k)
{
int i;
node *first, *temp, *future;
temp = head;
first = head;
//If Head is NULL return
if(!head)
return NULL;
for(int i =0;i<k;i++)
temp = temp->next;
//Taking care of the boundary condition where k equals the length of the list
if(!temp)
{
future = head;
head = head->next;
delete(future);
return head;
}
while(temp->next)
{
first = first->next;
temp = temp->next;
}
future = first->next;
first->next = future->next;
delete(future);
return head;
}
Here is my code....
#include<stdio.h>
#include<stdlib.h>
void main()
{
int a[100],n=0,i, j;
printf("Enter the total no. of elements in the array\n");
scanf("%d", &n);
printf("Enter the elements in sorted order \n");
for(i=0;i<n;i++)
scanf("%d", &a[i]);
j = 0;
for(i=0;i<n-1;i++)
{
if(a[i] > a[i+1])
{
printf("Array not sorted \n");
exit(0);
}
while(a[i] == a[i+1])
i++;
a[j++] = a[i];
}
if(i!=n)
a[j++] = a[n-1];
printf("The new array is \n");
for(i = 0; i<j; i++)
printf("%d ", a[i]);
}
Here is my solution that requires only one traversal...
#include<stdio.h>
#include<stdlib.h>
struct node
{
int value;
node * next;
};
node * delete_kth(node *, int);
void main()
{
int i, n1=0,n2=0,k=0,val = 0;
node *temp, *head, *prev;
printf("Enter the no. of nodes in the link list\n");
scanf("%d", &n1);
printf("Enter the values of the link list in order\n");
scanf("%d", &val);
head = (node *) malloc(sizeof(node));
head->value = val;
head->next = NULL;
prev= head;
for(i=1;i<n1;i++)
{
scanf("%d", &val);
temp = (node *) malloc(sizeof(node));
temp->value = val;
temp->next = NULL;
prev->next = temp;
prev = temp;
}
printf("Enter the value of the kth node from last that u wanna delete\n");
scanf("%d",&k);
if(k>n1 || k<=0)
printf("Wong input\n");
//Taking care of the boundary condition where you only have one node in the list
else if(head->next == NULL)
head = NULL;
else
head = delete_kth(head,k);
temp = head;
while(temp)
{
printf("%d ",temp->value);
temp = temp->next;
}
}
node * delete_kth(node *head, int k)
{
int i;
node *first, *temp, *future;
temp = head;
first = head;
//If Head is NULL return
if(!head)
return NULL;
for(int i =0;i<k;i++)
temp = temp->next;
//Taking care of the boundary condition where k equals the length of the list
if(!temp)
{
future = head;
head = head->next;
delete(future);
return head;
}
while(temp->next)
{
first = first->next;
temp = temp->next;
}
future = first->next;
first->next = future->next;
delete(future);
return head;
}
I don't understand the question properly but I guess the answer should be binary search tree.
- gauravk.18 February 22, 2008Here is the code for merging two sorted Link list without using any additional memory..
#include<stdio.h>
#include<stdlib.h>
struct node
{
int value;
node * next;
};
void merge(node * , node *);
void main()
{
int i, n1=0,n2=0,val = 0;
node *temp, *l1, *l2, *prev;
printf("Enter the no. of nodes in the first link list\n");
scanf("%d", &n1);
printf("Enter the values of the link list in order\n");
scanf("%d", &val);
l1 = (node *) malloc(sizeof(node));
l1->value = val;
l1->next = NULL;
prev= l1;
for(i=1;i<n1;i++)
{
scanf("%d", &val);
temp = (node *) malloc(sizeof(node));
temp->value = val;
temp->next = NULL;
prev->next = temp;
prev = temp;
}
printf("Enter the no. of nodes in the second link list\n");
scanf("%d", &n2);
printf("Enter the values of the link list in order\n");
scanf("%d", &val);
l2 = (node *) malloc(sizeof(node));
l2->value = val;
l2->next = NULL;
prev = l2;
for(i=1;i<n2;i++)
{
scanf("%d", &val);
node * temp = (node *) malloc(sizeof(node));
temp->value = val;
temp->next = NULL;
prev->next = temp;
prev = temp;
}
merge(l1,l2);
}
void merge(node * l1, node * l2)
{
int i;
node * head;
node * prev, * temp;
if(l1 == 0 || l2 == 0)
return;
if(l1->value < l2->value)
{
head = l1;
l1 = l1->next;
}
else
{
head=l2;
l2 = l2->next;
}
prev = head;
while(l1 != NULL && l2 != NULL)
{
if(l1->value < l2->value)
{
prev->next = l1;
prev = l1;
l1 = l1->next;
}
else
{
prev->next = l2;
prev = l2;
l2 = l2->next;
}
}//End of while
if(l1==NULL)
prev->next = l2;
else
prev->next = l1;
printf("The new sorted link list is:\n");
temp = head;
while(temp != NULL)
{
printf("%d ",temp->value);
temp = temp->next;
}
}
The solution that take sum of n numbers and subtract the sum of no given in order to find the missing no is not accurate as it will be exponential in nature. remember you are finding the product as n(n+1)/2. if n is very large n won't be able to fit in 32 bit word and so this multiplication will go in exponential of the no. of bits used to represent the number n. The best solution is as follows:
Lets say n = 8 and u have no. from 0-7 write in binary form all the no.You need 3 bits to represent each no. Take the column representing the MSB. Now it should have equal no. of 1's and 0's but since there is one element missing so it will have one of 1 or 0 less. Find out by counting the total no. of 0 and 1 in MSB. Lets say no. of 1 is more than no. of 0 so it means the missing no has its MSB as 0. Repeat this for the second column of bits but now counting no. of 1 and o only for those digits which has 0 as the MSb and so in this iteration you only have to scan through n/2 elements. Do this until u r r done with the LSB and so the total time taken will be n + n/2 + n/4 + ---- = O(n) complexity.
They are like servants, you instruct them to so sth and they do it for you.
- gauravk.18 February 17, 2008
why are comparing with B[2] and A[3] in order to determine which horse is the second fastest. It will either be A[2] or B[1]. If B[2] could be the answer then that will be wrong as B[1] is faster than B[2] and B[1[ is the not the fastest but can be the second fastest.
- gauravk.18 April 01, 2008