Ashish
BAN USER- 0of 0 votes
AnswersYou are given two sorted arrays of size n and n+m respectively. Merge these two sorted arrays without using a third array and the resultant array must be sorted ?
- Ashish in United States
For eg.
arr1 (size 3): {1, 4, 6}
arr2 (size 8): {2, 3, 5, 7, 8, null, null, null}
Result must be in arr2 as :
arr2 (size 8): {1, 2, 3, 4, 5, 6, 7}| Report Duplicate | Flag | PURGE
- 1of 1 vote
AnswersGiven a binary tree, find a binary search tree which is a subtree of the given binary tree and has the largest size?
- Ashish in India
Note : Here size means the no. of nodes and the binary tree can have more than one B.S.T. as its subtree.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersGiven two linked lists combine them in a way such that the resultant must contain the elements alternatively from one list and the other list?
- Ashish in India
For ex.
LL1 : 1->2->3->4
LL2 : 5->6->7
Result : 1->5->2->6->3->7->4
Also provide test cases for the algorithm ?| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Linked Lists
Yes, it will always be true that "fast" and "head" points move the same distance before reaching the intersection node. You can do a dry run by taking an example which will clear your doubt.
Also I did a mistake in the above code which I have rectified :
this
head = fast = slow;
should be
head = fast = slow = LL;
Node* findLoopNode(Node* LL){
if(!LL) return NULL;
else if(LL->next == LL) return LL;
//the linked list contains only one node which points back to itself
else{
Node* fast, *slow, *head;
head = fast = slow = LL;
do{
if(!fast->next && !fast->next->next)
fast = fast->next->next;
else return NULL;// there is no loop
slow = slow->next;
}while(fast!=slow);
//there is a loop and the below snippet finds the node pointed back
while(fast != head){
fast = fast->next;
head = head->next;
}
return head;//the required node
}
}
Node* kSmallest(Node* curr, int k, int *count){
if(!curr) return NULL;
else{
Node* left, right;
left = kSmallest(curr->left, k, count);
if(left) return left;
*count++;
if(*count==k) return curr;
right = kSmallest(curr->right, k, count);
if(right) return right;
return NULL;
}
}
@aka : I think he's traversing both the list in a while loop till the end and adding the numbers simultaneously.
i.e.
Linkedlist 1 = 5 -->4-->2-->9
LinkedList 2 =7-->3-->1-->1
Result = 12-->7-->3-->10
Here's the pseudo code :
1. Create three pointers p,q, result and point it to the head of the given linked lists.
2. if p, q are both not null then add p->data and q->data and store it in result and set p = p->next and q=q->next.
else if p is not null then store p->data in result and set p = p->next.
else if q is not null then store q->data in result and q = q->next.
else if both pointers are null goto step 4.
3. Goto step 2.
4. return result.
The tree is numbered as 1...N so the tree that you have taken as an example will actually be :
--------1
------2---3
----4----5--6
where 2 doesn't have a right child so you're formula will not work here.
To apply your concept you need to change the numbers of each node but then you won't be able to find the right index of that node in the matrix.
Another solution will be to keep another value associated with each node but will cost you Θ(N) space complexity.
Node* inorder(Node* curr, bool isRight=false, Node* par=NULL){
if(!curr) return NULL;
else{
inorder(curr->left, false, curr);
//inorderPred is the recent inorder predecessor viz. the rightmost child
Node* inorderPred = inorder(curr->right, true, curr);
//if the current node a left child
if(!isRight){
//if there is no right child then simply point to parent node
if(!curr->right) curr->right = par;
//if there is a right child and current node is a left child
//then inorder predecessor must point to its parent
else if (inorderPred) inorderPred->right = par;
return curr;
}
//if the node is a right child
else{
//return the rightmost node as the current inorder predecessor
if(!inorderPred) return curr;
else return inorderPred;
}
}
}
int calcExp(String str){
Stack st = new Stack();
int t1, t2, k;
for(int i=0; i < st.length(); i++){
if(str[i]=='+')
st.push('+');
else if(str[i]=='*'){
i++;
k=0;
while(str[i]!='+' && str[i]!='*')
k = str[i++]+ k*10;
st.push(st.pop()* k);
}
else{
k=0;
while(str[i]!='+' && str[i]!='*')
k = str[i++]+ k*10;
st.push(k);
}
}
while(true){
t1 = st.pop();
st.pop();
t2 = st.pop();
t1 = t1+t2;
if(st.empty()) return t1;
else st.push(t1);
}
}
//GREATER THAN FUNCTION
bool greaterThan(int N1, int N2){
if (MINUS(N1, N2)> 0) return true;
else return false;
}
//EQUALITY FUNCTION
bool equality(int N1, int N2){
if (MINUS(N1, N2)==0) return true;
else return false;
}
//INEQUALITY FUNCTION
bool inequality(int N1, int N2){
return !(equality(N1, N2));
}
//DIVIDE FUNCTION
int divide(int N1, int N2){
int res = 0, temp = N1;
while(temp>= N2){
N2 -= N1;
res++;
}
return res;
}
@debnath Let's say there are 3 nodes then the second node from initial state will be the middle one which the above code will return and in case #nodes are even for eg. 4 then the middle element can be 2 or 3 and the code will return 3th node which is indeed correct.
- Ashish May 18, 2013Assuming that by mid element you mean a node which is equidistant from the initial node whether you see from right or left i.e.
-1->2->3->4->1-
here 3 is middle as it is equidistant from head, which points to 1, from left and right.
Algorithm :
1. Take two pointers and point them to the initial node (head).
2. Move one pointer (turtle) by one step, another pointer(rabbit) by two step.
3. if rabbit == head OR rabbit->next == head then return turtle as the mid element.
Code :
Node* findMid(Node* head){
if(!head || !head->next) return head;
else{
Node* turtle,*rabbit;
turtle=rabbit=head;
while(rabbit!=head || rabbit->next!=head){
rabbit = rabbit->next->next;
turtle = turtle->next;
}
return turtle;
}
}
int[] add(int arr[], int val){
int carry = 0;
for(int i=arr.lenght() -1; i>=0; i--){
arr[i] = val%10 + arr[i] + carry;
val /= 10;
if(arr[i]> 9){
carry = 1;
arr[i] %= 10;
}
else carry = 0;
}
if(carry!=0){
int[] temp = new int[arr.length()+1];
for(int i=temp.lenght()-1; i>0; i--)
temp[i] = arr[i-1];
temp[i] = carry;
delete(arr);
return temp;
}
return arr;
}
Here is the code for Prasanna's algorithm
Node* par_array[100];/*array stores the parents of the node in the call stack which takes up log N space complexity, for simplicity here I am not using dynamic array*/
Node* pred(Node* curr, int item, int level=0){
if(curr==NULL) return NULL;
else{
if(curr->data == item){
if(curr->right!=NULL) return curr->right;
else if(curr->left!=NULL) return curr->left;
else if(!par_array.isEmpty()){
Node* par;
while(level>=0){
par = par_array[level-1];
if(par->left!=NULL) return par->left;
}
if(level < 0) return NULL;
}
else return NULL;
}
return pred(curr->left, item, level+1);
return pred(curr->right, item, level+1);
}
}
When I was being interviewed by microsoft, the guy told me to give a 4 line recursive solution to above question, this was my solution.
Node* alternate(Node* p,Node* q){
if (p== NULL) return q;
else if(q==NULL) return p;
else{
Node* temp = alternate(q,p.next) ;
return temp;
}
}
I don't understand if the question is worded correctly or not, the question says to find "any" smallest positive integer that can not be formed from the sum of numbers from array.
- Ashish December 08, 2014Now let's twist the question a little bit, what is the smallest positive integer ? 0. Is there an array containing only positive integers which can have a sum less than 0 ? No because it needs to have negative numbers then.
So shouldn't the answer always be zero.