In this month’s column, we feature a set of computer science interview questions.

We continue our discussion on computer science interview questions in this column, focusing on algorithms and data structures. (1) You have been given all the stock market transactions made by a user in his stock exchange account, as he bought and sold shares. Each transaction consists of details like, (a) the name of the company, (b) type of transaction – whether a purchase or sale, (c) number of shares bought/sold, (d) price of each share bought/sold, and (e) the date of the transaction. You also have access to stock market information like the price of each company’s stock at the end of every day. The user would like to know which of his shares he can sell at a profit of 10 per cent or more, on each day. You are asked to write a program, which examines the closing price of the previous day’s stock market prices, and provides recommendations to the user on which of his equity holdings he can sell that day for a profit of 10 per cent or more. Your recommendation would contain the company’s name, number of shares to sell, the sale price and the percentage of profit that the user will make if he sells at that price. What is the time complexity of your algorithm, assuming that you are given N transactions in total, corresponding to M different companies? (2) Consider the above question. Stock markets are quite volatile and the price of company stocks can fluctuate considerably during the day. You are now told that instead of using the previous day’s closing price, your application should offer in real-time, the fluctuating price of the stocks that the user holds, at any given point in time, and then recommend which stocks the user can sell at that point of time for a 10 per cent profit. Assume that you have stock market prices available as a real-time feed at 60-second intervals. How would you modify your solution

for Question (1) to satisfy this criterion? (3) You are given an array of N records containing employee information, including the employee’s date of joining, name, address and salary. You are told to sort the array in ascending order with regard to the date of joining. It is possible that multiple employee records may have the same joining date. In that case, the original order of these records should be retained in the final sorted array. (a) If you are told that there is no restriction on the additional space that your algorithm can use, what would be your solution? (b) If you are told that you can only use constant additional storage space, what would be your solution? (4) In Question (3) above, it is implicitly assumed that the array of N records can fit in the main memory. Now consider the case where the array of records is so large that the entire array cannot fit in the main memory. Under such a condition, you are asked to sort the array in ascending order on the disk, without changing the original order for those items whose date of joining is the same. What is the time and space complexity of your solution? (5) You are given a search query and you can use any of your favourite Web search engines to find the query’s results. Web search engines use their own ranking algorithms to rank the query search results. However, you are asked to apply a filter on top of the search engine query results such that the results are ordered temporally. For example, consider an example query of the form: ‘Donald Trump US Presidential election’. Given a set of search engine results for this query which will contain news articles, events, etc, you need to sort them temporally. For instance, a query result link on the news story from July 2015 describing Trump’s intention to run should be ranked before the news story featuring his