CodeSport

This month, we celebrate the 9th anniversary of LFY. It’s been a pleasure to be associated with the magazine. The CodeSport column has been primarily about helping newbie programmers and students learn the tricks of programming and problem solving, and enabling them to clear technical interviews. Therefore, for this special edition of CodeSport, we go back to the basics, featuring advice on how to prepare for and clear programming interviews.

What’s so difficult about a programming interview?

I frequently get the following question from our readers: “I have an interview coming up, which is primarily on programming. Can you give me pointers on how best to prepare for it? I have just 9 days left…”

Well, there is no magic formula that can help you suddenly become an ace programmer in 9 days. Therefore, if you want to be an expert programmer, you need to read and practice diligently. You cannot cram all your preparation into 9 days and expect to succeed. Becoming an expert programmer and remaining one is a lifetime quest.

Make sure that your basics in computer science are clear and strong. Here is a simple example. Most interviewers, no matter for what position on the technical ladder they are interviewing the candidate, start off with the basics in computer science — such as algorithms, data structures, operating systems and the fundamentals of computer architecture.

For instance, a candidate who cannot clearly enunciate when one would prefer to use counting sort rather than merge sort for sorting the given inputs is not someone you want to interview further. So get your basics right. For instance, in algorithms, you need to be familiar with Big O notation, the basics of searching — linear search versus binary search, the basics of sorting — quick sort, merge sort, heap sort and counting sort, and the trade-offs involved in preferring one sorting algorithm over another.

You need to know the different algorithmic approaches available, such as divide and conquer, greedy methods and dynamic programming. You are also expected to know about recursion, string-searching techniques, and the complexity classes of algorithms such as P, NP and NP Complete.

In data structures, the minimum expectation is that you should know the implementation of queues, stacks, linked lists, hash tables, heap, binary trees, binary search trees and some basics about balanced trees. In operating systems, you are expected to know about virtual memory, the basics of file-systems, interrupt handling, scheduling and synchronisation. In computer architecture, you should know about the trade-offs when choosing between a RISC and a CISC architecture, about Amdahl’s law, pipe-lining, cache hierarchy, cache coherence, NUMA, TLB, etc.

This is not an exhaustive list, but just a mere indication of the topics you should definitely be familiar with in order to convince an interviewer that your computer science basics are strong.

Expertise in one or two programming languages is important. If you are applying for a systems software position, typically C and C++ are the preferred languages. An important word of caution here: Many students claim that they have expertise in C++ when they have been using C++ as a glorified version of C, without really exploring its features with respect to templates, OOP concepts and STL.

If you claim that you are an expert in C++, the interviewer will expect you to know all about how virtual functions are implemented, multiple inheritance, and template specialisation. It is not enough to know how to use the STL vector, queue or set/map. You need to know when you would choose one data structure over another and what the trade-offs are, in terms of efficiency.

Here is a question: If you want to be able to minimise the invalidation of iterators and pointers, while being able to provide transactional semantics for insertions and deletions, which STL container would you use and why?

By this single question, the interviewer gets to know not only how much you know about STL containers, but also about your ability to think through multiple choices and trade-offs. By throwing in the part about transactional semantics, he is able to assess how comfortable you are with exception safety and concurrency as well.

Most interview questions are designed this way. They are expected to test not just what you know, but whether you can apply your knowledge to a different situation. More importantly, they test whether, given adequate information, you are able to use the information to build solutions to problems you may not have come across before.

All of us are familiar with how to find the minimum in an array of integers. If the array is already sorted, it is an O(1) operation to return the minimum.

Now consider a slight variant of the question: Given a sorted array of integers that has been rotated an unknown number of times, give an O(logN) algorithm to find the minimum element.

When you are given a question, first think about other problems for which you know the solution, which are similar. In this case, we know that finding a minimum in a sorted array is a similar problem. Another related problem is finding a particular element in a sorted array. Next, think about whether you have been given any additional information that can help you narrow your choice down to a particular algorithm.

In this case, the fact that you have been told that you need to design an O(logN) algorithm should make you think about using a binary search. Now that you have narrowed down the approach to a binary search, think about how you can modify a standard binary search to solve this problem.

Since the sorted array has been rotated, you will have an ascending sequence of integers, followed by an inversion or reset point which marks the start of the original sorted array, and then the sequence of integers ascend again. Now the minimum is the reset point. Having arrived at this, it becomes a straightforward issue to code the solution.

To write efficient code, there is no way of preparing except to “Write code, test it, write more code, test it” and so on, ad infinitum. Whenever you come across a programming question, please make it a point not to look at the solution first. First write down your version of the solution, code it and test it. Then compare it with the given solution to see where the differences are.

Ask yourself the question, “Does my code handle all the kinds of data inputs that are expected?”

For instance, the problem input may start with “Given an array of integers…”… am I making an assumption that the size of the array is less than some limit? What if there are more integers than can fit in the main memory? Has any specification been given on the limits the values can have?

For instance, if you are told that the integers represent age, then we know that they can be assumed to be limited between 0 and 100. But remember one thing: The only way you can become an expert in coding is to actually write code, test and run it.

No amount of reading books on coding can prepare you for writing actual code. This is especially important for students who do not have an opportunity to write code every day. Please set aside some time every day and solve programming problems by writing actual code.

My ‘must-read book’ for this month

This month’s “must-read book” suggestion is not a single book, but a set of books which I believe are must-reads in order to develop expertise in programming. Some of them have already been mentioned in our column before.

• Introduction to Algorithms — Cormen, Leiserson and Rivest
• Programming Pearls — Jon Bentley
• Programming Interviews Exposed — Mongan, Suojanen and Giguère
• Cracking the Coding Interviews — Gayle Laakmann

For C++, I recommend Scott Meyers’ Effective C++ and Effective STL series once you have read a basic C++ book. For C, after reading Kernighan and Ritchie’s C Programming Language, my favourite is Expert C Programming Deep C Secrets by Peter Van der Linden. Get your basics in operating systems clear by reading the book Operating Systems by Silberschatz and Galvin. For computer architecture, there is no better book than Computer Architecture: a Quantitative Approach by Hennessey and Patterson.