rkt
BAN USER- 0of 0 votes
AnswersN x N matrix where rows are sorted but columns are not. How will you search for an element ?
- rkt in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
Algo :
1) Push root into Stack
2) Now iterate steps 3,4,5 with condition - while(stack is not empty)
3) Pop a node, print it
4) if node->right is not NULL, push it
5) if node->left is not NULL, push it
Full working code here :
awesomecoder.blogspot.com/2012/08/preorder-traversal-of-bst-iteratively.html
#include<stdio.h>
int main(){
int a[] = {1,1,1,2,2,2,2,2,2,3,3,3};
int i=0,j=0,n,k;
int len = sizeof(a)/sizeof(int);
while(1){
n = a[i];
while(a[j]==n && j<len){
j++;
}
if(j>=len){
break;
}
a[++i] = a[j];
}
for(k=0;k<=i;k++){
printf("%d ",a[k]);
}
return 0;
}
awesomecoder.blogspot.com/2012/08/remove-duplicates-from-sorted-array-of.html
- rkt August 19, 2012I didn't understand the question correctly. If the given input string is str1, we have to 'produce' a new string str2 out of str1. So that means we might have to remove some characters from str1. So length of str2 might be less than str1. And according to the definition of beautifulness str2 can not be more beautiful than str1 because it's length might be smaller than str1 !! Can you please elaborate with an example ?
- rkt August 19, 2012Idea is to write a new function pushbubble() using push(), where an element is inserted into its sorted position (situation similar to insertion sort). In that case, the top element will always be the minimum element.
Full working code here : awesomecoder.blogspot.com/2012/08/push-elements-into-stack-pop-should.html
void stack::pushbubble(int elem){
int temp;
if(!this->isempty()){
temp = this->pop();
if(temp > elem){
this->push(temp);
this->push(elem);
} else {
this->pushbubble(elem);
this->push(temp);
}
} else {
this->push(elem);
}
}
Full working code here :
awesomecoder.blogspot.com/2012/08/merge-2-sorted-arrays-without-using.html
void mergeArray(int *A,int *B,int m,int n){
//A has m elements, B has n-m elements
int i=m-1,j=n-m-1,k=n-1;
while(i>=0 && j>=0){
if(A[i] > B[j]){
B[k--] = A[i--];
} else {
B[k--] = B[j--];
}
}
if(j<0){
while(i>=0){
B[k--] = A[i--];
}
}
}
Full working code : awesomecoder.blogspot.com/2012/08/delete-all-matching-elements-in-linked.html
Node* deleteNode(Node* head,int data){
Node* temp;
Node* n;
temp = head;
while(temp != NULL){
if(temp->data == data){
head = temp->next;
temp->next = NULL;
free(temp);
temp = head;
continue;
}
n = temp->next;
if(n != NULL && n->data == data){
temp->next = n->next;
n->next = NULL;
free(n);
continue;
}
if(n == NULL){
break;
} else {
temp = temp->next;
}
}
return head;
}
I was asked this question - How does free() knows how much memory to free ?- in bloomberg interview. The answer to that is - when you do malloc(size); it reserves size+1 bytes of memory and it stores the value size in the first block. So, when we do free(ptr), it immediately knows how much memory to free.
- rkt August 14, 2012I think it is better to flatten the binary tree using Pre Order traversal only. The point of flattening is to be able to un-flatten it at a future point of time.
If you flatten it using Inorder or Postorder, you would have difficulty finding out the root of the Tree from the list. But you wouldn't have that problem if the list is in Pre Order.
void delete(Node **l, int target){
if(*l == null) return;
Node temp,nxt;
//setting the head node whose value is not equal to target
while(((*l) != null) && ((*l)->data == target) ){
temp = *l;
*l = (*l)->next;
free(temp);
}
if(*l == null) return;
temp = *l;
nxt = temp->next;
//iterate over rest of the nodes
while(nxt != null){
if(nxt->data == target){
temp->next = nxt->next;
nxt->next = null;
free(nxt);
nxt = temp->next;
}
else{
temp = nxt;
nxt = nxt->next;
}
}
}
This problem can be divided into 2 sub problems.
1) Finding out unique elements in str1
2) For each unique element in str1, find out if it is there in str2
Assuming the chars in string are in ascii set.
int uniqueChars(char str1[],char str2[]){
static int a[256],b[256];
int i=0,j=0;
int ret = 1;
while(str1[i] != '\0'){
a[str1[i]]++;
i++;
}
while(str2[j] != '\0'){
b[str2[j]]++;
j++;
}
i = 0;
while(str1[i] != '\0'){
if(a[str1[i]] == 1){
if(b[str1[i]] == 0){
ret = 0;
break;
}
}
i++;
}
return ret;
}
I agree with @geeks .. in 2 way merge sort..in the merging process there are n comparisons and each comparison we compare 2 elements -> n * O(1) = O(n)
in 3 way merge sort , there will be n comparison and each time we compare 3 elements
-> n * O(2) = O(n)
and if k = n, the merging process will be O(n^2) . cos you compare n elements , n-1 elements and so on.
do a preorder traversal. So you visit each node only once. At each node , if it is not null, swap the left and right pointers.
void mirror(struct node *node){
if(node == null){
return;
}
else{
struct node * temp = node->left;
node->left = node->right;
node->right = temp;
mirror(node->left);
mirror(node->right);
}
}
struct node * constructBST(int a[],int low,int high){
if(low > high) return NULL;
int mid = (low+high)/2;
struct node * root = newNode(a[mid]);
root->left = constructBST(a,low,mid-1);
root->right = constructBST(a,mid+1,high);
return root;
}
newNode is the helper function which creates a new node and returns the struct node pointer.
- rkt March 01, 2012when u generate a random number n between 0 and 1, for equal probability, u assign the following way
0 - 1/6 = 1; 1/6 - 2/6 = 2; 2/6 - 3/6 = 3; 3/6 - 4/6 = 4; 4/6 - 5/6 = 5; 5/6 - 6/6 = 6
now for the even numbers to have 72% prob, we have to divide each 1/3rd into 1/3 * 28/100 and 1/3 * 72/100 i.e 28/300 and 72/300
now the ranges will be
0 - 28/300 = 1; 28/300 - 2/6 = 2; 2/6 - 128/300 = 3; 128/300 - 4/6 = 4; 4/6 - 228/300 = 5; 228/300 - 6/6 = 6
this way u get the biased probability of 72% for even numbers
pre-process the entire dictionary and form a graph. Now start from the first word (source node) and do Breadth first search and you will get the shortest path from the source word to the target word.
- rkt September 28, 2012