Engineer Blog #2

This is the problem I am doing, almost daily, in the morning.

I know the solution - I have seen it before, especially in video form. I have read the code, also.

I just don't get what would prompt a genius to think of stacks to solve the problem.

I am trying to get into the heart of the solution, and have been trying very hard, and unsuccessfully, for at least the past 2 months. Maybe more.

Once I have the complete algorithm in my mind, I still need to code it in 4 minutes, and get a compiled, correct result with optimized speed.

Then, it's the next easy, in a different category.

No more coming back to the stack. The only thing done like this, since 2024, is the 2 sum problem.

Given that I am doing the entire process, correctly, from start to finish, in less than 4 minutes, starting at the screen sleepily is dangerous.

If you have only 1 chance, are you going to take it?

Or are you going to let it go?

Anyway.

Here are random, very nice, and not very useful things I have realized in the 4 minutes of sacred attention, from my training.

I speak after training in the mountains, after grasping the essential nature of information.

Are you ready?

Satori #1

The string in the above problem - the series of brackets. They are not ordered.

Also, ordering them has a negative effect, since we need to detect whether the criteria of order is natively met.

Since ordering them corrupts the data, you don't need to sort it 👍

This insight rules out all sorting algorithms as being helpful.

Satori #2

This one is a little weird, so hang on.

It makes sense to treat the string as a random bracket generator.

That is, if there is a function that takes a single bracket, then as far as the function is concerned, as long as random brackets are given as input, when the feeding of brackets is over, can we determine if there had been a valid string?

In pseudo-code, the above is just a loop:

for every character in the string:

<do the logic>

The reasons I found this insight interesting, is because.....

A loop can act as a transformer, making a group of 'many' into discrete elements.

Put it this way, a loop is not just about 1 to 1 access, like how I viewed it - and o(1) access with lists, as you will see in Cracking the Coding Interview.

A loop, at its heart, is about using a funnel to slow the flow from the tap, and force a drip.

Then, each drop can be dealt with separately.

Kind of like the escapement in a pocket watch - the energy from the pendulum, is allowed to 'escape' at discrete time intervals, allowing the jarring motion to create the discrete motion of the second hand.

The loop doesn't just allow iteration - more than that, it's a tool for the engineer to convert one thing of 'many' into many 'one things'

Second reason - typically, I have always viewed the input as the data being given.

For example, a single data being given, (my age) is different from a group of such data (everyone's age).

I have cried internally, if the input is a matrix of matrices, and I need to solve the problem in 20 minutes.

I don't think I've questioned the input, as anything more than 'input'....I didn't overthink it.

Until, 2023, that is.

From the perspective of what's inside the loop, though, the inside doesn't have to know whether there are multiple brackets, 3, or 5 of them.

In fact, the string can be abstracted away completely, as something 'that spits out brackets, randomly' because for the inner algorithm......the string might as well be random.

So I'm wondering if the correct algorithm will still work if you paste that logic next to a bracket spitter.

Every second, a bracket comes out - ( or { or [ or ) or } or ]

So far, is the string valid?

And.....Will our logic hold if the string never spots spitting?

If the correct algorithm relies on finiteness (like in normal engineering) then it's safe to assume we always have access to the data.

But if the random bracket generator never stops spitting brackets, no logic can save us.

I don't have time to prove anything - I am looking for an IT role.

But I conjecture that:

As long as the brackets keep coming, the validity is still being decided, and so the program will only know if the string is valid, once the brackets stop coming.

In other words, you can't know if the string is valid, until the entire string is known.

But you can tell if a string is unsorted, as soon as you see something amiss.

Spot the badly ordered string:

[[[[[[[[[ [

[[[[[[[[ ]

Satori #3

I suspect the reason is a stack is being used, is because of the second constraint:

Open brackets are closed in the correct order.

The problem.....is problematic.

It took me a while to figure out that the "correct" order connotes nesting.

As in [](){} is OK, ({}) is OK, but this is not OK ([)] .

These examples are given in the question itself - but the relationship between order and recursive order is not specified.

There's no particular reason [ ( ] ) is an invalid string, unless validity assumes a certain, specific type of closure.

This is troubling for several reasons:

First, Neetcode in my opinion, is better than leetcode for training. Yet, I find this question ambiguous. I am not hating on it - neetcode is an exam, not training for computer science, even if I am focusing on the latter.

If the interviewer wants me to ask 'What do you mean by correct order?', that's not something I can ask my laptop while studying.

Second, if the interviewer is looking for a 100% match to their solution, in addition to testing for:

1. memory
2. conformity
3. speed
4. fluency

They are automatically rejecting to test for:

1. Creativity
2. Resilience (when creativity backfires, how the candidate handles it)
3. Communication (especially with peers, mentors, and juniors)

For example, I believe making a mistake in criticizing an established algorithm already indicates these:

1. Comprehensive understanding of computer science topology
2. How I handle mistakes

I don't think most interviewers are focusing on (1) and (2), for some reason....they seem to be focusing on 100% validity for difficult problems, and sometimes, their version of validity.

But wait, there's more!

Referencing their (correct) version also implies that all the necessary details are mentioned upfront.

This approach on vetting the results in my opinion, also increases the pressure on the interviewer to remember all the details needed to vet thoroughness.

You can vet for talent by using a riddle.

Or, recite a 9x9 sudoku, remembering all the numbers, orders, and sub-square ordering perfectly, and then giving the candidate 20 minutes to find the one and only solution.

Imagine the horror if the interviewer forgets 1 number, or mixes 2 sub-squares.

Unlike before, I am not criticizing MAANG, or the focus on leetcode as a way to validate talent.

By thinking from their perspective, my skills are improving by leaps and bounds.

Being jobless is the perfect time to become better - I have time and space at my disposal, unlike my compatriots who are working hard for their boss.

I believe a master can pass the beginner exam, but not the other way round.

But it's just weird - a vendor is essentially a plumber, and even skilled engineers don't always work on new problems, all the time.

Some of coding, even at Microsoft, is just routine, domain-heavy expertise that relies on connecting things correctly, and not critiquing Djikstra.

Leetcode was always absurd - the idea of using difficult questions intentionally (like MAANG) or to vet sound reasoning, is a weird reason, even if it was a working one.

But, I get it.

If it works, it works. Leetcode and I are friends, now.

2024/25 is a new level of absurdity, and unfortunately, an unproductive one.

I don't think it's working.

At this rate, not only will IT lose talent, talent will go elsewhere.

Satori #4

Mathematical exhaustiveness - in this case, a valid string, is the opposite of an invalid string.

So knowing 1, disproves the other. A string can't be both valid, and invalid - validity is truly boolean.

Not all problems are like this, though - sometimes, you can't really say that knowing 1, solves the other half of the coin.

Good example:

A robot is given a coin that has heads on one side, and tails on the other side.

Whenever your boss at Amazon touches a button on his dashboard, this coin is flipped by the robot.

You need to write a function, so that whenever a tail is revealed, every 10 times, the robot notifies the boss.

What's the time complexity of this function?

Looks like I am qualified to interview myself 😆

But my point is, the answer to this question isn't boolean.

It's more like:

1. What do you mean by reveal? (requirements clarification)
2. How is my function told that a coin flip happened? (technical clarification)
3. How many times does the boss touch the dashboard? (system design, to think about storage - if the boss touches the dashboard m times, then the coin is flipped m times. Say, tails occurs only 50% of the time, then a notification is required only m/(0.5 x 10) times).

Or look at this question:

Write a program that flips a coin.

Return how many times Head happens, unless Tails happens 3 times in a row.

Here, the termination of the program is triggered by Tails happening 3 times consecutively.

We're not really concerned about how many times Tails happens, nor that Head / Tails are mutually exclusive, in the boolean sense. We might assume that, but the boolean mutual exclusion is not tied to the meat of the algorithm itself.

We are only concerned about how many times Head happens, till 3 Tails happens.

Conclusion

There you go.

4 satoris:

1. Ordering a data set can actually hinder the problem solving process.
2. A for loop takes 1 of many, and breaks them down into discrete 1s. This allows the next function to operate on the 1s separately.
3. It took me a while to figure out what 'order ' means. Seems arbitrary, and worth asking in the interview. Since order connotes nesting here, using a stack makes sense, due to their associations with recursion, which is itself very nest....ive.
4. Returning true or false, may come from a boolean result at the end of algorithm. But maybe not always. Back to basics reminder that computers can also be used for automation, repetitive precise behavior, and not just for business applications.

See you on the next blog.