Amit
BAN USER- 0of 0 votes
AnswersFind x^y where y can be float. Any good algorithm for that?
- Amit in United States| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - -1of 1 vote
AnswersBy mistake I wrote the following program and it compiles and runs without any error in gcc compiler. enter code here
- Amit in India
#include<stdio.h>
#include<stdlib.h>
int main()
{
int i,**data;
data=(int **)malloc(sizeof(int)*1000000);
for(i=0;i<1000000;i++)
data[i]=(int *)malloc(sizeof(int)*1000000);
printf("done\n");
return 0;
}
But I don't understand how is it allocating an array of 1000000*1000000 bytes,almost equivalent to 1TB??| Report Duplicate | Flag | PURGE
SDE1 C - 2of 6 votes
Answersthere is an infinite line.you are standing at a particular point you can either move 1 step forward or 1 step backward.you have to search for an object in that infinite line.your object can be in any direction. Give optimal algorithm.
- Amit in United States| Report Duplicate | Flag | PURGE
Amazon
for each element a[i],we need to find
1.largest elemnt smaller than current element from 0 to i-1..will be stored in an array.
2. largest element greater than current element from i+1 to n-will be stored in oder array,
1. for finding first,we'll create a balanced BST or AVL and find floor.
insert a[0] in AVL tree
start loop from i=1 to i=n-2
search for floor in AVL and store in another array say b
insert a[i] in AVL
2. for second array,linear scan.(finding greatest element on right side).
and store this value for each element in a diff array say c
now check for every element
3.Now find index i for max a[i]*b[i]*c[i]
Time complexity--o(nlogn) for part 1 and o(n) for part 2 and 3..overall-o(nlogn)
space complexity-o(n)
#include<stdio.h>
#include<limits.h>
int myfn(int a[],int b[],int n,int i1,int i2,int min,int max)
{
int j,k;
for(j=i1;j<n;j++)
if(a[j]>min && a[j]<max)
break;
for(k=i2;k<n;k++)
if(b[k]>min && b[k]<max)
break;
if(j==n && k==n)
return 1;
if(((j==n)^(k==n)) || a[j]!=b[k])
return 0;
return myfn(a,b,n,j+1,k+1,a[j],max) && myfn(a,b,n,j+1,k+1,min,a[j]);
}
int isSameBST(int a[],int b[],int n)
{
return myfn(a,b,n,0,0,INT_MIN,INT_MAX);
}
int main()
{
//int a[]={8,3,6,1,4,7,10,14,13},b[]={8,10,14,6,3,4,1,7,13};
int a[]={1},b[]={2};
int n=sizeof(a)/sizeof(a[0]);
printf("%s\n",isSameBST(a,b,n)?"BSTs are same":"BSTs not same");
return 0;
}
Leave the least significant digit. From 2nd digit onwards,find the first digit which is not 9.If no such digit,return error or -1
Let k be that digit..store all digits before that in an array
Increment kth digit by 1 and for all digits before kth digit,sort them and then, decrement the lowest nonzero digit and add after the incremented digit
111
kth digit is 2nd one
increment it to 2 and den decrement 1 at LSB
191
increment 1 at MSB to 2
sorting gives 1 9,decrement 1 to 0 and add after 2...its 209
check for other numbers 190-208
0999-1899 and so on
A very easy recursive solution without building the tree
#include<stdio.h>
#define max(x,y) x>y?x:y
int findlen(char a[],int *x)
{
if(a[*x]=='\0')
return 0;
(*x)++;
if(a[*x-1]=='L')
return 1;
int y=findlen(a,x),z=findlen(a,x);
return (1+(max(y,z)));
}
int main()
{
char a[]="PPPLLLPLL";
int x=0;
printf("depth of given tree=%d\n",findlen(a,&x));
return 0;
}
#include<stdio.h>
#define max(x,y) (x>y?x:y)
int findsum(int a[],int n)
{
if(n==0)
return (a[0]>0?a[0]:0);
int i,x,y,z,tem;
x=a[0]>0?a[0]:0;
y=a[1]>0?a[1]:0;
z=0;
for(i=2;i<n;i++)
{
tem=z;
z=x;
x=y;
y=(max(tem,z))+(max(a[i],0));
}
return max(x,y);
}
int main()
{
int a[]={-5,-6,-10,-40,50,-35};
int n=sizeof(a)/sizeof(a[0]);
printf("max sum=%d",findsum(a,n));
return 0;
}
1. store inorder traversal of binary tree in an array say A and sort it
2. now again make any traversal, and for each node search the node's value in the array. Let the position of the element be i. So add the elements from i+1 to end with the node's value
Time Complexity of this algorithm is o(nlogn) and space complexity is o(n)
however,if we had BST instead of binary tree,the time complexity can be modified to o(n) and space complexity to o(1)(ignoring recursion stack space)
We can do it in a single scan
1. find the kth node from start(with previous node) say x(Also keep track of previous node of kth node).If no of nodes<k,return.
2.let z=x,y=head
3.now in a loop make y=y->next and z=z->next until you reach the end from z. y then contains the kth node from end.(Also keep the previous node of this kth element from end,a little modification inside loop can help)
4.swap x and y by the previous nodes we kept in step 1 and 3
5.check if k==1 or k==n and change head if required
the algo i thought...i will call a fn with 2 arrays A and B with same length n say with min=INT_MIN and max=INT_MAX,index1=0,index2=0
1. now starting from index1 in A and index2 in B,find 1st element in both arrays greater than min and less than max.If no such element in both the arrays,return true...If such element is only in 1 array return false.let index of such element in array A is i1 and array B is i2. If both elements are not same return false
2. call the same fn twice
return
isSameBST(A,B,A[i1],max,i1+1,i2+1) &&
isSameBST(A,B,min,A[i1],i1+1,i2+1).
RepAmit, None
Repmendezleah216, Analyst at Bosch
Hello,everybody,I'm Leah Mendez.I want to make some friends here.I’m a woman with ambition and ...
RepNatalieLutz, Applications Developer at Absolute Softech Ltd
Pitch trending story topics and continually look for ways to push breaking and/or viral stories forward with new angles ...
Rephinescarol45, +27655765355 SSD MONEY CLEANING CHEMICAL +27655765355 BLACK MONEY IN JOHANNESBURG, OMAN, SAUDI ARABIA, SUDAN, Somalia ,Zimbabwe Botswana at 247quickbookshelp
I am Carol From San Diego USA, I am Working as a Personal assistant in a Castle Realty organization, I ...
@rapirapp-i think minheap will help in finding k largest,not maxheap
- Amit June 27, 2013