Solve two interview coding problems
Company: Mavenclinic
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Quick Answer: This question evaluates graph traversal and pathfinding with weighted edge composition for currency conversion reachability, and sequence partitioning with diversity-aware pagination for preserving ordering and maximizing distinct identifiers, testing skills in modeling relationships, reachability, aggregation of multiplicative metrics, and constrained list processing. It is commonly asked in technical interviews in the Coding & Algorithms domain to assess practical application of data-structure and algorithmic concepts (graph algorithms and list processing/data partitioning), emphasizing efficiency, correctness, and pragmatic reasoning about reachability and ordering rather than purely theoretical understanding.
Shortest Currency Conversion Path
Constraints
- Rates are directed
Examples
Input: ([('CAD', 'USD', 0.88), ('USD', 'JPY', 2000.0)], 'CAD', 'JPY')
Expected Output: {'path': ['CAD', 'USD', 'JPY'], 'rate': 1760.0}
Explanation: Two-edge conversion.
Input: ([('A', 'B', 2.0), ('A', 'C', 3.0), ('C', 'B', 4.0)], 'A', 'B')
Expected Output: {'path': ['A', 'B'], 'rate': 2.0}
Explanation: Chooses fewest conversions.
Input: ([], 'A', 'B')
Expected Output: None
Explanation: Unreachable.
Hints
- BFS finds the path with the fewest edges in an unweighted graph.
Paginate Listings by Payer Diversity
Constraints
- records are pre-sorted
Examples
Input: ([{'payer_id': 'a', 'listing_id': 1}, {'payer_id': 'a', 'listing_id': 2}, {'payer_id': 'b', 'listing_id': 3}, {'payer_id': 'c', 'listing_id': 4}], 2)
Expected Output: [[1, 3], [2, 4]]
Explanation: Prioritizes distinct payers per page.
Input: ([], 3)
Expected Output: []
Explanation: No records.
Input: ([{'payer_id': 'a', 'listing_id': 1}, {'payer_id': 'a', 'listing_id': 2}], 3)
Expected Output: [[1, 2]]
Explanation: Fills when diversity unavailable.
Hints
- Build one page at a time: first pass takes unseen payers, second pass fills leftover capacity.