I went to a first round Facebook interview, and I requested to be on campus, since the phone can be unclear. *It was for a web front end dev role* So the interviewer asked me to solve the "Maximum Stock Gain" problem. Simply enough, given an array of stock prices, such as from Jan 1 to Dec 31 of the year, find out the maximum gain possible. You can buy on any day, but you have to sell after you buy. (no short sale... hm... this is not related to GameStop)... Only one buy and sell in the future, find the maximum gain possible. The obvious, simple solution is to use a solution that is O(n²), to use nested loops. So he asked me can I do better. I told him I have read a story about that 2, 3 years ago, in the book Programming Pearls by Jon Bentley, but I can't remember. He asked me to try anyway. I was stuck at first. And then after about 10 minutes, I came up with the solution that is time complexity O(n). He then told me, if I don't have the O(n) solution, he was sure I won't even go to the onsite round. I would be immediately disqualified. So I wonder, do you want to give it a try? It took Jon Bentley a couple of years to find the solution. The interviewer wanted the solution in 20 minutes. (actually, the book Programming Pearls presented it as a maximum subarray sum problem. But if you construct a new array, with each element being the "price change", the delta, of the stock price change from one day to the next, then it becomes of maximum subarray sum problem. Likewise, you can convert it from the maximum subarray sum problem back to the maximum stock gain problem). The algorithm book from MIT by Thomas Cormen mentioned a divide and conquer method that is a O(n log n) solution, and briefly mentioned the O(n) solution (in the homework exercise section). Since somebody think "oh it is so simple solution", I will write it here. First of all, if you use nested loops, you are O(n²) and it will fail the interview. Since the code would choke if it has the less than sign because the editor thinks it is an HTML tag, I will post it as a picture which can only be placed at the end. So this is how it is? Whether I know the solution or not, does that mean I am a bad or good programmer? Just because I haven't seen the problem before or memorized the answer, I am automatically disqualified? The aftermath was, I went onto the second round interview, for 5 rounds of interview. Note that it was for a web front end role. The first interviewer spent 35 minutes asking me how the engineering process was at Apple when I worked there, and how I dealt with the offshore workers, and left 10 minutes to me for the technical question. Another interviewer asked me to design the Google search engine server infrastructure, and the load-balancing. If I worked 10 years as a front end dev, guess how good I am designing server infrastructure. So I could consider it close to 8 hours of interview wasted. Of course, I can consider it "Interview Preparation Class -- Free of Charge". I am finding the Amazon interview perhaps similar to the FB interview too. Anybody can say if it is or not? But oh well, if I memorized or have read all those problems and solution and can give the optimal answers, what does it mean? I do notice that, some 2000 years ago, in some dynasty, you can be a common and poor villager. Only if you memorize 500 poems and old scriptures, then you go to exam in the capital, and if you answer well, then they make you the "top person". And then you become the country official and go back to your village, obeying the king, and then force it upon the other villagers. The key is, "you showed that you obeyed their system and is willing to be a servant for them." Some people said at that time, it just meant you are willing to be a "running dog" for the officials. How is it different from the interviews nowadays? From of the answers below, it seems quite many people have a consensus: the company doesn't want to know you are smart or can think well. They just want to see you prepared for the interview (and perhaps ready to be obedient and be running dogs). Some people claimed this is just a LeetCode easy problem. Some people just seem to regurgitate how it is like on the LeetCode optimal solution and don't quite understand why it worked. I wonder if they tried it on LeetCode, couldn't solve it in 20 minutes, saw the optimal solution, and from that point on, they just claim, "Dude, it is LeetCode Easy". The LRU Cache problem, which is medium on LeetCode. It seems Amazon would disqualify you if you don't have the optimal solution in the first 3 minutes too. Basically, I propose putting a "last touched" timeStampID" (a monotonously increasing integer) into the element and use a Heap (priority queue) so that I always have the min, and so if it is full, then just remove the min node. It is not bad if compared to the optimal solution. Yet in that 3 minutes, I didn't come up with the optimal solution, and they disqualified me afterwards. And, would you tell the interviewer you have seen the question before? In the 90's and early 2000, it was said that you should tell the interviewer you have seen it before, so that he will ask you a different question you haven't seen before. If they detect that you have seen it before and didn't say so, they automatically disqualify you. A poll: would you tell the interviewer you have seen the question before? --- But if you don't tell them and you can give an optimal answer, isn't it obvious you have seen it before? Or both you and the interviewer just quietly accept the fact that you have seen it before and no surprise. #swe #interview #facebook
TC or gtfo
That is a easy and famous problem. Unfortunately if they hire people on basis of logical thinking then everyone will think they are entitled to get the job because they are the smartest and the best. The key is to respect their process and prepare for it.
yup, sometimes I can feel on the interviewer's face that he thought, "this is a bright person, but I wonder if he will pass us or the hiring committee". > respect their process and prepare for it So this is indeed about the running dogs.
The company is hiring you to do a job, you seem to think the company should mold to fit your skill set, and anything else is “running the dogs”
to be fair an 8th grader with 1 month of prep could give an optimal solution for this
> It took Jon Bentley a couple of years to find the solution. So I guess they don't want you to think. They want you to memorize.
Please please do NOT just memorize. Anyone with a few weeks of prep should be able to at least reason about this. Idc who this guy is
Lol dude, I've spent ten years doing embedded systems on microcontrollers and they asked me to design a distributed web crawler... I think you can guess how well that went
Well? How did you design it
yes, tell me how you design it in 10 minutes. And it must be a good design
It's how facebook works. They prefer you to just grind leetcode and know the most common LC problems cause you were already exposed to them.
Yes. Because you need to be good at grinding to be successful at FB.
Not true. But that's how the interview process works compared to other companies
It is a game and rules are set by them. If you don’t like the rules, don’t play. You may vent here and feel better, but this is the reality. For instance- https://twitter.com/mxcl/status/608682016205344768?s=20
That's it though, isn't it? It's just a game to them. They aren't doing a good job ascertaining domain skills because they ask general questions that are likely not related to the candidates experience or the team's needs. In the end, it doesn't matter so much since FB is just one company, but it's still interesting to talk about how different companies judge the skill and experience of candidates.
Nobody told me there is such a rule. Like I said, in the 90's or early 2000, they asked you to tell if you have seen or heard of the problem before so that they give you a different question. If you pretend that you never heard about it, it is considered cheating and bad moral of the candidate and they may disqualify you for that.
Is that maximum gain using a single trade? So taking the difference between each number and minimum number that came before it? If so, that's considered an easy problem now and if they didn't filter based on O(N) time complexity, then it wouldn't filter at all. The interviewer saying that is actually good because you don't have to worry about if your solution is or isn't optimal. You know the time complexity ahead of time
Yah, 2 trades to k trades gets interesting, but isn't one buy + one sell just trivial?
why don't you write it down here. I don't quite get the algorithm of "taking the difference between each number and minimum number that came before it?" If it is really simple, the MIT algorithm book won't be diving into a complicated O(n log n) solution.
Was that a “System Design” or “Product Design” interview? Still not sure what the difference really is.
Fb designed interview not to make it interesting for you or relevant to your previous experience. They filter those who will be able to refactor 10yrs old php code or write objective c without complains. If you didn't like the interview you had - just don't join
Layoffs
Yesterday
3454
Google laid off 200+ in core team
India
Yesterday
736
Modi is a legend, will be remembered for centuries to come
India
Yesterday
785
Who are these retards asking for dictatorship in India?
Tech Industry
Yesterday
1762
The end of Backdoor Roth?!
Tech Industry
Yesterday
2193
Quitting this Slave life
too much text
yup, attention span of goldfish popular nowadays
Perhaps, but that was really too long.