arwin
BAN USER- 0of 0 votes
Answerssort a linked list in O(n)....
- arwin| Report Duplicate | Flag | PURGE
Microsoft
No my question is what is the complexity of deleting one element from the heap? we may have to delete intermediate nodes in the heap when we dont know the exact position of that node in the heap. So should not it take O(n) time to find it first and then to delete it will take O(log n) time?
- arwin November 25, 2012I am not getting one thing.. in heap solution, when we have to delete elements from j to j', how can we make sure that it takes O(log n) time? because we may have to delete any node of the heap and the search of the node a[j] to a[j'] can be worst case O(n) time and then deletion will take O(log n) time after finding that element.
- arwin November 24, 2012I am assuming that list's head is pointing the start of queue (so the front) and tail is pointing the end of queue (so the rear as first in first out). So if the list is circular, then if we have a pointer that points to the head, then for enqueue operation, we have to traverse to the end of the list and then can add a new element (I am assuming list in single linked list). But if we have a pointer at tail, then for enqueue we can do that O(1) by newnode->next=tail->next->next; tail->next=newnode; tail=newnode;
For dequeue, We can do that in O(1) too, newnode=tail->next; tail->next=tail->nex->next; return newnode;
So answer should be rear.
approach 1: naive: check every character of string 1 with every other character of string 2, O(n2)
approach 2: sort both strings and check similarity, O(nlog n)
approach 3: take a hash table and hash all characters of string1 and check whether all characters of string 2 matches O(n) time O(n) space
approach 4: take a 256 size character array where all elements are initially 0 and then every ith element takes count of that character occurance in string 1. Then for every occurance of that character in string 2, decrease that count by 1. Finally check whether all elements has count==0
O(n) tima, O(1) space
My solution is: if we use a bottom up approach to store the results from right bottom corner of the array and we store the results in additional 2d array M and original array was A,
Then for every A[i][j],
if A[i][j]=="W", that implies cannt go through it, so M[i][j]=0;
if A[i][j]=="L",
then we have to check 3 cases:
a) if its adjacent right cell A[i][j+1] is "W", then no land cannt be extended via right point, So M[i][j]=M[i+1][j]+1;
b) if its adjacent down cell A[i+1][j] is "W", then no land cannt be extended via its bottom point, So M[i][j]=M[i][j+1]+1;
c) if both A[i+1][j] && A[i][j+1] is Land, that means M[i][j] will be sum of both. But land starting from A[i][j+1] and spreading right and below as much as possible and land starting from A[i+1][j] and spreading has a common intersection which is considered twice which starts at point A[i+1][j+1].. So have to delete this intersection once :
So in this case ,
M[i][j]=M[i][j+1] + M[i][j+1] +1 -M[i+1][j+1].
My observation:
correct position of i if i belongs to 1st half of the array will be j=2*i, or if i belongs to 2nd half then it will be j=2*i-len+1
if length is not power of 2:
say
12345abcde
start from i=1;
then try to place s[i] to its correct poition j which is 2;
then take s[j] and try to place it in proper place which is 4. So new j is 4.
next j=8.
and go on like this..
Now if lenth is not power of 2, then in one round it gets over..
But if its power of 2,
eg:
1234abcd
0->0
1->2
2->4
4->1
5->3
6->5
7->7
so starts with i=1;
1->2
2->4
4->1
one cycle ended.. new cycle starts from 3...
so for length len where len=power of 2...
one cycle starts from 1
next cycle from 3
next from 5
then 7
........until its <len/2
code is
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int ispowerof2(int len){
if(len==1)
return 1;
if(len%2==1)
return 0;
return ispowerof2(len/2);
}
char *change(char *str){
int i=1,j,k;
int flag=0;
char t,t1;
int len=strlen(str);
if(ispowerof2(len))
flag=1;
if(flag==0){
t=str[1];
while(1){
if(i<len/2)
j=2*i;
else
j=2*i-len+1;
if(str[j]==t)
return str;
t1=str[j];
str[j]=t;
t=t1;
i=j;
}
}
else{
k=1;
i=1;
t=str[1];
while(k<len/2){
if(i<len/2)
j=2*i;
else
j=2*i-len+1;
if(str[j]==t){
k+=2;
t=str[k];
i=k;
//continue;
}
else{
t1=str[j];
str[j]=t;
t=t1;
i=j;
}
}
return str;
}
}
main(){
char *s;
s=malloc(100*sizeof(char));
strcpy(s,"123456789abcdefghi");
s=change(s);
printf("%s",s);
}
Here is tha algo:
2 strings are say A and B..take two pointer, pointer1 for A,pointer2 for B.
For getting all possible interleavings, we gave two choices,
either take char pointed by pointer1 and advance pointer1
or, take char pointed by pointer2 and advance pointer2.
We can not advance the pointers further if the corresponding string's end is reached...
So here is my code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void interleaving(char *a,char *b,int s1,int s2,int e1,int e2,char *c,int index){
if(s1<=e1&&s2<=e2){
c[index]=a[s1];
interleaving(a,b,s1+1,s2,e1,e2,c,index+1);
c[index]=b[s2];
interleaving(a,b,s1,s2+1,e1,e2,c,index+1);
}
else if(s1<=e1){
c[index]=a[s1];
interleaving(a,b,s1+1,s2,e1,e2,c,index+1);
}
else if(s2<=e2){
c[index]=b[s2];
interleaving(a,b,s1,s2+1,e1,e2,c,index+1);
}
else{
int i;
for(i=0;i<index;i++){
printf("%c",c[i]);
}
printf("\n");
}
}
main(){
char a[10],b[10],c[20];
gets(a);
gets(b);
int start1=0,start2=0,end1,end2;
end1=strlen(a)-1;
end2=strlen(b)-1;
interleaving(a,b,start1,start2,end1,end2,c,0);
}
counting sort takes extra space....here one O(1) solution
1+2+..+n=n*(n+1)/2;
here one number is missing and 1 is duplicated.
So say, sum=total sum of array elements
and
mul=multiplication of array elements.
now,
if a=missing no and b=duplicated no,
| sum-n*(n+1)/2 | = |a-b|
and
mul/(n!) = b/a;
from this two equation, we can solve a and b..
Repnetteyoder22, Applications Developer at 247quickbookshelp
Nette, transportation inspector inspects goods and equipment associated with transporting people or cargo to ensure safety. I typically work for ...
RepBriannaWright, Analyst at A9
I am a skilled project manager with years of exemplary service in diverse IT roles. I am passionate about utilizing ...
If I understand correctly, you are swapping every element a with the element b in left holding a's actual position. But I guess just swapping will not work.you have to insert it in its proper position by shifting all elements from b to a.
- arwin September 02, 2013try this example
9 9 8 7 5 4 3 2
0 0 0 3 0 5 1 7