is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.
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.
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.
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.
What about going in a groups of 3 items starting with 0 (which gives us -1 (=1), 0 and 1) and ending with n-1 and adding the both value of current element and result of multiplication of those items to the BST (ordering by result of multiplication).
- ba.andrzejczak March 03, 2016BST elements besides simple left and right fields would have to feature prev and next elements - pointers to other nodes of the BST, that come before and after the elements in balloons list. That would be a mix of BST and a double-linked list.Adding elements to such tree given a list as an input would yield complexity of O(n*log n).
Then with such tree, until the tree is not empty, we would extract minimum element O(log n). If it has both prev and next pointers set (it's not on the boundary) then we would add it's multiplication result to the overall sum, get prev and next elements, remove them from the tree and add them again so that they become adjacent to each other (that means dividing their multiplication result by value of popped element and multiplying it by the value on the element that they're becoming adjacent to. Also we need to change their next and prev fields to point to each other).
If this minimal value in a tree is a boundary value (it has empty prev or next field), we look for maximum value, and pop it with the rules mentioned above.
This process is taking place for n elements and for each of them lookups of minimum/maximum elements take log n time, which gives us complexity of O(n*log n).
The overall time complexity is O(n*log n) and space complexity is O(n)