the wall

Today I have decided to start practicing a bit of c++ by diving straight into coding - an orderbook.

Why not rust! Well a lot of the borrow, trait-ish semantics are present in c++. With concepts and templates it make dynamic dispatch possible without v-table. A lot of companies in this space works in C++, so is gpu kernel. Also rust’s semantics adds an overhead, I have seen c++ and dealt with c before.

I have got the nasdaq gz file, learned the structure for procressing. I am taking an AI assisted approach.

It started off using conan to setup the repo, and then creating a skeleton for a proper project. Then was asked to prepare some skeleton code needed to know to build this.

This led me to understand:

• template
• lambda expressions, &, =, seen, &seen
• typename
• constexpr

Some of the concepts are understandable, sometime it looks more like rust. Some books on C++, start with borrowing and stuff.

Had an interview with arctic wolf today. I think i have given my worst interview till day.

Mostly because of talking.

First question was designing LFU. I have designed LRU before, didn’t practice it before interview. Its a simple struct with two things: cache of key to item and freq of int(freq) to a linked list of items.

First mess-up was agreing on having to traverse list to get the frequency and update to the newer freq line. And I resorted to using a map to find. It was in the end, I realized the list is a pointer of item.

The mistake was not writing out the Get and engage in a discussion, the cache[key] would give back the item, and item being a doubly linked node, the delete is always O(1)

The worst part was on the system design round. The ask was simple:

Ingestor and Processing pipeline and alerts with AI metrics and summarization.

The FR and Non-FR were produced on a screen. This was generally a drift in-terms of how I have practiced. In here, I would figure out the flow, and list the FR/Non-FR and then try and do the normal design to satisfy the Non-FR.

What went wrong was:

• Things started off with a deviation
  • I should have written down the FR seperately on the board
• I looked the FR and tried to dump everything from memory
• This led me to drawing incomplete structures, loosely connecting ideas, no explanation on the lines drawn
• In General I would go one FR at a time, drilling into failures and non-FR for each component in the FR.
• The interview-er kept prompting to complete the requirements one at a time
• In my head I was trying, to figure out what’s going wrong, rather than recalibrating
• While discussing infra, I missed addressing how to scale servers, rather I completely failed to discuss component failure, because I never drew the right components.

Solutions:

• Practice the already practiced problems from various angles and find a way to get to the flow we know for us.
• Think about the thoughts that are leading to freeze-up and find problems around it
• Shadown practice thinking about interview situation on-line and on-board.

Each of these interviews are a very costly learning experience. The number of accepts is so less, like 1 in 50-60 would probably turn up.

We are to handle two LC hards:

1. Trapping rain water
2. Largest Rectangle in histogram

Rain water trapping:

• height = [0,1,0,2,1,0,1,3,2,1,2,1] → 6

Lets try out step by step:

1. smallest thing
2. current state and relationship
3. add items and events
4. observe change in relationship (preserve/discard/compound)

• The question involves and array, and asks to query for aggregate.
• Water can overflow or be contained, which means some values can be preserved and some can be discarded

h = [0]

nothing here

h = [0] + [1]

• water would overflow on left
• so h[0] can be discarded

h = [1] + [0]

• water would flow to the right
• but there could be a higher value on the right

h = [1, 0] + [2]

• water can be contained
• running amount contained would be min(h[1], h[3]) * (gap) = 2
• I guess from here, we can discard 1 and 0, because both are less than new max and can not be used in a way walls are submerged

h = [2] + [1] + [0]

• water overflows, but from 1 to rest there can be bigger wall
• running max is 2
• I am thinking at this point we just keep acumulating index than values

h = [2, 1, 0, 1] + [3]

• again we encounter a number greater
• get rid of all values less < current max (3)

h = [3] + [2] + [1] + [2]

I think I should have started with general observations and not smallest thing. Or rather I shouldn;t have used the full example.

The general observation is, A pocket can be formed, when:

• the left tower > right tower, but there is a gap
• the right tower > left tower, but there is a gap
• towers of same height, but there is a gap

So,

• [5, 0, 6]
• [6, 0, 5]
• [2, 0, 2], and a curve
• [4, 1, 5]

We made an error in step 5, we didn’t account for displacement made by 1.

• h = [5], nothing
• next element can either be higher or smaller
• h = [5] + [1], holding water possible, but need to wait until next element to be greater or equal to 5

• h = [5] + [6], holding water not possible, because there is nothing on the left, and 5 could be discarded, because we already have a higher tower

• h = [5, 1] + [2], or h = [5, 1] + [6] or (h = [5, 1] + [0] and [5,1,0] + [6])
• last case, we don’t do anything, if its not the end.
• but in other cases, since 1 is < 2 or 6, it qualifies for a pocket
• for 5, 1, 2 - 1 can be discarded for ever, but 5 and 2 can remain
• for 5, 1, 6 - 5 and 1 can be discarded, since 6 will always tower
• for 5,1,0 - none can be discarded because its waiting for either end of arr or next element >=

so anytime an incoming element becomes greater than the last seen element, we compute the units. where units of water covered is equal to height * width, where

• height is the min of the difference in height of left and right side

• width is r - l - 1 (derieved manually)

• so when we calculate hight at 6 for (5,1,2,6), for 5 and 2 the (1,2) is computed
• then for (5,2,6), the upper rectangle is calculated, the previous sum contains the contribution caused by 1.

   _______█
  █       █
  █   2   █
  █_______█
  █ 1  █  █
  █ █  █  █
  └────────
  5 1  2  6

█

We took a break, after solving the next greater and next greater ii. Was watching F1 - probably for the 4th time.

I mean I dunno, if it takes eons to become good at something, I get the sacrifice and dedication parts, but idk if mt frontal cortex isn’t fully developed or what.

One thing I like though is, “who said anything about safe!” - its not arbitrary, its mostly about look where no-one is looking.

The part where he opened up about how he was such full of potential and then he lost a race, lost his way, lost himself, and then he races to race.

The interesting bit is about finding ways, be it fair or unfair. But even then the car needed to work where it was needed to work, on the corners.

But the whole idea of F1 is quite appealing, the speed, the stress, the things they fight for: 1/10th of a second.

I like that

Given that sliding window and next greater were new concepts, I guess its better to related this to real world.

Sliding window maximum real world usecases are in gauges, here one would be tracking changes over time, to answer question like:

What is the change in highest usage over a given time-window?

like : cpu or memory usages over time, latencies, temperature changes etc.

In such problems, the data is a stream, and the answer is demanding for an answer within a window.

For example: If the cpu usage metrics looks: [10, 40, 30, 20, 70, 90], measured every ms window. Then to get the max every 3ms window, one would keep a canidate list where:

• 10 can be discarded in the first window
• 30 can be kept in candidate list
• 40 can be discarded in the next window
• 30 then becomes the new max
• 20 can be kept in candidate list, since its after 30
• and, on the next window both 30 and 20 gets discarded b/o 70

I think we should look at the solution, memorize all the problems using stack, a couple from each of easy, medium, hard?

Tbh, I have been waiting on this for so long, and I have a similar feeling while solving the sliding window maximum, I am afraid that whatever I derieved as to when to discard candidates, might go out of my internal memory.

The answer had kindof dawned on me, after a day of thinking and staring at nothingess and visualizing the array.

I should say: I do have a temporary photographic memory.

There are two things that happen to me:

1. I spend so much time or understanding behind something, or sometimes things just click, and those knowledge become a part of me. I do not reach for the brute-force type of solution anymore.
2. I seem to remember things when its realted to daily events - for me its writing code
3. I can see and remember things, to an extent, like anatomy of a frog, and I can recreate it from memory, only to forget it, after the requirement is over.

For the sliding window here are key things:

• A new element entering the window can either be greater or smaller than the present max
• If its greater, then no element can be greater then no older element in the window can ever be greater than the new element
• If not, any one of the element lower than the present max in present window, and appears after the persent max. can become the max in future window

The candidate list, is to maintain this possible greater element. The candidates get permanently discarded once we see an element greater than the elements in the candidate list.

Going back to the AI agent, I asked:

Instead of waiting things to dawn on me, how should I approach the last part of things.

It has given me a step by step, somewhat. I am not sure if it can be generalized - we will see going later.

1. Take the smallest possible thing.
2. Add/remove things to it, see changes in relationships
3. State what changed on doing so
4. Either nothing happens, or something changes in the relationship
5. State/write the relationship, what became true, what became false
6. See if any of monotonicty, dominance, convex/cav, etc matter
7. See if things are getting added or discarded.

smallest_thing -> current_state -> event -> what_changed -> why

Fuuccckkkinggg hell shitfuck. God fuck, with an interview in 3 more days, I haven’t been able to complete 100crore leetcode, and I have somehow subjected myself to this shit.

Where William Lin spends an hour to solve the entire 4week challange, I am spending 2 weeks to barely solve 4.

Fucking entrance exams after entrance exams to write some fucking code to earn money.

Step 1:

• nums = [5]

Step 2:

• [5, 3]

5>3, but 3 can be a possible max.

Step 3:

• [5, 3] + [4]
• [5, 3] + [2]

• [5, 3] + [6]

• case 1: 4 > 3 and its the next adjacent, so can be removed from candidate
• case 2: 2 < 3, but there could be something more coming in, so it stays
• case 3: 6 > 3, and 6 > 5, but the indices aren’t adjacent, so 5, 6 stays.

This just looks like the candidate list operation is like the sliding window, for any candidate numbers, preserve the numbers in candidate list, if candidates.last() > new_item, otherwise pop them.

What the actual fuckkkkkkk….

Then I guess, the algorithm is like:

• for each item in nums2 build the map for the next greater element
• for each item in nums1, use the map to get the result.
• have a defaultdict with -1, for items that have nothing in map

now to build the map:

• when poping tems from the stack, map {clist.last(): current_item}, until the loop stops
• once done, add the current_item to array/stack

One eternity later.

Since its to the right, and the nums1 is a subset of nums2. there might be a way where we are able to store the some candidates which can be greater, and we would want to iterate over nums2.

Also it greater to the right, maybe we want to iterate from the back of the list.

nums2 = [5, 3, 4]

Observations:

• Values in either arrays are unique
• We can keep a map of the greater element to the right
• We need to keep a ordered candidate list for possible greater elements
• candaidate list then can be de-scending
• ideally elements which are lower than any value in the nums1 can be discarded

Never have I thought I will have to struggle with stacks. I have done things like: matching parens. I had done rain-water trapping before, but now it seems like an impossible feat.

The problem I am stuck at is the Next Greater Element:

Given distinct arrays nums1 (subset) and nums2.

- nums1=[4,1,2], nums2=[1,3,4,2] → [-1,3,-1]
- nums1=[2,4], nums2=[1,2,3,4] → [3,-1]

Its not the next greater value, but the immediate one
to the right

- nums1=[2,4], nums2=[1,2,4,3] → [4,-1]

The brute force can be like:

• Have a nums2_map with { num: index }
• for each num in nums1, find the value in the map
• and find the highest value within [index:n]

I don’t see much, here.

One of the things I have realised, from codeforces and a bit of help from jipit, structures are not data strucutres, they are more like properties/behaviours.

Here goes the list:

Does something only increase/decrease?
        → monotonicity

Does something become permanently irrelevant?
        → dominance

Do slopes/marginal gains increase/decrease?
        → convexity/concavity

Does something repeat?
        → DP / memoization

Does a quantity accumulate?
        → prefix sums

Does only odd/even matter?
        → parity

Does ordering matter?
        → sorting / binary search / sweep line

Can candidates be eliminated permanently?
        → greedy / monotonic structure

Does the same state appear again?
        → dynamic programming

Does the problem have a graph/tree structure?
        → graph algorithms

1. Sliding window maximum

I was really stuck at this problem, but not as much as the next greater element.

Next greater element was a harrowing shameful experience, and its marked as easy.

Looking the sliding window maximum, the brute force approach was easy:

• Get slices of i to i+k, and compute the max.

But computing max is also a loop, so, the complexity came down to O(n*m). Even with go-routines at 10^5 scale, LC gives us TLE.

If I looked a bit close, and considered sliding window:

1. Some maxes are getting recalculated, so some of these numbers in the window can become the next maximum
2. Once a value exits the window, there can be two cases: a. the new number is smaller, in which case it can be a candidate for a future window b. the new number is greater than the max of this window, in which case the present max can no longer be the max c. once a greater number leaves the window, it can no longer be considered as a candidate for max

I guess then, As the window moves, have a ordered list of candidates, and remove the items which can no longer be considered as possible maxes.

Since an invariant is a property, we can say, the invariant

After processing each element, the candidate is an ordered list of elements which contains every element that can still become the maximum after it.

Easier said that done, it took me the rest of the day to figure out how to represent this.

Agent says, I am skipping steps here, (which in hindsight is how my brain has worked, even in exams I have jumped steps - probably the only person to get marks deducted for jumping steps)

So, one of the realizations is:

Anything to the left of the max value, can never become the greatest in the window.

I am traversing the array from left to right, which means, any element in the candidate
list which is smaller than the present value, can safetly be discarded.

Apart from that, we also need to maintain the index, so that we can discard of any value which is less than the window - ci < ni - k + 1 (lookback) can be discarded. Maintaining the index in the candidate list should be enough to give the value, instead of (ci, v)

Idk, why this realisation took me the whole day, maybe I am too dumb. The agent is built in a way, that it is supposed to always ask me meta question, not give the answer. It did ask the question, but the answers came to me after a real long time.

With this I guess, what we can do is, to the candidate list:

• pop the items from the front, which are no longer in the window because, front has max items, by default, and we are moving from left to right
• pop items which are less than the present value (and has/will have a bigger index than prev)
• insert the present index in the candidate list
• the answer for the window is the value at candidate_list[0]

This shorts and wall is proving effective. I can revise things, and write more in english.

Two problems one of which could solve and one I couldn’t.

1. Longest Repeating Character Replacement
2. Sliding Window Maximum

Most of the substring problem require a window. Although its a trap, because sometimes its not a slider, the window-ing is there, but maybe some data can be reused later.

1. Longest Repeating Character Replacement

Here the property is within a given window, there would be some repeating characters, one of which will be the largest, and for the window to be valid the invariant would be:

• length of the window - the maximum count of the unique character <= to k (given replacements allowed)

• Init: window len = 0, max count = 0 so, w - m <= k, is true
• Body: add characters to the window, computing the maxFreq, then make sure the invariant is true, which is (w - m) > k, reduce the window, reducing the counter.
• End: once the window is valid again, we compute the maxLen of the window

Well, I have come across the concepts on invariants. It sounds simple, but its not. I mean sometimes it is, but most times its tricky.

Invariant is a property, which has to remain true at any point during the execution

But its tricky because, you can’t just think of this invariant, it has to fit as well. Sometimes it might look like you have found it but it has to work for all cases.

There are three parts:

• Init: where the invariant gets initialized.
• Body: add/remove things and check and make the invariant property true

There has been two problems, or rather one problem. The brute force, I get it. But even if I kindof can think or feel about what the solution might look like.

The structured way to fill up the blanks is getting difficult. However I have never thought about things in terms of language.

I am more comfortable thinking in code, which seems to be a problem in interviews. The whole process is a mess for me.

I have two ways I am trying to become human:

1. letting the AI build me drills for converting english to code
2. a codeforces blog says, just look at the solutions to a whole bunch of problems and think about them.

So telescoping and immersion. This is something I am really hating man, I wanted to be able to derieve things.

What I want to achieve is not like solve leetcode, but a fundamental way/shift in my thinking patterns.

I don’t really care, if some interview demands if I have studied and memorized some tricks and tips of leetcode question. I care more about how do I shift my thought process to be more structured, that this becomes second nature.

I have build this agent to kindof help me out, in solving questions. After a couple of interractions, the problem it figures, and I hope its right, I am trying to jump or fit structures rather than solving the problem.

I guess this comes mostly from my fear - the bad kind, the anxiety to just get it right, or appear like I am able to use some combination of the handful of datastructures I know.

I gotta be honest, my brain feels fucking fuzzy. I barely solve 1 question a day, doesn’t matter its a hard one or an easy one. I have spent a day equally on solving:

• Maximum length of repeating characters with K replacements
• Maximum number in a given window
• Next greater element I

From 12pm to 2am. No help.

People say reason from first principles, but it only works out for them. Anyone can lookup the actual price of building a rocket, its not really that rocket sciency.

As devs, I have never developed any novel algorithms. Most times, I have implemented them, by reading at docs, rfcs. Somehow it feels like this has affected my articulation. Of late I find it quite difficult to interract with people in interviews. Thinking out loud.

I have never thought out loud, its disgusting to make people see the clumsyness. People expect me, to solve something I am supposed to know from before hand, and somehow pretend that I am self discovering this.

In a way this process of interviewing has become like some entrance exam to sit.

But honestly I am not that guy. So this month, I have taken upon something

• I should have done back in college, when I had the time,
• I should have done 3 months before instead of building stupid apps
• I should have done when I had a stable job

I want to take things in from a first principle basis. The goal is not even to solve the problem, it more about how do I get to ask the right questions.

I don’t think people understand what comes with having a hint of AuDD.

But as Sinestro says: ‘Fear is a great motivator’

Most agent frameworks treat “reasoning” as a straight line — think, act, observe, repeat. But an agent’s decision space is a graph: states, transitions, branches that dead-end, branches worth revisiting. Game AI solved most of this decades ago, and none of it made it into the agentic-AI toolbox.

Concretely, what’s sitting there unused:

• BFS/DFS as retrieval strategy, not just a data structure exercise. CRAG-style iterative retrieval (retrieve → critique → expand → retrieve again) is already a graph walk in disguise. Choosing BFS-shaped exploration (wide, shallow, cheap to prune early) vs DFS-shaped (commit to a branch, go deep, backtrack on failure) should be a deliberate call based on the query shape — not whatever the framework’s default loop happens to do.
• A* and heuristic search, for tool selection. A* is just “BFS with a cost function telling you which branch is worth expanding first.” An agent choosing which tool/sub-agent to call next is the same problem — a cheap heuristic (expected relevance, expected token cost, past success rate) should prune the search instead of trying every tool in sequence and hoping.
• GOAP (Goal-Oriented Action Planning). Game AI has used this since the mid-2000s — an agent picks actions by working backward from a goal state through preconditions, not forward from the current state guessing what to try next. Most agent loops still plan forward. Planning backward from “what does success actually look like” is a different, often better-constrained search.
• Bottleneck-finding. Game engines profile the decision tree to find which node actually gates the outcome — same instinct as profiling a request path for the slow span. Agent frameworks rarely do this: which step in a reasoning chain is the one actually worth more compute, more retries, a bigger model? Right now most systems spend the same budget everywhere instead of finding the bottleneck node first.
• Parallelization at the right places, not everywhere. Hierarchical/parallel A* only parallelizes independent frontiers — it doesn’t fan out blindly. ParallelReACT should mean the same discipline: parallelize branches that are provably independent (no shared state, no ordering dependency), not just “call five tools at once because we can.”

None of this is novel — it’s a “AI 101 for games” chapter most agent-framework authors never read, because they came from NLP/ML, not from game engineering. The vocabulary already exists: frontier, heuristic, admissibility, backward chaining, critical path. Borrowing it directly would save agent frameworks from re-deriving badly, by trial and error, what search theory already worked out.