Technical Interview Questions - Data Structure

1. Given a dynamic stream of integral numbers, write a function that returns its median. The numbers may arrive in bursts at any time.

    min/max heap

2. There are two integer arrays ,each in very large files (size of each is larger than RAM). How would you find the common elements in the arrays in linear time.

    bitmap?

3. For an array of integers, find if there are 3 numbers that add up to zero. An algorithm of complexity O(n^2) was required.

    hash table

4. What is the complexity of an algorithm to check whether a binary tree is symetric or not. No need to check the data only the structure needs to be verified.

bool IsSymmetric(Node* r) {

    if ( r == NULL ) return true;

    return IsSymmetric(r->left, r->right);

}



bool IsSymmetric(Node* L, Node* R) {

    if ( !L && !R ) return true;

    if ( !L && R || L && !R ) return false;

    return IsSymmetric(L->left, R->right) && IsSymmetric(L->right, R->left);

}

5. Implement stack class, algorithm for returning minimum number

6. Implement Trie