Codesport

In this month’s column, we feature a set of interview questions on algorithms, data structures, operating systems and computer architecture.

For the past few months, we have been discussing information retrieval, natural language processing (NLP) and the algorithms associated with them. In this month’s column, we take a break from our discussion on NLP and explore a bunch of computer science interview questions.

1. You are asked to write a small code snippet in C to determine whether your computer is a little endian machine or a big endian machine. Assume that you can compile and run your C code using your favourite compiler on this computer. Is it possible for you to determine the endianness by looking at the assembly code without running the program? If not, explain how you can determine the endianness of the machine by running your code snippet.
2. You are running a C program and from the console you see that your program terminated with a ‘stack overflow’ signal error. When would a stack overflow signal be generated?
3. We all know that physical memory is volatile and, hence, when there is a power failure or system shutdown, contents of the physical memory are lost. Is it possible to have non-volatile physical memory? What are the different types of non-volatile physical memory?
4. If your computer has non-volatile physical memory instead of volatile physical memory, can you explain what would be the major operating system support needed to enable an application to restart from where it crashed?
5. Why do computer systems have multiple levels of cache hierarchy instead of a single large huge cache? Is it possible for an application to bypass the cache and read/write directly from the main memory?
6. We are all very familiar with Moore’s law, which can be approximately stated as: “The transistor count on a processor chip doubles every 18 months.” This has been resulting in the approximate doubling of processor speeds till now. However, over the last five years, there has been considerable talk about the end of Moore’s law. What are the factors that are causing the end of Moore’s law? Can you explain what the term ‘dark silicon’ means?
7. What is meant by ‘Non-Uniform Memory Access (NUMA)’ systems? If you have written a C application that runs on your personal computer, do you need to make changes to it in order for it to run on a NUMA system? If yes, what changes are needed? If not, explain why no changes are needed.
8. Given the wide prevalence of Android mobile devices today, what is the operating system running on these devices? If you have written a Java program that runs on your personal computer, can you run it without any changes on your Android mobile system? If not, explain why it can’t be run, as is.
9. We all know that the data present on our laptops and personal computers is typically organised into files and directories. What are the different storage abstractions that are available on Android mobile devices for mobile applications to store data?
10. Many computer systems today have both a CPU and GPU built in to the same system, in what is known as ‘Heterogeneous System Architecture (HSA)’. Is it possible for the same memory address space to be shared by the CPU and GPU? If yes, explain how it can be shared. If not, explain how data will be transferred between CPU and GPU.
11. We are familiar with various search algorithms such as Breadth First Search (BFS) and Depth First Search (DFS). If you are asked to pick a specific search algorithm to be run on a machine that is limited by the amount of physical memory available, which search algorithm would you prefer and why?
12. What is meant by a ‘topological sort’ of a directed acyclic graph? Can you write an algorithm for it? If you run the topological sort algorithm on a directed graph which may contain cycles, what can you expect?
13. We are all familiar with algorithms for finding the shortest path in a graph such as Dijkstra’s algorithm, which belongs to a category known as greedy algorithms. Can you explain what is meant by a greedy algorithm? Is it possible to come up with one for all programming problems?
14. What is the difference between the algorithmic complexity of classes P and NP? Given any problem, is it always possible to come up with an algorithm of complexity class P to solve it? If not, can you provide an example of a problem that is not known to have a solution of complexity class P?
15. Given a sentence in the English language consisting of words, how will you reverse the order of words in that sentence? For example, given the input sentence “Source control code system used by Linux kernel is Git,” the program should output the sentence “Git is kernel Linux by used system code control source.”
16. You are given a sorted array A of integers. You are asked to find out whether there are two indices ‘i’ and ‘j’ such that A[i] + A[j] = 0. What is the complexity of your solution?
17. What is the order of complexity of the following operations on a singly linked list: (a) Insertion (b) Deletion (c) Delete-minimum, and (d) Search for a specific value?
18. Is it always possible to transform a recursive function into a function containing an iterative loop? If not, give an example of when this transformation is not possible.
19. If you are given a single threaded application, and are asked to reduce its execution time, what would your approach be for the same?
20. Consider the following problem: you are given the task of identifying all the primes that exist between 1 and 8000000. You are also given a routine known as IsPrime, which when given an integer, returns true if it is a prime; else, it returns false. Given that you have access to a 64-core multi-processor system, how would you parallelise your application?
21. In problem (19), you were asked to find all primes that exist between 1 and 8000000. Now, if you are asked to find all primes that exist between 1 and 100, would your solution change?
22. What is the ‘time of check to time of use’ (TOCTOU) race condition? Given the potential for TOCTOU race conditions in file systems, what are the ways of preventing them?
23. Given the wide variety of synchronisation mechanisms available on Linux such as mutex, spinlock, semaphore, reader-writer lock and RCU, how would you decide which synchronisation mechanism to use for protecting a critical section of code in your application?
24. Given a binary search tree T containing N integers, and a value ‘k’, can you write an algorithm to find the predecessor and successor of ‘k’ in the tree T? Can there be a situation where the tree ‘T’ does not contain the predecessor to ‘k’? Can there be a situation where the tree ‘T’ does not contain the successor to ‘k’?
25. Consider a multi-threaded program executing on a multi-core system with N threads. Now, one of the threads in the program receives a SIGSEGV (segmentation violation) due to referencing an illegal memory address. What would happen to the application?
26. What is the worst case time complexity of the following operations on stack: (a) Insertion (b) Deletion (c) Delete-minimum, and (d) Search for a specific value?
27. What is the worst case complexity of a sorting algorithm? Is it possible to have a sorting algorithm which can sort in linear time? If yes, what are the additional assumptions that need to be enforced to ensure sorting in linear time?
28. You are asked to compute the factorial of a number N, where N is very large. You have the choice of either: (a) using recursion to compute the factorial, or (b) of remembering the solutions of earlier iterations in a memorisation table and computing the result by using the formula factorial (N) = factorial(N-1) * N by looking up the table for the value of factorial (N-1). Which of these two choices would be efficient in terms of: (a) the time complexity of the solution, or (b) the space complexity of the solution?
29. Given an array of N integers, how many comparisons are needed for finding the maximum? If you are asked to find both the minimum and maximum, how many comparisons are needed?
30. We are all familiar with the problem of a deadlock in concurrent code and we know how it can be detected and prevented. Assume that you have a concurrent application in which there is no circular wait among the threads. We know that if there is no circular wait, then the application cannot suffer from deadlock. Is it possible for the application to suffer from ‘livelock’? If yes, explain how?
    If you have any favourite programming questions/software topics that you would like to discuss on this forum, please send them to me, along with your solutions and feedback, at sandyasm_AT_yahoo_DOT_com. Till we meet again next month, happy Diwali and happy programming!