Day 4/90: HFT Prep – Navigating Rotated Arrays & Memory Reallocations

Watch the Day 4 raw log here: https://youtu.be/TNzKKlwQrYM

The Pursuit of Discipline

Day 4 is about refining the "Signal." In high-frequency trading, every nanosecond counts, and today I focused on how both our algorithms and our choice of data structure management impact latency. I’m continuing to use my digital tablet setup to practice "whiteboarding" my thought process—it’s a raw way to ensure I can communicate complex logic clearly under pressure.

The "Rubber Duck" Breakthrough

As always, Mr. Pengu was there to "interview" me as I worked through the logic. I spent some time troubleshooting my recording setup to ensure a steady frame rate for the live coding segments.

Technical Deep Dive: Search in Rotated Sorted Array

I tackled the Search in Rotated Sorted Array problem (LeetCode 33).

1. The Problem Statement

Given an integer array nums sorted in ascending order with distinct values, which is then possibly rotated at an unknown pivot index k, find the index of a target value.

Brute Force (O(N)): A linear search checking every element.
HFT Optimized (O(log N)): Even in a rotated array, one half (either left or right of the midpoint) is always sorted. By identifying the sorted half and checking if the target lies within its range, we maintain binary search efficiency.

2. The Logic

We calculate the midpoint using the overflow-safe formula: low + (high - low) / 2.
Identify which half is sorted by comparing nums[low] with nums[mid].
If the left half is sorted, check if the target is within that range to decide where to move the pointers.
Repeat the logic for the right half if the left isn't sorted.

3. The HFT "Gotcha": `std::vector::reserve`

I spent about 30 minutes analyzing the hidden costs of std::vector.

The Problem: Dynamic resizing (vector doubling) is expensive because it requires reallocating memory and copying all existing elements.
The Solution: Use v.reserve(n) to allocate memory upfront. This prevents multiple reallocations and unnecessary data movement during push_back operations, which is critical for low-latency systems.

Current Status: 4/90 Days Complete

I'm starting to see the connections between basic DSA and hardware-level performance. Mastering these reallocations and boundary conditions is the only way to handle the high-pressure questions asked by firms like Graviton or Tower Research.

#HFT #CPP #BinarySearch #90DayChallenge #MAIT #FedoraLinux