Interview Questions 11

1. Given 10K of 16bit integers and unlimited memory, find most efficient algorithm that counts number of bits set to 1.

2. Print the pascal triangle. Don’t worry about formating.if i/p is 1 then print first line. if 2 then print 2 lines of triangle.see wiki about pascal triangle.

3. Print elements that are in a vertical column (per column) in a Binary tree

4. Given customer vs visited pages log for three days, find the customers who have visited for exactly 2 days and visited page count > 2. Customer can visit the same page any number of times.

5. How to represent a map of large nodes and edge in memory

6. Palindrome Date: A date is said to be a palindrome when it is expressed in MMDDYYYY format, it reads the same both ways. Given 2 years as input(ex: 2000, 2010), print out all the dates which are palindrome dates.

7. You are given a sets of words ,Write a C code which output the anagrams sets.
Eg for Input: algorithm testing asdfgh esttngi gorialmth
Output:
algorithm gorialmth
testing esttngi

8. Write a preorder traversal of a binary search tree w/o recursion / stack / extra memory storage. Hint – you can augment the node data structure. However, you can’t add a visited field to the node.

9. How will you remove white space from a string?

10. Prove that you can’t build a random number generator function that will output numbers 1 to 7 with uniform distribution and guaranteed to work in finite time using a random number generator that outputs either 1 or 2 with equal probability

11. An array is given like {1,4,5,2,3,6,7}. sort the odd elements in descending order and even numbers in ascending order. so result would be {7,5,3,1,2,4,6}.

Advertisements

About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

3 Responses to Interview Questions 11

  1. oshin says:

    1.) Unlimited memory suggests creating a look-up table for the first pow(2,16) whole numbers. The look-up table can be created in the following manner :
    a.) Start filling the table in the increasing order of values 0,1,2,3, so on
    b.) Initailize A[0]=0, A[1]=1
    c.) For every i, if i is a power of 2, then A[i] = 1,
    else write i = a + b , where a is the highest power of 2 less than i, then A[i] =
    1+A[b]

    2.) Use the fact that an entry in the Pascal’s triangle is a sum of the above two numbers [DP]

    3.) Really interested in knowing good approaches to 3 & 4.

    7.) Create a hash such that the anagrams hash to the same bucket. One way could be : For each word, sort it alphabetically, calculate its numeric value by assigning each alphabet a number (0-26), then use 26 base to calculate the value. Insert it into the hash table now. A collision would mean an anagram found.
    Another way could be : Assign first 26 prime numbers to the alphabet set & then hash value for a word would be multiplication of the letters of the word.

    9.) Can be accomplished in a single pass without extra space I believe. Maintain two pointers, one that traverses the array, other one which maintains the location where next next non-space character has to be written.

    11.) In a single pass, bring the odd elements to the left side, even elemnets to the right by keeping two pointers – one at start, one at end. Then sort the 2 parts individually. Is there a better way ?

    • Avi Dullu says:

      @oshin
      Questions 2, 7, 9 and 11 were meant only for coding. Not real algorithms in them as you rightly pointed out. These problems are simple but have some very critical boundary cases which need to be handled eg. in 7, making sure all the words are normalized to lowercases (or uppercases) etc. and you need to also keep track of how to identify the words after you have hashed them. The devil is in the details 🙂

      3. There is a cleaner method of doing this (I guess), by using O(logn^2) space and mapping the entire tree onto a 2D array and printing the columns. Another way could be using a DFS but will be involved. I’ll get back to you with a refined solution as soon as I come up with one.

      4. I have an approach in mind. If you have an approach, do post it. Note:It should not involve either storing or sorting all the log files.

  2. lalit mohan says:

    Sol to (8)
    For every node keep a pointer to the parent.

    struct TraversalState
    {
        enum Enum
        {
            FROM_PARENT,
            RETURN_FROM_LEFT_CHILD,
            RETURN_FROM_RIGHT_CHILD
        };
    };
    void preorderTraversalWORecursion(BSTNode* root, std::vector& data)
    {
        BSTNode* currNode = root;
        TraversalState::Enum state = TraversalState::FROM_PARENT;
        bool done(false);
        while (!done)
        {
            switch(state)
            {
            case TraversalState::FROM_PARENT:
                if (currNode->left)
                {
                    data.push_back(currNode->data);
                    currNode = currNode->left;
                    state    = TraversalState::FROM_PARENT;
                }
                else
                {
                    state    = TraversalState::RETURN_FROM_LEFT_CHILD;
                }
                break;
            case TraversalState::RETURN_FROM_LEFT_CHILD:
                if (currNode->right)
                {
                    currNode = currNode->right;
                    state    = TraversalState::FROM_PARENT;
                } 
                else
                {
                    state   = TraversalState::RETURN_FROM_RIGHT_CHILD;
                }
                break;
            case TraversalState::RETURN_FROM_RIGHT_CHILD:
                if (currNode == root)
                {
                    done = true;
                }
                else
                {
                    if (currNode == currNode->parent->left)
                    {
                        state = TraversalState::RETURN_FROM_LEFT_CHILD;
                    } 
                    else
                    {
                        state = TraversalState::RETURN_FROM_RIGHT_CHILD;
                    }
                    if (!currNode->left && !currNode->right)
                    {
                        //leaf node
                        data.push_back(currNode->data);
                    }
                    currNode  = currNode->parent;
                }
            }
        }
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: