Facebook Pixel

Amazon Online Assessment 2021 (OA) - Economy Mart

EMart is a big name in the online shopping world; they're known for showing the least pricey products first. There's an ongoing process of shifting all of their product data to a new database. The customers shopping on our digital platform will now interact with this new database to see products.

EMart has a unique way to show items;

  • When a customer sees the first item listed, it's the piece with the lowest price from the entire database.
  • When a client is currently on the Kth lowest-priced product, the next item they'll see would be the (K+1)th least expensive product.
  • And if there's more than one product at the same price, they're listed in ascending alphabetical order.

Discussions on the database include two types of entries:

  • A row may start with "INSERT," followed by the name of the item and its price in a string format. This string format means it's a sequence of characters, and it's telling an integer number, so we might need to convert it to be used. This row type means that a product has been added to the database.
  • If a row begins with "VIEW," it means that a customer just viewed a product. The next two entries in this row type contain "-", which can be safely ignored. When a customer views an item, one thing is guaranteed: at least one product has been added to the database.

Now, during this data transfer, a customer, not having any idea about this process, logs into the website and starts shopping around some Economy Mart's items. Suppose we have the server log that's recording events sequentially. In that case, we have to figure out what items were shown to this unsuspecting customer.

Relevant Amazon OA Problems:

Input

  • entries: each row in the matrix represents an individual log entry

Output

answers to each of the "VIEW" queries

Examples

Example 1:

Input:

entries = INSERT milk 4
INSERT coffee 3
VIEW - -
INSERT pizza 5
INSERT gum 1
VIEW - -

Output: coffee coffee

Explanation:

Example 2:

Input:

entries = INSERT fries 4
INSERT soda 2
VIEW - -
VIEW - -
INSERT hamburger 5
VIEW - -
INSERT nuggets 4
INSERT cookie 1
VIEW - -
VIEW - -

Output: soda fries hamburger nuggets hamburger

Explanation:

Constraints

  • 1<=n<=10^5
  • 1<=|itemName|<=10 (The name of each item will be 1 to 10 characters long)
  • All itemName strings are distinct
  • 1<=price<=10^9
  • k<=length of the database (That is, there will always be at least k items in the database when the customer is viewing for the kth time)

Try it yourself

Solution

Invest in Yourself
Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.
Go Pro