Amazon interview experience Set 1

Amazon interview experience set 1

Online Round
1. Write a function to merge two sorted linked list in a linked list which is sorted. The time complexity of this function should be O(n+m) where n and m are sizes of two linked list, the space complexity should be O(1).

2. Implement a stack which has three operations: Push, Pop, and Max. The time complexity of all these operations has to be O(1) and space complexity can be O(n) where n is the number of elements present on the stack.

3. Find a missing number in an array which has numbers in range 1 to N and only 1 element is missing.

DS and algorithm round 1
1. Given a stream of integers, find the median of all the integers appeared till now.

2. Print right side view of a binary search tree.

DS and algorithm round 2
1. Given a stream of integers, find if there is a subset of these integers which add up to a particular sum.

2. Given a log file, implement a function which reads the last 10 lines of this file.

System design round
1. Implement an email service.

Cultural fit round
1. How did you handle conflict with your manager or a colleague?
2. What do you do when you see someone is taking credit for things you delivered.

If you are preparing for an interview and looking for personalized coaching, please book a free session with us.

Print unique rows in a boolean matrix

Unique rows in boolean matrix

Given a matrix of 0 and 1, print all unique rows in boolean matrix. For example, if the matrix is show below:
0 1 0 0 1
1 0 1 1 1
0 1 0 0 1
1 0 1 0 0
Output should be
 0 1 0 0 1
 1 0 1 1 1
1 0 1 0 0

The first brute force solution which has a complexity of O(n2 m) where is n is the number of rows and m is the number of columns is as follows:
For each row in the boolean matrix, check all the rows if it matches with any one of them. If yes, skip printing, else print the row.
Another way which is better than the above approach is to convert each row in equivalent decimal and then check for duplicates. Again it has a complexity of O(n * m) where n is the number of rows and m as the number of columns.

Can we do better than this? There is a standard technique to check if a particular pattern is already seen or not. That’s using tries. Each pattern is added to trie, when we try to add a duplicate pattern, we will end up at the leaf node which is already marked as leaf due to an earlier pattern.
With given info, we can say that we will insert each row pattern in the trie. We will modify the insert function of trie to return us whether the row is added newly or it was already present in the trie. As explained above it can be ascertained by the fact that if the last node is marked as leaf node already, then it is duplicate row as we must have traveled the same nodes above. If the last node is not a leaf node already, then there is at least one digit which is different and hence row becomes unique. Mark last node of this pattern as a leaf node, so that same patterns will be detected as duplicates.

Add a row in the trie.
If the last node while entering the pattern is the leaf node, return false. It’s not a unique row.
If the last node is not a leaf node, mark it as a leaf node and return true.
If insert operation returns true, print the row.
Else, skip printing row.

#include<stdio.h>
#include<stdlib.h>

#define MAX_SIZE 2

#define LEAF_NODE  1
#define true 1
#define false 0

typedef struct trie_node_t {
    int value;
    struct trie_node_t * children[MAX_SIZE];
}Node;

typedef struct trie{
    int count ;
    Node *root;
}trie;

void initialize(trie *t){
    t->root = (Node *)malloc(sizeof(Node));
    t->count =0;
}

int insert_1(trie *t, int key[], int col){

    int i;

    if(t->root == NULL){
        printf("\n Trie is not initialized\n");
    }

    Node * current = t->root;
    for(i=0; i<col; i++){
        int index  =  key[i];
        if(current->children[index] == NULL){
            current->children[index] = (Node *)malloc(sizeof(Node));
        }
        current = current->children[key[i]];
    }

    /* To mark it as leaf */
    if(current->value != LEAF_NODE){
        current->value = LEAF_NODE;
        return true;
    }
    else{
        return false;
    }
}

void print_unique_rows(int a[5][5], int col, int row){

    int i,j;
    int key[col];

    trie t;
    initialize(&t);
    for(i=0; i<row; i++){
        for(j=0; j<col; j++){
            key[j] = a[i][j];
        }
        if(insert_1(&t, key, col)){
            for(j=0;j<col; j++){
                printf("%d", key[j]);
            }
            printf("\n");
        }
    }
}
//Driver program
int main(){

    int a[4][5] = {{0, 1, 0, 0, 1},
                    {1, 0, 1, 1, 0},
                    {0, 1, 0, 0, 1},
                    {1, 0, 1, 0, 0}
                  };

    print_unique_rows(a, 5, 4 );

    return 0;
}

The complexity of trie based solution is O(n * m).