Crazy Tesla
BAN USER- 0of 0 votes
AnswersAn array of size N is given. Array is sub divided into sub array of size K. Find maximum value of each sub array.
- Crazy Tesla in India
My ans-
While traversing the array keep on adding values to max heap of size K and keeping a virtual window of size K on array.
When element leaves the window then remove the leaving element from heap too and reheapify the heap. And max element of that window will be again on top in heap.
Any better approach?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Arrays
bool check(int a){
int mask = 5;
if(a < 0) a*=-1; // if a is -ve
if(a < mask) return 0; // False
while((mask << 2) < a){
count++;
mask=mask << 2;
}
if (mask==a) return 1; // True
return check(a-mask);
}
#include <iostream>
using namespace std;
int main() {
int c1=0, c0=0;
char in;
while(1){
cin>>in;
if(in=='1') c1++;
else if(in=='0') c0++;
else break;
for(int i=c0; i>0; i--)
cout<<0;
for(int i=c1; i>0; i--)
cout<<1;
cout<<endl;
}
return 0;
}
Starting from tenth place move to left.
1. Replace the current position digit with the digit greater then this in right.
2. Arrange the all right digits in ascending order.
2 5 6 7 5 4 3 2 1 <- Initial
^
2 5 7 6 5 4 3 2 1 <- Step 1
^ ^ 6<->7
2 5 7 1 2 3 4 5 6 <- Step 2
^-----------^ ascending order sort
Correct me if m wrong.
- Crazy Tesla January 14, 2014.....1
..../.\
...2...3
../.\...\
.4...5...7
@Shashi what if in abaove tree we have left child of 3 too.
- Crazy Tesla January 24, 2013how?
- Crazy Tesla January 24, 2013but i understood other way that after designing tree should follow the given condition
- Crazy Tesla January 24, 2013@nitin can you please explain the question?
- Crazy Tesla January 24, 2013this will convert all tree nodes to 0 as sumUp will first calculate sum on leaf nodes. and Smash!!!!
So if amazon is asking this question you must check this condition too.
sum function should not be called for leaf nodes. Coz leaf node don't have any children.
int sumUp(struct node* root)
{
if(root == NULL) return 0;
if(root->left == NULL && root->right == NULL) return root;
root->data = sumUp(root->left) + sumUp(root->right);
return root->data;
}
/* last is a global/static variable*/
void inOrder(node *root){
if (root==NULL) return;
inOrder(root->left);
if(last!=NULL)last->next = root;
last = root;
inOrder(root->right);
}
algo:
1# find path to both of the nodes from root lets say pPath and qPath.
2# compare paths till the both start getting on different way. the previous node where the are departing will be least common ancestor.
Note: space complexity will be high but as i know time complexity will be maximum O(n+n+n) i.e. O(n)
comments and improvements are welcome.
is the given matrix is adjacency matrix? then why it is MxN ?
- Crazy Tesla January 23, 2013@Shashi can you please explain, what do you mean by vertical sum exactly.in below tree.
.....1
..../.\
...2...3
../.\...\
.4...5...7
ignore (.)s
Working Code ....
{
string fillString(string s, string w){
int m,i;
m=s.size()-1;
i = w.size()-1;
bool flag = false;
int start,cur;
while(m>-1){
if(s[m]==w[i] || s[m]=='?'){
start = flag ? start : m;
i--;
flag = true;
}
else{
m = flag ? start : m;
flag=false;
i = w.size()-1;
}
if(i==-1 && flag == true){
cur=m; i=0;
while(cur<=start){
s[cur++]=w[i++];
}
flag = false;
i = w.size()-1;
}
m--;
}
cur=s.size()-1;
while(cur>-1){
if(s[cur]=='?')s[cur]='A';
cur--;
}
return s;
}
}
i think the logic is same as of shashi. time complexity min O(n) max O(n*m)
For this recursion is the only soluton as K is variable
- Crazy Tesla January 23, 2013Yes. But check your answer no '2' is there in string.
- Crazy Tesla January 23, 2013as condition for balanced tree is difference between minimum and maximum height of tree should be 0 or 1
- Crazy Tesla January 22, 2013this problem can occur only when we move upward from given node.
So we have to make sure when we move upward we only have to trigger function to find (k-i)th node for either left child or right child not the both.
thanks for specifying this point.
yeah it works!
O(n)
thanks gautam
Kamy check your algo on.
6 5 4 3 1 2 3 4
K is 3
It is sliding window.
Let array be
1 2 3 4 5 6
k=2
Sub array 1 2. 2 3. 3 4. 4 5. 5 6.
We have to delete an element from array too. To insert new element.
Try your algo on
5 6 1 2 3 4 5 6 7 8 9
K is 3
How can i have maximum value of each k section?
- Crazy Tesla January 20, 2013It will not work as i know. Can u pls share algo.
- Crazy Tesla January 20, 2013This can be done in following way.
1# trace path from root to given node store that path in a linked list
or data structure where you can back trace it.
2# start from given node to find kth nodes in sub trees of given node.
3# start from given node. Back trace till kth node on root path. On each node occure in that path, find k-1, k-2, k-3...1th node respectively from current node on path.
This algo will work even if you don't have parent pointer. If parent pointer is given skip step 1# and back trace with parent pointer
@learner here we only need to check leaves. Not the whole tree, mirror image will consider whole tree.
- Crazy Tesla January 20, 2013Logic is not complete you have to reset pathList every time you get new maxValue. and print all paths when you have finished up traversing whole tree.
- Crazy Tesla January 20, 2013if height of leaf nodes is not considered then this question is very easy.
just add all leaf nodes to array of both trees and compare both array without reversing.
(bit change in DashDash algo)
there are 2 conditions
......2
...../.\
....1...2
......+
......3
...../.\
....1...2
......=
......2
...../.\
....1...2
.....\./
......3
these both can be merged
what of
......2
...../.\
....1...2
.../.\
..2...3
......+
......3
...../|\
....2.3.2
......=
.....?
can these be merged?
please don't say tree should be binary, as this is just for explanation
refer this
en.wikipedia.org/wiki/AKS_primality_test
awesome....
- Crazy Tesla January 19, 2013this solution is wrong, as i know pushing means order of non zero numbers should be maintained.
my solution is here
int sort(int *a,int size){
int z,p;
z=size-1;
while(a[z]&&z>0)z--;
if(z==0){
// no zero
return 0;
}
p=z;
while(p>-1){
if(a[p]){
a[z--]=a[p];
a[p]=0;
}
p--;
}
return 1;
}
working code with time complexity o(n);
#include <iostream>
using namespace std;
class list{
public:
int value;
list* next;
list* end;
list(int v){
value = v;
next = NULL;
end = this;
}
bool insert(int v){
if(end->next!=NULL){
list* t = new list(v);
t->next = this->next;
this->next = t;
return true;
}
list* nlist = new list(v);
end->next = nlist;
end = nlist;
return true;
}
void print(){
cout<<endl;
list* c = this;
while(c){
cout<<c->value<<" ";
c=c->next;
}
}
};
list* array2LL(int *a,int size){
if(size==0) return NULL;
list* start = new list(a[0]);
for(int i=1;i<size;i++){
start->insert(a[i]);
}
return start;
}
int main () {
int a[]={5,6,5,6,7,8,9,10};
list* start = array2LL(a,8);
start->print();
list *i,*j;
j=start;
while(j->next){
if(j->value > j->next->value){
break;
}
j=j->next;
}
list *p = new list(0);
list *pdmp;
pdmp = p;
i = new list(0);
i->next = start;
start = i;
p->next = j->next;
j->next = NULL;
list *cstart, *cend;
while(i->next!=NULL&&p->next!=NULL){
if(i->next->value >= p->next->value){
cstart = p->next;
while(i->next!=NULL&&p->next!=NULL){
if(i->next->value < p->next->value){
cend = p;
break;
}
p = p->next;
}
if(!p->next){
j = i->next;
i->next = cstart;
p->next = j;
start->next->print();
return 0;
}
pdmp->next = p->next;
p=pdmp;
j = i->next;
i->next = cstart;
cend->next = j;
}
i=i->next;
}//*/
if(!i->next){
i->next = p->next;
}
start->next->print();
return 0;
}
Check this complexity will be k
int main(){
int a[]={0,3,7};
int b[]={0,5,10};
int aSize = 3,bSize = 3;
int x=0,y=0,i=0,j=0,k=9; // suppose k=9
while(x!=aSize && y!=bSize && k>0){
i=x+1;j=y+1;
cout<<a[x]<<","<<b[y]<<endl;
k++;
while(i!=aSize && j!=bSize && k>0){
if(a[x]+b[j]<b[y]+a[i]){
cout<<a[x]<<","<<b[j]<<endl;
j++;
}
else{
cout<<b[y]<<","<<a[i]<<endl;
i++;
}
k--;
}
while(i!=aSize&&k>0){
cout<<b[y]<<","<<a[i]<<endl;
i++;
k--;
}
while(j!=bSize&&k>0){
cout<<a[x]<<","<<b[j]<<endl;
j++;
k--;
}
x++;
y++;
}
return 0;
}
what about input [ 2 3 4 5 6 7 10 10 9 8 7]
- Crazy Tesla October 03, 2016