Facebook Interview Question for Software Engineers


Team: Advertisement optimization
Country: United States




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

I can see a couple of performance problems with your code.

First, you're passing the SparseVector by value instead of passing them by reference.

Second, you're using the map find. That's going to make the complexity

O(min(m,n)*log(max(m,n)))

. Additionally you're using

SparseVector::getValue

which does another lookup.

static double s_dotProduct(const SparseVector& a, const SparseVector& b){
        if (a.m_size != b.m_size)
            return 0.0;

        double sum = 0.0;
        auto a_it = a.m_map.begin();
        auto b_it = b.m_map.begin();
        while (a_it != a.m_map.end() && b_it != b.m_map.end()) {
            if (a_it->first == b_it->first) {
                sum += a_it->second * b_it->second;
                a_it++;
                b_it++;
                continue;
            }
            a_it->first < b_it->first ? a_it++ : b_it++;
        }
        return sum;
    }

- gxg February 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I have just looked quickly and saw the following points:
1) They asked for the dot-product of a matrix, you implemented it for a special case, a vector. Not sure if that was the question or clarification you got.

2) I guess, if you need a data structure for dot-product it's not so cool to use a map because of the O(m*log(n)) nature of your algo. With 24h I had expected a O(n) solution - e.g. using the hashtable, there is no real advatage in keeping the order, I totally don't understand your 2nd comment on this.

Then, if you use only a vector, you get away with a linked list, that will keep the index and value, which is then not optimized for setValue but multiplication can be done in a merge-sort kind of way.

How to improve: Just keep solving problems, buy gayle's book she has a nice, pragmatic approach. Code more, read code from pros (e.g. github projects)

3) c++:
- an iterator with it++ instead of ++it. Which a c++ programmer must know.
- getValue and getSize should be const-methods, just good practice, should go automatic, I guess if they give you time to do so, they expect it, on the white board, I think nobody really cares that much.
- worst is your constructor, it leaks unnecessary new (sorry, but it's really bad)
- How to Improve: Read stroubstrub, effective c++, more effective c++ and effective modern c++ (if it has to be C++)

Coding style: there is this if in the s_dotProduct-Method which essentially doubles code, since you want to minimize the amount of lookups in the map. Here it would be better to have pointers to the two maps and just swap them and have the multiplication code only once. This copy/paste kind of code is not good!
- How to Improve: Whenever you copy / paste such a block of code, ask yourself, can I put it into a helper method, might be inline, or can I just swap some arguments or anything to not double code.

OO-design, in some way a taste thing, I would Expect the Matrix class having a multiplication method so you can write vect1.mul(vetc2) instead of vector::multiply(vec1, vec2). The template method s_toString, I'm not sure it belongs into the vector class

And an other thing, if you get so much time, why don't you write some unit-test like test cases, I mean this case is neat to show you understand TDD and you have passion and are willing to work.

- Chris February 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I also wrote on my comments before submitting to FB that I could have used hash table as well, but map allows me to keep sparse vectors sorted and would help when two vectors are of largely different sizes. I have done some research on this topic before and had read several articles but I guess did not help.

Any suggestions would help me improve my performance. Thank you people!

- Ad February 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Facebook, this time, asked I guess a meaningful question. What they do - this question makes sense from a practical point of view. If you are certain that your code works, then perhaps you missed this : [ dl.acm.org/citation.cfm?id=1377232 ]
I am not too sure though.

- NoOne February 07, 2017 | 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