"Senior software engineers are the most experienced member of a software team and usually carry the most responsibility and authority of that team. Because of this, interviews will be designed to find candidates who have expert knowledge of the field and years of experience as a software engineer. Expect to be asked tough technical questions and to give examples of previous projects that you have worked on."
How do you find 2 missing elements in an array of consecutive integers that are not sorted who's size is N-2.
hint sum (n) = n X (n+1)/2
One problem with that solution (sum) is that if the sum of numbers is of exorbitant size, you run a risk of overflow, given that there's no limit imposed on N. You can sort the array, but if you don't want modify the user's array, you'll need to make a copy...which depending on the size of the array, might be expensive. An alternative that I thought of would be to create a bitmap for each element (initializing all bits to 1). Then pass through the vector once and set the corresponding bit 0. After one pass through, you can make a second pass to determine which "sectors" still contain set bits and can extrapolate the missing value accordingly. Worst case O(2N) A strategy might be to impose one of the two methods, depending on the size of the array, but sorting inevitably has a floor of O(N), unless you're going to take a probabilistic guess and skip over elements you think might already be sorted. Most algorithms are O(n log n) because the need to visit every element, and the revisiting of some elements to perform the proper placement.