Bloomberg LP Interview Question for Software Engineer Interns


Country: United States
Interview Type: Phone Interview




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

for 1-10K, use counting sort - O(n);
for 10K between 1-50K, use radix sort - O(nk); n = 10K, k = 5;

- vaticanoptimist September 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

For sorting numbers between 1 and 50,000, the interviewer might have expected you to produce an O(50k)-time solution. Initialize an array from 1 to 50,000 with zeros. Iterate through your numbers and update the appropriate buckets. Then go through the 50k-sized array and emit the numbers in order, using the bucket counts to determine how many values you emit. I think the interviewer is kind of clever, because the 5:1 ratio of max-value to N is in the range where a traditional O(NlogN) might actually be faster.

The second question was about finding the best sort for arrays and linked lists. For arrays, quicksort and heapsort are pretty comparable, because they can both be done in place in O(NlogN) time. For linked lists, you can cheat by copying the linked list into an array in linear time, but linked lists also play really nice with quicksort. Pop the head off the list, and use that as a pivot. Partition the lows and highs into two new linked lists. Recursively sort the other linked lists, then chain them back together.

Here's the key piece of a linked list based quicksort:

LIST quicksort(LIST list) {
    if (!list.head) return list;
    PNODE head = list.head;
    char *pivot = head->value;
    LIST smalls;
    smalls.head = NULL;
    smalls.tail = NULL;
    LIST bigs;
    bigs.head = NULL;
    bigs.tail = NULL;
    PNODE p;
    PNODE p_next;

    for (p = head->next; p; p = p_next) {
        p_next = p->next;
        p->next = NULL;

        if (strcmp(p->value, pivot) > 0) {
            bigs = append_node(bigs, p);
        }
        else {
            smalls = append_node(smalls, p);
        }
    }
    head->next = NULL;
    bigs = quicksort(bigs);
    smalls = quicksort(smalls);
    return concat(append_node(smalls, head), bigs);
}

- showell30@yahoo.com March 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you are creating an array of size 50k, then what is the purpose of this statement given in the question "there are 10000 numbers between 1 and 50000". Is there any possible solution which uses only 10k size array.

- Algorithmist March 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Look at "counting sort" in wikipedia. I edited my answer to say 50k, not 500k--sorry, the I miscounted the zeros (dyslexia). There are perfectly valid solutions that run in the 10k size array (in-place heapsort, in-place quicksort, etc.), but many of them run in NlogN time, which is inferior to a counting sort for a small range of numbers. Like I said, I think the interviewer chose the numbers cleverly, because the counting sort might not actually beat the in-place sorts in terms of actual time, and the counting sort is obviously inferior in terms of space usage (but usually time is constrained more than space).

- showell30@yahoo.com March 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Modified in-place version of counting sort for numbers/integers.

- Anonymous March 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

maybe count sort

- zyfo2 March 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use counting sort.

- alex March 19, 2013 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book on 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