In a recent essay, I provided an overview of items to consider when preparing for a technical interview. Portions of this content were expanded into a webinar, including a basic framework for answering tough questions when going to the whiteboard. Even though we specialize in iOS development, the process is general enough so that it can be applied to any programming language:
- Ask clarifying questions
- Create a conceptual diagram
- Express a brute force solution in pseudocode
- Refine your solution with workable code
- Check for errors or omissions
Following a set of predefined steps becomes particularly important when coding under time constraints or are dealing with an unfamiliar subject. Let’s see how to use this process to answer the following question:
How would you design a
Stackclass which, in addition to a
popmethods, also has a property
count, which returns the number of elements? Push, pop and count should all operate in O(1) time.
This problem tests the candidates knowledge of Big O Nation as well as algorithms & data structures. However if you didn't know these subjects, you could still discover a solution by asking a few clarifying questions:
What is a Stack? Is there an iOS equivalent?
As iOS developers we’re accustom to using Swift and the iOS SDK to build user interface elements, processes and apps. This question provides value because the candidate (correctly) assumes a Stack isn’t something normally used in development. From the candidates perspective, the answer to this question could connect the everyday activity of managing UITableViews with a UINavigationController.
What’s O(1) Time?
This answer will reveal how one should be thinking about algorithm’s performance. By understanding the importance of O(1) (e.g. constant time) they'll see there are significant advantages to processes that perform at the same speed - regardless of their input size. Even though asking this question during an interview would be the best course of action, studying up Big O Notation beforehand would provide many added benefits.
This one we’ve all heard of, but in practice, it’s difficult advice to follow. As we work through the problem to eventually get to a solution, we need to let our interviewer know what we’re thinking - even if our ideas appear silly or half-baked. In most cases, interviewers want you to succeed so they’ll be looking for opportunities to steer you in the right direction. Without any verbal feedback, they can’t help. As we know, this is often when things get tense and awkward.
Refining Your Solution
When writing code during an interview, it's best practice to code a basic solution “that just works,” then continue to refine its syntax and functionality. In performance terms, this often translates to building a workable solution at O(n) or even O(n2). This 2-step process not only provides an opportunity to gather your thoughts, but also lets the interviewer know you’re on the right track.
Finally, as you refactor your code to a final solution ask yourself, how would this algorithm perform if it had to process 1M rows of data? Reframing the question often allows one to dissect parts of your solution that look solid, but could be improved even further.