Codesport

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 2016 New Year wishes to the American electorate. Essentially, your task is to organise the search engine query results on a timeline. What are the challenges in organising the Web search engine query results temporally?
(6) You are asked to write a script that can list the set of processes currently running on your Linux machine and satisfy the criterion that they have been running for a time > T, where T is provided as an argument to the script, in seconds. This should include all the processes in your system, including those of other users and system processes.
(7) You are given an array A of N integers. These integers represent the average yearly rainfall measured in centimetres, in your city for the last N years. Your function should output the frequency of the unique values of the rainfall measures contained in the input array. For instance, if you are given as input [5, 10, 5, 20, 10, 35, 5, 10], your function should output the following result:
5 -> 3
10 -> 3
20 -> 1
35 -> 1
Essentially, for each unique value in the input array, output how many times it occurs in the given array. What is the time complexity of your algorithm? Now assume that the input array A cannot fit in main memory. In that case, how would you modify your approach to find the frequency distribution of array A?
(8) In bank cheques, a customer needs to write the amount of the cheque both in numbers and in words. For instance, if the cheque being issued is for Rs 3238 in numerical form, the customer also needs to provide a textual description of the amount –‘Three thousand two hundred and thirty eight’. You are asked to write two functions: (a) function cheque_itoa, which takes as input a positive integer, and outputs a string which contains the textual description of the input integer; (b) function cheque_atoi, which takes as input a string containing the textual description of the cheque amount and returns the numerical integer of this amount.
(9) You are given an array of N integers. You are asked to find the largest element which appears an even number of times in the array. What is the time complexity of your algorithm? Can you do this without sorting the entire array?
(10) Given a stream of input integers in real-time, you are asked to find the minimum element in the stream at any point in time. What is the complexity of your algorithm? How would your solution change, (a) if you are asked to find both minimum and maximum elements in the stream at any point in time? (b) If you are asked to find both the first minimum and second minimum in the stream at any point in time?
(11) Given a singly linked list, you are asked to write a function to find the middle element of the linked list. You are not given the length of the list. How would you modify your solution if the given linked list is a singly linked circular list?
(12) You are given four strings — S1, S2, S3 and S4. S1 is a large string and S2, S3, and S4 are comparatively smaller. You are asked to find the smallest length sub-string ‘t’ of S1 such that it contains S2, S3 and S4 as its sub-strings. For example, given string S1 ‘BytheriversofBabylon’, and S2=er, S3=of and S4=so, your function should return ‘ersof’. How would you modify your solution if you are now told that the ordering of S2, S3 and S4 should be maintained in the sub-string ‘t’ (i.e., S2 should appear before S3, and S3 should appear before S4 in sub-string ‘t’)?
(13) You are given a large text ‘T’ and a small sub-string ‘S’. You are asked to find out whether sub-string S appears anywhere in T. What is the complexity of your solution? How would your solution change if you are asked to now find all the occurrences of ‘S’ in the large string ‘T’? Now, what is the time complexity of your algorithm?
(14) You are given an HTML page containing texts, ads, images, banners, menu boxes, etc. Can you write a script to extract all the text contained in the Web page?
(15) You are given a stream of incoming words. They are coming in at the interval of 1s. At any second, you are asked to find the 10 most repeated words seen in the stream so far. What is the complexity of your algorithm? How would you modify your solution, if you are also asked to print the occurrence frequencies for the 10 most repeated words seen in the stream up to that point in time? What is the time and space complexity of your solution?
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 programming!