← Navan Interview Insights

Navan·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Navan coding screen for a software engineer role. One algorithmic problem, pretty focused, nothing wild about the setup itself but the problem had a small gotcha that I almost missed.

Questions Asked (1)

Q1

Given an array of positive prices and a discount percentage, apply the discount only to the single most expensive item (first occurrence if there are ties), then return the floor of the total sum.

Algorithms & Data Structures
Author's notes

My first instinct was to sort, which would've blown the O(n) requirement.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem constraints and edge cases (e.g., empty array, ties, discount range). Then, outline an efficient algorithm: find the index of the maximum price (first occurrence), compute the total sum, subtract the discount amount from that item, and return the floor of the result. Finally, discuss time and space complexity and test with examples.

Pro tip: Mention that you can compute the total sum and the maximum in a single pass, and that using integer arithmetic (e.g., price * (100 - discount) / 100) avoids floating-point precision issues when flooring.

1. Clarify requirements and edge cases

Ask about input constraints: array size, price range, discount percentage range, and behavior for empty arrays or ties. Confirm that the discount applies to the first most expensive item and that the result is floored.

2. Design the algorithm

Plan to find the index of the maximum price (first occurrence) and compute the total sum. Then calculate the discounted price for that item and adjust the total accordingly.

3. Implement efficiently

Write code that iterates through the array once to compute the sum and track the maximum and its index. Use integer arithmetic to avoid floating-point errors when applying the discount.

4. Test with examples

Walk through test cases: normal case, tie for maximum, single element, empty array, and discount of 0% or 100%. Verify that the floor is applied correctly.

5. Analyze complexity

State that the time complexity is O(n) and space complexity is O(1), as only a single pass is needed and no extra data structures are used.

Key Points to Mention

  • Handling ties by selecting the first occurrence of the maximum price.
  • Using integer arithmetic to avoid floating-point precision issues when applying the discount and flooring.
  • Edge cases: empty array, single element, discount of 0% or 100%.
  • Time complexity O(n) and space complexity O(1).
  • The importance of clarifying assumptions before coding.
  • Testing with examples to ensure correctness.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.