Nitin
BAN USER
- 0of 2 votes
AnswersGiven a circular linked list with each node either r,g,y or b. number of nodes of each color are same. Arrange the nodes in a specified order. Eg. if list is like "rrrgggyyybbb" and order is "rgyb" then after rearrangement it should be "rgybrgybrgybrgyb". Just a bit more explanation...the question was given in form of students stading in a circular fashion and color denotes the club they are in. Hence adding new node or list is not possible.
- Nitin in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm
push the open parenthesis and the operators and check the top element on seeing a closing parenthesis. If it is open one we have duplicate.
int check(char s[])
{
int i=0;
char ch;
while(s[i]!='\0')
{
if(s[i]=='(' || s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/')
push(s[i]);
else if(s[i]==')')
{
ch=pop();
if(ch=='(')
return 1;
while((ch=pop())!='(')
;
}
i++;
}
return 0;
}
Its simple to finding kth element in the merged array in logarithmic time.
take pivot in two arrays such that sum of pivot 1 + pivot 2 =n.
compare the pivot elements and search the correcponding array half if not equal
int getk(int a[],int l1,int m,int b[],int l2,int n,int k)
{
if(m<=0 || k<=0 || k<=0 || k>(m+n))
return -1;
int i = m * (k-1) / (m+n);
int j = k-i-1;
int ai_1 = (i==0)?-100:a[l1 + i-1];
int bj_1 = (j==0)?-100:b[l2 + j-1];
int ai = (i==m)?100:a[l1 + i];
int bj = (j==n)?100:b[l2 + j];
if(bj_1<=ai && ai<=bj)
return ai;
if(ai_1<=bj && bj<=ai)
return bj;
if(ai<bj)
return getk(a,l1+i+1,m-i-1,b,l2,j,k-i-1);
return getk(a,l1,i,b,l2+j+1,n-j-1,k-j-1);
}
int getmed(int a[],int m,int b[],int n)
{
if((m+n)%2!=0)
return getk(a,0,m,b,0,n,(m+n)/2+1);
return (getk(a,0,m,b,0,n,(m+n)/2) + getk(a,0,m,b,0,n,(m+n)/2+1))/2;
}
You will need to have a stack and a completed array. completed array denotes if you have seen both the children of the tree.
Now push a node in the stack and increment its children count. when the completed count is 2 you can pop out the node.
The code can be written as:
void printpath()
{
int i=0;
for(i=0;i<in;i++)
printf("%d\t",stack[i]->val);
printf("\n");
}
void allpaths(struct tnode *root)
{
int done=0;
int completed[100];
int i=0;
for(i=0;i<100;i++)
completed[i]=0;
struct tnode *cur = root;
while(done!=1)
{
if(cur!=NULL)
{
push(cur);
completed[cur->val]++;
cur = cur->left;
}
else
{
cur = front();
while(cur != NULL && completed[cur->val]==2)
{
if(cur->left==NULL && cur->right==NULL)
printpath();
pop();
cur = front();
}
if(cur!=NULL)
{
completed[cur->val]++;
cur = cur->right;
}
else
done =1 ;
}
}
}
void paths(struct tnode *root,int num)
{
int done=0;
int complete[100];
int i=0;
for(i=0;i<100;i++)
complete[i]=0;
struct tnode *cur = root;
while(done != 1)
{
if(cur!=NULL)
{
push(cur);
if(cur->val==num)
break;
complete[cur->val]++;
cur = cur->left;
}
else
{
cur = front();
while(cur != NULL && complete[cur->val]==2)
{
pop();
cur = front();
}
if(cur != NULL)
{
complete[cur->val]++;
cur = cur->right;
}
else
done = 1;
}
}
if(done==0)
printpath();
}
where we have to find path from root to num.
- Nitin May 03, 2014In case of complete bst we can utilize the property of having n depth and 2^n-1 elements as :
int getnode(struct tnode *root,int n,int k)
{
if(root==NULL)
return -1;
if(n/2 +1 == k)
return root->val;
if(n/2 + 1 > k)
return getnode(root->left,n/2,k);
return getnode(root->right,n/2,k-n/2-1);
}
n here is total nodes in tree
- Nitin May 01, 2014int isvalid(int a[],int ind,int data)
{
int i=ind-1;
while(i>=0 && a[i]!=data)
i--;
if(i<0 || ind-i-1==data)
return 1;
return 0;
}
void getarray(int a[],int ind,int n,int val[])
{
if(ind==2*n)
{
int i=0;
for(i=1;i<=n;i++)
{
if(val[i]==0)
return;
}
for(i=0;i<2*n;i++)
printf("%d\t",a[i]);
printf("\n");
return;
}
int i=0;
for(i=1;i<=n;i++)
{
if(isvalid(a,ind,i))
{
a[ind]=i;
val[i]++;
getarray(a,ind+1,n,val);
val[i]--;
}
}
}
struct tnode *addnode(int num)
{
struct tnode * root = (struct tnode *) malloc(sizeof(struct tnode));
root->val=num;
root->left = NULL;
root->right=NULL;
return root;
}
struct tnode * create(int a[],int n)
{
int i=0;
while(a[i]!=-1)
i++;
struct tnode * root = addnode(i);
push(root);
struct tnode * temp = pop();
while(temp!=NULL)
{
for(i=0;i<n;i++)
{
if(a[i]==temp->val)
{
if(temp->left==NULL)
{
temp->left = addnode(i);
push(temp->left);
}
else
{
temp->right = addnode(i);
push(temp->right);
}
}
}
temp=pop();
}
return root;
}
void getbfs(struct tnode *root)
{
int a[100][100],ind=0,in=0;
struct tnode *dummy = addnode(-1);
push(root);
push(dummy);
struct tnode *temp = pop();
while(temp!=NULL)
{
while(temp!=dummy)
{
a[ind][in++]=temp->val;
if(temp->left!=NULL)
push(temp->left);
if(temp->right!=NULL)
push(temp->right);
temp=pop();
}
if(temp==dummy)
{
a[ind][in]=-1;
ind++;
in=0;
}
temp=pop();
if(temp!=NULL)
push(dummy);
}
while(ind-->0)
{
in=0;
while(a[ind][in]!=-1)
{
printf("%d\t",a[ind][in]);
in++;
}
printf("\n");
}
}
void divide(int num,int denom)
{
if(denom==0)
return;
int mask=1;
int q=0;
while(denom <= num)
{
denom = denom<<1;
mask = mask<<1;
}
while(mask > 1)
{
mask = mask>>1;
denom = denom>>1;
if(num > denom)
{
num = num - denom;
q = q|mask;
}
}
printf("Quotient is %d and remainder is %d\n",q,num);
}
void longest(int a[][M])
{
int i=0,j=0;
int max=0,row=-1,col=-1,count=0;
for(j=0;j<M;j++)
{
count=0;
for(i=0;i<N;i++)
{
if(a[i][j]==1)
count++;
else
{
if(count>max)
{
max = count;
row = j;
}
count =0;
}
}
if(count>max)
{
max = count;
row = j;
}
}
for(i=0;i<N;i++)
{
count=0;
for(j=0;j<M;j++)
{
if(a[i][j]==1)
count++;
else
{
if(count>max)
{
max = count;
col = i;
}
count =0;
}
}
if(count>max)
{
max = count;
col = i;
}
}
if(col==-1)
{
printf("Row is %d and sequence count is %d\n",row,max);
count=0;
for(i=0;i<N;i++)
{
if(a[i][row]==1)
count++;
else
count =0;
if(count==max)
col=i;
}
printf("Sequence is from [%d,%d] to [%d,%d]\n",col-max+1,row,col,row);
}
else
{
printf("Column is %d and sequence count is %d\n",col,max);
count=0;
for(i=0;i<M;i++)
{
if(a[col][i]==1)
count++;
else
count =0;
if(count==max)
row=i;
}
printf("Sequence is from [%d,%d] to [%d,%d]\n",col,row-max+1,col,row);
}
}
int bfs(int graph[][V],int src,int dest,int parent[])
{
int visited[V];
int i=0;
for(i=0;i<V;i++)
visited[i]=0;
push(src);
parent[src]=-1;
visited[src]=1;
int temp = pop();
while(temp!=-1)
{
for(i=0;i<V;i++)
{
if(visited[i]==0 && graph[temp][i]>0)
{
visited[i]=1;
push(i);
parent[i]=temp;
}
}
temp=pop();
}
return visited[dest];
}
void dfs(int graph[][V],int src,int visited[])
{
visited[src]=1;
int i=0;
for(i=0;i<V;i++)
{
if(visited[i]==0 && graph[src][i]>0)
dfs(graph,i,visited);
}
}
int getmin(int graph[][V],int src,int dest)
{
int res[V][V];
int i=0,j=0;
for(j=0;j<V;j++)
{
for(i=0;i<V;i++)
res[i][j] = graph[i][j];
}
int parent[V];
int flow=1000;
int mincap=0;
while(bfs(res,src,dest,parent))
{
flow = 1000;
int v = dest;
while(v!=src)
{
int u = parent[v];
if(flow>res[u][v])
flow = res[u][v];
v=u;
}
v = dest;
while(v!=src)
{
int u = parent[v];
res[u][v] = res[u][v]-flow;
res[v][u] = res[v][u]+flow;
v = u;
}
mincap = mincap + flow;
}
int visited[V];
for(i=0;i<V;i++)
visited[i]=0;
dfs(res,src,visited);
for(i=0;i<V;i++)
{
for(j=0;j<V;j++)
{
if(visited[i]==1 && visited[j]==0 && graph[i][j]>0)
printf("%d---->%d\t",i,j);
}
}
printf("\n");
return mincap;
}
void getmax(struct ele a[])
{
int i=0,j=0;
struct temp b[2*N];
for(i=0;i<N;i++)
{
b[j].time = a[i].start;
b[j++].c = 's';
b[j].time = a[i].end;
b[j++].c = 'e';
}
sort(b,0,2*N-1);
int count=0,start=0,max=0;
for(i=0;i<2*N;i++)
{
if(b[i].c == 's')
count++;
if(b[i].c == 'e')
count--;
if(max<count)
{
max = count;
start = b[i].time;
}
}
int begin=100,end=0;
for(i=0;i<N;i++)
{
if(start>a[i].start && start <a[i].end)
{
if(a[i].start<begin)
{
begin = a[i].start;
end = a[i].end;
}
}
}
printf("Max overlapping interval is (%d,%d) and max overlap is %d\n",begin,end,max);
}
void swaps(int a[],int b[],int n)
{
int i=1;
int hash[100];
for(i=1;i<=n;i++)
hash[a[i]]=i;
for(i=1;i<=n;i++)
printf("%d--->%d\n",i,hash[i]);
int count=0;
i=1;
while(i<=n)
{
if(b[i]==a[i])
i++;
else
{
int temp = hash[b[i]];
b[i]=b[i]^b[temp];
b[temp]=b[i]^b[temp];
b[i]=b[i]^b[temp];
count++;
}
}
printf("Count is %d\n",count);
}
I think what we need here is all possible subsets which sum to a particular value say s.
In case of all positive values we can sort and ignore values >s and get subsets of remaining values which sum to s.
In case of both negative and positive values we need to go for subsets of whole array and sorting would be irrelevant in this case.
Same code ... just marking visited flag to avoid repeated usage of that.
int check(char a[][N],int i,int j,char s[],int ind,int n)
{
if(ind==n)
return 1;
if(i<0 || j<0 || i>=M || j>=N || a[i][j] != s[ind] || a[i][j]=='-')
return 0;
a[i][j]='-';
return check(a,i+1,j,s,ind+1,n) || check(a,i-1,j,s,ind+1,n) || check(a,i,j+1,s,ind+1,n) || check(a,i,j-1,s,ind+1,n);
a[i][j]=s[ind];
}
One solution can be we get the span of ith day by checking if any j<i exists such that a[j]<a[i].
If so, in that case span[i]=span[j]+1 else it will be 0.
void getspan(int a[],int n)
{
int span[100];
int i=0,j;
span[0]=0;
for(i=1;i<n;i++)
{
j=i-1;
while(j>=0 && a[j]>=a[i])
j--;
if(j==-1)
span[i]=0;
else
span[i]=span[j]+1;
}
for(i=0;i<n;i++)
printf("%d\t",span[i]);
printf("\n");
}
void findlongest(struct tnode *root,int a[],int ind,int level,int *max,int path[])
{
if(root==NULL)
{
if(level>*max)
{
int i=0;
for(i=0;i<ind;i++)
path[i]=a[i];
*max=level;
}
return;
}
a[ind]=root->val;
findlongest(root->left,a,ind+1,level+1,max,path);
findlongest(root->right,a,ind+1,level+1,max,path);
}
int main()
{
int i,num;
struct tnode *root=NULL;
for(i=0;i<N;i++)
{
scanf("%d",&num);
root=addnode(root,num);
}
int a[100],leftpath[100],rightpath[100];
num=0;
findlongest(root->left,a,0,0,&num,leftpath);
while(num>0)
printf("%d\t",leftpath[--num]);
printf("%d\t",root->val);
num=0;
findlongest(root->right,a,0,0,&num,rightpath);
for(i=0;i<num;i++)
printf("%d\t",rightpath[i]);
printf("\n");
getch();
return 0;
}
int mina1[100];
int n1;
int mina2[100];
int n2;
void getsub(int a[],int n,int a1[],int ind1,int a2[],int ind2,int sum1,int sum2,int *min)
{
if(n==0)
{
if(sum1>sum2)
{
if(sum1-sum2<*min)
{
*min=sum1-sum2;
int i=0;
for(i=0;i<ind1;i++)
mina1[i]=a1[i];
n1=ind1;
for(i=0;i<ind2;i++)
mina2[i]=a2[i];
n2=ind2;
}
}
else
{
if(sum2-sum1<*min)
{
*min=sum2-sum1;
int i=0;
for(i=0;i<ind1;i++)
mina1[i]=a1[i];
n1=ind1;
for(i=0;i<ind2;i++)
mina2[i]=a2[i];
n2=ind2;
}
}
return;
}
a1[ind1]=a[n-1];
getsub(a,n-1,a1,ind1+1,a2,ind2,sum1+a[n-1],sum2,min);
a2[ind2]=a[n-1];
getsub(a,n-1,a1,ind1,a2,ind2+1,sum1,sum2+a[n-1],min);
}
void getmin(int a[],int n,int num)
{
int i=0;
int b[100];
push_back(0);
for(i=1;i<n;i++)
{
while(front()!=-100 && front() <= i-num)
pop_front();
while(front()!=-100 && a[back()]>a[i])
pop_back();
push_back(i);
if(i>=num-1)
b[i-num+1]=a[front()];
}
for(i=0;i<n-num+1;i++)
printf("%d\t",b[i]);
printf("\n");
}
void formatsize(int size)
{
int dig=0;
int pow=1;
int num=size;
while(num>0)
{
num=num/10;
dig++;
pow=pow*10;
}
num=size%pow;
size=num;
dig=0;
pow=1;
while(num>0)
{
num=num/10;
dig++;
pow=pow*10;
}
num=size;
if(dig<=3)
{
printf("%dB\n",num);
return;
}
pow=pow/100;
if(pow<=1000)
pow=1000;
else if (pow<=1000000)
pow=1000000;
double n=(double)size/pow;
if(pow==1000)
printf("%.1fK\n",n);
else if(pow==1000000)
printf("%.1fM\n",n);
}
struct tnode *rightmost(struct tnode *root)
{
while(root->right!=NULL)
root = root->right;
return root;
}
struct tnode *getpre(struct tnode *root,struct tnode *node,struct tnode *prev)
{
if(root==NULL)
return NULL;
if(root==node)
{
if(root->left!=NULL)
return rightmost(root->left);
return prev;
}
struct tnode *temp=getpre(root->left,node,prev);
if(temp==NULL)
return getpre(root->right,node,root);
return temp;
}
void findbelow(struct tnode *root,int level,int k)
{
if(root==NULL)
return;
if(level==k)
{
printf("%d\t",root->val);
return;
}
findbelow(root->left,level+1,k);
findbelow(root->right,level+1,k);
}
void findabove(struct tnode *root,struct tnode *node,int level,int k)
{
static int vector=0;
if(root==NULL)
return;
findabove(root->left,node,level+1,k);
findabove(root->right,node,level+1,k);
if(root==node)
vector = vector | 1<<level;
if(vector & 1<<(level+k))
{
vector = vector ^ 1<<(level+k);
printf("%d\t",root->val);
}
}
Solution only for + and * operator
void evaluate(char s[])
{
int i=0;
int dig=1;
int num=0;
char c;
while(s[i]!='\0')
{
if(s[i]<='9' && s[i]>='0')
{
num = num*dig + s[i]-'0';
dig=dig*10;
}
else if(s[i]=='+' || s[i]=='*')
{
if(num!=0)
{
vpush(num);
num=0;
dig=1;
}
if(s[i]=='+')
{
c=opop();
if(c=='*')
{
int num1=vpop();
int num2=vpop();
vpush(num1*num2);
}
}
opush(s[i]);
}
i++;
}
if(num!=0)
{
vpush(num);
num=0;
dig=1;
}
while(oind>0)
{
c=opop();
int num1=vpop();
int num2=vpop();
if(c=='+')
vpush(num1+num2);
else
vpush(num1*num2);
}
printf("Answer is %d\n",vpop());
}
For subset code can be
void printarray(int a[],int start,int end)
{
int i=0;
for(i=start;i<=end;i++)
printf("%d\t",a[i]);
printf("\n");
}
int power(int a,int n)
{
while(--n>0)
a=a*2;
return a;
}
void getsubset(int a[],int n)
{
int i=0,j=0;
int set[100];
int ind=0;
int count = power(2,n);
int sum=0;
for(i=0;i<count;i++)
{
sum=0;
ind=0;
for(j=0;j<n;j++)
{
if(i&(1<<j))
{
sum = sum + a[j];
set[ind++]=a[j];
}
}
if(sum==0)
printarray(set,0,ind-1);
}
}
As per example given..the code can be
void printarray(int a[],int start,int end)
{
int i=0;
for(i=start;i<=end;i++)
printf("%d\t",a[i]);
printf("\n");
}
void getsub(int a[],int n)
{
int i=0,j=0;
int b[100];
b[0]=a[0];
for(i=1;i<n;i++)
b[i]=b[i-1]+a[i];
for(i=0;i<n;i++)
{
if(b[i]==0)
{
printarray(a,0,i);
continue;
}
for(j=0;j<i;j++)
{
if(b[j]==b[i])
printarray(a,j+1,i);
}
}
}
char toupper(char c)
{
if(c>='a' && c<='z')
return c-32;
return c;
}
void out(char s[])
{
int i=0,count=0;
while(s[i]!='\0')
{
if(count==0)
{
printf("%c",toupper(s[i]));
count++;
}
else
{
if(toupper(s[i])==toupper(s[i-1]))
count++;
else
{
printf("%d",count);
count=0;
i--;
}
}
i++;
}
printf("%d\n",count);
}
You can use binary search and insertion for each element generated. The O(log n) will enable you for minimum memory utilization assuming only half array will be in memory for each computation. We can publish the array to the disk. Keeping the array in sorted order can help in generating a stream for the same and printing while fetching from any disk storage.
- Nitin November 24, 2016