Codesport

Over the past few months, we have been discussing natural language processing and insight-centric storage systems. This month, we take a break from that discussion to explore a bunch of computer science interview questions. Let us start off on a light-hearted note.
1. What is the KISS Principle in computer science?
2. File systems and database systems both act as containers of user data, albeit in different ways. Can you differentiate the two in terms of the consistency guarantees they provide to the end user?
3. Consider a file ‘1.txt’ on the same file system, say ext4, on Linux, which is opened by two different processes. Both these processes modify overlapping regions of the file and close their individual file handles. While each process has its own file handle on which it operates, how many file descriptors are actually created for this file in the file system in the kernel? If both process1 and process2 write ‘a’ and ‘b’ as the value at logical offset ‘0’ of the file ‘1.txt’, what would actually be stored when these processes close their descriptive handles?
4. When the user invokes ‘ls’ on the root directory of your file system, can you explain what Linux system calls get invoked internally?
5. What is a FUSE file system? How is it different from a kernel level file system module? Can you reimplement the Linux ext4 file system as a FUSE module? If not, why not?
6. Instead of having local storage on a hard disk connected to the device, you are asked to design a file system which will store its data on a public cloud storage provider like Amazon S3, which has an object interface. The file system needs to provide normal file access semantics to local applications, but has to store its durable data in the cloud. What are the design considerations when creating such a system?
7. We all know that databases support ACID semantics where the ‘A’ in ACID stands for atomicity. Atomicity means that either the transaction completes successfully in its entirety or it appears not to have started at all. For example, consider the simple example of transferring money from your account to your father’s account. Successful completion means that the money is debited from your account and credited to your father’s account. So if there is a failure while the transaction is in progress, say after the money has been debited from your account but before it is credited to your father’s account, then the transaction is aborted and the effect to the end user is as if the transaction never started at all. This means that it appears as if the money was never debited from your account. Can you explain the mechanism by which databases support such failure atomicity? Think of how it would be possible to roll back a partially completed transaction.
8. What is a gossip protocol? How would you implement it in a local network of computers?
9. The conventional wisdom with regard to traditional storage media is that interrupt based signalling of IO completion is more efficient than polling. Can you think of a situation where polling may be better than interrupt based IO completion signalling? There is an interesting research paper which discusses this issue in detail, available at https://www.usenix.org/legacy/events/fast/tech/full_papers/Yang.pdf
10. What are content addressable memories as opposed to traditional random access memories?
11. You are asked to write a program which supports the following operations:
(a) Encrypts the input data and stores it as a file
(b) Decrypts the data it reads from a file and displays it
Can you write a small code snippet to do the same? If you are told that your program will execute on a processor, which supports AES-NI instructions, how will you modify your code to take advantage of this functionality?
12. Given an array of N integers and a number ‘k’, write a function which returns true if the array has a contiguous sub-sequence, which sums up to exactly ‘k’? How would your code change if you are asked to return the start and end of the contiguous sub-sequence, if such a sub-sequence exists in the array. What is the time complexity of your solution?
13. You are given an array of N integers and asked to return a popular item in the array, if such a popular item exists in the array. A popular item is an element which repeats at least N/4 times in the array. How would you modify your code if you are asked to return all such popular elements? What is the time and space complexity of your solution?
14. You are given an array of N integers and asked to write a program to find the maximum difference between two array elements A[i] and A[j] such that i < j. How would your solution change if the condition that ‘i’ needs to be smaller than ‘j’ need not hold true for your program?
15. You are given an array of N elements, where each element is a task. Each task has a priority, which is marked as either High, Medium or Low. You are asked to rearrange the array such that all tasks which have the priority value ‘High’ appear first, followed by tasks whose priority is ‘Medium’, and then by tasks whose priority is ‘Low’. You are asked to do this in-place with constant additional storage. What is the time complexity of your solution?
16. You are given a text file, which contains C/C++ code. The code has comments in it. The comments can be either single line or multi-line. Single line comments begin with a ‘//’ character and do not span beyond a line. Multi-line comments are enclosed by ‘/*’ and ‘*/’ characters. Comments cannot nest inside each other. You are asked to write a code snippet which strips out the comments from the code in the input file.
17. You are given a binary search tree containing N integers. You are asked to return the ‘kth’ largest element in the binary search tree. Write a code snippet to do this. How would your solution change if you are asked to return the ‘largest’ element and the ‘smallest’ element in the binary search tree? What is the time and space complexity of your solution?
18. You are given a list of N users along with their login and logout times on the computer, over a period of one week. You are asked to write a program to:
a. Find the time when the number of users that were logged into the computer was the maximum
b. Find the time when the number of users that were logged into the computer was the minimum
c. Find the user who was online for the maximum cumulative time over the one week
d. Find the user who was online for the longest single duration slot over that week
What is the data structure you would use to represent the login, logout time intervals?
19. A string is said to be unique if no two characters in the given string are identical. Given a set of N strings, you are asked to find all unique strings present in the set.
20. Given a string, find all the sub-strings of that string which are palindromes.
21. You are given two binary trees and asked to determine whether the two trees are identical both in terms of structure and the elements contained in them. Write a program to do this. What is the time and space complexity of your solution? How would your code change if you are told that the binary trees are actually binary search trees?
22. If you are asked to write a sort routine to replace the sort utility in UNIX/Linux, which sorting algorithm would you use and why?
23. If you are asked to design a data structure which needs to support (a) insert, (b) delete, (c) search, (d) find-minimum, and (e) find-maximum, which data structure would you use and why?
24. What is a lock-free data structure? Can you give an example of one?
25. The two terms ‘concurrency’ and ‘parallelism’ are often mistaken for each other in computer science. Can you differentiate between the two with appropriate examples of where concurrency exists and where parallelism does?
If you have any favourite programming questions or 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 programming!