CodeSport

In last month’s column, we discussed a few of the programming errors that can lead to software bugs. In this context, one of our readers, Balamurugan, had emailed us a pointer to his favourite open source static analysis tool for Java, called FindBugs. There is also a good discussion on programming errors that lead to hard-to-detect bugs, by William Pugh, the author of FindBugs, available here [PDF]. I would encourage our readers to go through this presentation.

Another reader, Raghunath, had sent a pointer to Clang, which can be used to detect coding errors in C programs. Clang is not a static analysis tool per se, but is a compiler front end for C, and uses LLVM as the backend. The Clang frontend provides static analysis tool capabilities to detect coding errors. A standalone version of the tool is also available.

We thank our readers Balamurugan and Raghunath for sharing these pointers to their favourite tools for detecting software bugs. If you have a favourite static analysis/runtime tool to detect programming errors, please do send me a note. I will share your inputs with other readers in next month’s column.

A few of our student readers had written in with a request to feature a set of programming interview questions that they could use for practice. Therefore, in this month’s column, we take a break from our discussion of software bugs, and instead feature a set of programming problems. We will continue our discussion on static and runtime tools to detect software bugs in next month’s column.

Before we get started on this month’s questions, I wanted to point our readers to a useful link related to preparing for an interview that I came across. We all know that many of our readers dream of getting to join companies like Google or Facebook. In fact, MIT now offers a course on how to crack the programming interviews in companies like Google or Facebook. Here’s the link to the course.

This month’s programming problems

1. Given two sorted integer arrays X and Y of size m and n, you are asked to find the k^th smallest element in the new array Z formed by merging X and Y.
   1. Can you give a solution which is O(m+n)?
   2. Can you give a solution which is O(k)?
2. Given two sorted integer arrays X and Y of size m and n, you are asked to find the intersection of the two arrays.
   1. What is the complexity of your solution?
   2. Can you give a solution which is O(m+n), and using constant extra space?
3. We are familiar with the queue data structure, which supports push_back and pop_front operations in constant time. Can you design a queue data structure that supports the operation extract_min in constant time, along with push_back and pop_front operations?
4. Given a binary tree:
   1. Write a program to determine whether it is a binary search tree.
   2. If the binary tree is not a binary search tree, can you find a binary search tree with the largest number of nodes in the binary tree? The largest BST may or may not include all of its descendants; i.e., the largest BST you find need not be a sub-tree of the binary tree.
5. You are representing a set of integers using a linked list. You are asked to support the array index operator on the linked list. Given an index i, you need to support the following operations:
   1. List[i], which returns the element present at the i th node of the list.
   2. InsertList(value, i), which inserts the new element as the i^th node in the list.
   3. DeleteList(i), which deletes the i^th node of the list.
6. Given an array of integers S, and a number N, can you print the combination of numbers from S which sum up to N? Note that we want the combination, and not the permutation. For example, given S as 1,2,3,6,2,4,1 and N as 8, one combination we can print out is (1,2,3,2), and if we print out this combination, we should not print out (2,3,2,1), etc.
7. Given a string S, a three-letter pattern xyz, and a character D, write an algorithm to replace all occurrences of the pattern xyz in S by D, in-place. Note that if multiple copies of the pattern xyz occur together, they should be replaced by a single D. For instance: if you have axyzxyzb, then after replacement, the string should be aDb.
8. Given a linked list L, which consists of N nodes, split this into two lists: L1, which contains the front part of L, and L2, which contains the back part of L. L1 and L2 each contain half the elements of L. If N is odd, add the extra element to L1.
   1. What is the complexity of your algorithm?
   2. Can you do this in a single list traversal?
9. What is the difference between the keyword new and the operator new in C++?
10. In concurrent programming, what is the difference between wait freedom and lock freedom? Which one provides a stronger forward-progress guarantee?
11. You are given an array of integers N, such that each integer in it appears thrice (i.e., there are triplicates for every element) except one integer. Can you find the single integer that does not have copies in the array?
12. You are given a set of unsorted integers, which is represented by a linked list. Each node of the list contains an integer. If you are asked to sort the set of integers, what approach would you use, and why?
13. Can you explain what a NoSQL database is? Do they provide ACID guarantees?
14. What is the difference between the super-scalar and VLIW architectures? And what is the difference between in-order and out-of-order processors? Does super-scalar imply out-of-order execution?
15. Can you differentiate between an archive library and a shared library? When would you prefer to link an archive library with your application, and when would you prefer to use a shared library?
16. Can you write a handler for a SIGILL signal? When is SIGILL typically encountered?
17. Pages are typically of size 4K and above. Why is the page size as high as 4K? Why can’t we have a page size of 128 bytes? What are the pros and cons of having a small page size?
18. Do you know the difference between simultaneous multi-threading and hyper-threading?
19. What is the significance of the memristor, phase-change memory and spin-torque-transfer RAM technologies to the computing paradigm?
20. What is the difference between actor-based programming and thread-based programming?
21. What are the various code-coverage measurements you would do to make sure that your code is tested adequately?
22. Do you know what is meant by cyclomatic complexity?
23. Can you explain how a breakpoint is implemented in a debugger?
24. What is ROP or return-oriented programming?
25. What are lambda expressions in C++?

This month’s takeaway question

Since there were no correct solutions from our readers for last month’s takeaway question on calling delete on a void* pointer, I would like to keep the question open for this month as well. Please do send me your answers. Remember that we are invoking the C++ keyword delete with a void* pointer, in the problem given in last month’s column. What would happen in that case? Think about what the difference is between delete and the operator delete.

My ‘must-read book’ for this month

This month’s “must-read book” is actually one that I came across as an online version. It is called 97 Things A Programmer Should Know, from O’Reilly. The contributions published in the book are available at the wiki.

Though some of the contributions are simple, common-sense approaches to programming, it makes an interesting read, since a wide spectrum of topics are covered, right from coding errors to refactoring. If you have a favourite programming book that you think is a must-read for every programmer, please do send me a note with the book’s name, and a short write-up on why you think it is useful, so I can mention it in this column. It would help many readers who want to improve their coding skills.