Facebook Interview Question
Software EngineersTeam: Advertisement optimization
Country: United States
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.
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!
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
. Additionally you're using
which does another lookup.
- gxg February 07, 2017