How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Compute discounted prices and full-price indices

Q: Compute discounted prices and full-price indices

This question evaluates array-processing skills, competency with next-smaller-or-equal element patterns, and the ability to compute aggregated results under ordering constraints.

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given an array `prices` of length \(n\). Items are sold from left to right, and each item’s final selling price is computed as follows: For item \(i\): - Find the **first** index \(j > i\) such that `prices[j] <= prices[i]`. - If such \(j\) exists, the final price is `prices[i] - prices[j]`. - Otherwise, the final price is `prices[i]` (sold at full price). You must output **two lines**: 1. The **total** of all final prices. 2. All indices (0-based) of items that are sold at **full price**, in increasing order. ### Input - Integer \(n\) - Array `prices` of length \(n\) ### Output - Line 1: integer total final price - Line 2: space-separated 0-based indices sold at full price (print an empty line if none) ### Example (informal) If `prices = [5, 1, 3]`, then item 0 is discounted by 1 (final 4), item 1 has no qualifying item to its right (final 1), item 2 has none (final 3). Total = 8, full-price indices = `1 2`.

Quick Answer: This question evaluates array-processing skills, competency with next-smaller-or-equal element patterns, and the ability to compute aggregated results under ordering constraints.

You are given an integer n and an array prices of length n. Items are processed from left to right. For each item i, find the first index j > i such that prices[j] <= prices[i]. If such an index exists, the final selling price of item i is prices[i] - prices[j]; otherwise, the item is sold at full price and its final selling price is prices[i]. Compute the total of all final selling prices and identify every 0-based index that is sold at full price. For this function-based version, return a tuple (total, indices), where indices is the list of full-price indices in increasing order.

Constraints

0 <= n <= 2 * 10^5
len(prices) == n
0 <= prices[i] <= 10^9
Use a 64-bit integer type for the total in languages with fixed-size integers

Examples

Input: (3, [5, 1, 3])

Expected Output: (8, [1, 2])

Explanation: Item 0 is discounted by prices[1] = 1, so its final price is 4. Items 1 and 2 have no qualifying item to their right, so they are sold at full price. Total = 4 + 1 + 3 = 8.

Input: (5, [8, 4, 6, 2, 3])

Expected Output: (15, [3, 4])

Explanation: Final prices are [4, 2, 4, 2, 3]. Items at indices 3 and 4 have no smaller-or-equal item to their right.

Input: (4, [5, 5, 5, 5])

Expected Output: (5, [3])

Explanation: Each of the first three items is discounted by the next 5, so their final prices are 0. The last item has no discount and remains 5.

Input: (4, [1, 2, 3, 4])

Expected Output: (10, [0, 1, 2, 3])

Explanation: No item has a smaller-or-equal value to its right, so every item is sold at full price.

Input: (1, [7])

Expected Output: (7, [0])

Explanation: With only one item, there is nothing to the right, so it is sold at full price.

Input: (0, [])

Expected Output: (0, [])

Explanation: There are no items, so the total is 0 and there are no full-price indices.

Hints

Try scanning from left to right while keeping track of earlier items that still have not found a discount.
If the current price is less than or equal to some previous prices, it becomes the first valid discount for those previous items.

Quick Overview

This question evaluates array-processing skills, competency with next-smaller-or-equal element patterns, and the ability to compute aggregated results under ordering constraints.