Katkat
Back

Solve two interview coding problems

MavenclinicSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to handle currency conversion using graph pathfinding (multiplicative weights) and implement a custom pagination algorithm that balances item distribution while respecting original ordering.

Part 1: Currency Arbitrage

You are given a list of exchange rates as a list of tuples (source, target, rate). Implement a function can_convert(source_currency, target_currency, rates) that returns the maximum conversion rate possible between two currencies. If no path exists, return 0.0.

Example: Input: rates = [('USD', 'EUR', 0.9), ('EUR', 'GBP', 0.8)], src = 'USD', dst = 'GBP' Output: 0.72

Part 2: Diversity-Aware Pagination

You have a list of items, where each item has an id and a category. Write a function get_page(items, page_size, page_number) that returns a page of items. The constraint is that the result must be "diverse": no two items with the same category should appear consecutively in the paginated view, even if the original list is unsorted. If the constraint cannot be met, return the items as they naturally appear in the list.

Example: Input: items = [{'id': 1, 'cat': 'A'}, {'id': 2, 'cat': 'A'}, {'id': 3, 'cat': 'B'}], page_size = 2, page_number = 0 Output: [{'id': 1, 'cat': 'A'}, {'id': 3, 'cat': 'B'}]

Constraints

  • Part 1: Graph may contain cycles (but assume no profitable arbitrage loops > 1.0).
  • Part 2: page_size is between 1 and 50; total items can be up to 10,000.
  • Maintain stability for items of different categories.

Hints

Hint 1

For Part 1, treat currencies as nodes and exchange rates as weighted directed edges, using a modified BFS or Dijkstra's algorithm to track the product of rates.

Hint 2

For Part 2, first filter the input to create a rearranged list that satisfies the 'no consecutive categories' rule using a greedy approach or a frequency-based priority queue.

Hint 3

For Part 2, remember that pagination happens *after* the transformation, so you must pre-process the entire list to ensure the sequence property holds across page boundaries.

Follow-up questions

  • How would you detect if a currency loop exists where you can gain money (i.e., product of rates > 1)?
  • In the pagination problem, what is the time complexity if you need to ensure global diversity across an infinitely streaming list?
  • How would you modify the graph algorithm if exchange rates were updated in real-time?