Design an algorithm that outputs the time-stamps

Assignment Help Computer Engineering

Reference no: EM133218014

Purpose: Practice algorithm design and the use of data structures. This problem was an interview question! Consider a situation where your data is almost sorted-for example you are receiving time-stamped stock quotes and earlier quotes may arrive after later quotes because of differences in server loads and network traffic routes. Focus only on the time-stamps. To simplify this problem assume that each time-stamp is an integer, all time-stamps are different, and for any two time-stamps, the earlier time-stamp corresponds to a smaller integer than the later time-stamp. The time-stamps arrive in a stream that is too large to be kept in memory completely. The time-stamps in the stream are not in their correct order, but you know that every time-stamp (integer) in the stream is at most hundred positions away from its correctly sorted position. Design an algorithm that outputs the time-stamps in the correct order and uses only a constant amount of storage, i.e., the memory used should be independent of the number of time-stamps processed. Tip: solve the problem using a heap.

Reference no: EM133218014

Questions Cloud

Four rules for credit rating and each customer : Enter formulas/functions for rules 1-4 in columns I, J, K, and L respectively. These formulas will demonstrate if the customer credit is approved based on each

Evaluate various platforms for characteristics : Evaluate various platforms for characteristics, advantages, and weaknesses for hosting a web-based software application. Consider the following in your

Provide an overview of your data : Provide an overview of your data, business/organization, and use case Analyze the data and give reasoning of why you think it is useful to the business

Draw a deterministic and non-deterministic finite automate : Draw a deterministic and non-deterministic finite automate which accept AA and BB at the end of a string containing A, B in it, e.g., ABABABAA but not AAABBBABA

Design an algorithm that outputs the time-stamps : Design an algorithm that outputs the time-stamps in the correct order and uses only a constant amount of storage, i.e., the memory used should be independent

Describe what are the sub-problems here : Describe what are the sub-problems here and what is the size/count of sub-problems and Describe which inputs to the knapsack problem (value and size)

Average wages of females : Does the earnings gap between the average wages of females and the average wages of males prove labor market discrimination? Why or why not?

Impacts on success of an individual business organization : An assessment of extent to which working in international environment impacts on the success of an individual business organization".

Which of the predictors are statistically significant : Which of the predictors are statistically significant in each model? If you wanted to create the most parsimonious model (i.e., the one that did the best job

User Account

All Pages