Tech Jobs and Interviews

In today's session, I show the group a tricky, tricky integer overflow detail that is pervasive in binary search and mergesort implementations. How tricky is this whole thing? According to the Google Research blog, most of the first year CMU Ph.D. students' implementations of the rudimentary algorithms were flawed due to overflow problems . Moreover, various cybersecurity lists name integer overflow as one of the top software flaws . The Google blog also recommends Jon Bentley's classic Programming Pearls (Amazon affiliate link) book which motivates this and other Google-style large scale questions such as sorting billions of integers efficiently limited memory. You can probably snag that book in the local library, but we'll cover these and other popular interview questions. But back to the main point, integer overflow is a popular conceptual interview question in some quarters. The interviewer wants to see if you understand integer overflow and by extension an u

This is the second part of a series. Go back to part 1 if you haven't read it already. In a fast paced interview, running time analysis is often about recognition of common running times of basic operations and combining them together, since you won't have time to derive the running time of each subcomponent of your algorithm. For example, say you had an algorithm that first sorted an array and then made a constant number of passes through the sorted array. You should point out to your interviewer that the sorting took O ( n log n ) assuming mergesort or heapsort and the constant number of passes took O(n) which is dwarfed by O ( n log n ) for large n. Therefore the whole algorithm is O ( n log n ) . This is the kind of thing you have to learn to recognize. As we go over common algorithms and algorithms for specific real interview questions, I will point out the running times of the var