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

**Watch the Day 4 raw log here:** [https://youtu.be/TNzKKlwQrYM](https://www.google.com/search?q=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