Google

PART 1: ALGORITHMIC PROBLEM - CURRENCY ARBITRAGE (NEGATIVE CYCLE DETECTION) BASE PROBLEM You are building the core algorithmic engine for a quantitative trading firm. You are given a 2D matrix of `N` currencies, where `rates[i][j]` represents the exchange rate from currency `i` to currency `j`. Task: Design an algorithm to determine if an arbitrage opportunity exists—a sequence of trades where you start with 1 unit of a currency and end up with more than 1 unit of that same currency (i.e., the product of the rates along a cycle is strictly greater than 1.0). Since graph algorithms usually work with sums rather than products, what mathematical transformation must you apply to the edge weights, and which algorithm (like Bellman-Ford or SPFA) allows you to detect this specific type of cycle in O(V * E) time? FOLLOW-UP 1 In a live market, exchange rates update millions of times per second. Running a full O(V * E) Bellman-Ford traversal on every single tick is far too slow. Assuming only a few edge weights change per microsecond, how do you design a dynamic graph algorithm or incremental cycle detection mechanism to maintain the shortest path tree and detect newly formed cycles without recalculating from scratch? FOLLOW-UP 2 To achieve ultra-low latency, this engine is written in C++. Standard `std::vector` or pointer-based graph representations cause cache misses and dynamic allocation overhead, slowing down the Shortest Path Faster Algorithm (SPFA) queue. How do you design an allocation-free, flat-array adjacency list and a lock-free circular buffer for the SPFA queue to ensure strictly sequential memory access and maximize L1 CPU cache hits? ------------------------------------------------ PART 2: SYSTEM DESIGN - DISTRIBUTED AD CLICK AGGREGATOR BASE PROBLEM You are designing the billing and analytics backend for a global advertising network. The system must ingest 5 million ad click events per second from user browsers, aggregate them by `ad_id` and `campaign_id`, and update the advertiser's live billing dashboard within 60 seconds. Design the high-level stream processing architecture (e.g., using Kafka and Flink). FOLLOW-UP 1 Advertisers will refuse to pay if they are billed for duplicate clicks (e.g., a user double-clicking, or a mobile client retrying a request due to a dropped connection). How do you implement global "exactly-once" processing and deduplication at this massive scale? Discuss the use of distributed state stores, Bloom Filters, and idempotency keys to ensure a click is never double-counted. FOLLOW-UP 2 The data science team wants to join this real-time click stream with the historical user profile database (containing billions of rows) to determine which user demographics are clicking the ads in real-time. Performing synchronous database lookups over the network for 5 million events per second will completely collapse the pipeline. How do you implement a "Stream-Table Join" using partitioned local state stores (like embedded RocksDB) to perform these joins with zero network overhead? ------------------------------------------------ PART 3: AI / ML DISCUSSION QUESTIONS In high-frequency trading or time-series machine learning models, why is mitigating "look-ahead bias" critical, and how do you implement purged or embargoed K-fold cross-validation to prevent data leakage? What is the fundamental difference between standard Model Weight Quantization (e.g., INT8/INT4) and KV Cache Quantization during LLM inference, and how does the latter specifically target the memory bandwidth bottleneck of the decoding phase? Explain the "MoE (Mixture of Experts) Routing Collapse" problem during training. How do mechanisms like load-balancing loss prevent all tokens from being routed to a single, over-utilized expert network? When deploying a PyTorch anomaly detection model to a C++ backend for millisecond-level network traffic analysis, what are the compilation steps and latency differences between running the native LibTorch runtime versus an optimized TensorRT engine?