Google Interview Question Software Engineer / Developers




Comment hidden because of low score. Click to expand.
1
of 1 vote

Why can't we use arrays to store large number of integers
We can use the Select Algorithm to find the median. This algorithm also has time complexity of O(n)

- abhimanipal on February 02, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Note the qualifier: "large number". If Google says large number, that should be massive. That amount of data can only be stored in hard drive or tape etc, where IO dominates the efficiency. So, to speed up searching, B-tree is optimal.

For median, I guess we can search in the leaf nodes. B-tree is ordered. So, you can find the median half way through keys of the leaf nodes.

- Peng Du on February 12, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Note the qualifier: "large number". If Google says large number, that should be massive. That amount of data can only be stored in hard drive or tape etc, where IO dominates the efficiency. So, to speed up searching, B-tree is optimal.

For median, I guess we can search in the leaf nodes. B-tree is ordered. So, you can find the median half way through keys of the leaf nodes.

- Peng Du on February 12, 2010 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

<pre lang="" line="1" title="CodeMonkey45093" class="run-this">Use two heaps
Max heap and Min heap
( The constraint is that the size difference between minheap and maxheap should be 0 or 1)

Read the elements from source:
median is represented by the root of maxheap ( if number of elements is odd)
median is represented by the average of the root of maxheap and minheap (if the number of elements is even)

if the incoming element is less than the median
if the size of maxheap is greater than minheap by 1. Delete the element from maxheap and insert to minheap.
insert the element to maxheap
else
if the size of minheap is greater than maxheap by 1. Delete the element from minheap and insert to maxheap.
insert the element to minheap

comments Welcome :-)</pre><pre title="CodeMonkey45093" input="yes">
</pre>

- Anonymous on August 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Median can be found in O(1) time

- Kirubakaran on August 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hey,

Are these questions asked in a Phone Interview?

- Amit on February 03, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution (C). For the even tree_size, traverse_inorder may be optimized for returning two nodes instead of one (using a struct)

/**
 * Traverse inorder
 * left-root-right
 * @param N Nth number in the ordered list
 */

int traverse_inorder(Node_t *root, int N)
{
    static int counter = 0;
    if(!root) return;
    
    traverse_inorder(root->left, N);
    counter++;
    if(counter == N) /*Nth number in list is found */
    {
        return root->data;
    }
    traverse_inorder(root->right, N);
}
    
    
find_median(Node_t *root, int tree_size)
{
    int N = 0;
    int lower = 0;
    int higher = 0;
    if(tree_size & 1)
    {
        N = (tree_size/2) + 1;
        return traverse_inorder(root, N);
    }
    else
    {
        N = tree_size/2;
        lower = traverse_inorder(root, N);
        N++;
        higher = traverse_inorder(root, N);
        return (lower + higher)/2;
    }
}

- volongoto on February 20, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your function traverse_inorder uses a static counter. The function won't return an accurate result more than once because the counter is not reset during subsequent calls.

- Pushkar on February 22, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

b+ or b- trees are a better solution than binary tree so your solution doesnt really hold good..

- daisy898 on January 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

guys does it make sense to use self-balancing trees as root will roughly represent the median of all the numbers...

how does this sounds?

- ZooZoo on March 14, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It sounds like your name ...

- Anonymous on May 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

lol

- Anonymous on September 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

rofl

- anonymous on February 09, 2011 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More