In this month’s col­umn, we fea­ture a set of com­puter sci­ence in­ter­view ques­tions.

OpenSource For You - - CODE SPORT -

We con­tinue our dis­cus­sion on com­puter sci­ence in­ter­view ques­tions in this col­umn, fo­cus­ing on al­go­rithms and data struc­tures. (1) You have been given all the stock mar­ket trans­ac­tions made by a user in his stock ex­change ac­count, as he bought and sold shares. Each trans­ac­tion con­sists of de­tails like, (a) the name of the com­pany, (b) type of trans­ac­tion – whether a pur­chase or sale, (c) num­ber of shares bought/sold, (d) price of each share bought/sold, and (e) the date of the trans­ac­tion. You also have ac­cess to stock mar­ket in­for­ma­tion like the price of each com­pany’s stock at the end of ev­ery 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 pro­gram, which ex­am­ines the clos­ing price of the pre­vi­ous day’s stock mar­ket prices, and pro­vides rec­om­men­da­tions to the user on which of his equity hold­ings he can sell that day for a profit of 10 per cent or more. Your rec­om­men­da­tion would con­tain the com­pany’s name, num­ber of shares to sell, the sale price and the per­cent­age of profit that the user will make if he sells at that price. What is the time com­plex­ity of your al­go­rithm, as­sum­ing that you are given N trans­ac­tions in to­tal, cor­re­spond­ing to M dif­fer­ent com­pa­nies? (2) Con­sider the above ques­tion. Stock mar­kets are quite volatile and the price of com­pany stocks can fluc­tu­ate con­sid­er­ably dur­ing the day. You are now told that in­stead of us­ing the pre­vi­ous day’s clos­ing price, your ap­pli­ca­tion should of­fer in real-time, the fluc­tu­at­ing price of the stocks that the user holds, at any given point in time, and then rec­om­mend which stocks the user can sell at that point of time for a 10 per cent profit. As­sume that you have stock mar­ket prices avail­able as a real-time feed at 60-se­cond in­ter­vals. How would you mod­ify your so­lu­tion

for Ques­tion (1) to sat­isfy this cri­te­rion? (3) You are given an ar­ray of N records con­tain­ing em­ployee in­for­ma­tion, in­clud­ing the em­ployee’s date of join­ing, name, ad­dress and salary. You are told to sort the ar­ray in as­cend­ing or­der with re­gard to the date of join­ing. It is pos­si­ble that mul­ti­ple em­ployee records may have the same join­ing date. In that case, the orig­i­nal or­der of th­ese records should be re­tained in the fi­nal sorted ar­ray. (a) If you are told that there is no re­stric­tion on the ad­di­tional space that your al­go­rithm can use, what would be your so­lu­tion? (b) If you are told that you can only use con­stant ad­di­tional stor­age space, what would be your so­lu­tion? (4) In Ques­tion (3) above, it is im­plic­itly as­sumed that the ar­ray of N records can fit in the main mem­ory. Now con­sider the case where the ar­ray of records is so large that the en­tire ar­ray can­not fit in the main mem­ory. Un­der such a con­di­tion, you are asked to sort the ar­ray in as­cend­ing or­der on the disk, with­out chang­ing the orig­i­nal or­der for those items whose date of join­ing is the same. What is the time and space com­plex­ity of your so­lu­tion? (5) You are given a search query and you can use any of your favourite Web search en­gines to find the query’s re­sults. Web search en­gines use their own rank­ing al­go­rithms to rank the query search re­sults. How­ever, you are asked to ap­ply a fil­ter on top of the search en­gine query re­sults such that the re­sults are or­dered tem­po­rally. For ex­am­ple, con­sider an ex­am­ple query of the form: ‘Don­ald Trump US Pres­i­den­tial elec­tion’. Given a set of search en­gine re­sults for this query which will con­tain news ar­ti­cles, events, etc, you need to sort them tem­po­rally. For in­stance, a query re­sult link on the news story from July 2015 de­scrib­ing Trump’s in­ten­tion to run should be ranked be­fore the news story fea­tur­ing his

Newspapers in English

Newspapers from India

© PressReader. All rights reserved.