02.08.2022 (19/n)

- 1864. Minimum Number of Swaps to Make the Binary String Alternating (medium)
- 239. Sliding Window Maximum (hard). Fails on time limit exceeded.

I tried to solve both Amazon-like challenges but only managed the first one. The second fails with a time limit exceeded 🤷.

The first one, again, has something to do with 0 and 1. This time it's a number of swaps to get the correct alteration of 1/0, e.g. 010 is correct, but 100 is not. It takes a single swap to turn 100 into 010. The first obvious step here is to check whether or not a correct alteration exists. After that, for even strings, you check both cases: string starting with 0 and string starting with 1 to find the minimum number of swaps. For odd string, however, you can only pick one, e.g. if there are a total of 5 zeroes and 4 ones, the correct strings 100% starts with a zero.

The problem here is the last bit. You can't just count "min swaps starting with 0" and "min swaps starting with 1" for odd-length strings. This gives you wrong results for odd strings where you explicitly have to pick one starting char over the other.

The second one still fails on the time limit exceeded, because I tried to use max-heap here, but removing an element from max-heap is O(n) due to the search taking O(n) and the actual remove is a negligible O(log(n)). The pinned hints suggest using deque for this task, but I'm not super sure how to do it exactly 🤔 I guess with deque once you get to the current max element, you can remove every single element less than this max. Still don't understand how it saves time, because your max could always be the left-most element which you don't drop, and once you drop it, you have to find another max in O(n). I'd have to think about it tomorrow, too tired now.

Also, how on earth are you supposed to figure it out with 1 hour 30 minutes for two tasks if you have not done it before? Guess that's why you grind.

03.08.2022 (20/n)

Today I did almost nothing productive! Not even much work-related. It's good when you can have a break from everything in the middle of the week without the self-inflicted feeling of shame.

Okay, maybe one productive thing. I was reminded of these awesome MIT lectures on distributed systems: Spring 2020 or Spring 2022. One of the labs there includes building a key-value store with raft consensus protocol using Go. I really want to start working through it, because the last time I dropped in on lecture 5, remember that those were one of the best sources of knowledge on distributed systems I've encountered. Not as overreaching as Distributed Systems by van Steen and Tanenbaum (it's free!) but more practical. That being said I already have an AWS course, a System Design course and a bunch of leetcode. Might be better to finish something first...

04.08.2022 (21/n)

- 239. Sliding Window Maximum (hard)
- 502. IPO (hard). Time limit exceeded

The good news #1: the deque approach for 239 which I mentioned two days ago does work. Makes sense to learn what methods Deque interface in Java has because there are a lot of them and half of those are not obvious, at least for me.

The good news #2: It's the 3rd or 4th time I'm hitting the wall of Time Limit Exceeded with leetcode hards. This is a good thing because a month ago I was not able to solve any of them! Now it's clear that with enough practice it will boil down to "can you figure out the optimal solution in N minutes during the interview". There is still a long road ahead just to finish with even the basic patterns, so I can take my time. Still, it's not as impossible as I used to think.

07.08.2022 (22/n)

- 502. IPO (hard)
- 23. Merge k Sorted Lists (hard)

Easy! Only took like 2 hours to solve both which is slightly over the limit of 45 minutes on the real interview. Apparently, leetcode does support the Pair class in the normal Java compiler, only for some reason this Pair comes from javafx and has a weird interface. The Pair could be very useful when you want to store both data and array index, for example, because most challenges pass in an array of something. Speaking of approach is a straightforward priority queue for both, only for the first one, it's actually two PQs (max profit of available and min capital of non-available. And you switch between) and for a second it's all the current available heads of the list of heads;

Speaking of 45 minutes, If you want to feel inadequate, this guy on youtube solved all 4 hards from Facebook, Apple, Amazon and Google in the 45 minutes span. An absolute beast!

09.08.2022 (23/n)

- 436. Find Right Interval (medium)

A very curious challenge. If I didn't know that you can solve it with two priority queues I would've automatically assumed that binary search is the only way. But it's not! Although this "medium" with a priority queue is even harder than "hard" 502. IPO from above. Go figure.

On the other topic, I did pass Amazon's initial "testing" with 1 medium and 1 hard from here. Tomorrow I'll have a phone screen with them. Wish me not to forget the "leadership principle" and a bit of luck of course!

10.08.2022 (24/n)

Had to move the interview today to tomorrow. I was gathering a few "leadership principle" stories today, and boy do I have a lot. From the time I hired 15 years of experience guy without a coding assignment because heck 15 is a lot, what could go wrong? Literally everything! Till the time I went through PCI DSS compliance check which included 3 days of 8 hours calls. Hope I don't forget all that the second I'm getting asked a behaviour question...

11.08.2022 (25/n)

Well, that was the easiest phone screen in my life. I've already passed it and the next and the last interview, which is a 4 hours rodeo of leetcode/system design/behaviour, will be around August 31st.

It started with a few basic experience questions, e.g. what did you do on the last job and what's your tech stack, then continued into simple algorithm questions, e.g. what is a hashmap, what's the difference between BFS and DFS and what is a binary search tree. All of those also included complexity questions and just saying hashmap is O(1) is enough, even though that's not true 100% of the time.

There was one particularly weird question: given a list of items, how complex is a query "find all items with the letter X is in the name". I tried to say that the brute force approach is ~ n because the length of the name is most likely neglectable and can be treated as a constant, but it may be quadratic if the names are gigantic (said it as a joke), but I was stopped as soon as I said quadratic. Go figure 🤷‍♂️

The last bit was two behaviour questions:
- tell me about a time when you did something outside of your direct responsibilities.
- tell me about the time when you received feedback.

For the last part, I said that I wasn't lucky enough to work in companies which actually did 1:1 with members of the team and frankly never received feedback worth mentioning, apart from "you did fine, brother", yet I did have a story, where I gave feedback and actually helped one underperformer to get on par with everybody. Lesson number 1: managing experience allows you to blast your way out of behaviour questions during phone screens at least. Lesson number 2: be ready for follow-ups. Your chances of making up a story go to zero pretty quick. Seems to me that having a weak but believable story is much better than absolute nonsense. They are really good with follow-ups, e.g. "tell me what was the benefit of your decision and how do you quantify that" or "what will you do differently next time and why".

13.08.2022 (26/n)

- 78. Subsets (medium)
- 90. Subsets II (medium)
- 46. Permutations (medium)
- 784. Letter Case Permutation (medium)
- 22. Generate Parentheses (medium)

Noice. These all use the same pattern somewhat similar to BFS where you build the children's level of the tree by using the values from one or more parent levels. For example the permutation problem. You start with an array [1,2,3]. The first level of the tree is a value 1. The second level is two values: [1,2] and [2,1]. How do you get it? You put the parent 1 to each possible position in regard to 2, meaning you put it in front of 2 and behind it.

[1]
v
[1,2] (in front), [2,1] (behind)

Now we get to 3. How do we update existing permutations for 3? The same exact way! Take all permutations on level 2 and add 3 to every possible place.

[1,2] => [3,1,2] (front), [1,3,2] (middle), [1,2,3] (back)
[2,1] => [3,2,1] (front), [2,3,1] (middle), [2,1,3] (back)

And just like that, you get the answer. Some of those are harder than the others because sometimes you'd also need to look at multiple parents like in the Subsets problem. Or even worse either look at all parents or only some like in Subset II, yet the core idea stays the same. And just like in BFS, having a queue to store all values of a single tree level might simplify solution dramatically.

15.08.2022 (27/n)

- 47. Permutations II (medium)
- 224. Basic Calculator (hard). Runtime Failure on one specific case with a negative value 🤷‍♂️

224 is a fun one. It seems simple on the surface, just create two stacks one for operands and another for operations and compute whatever value possible. Only that with this approach you are quickly overwhelmed with cases around the - sign:
- negative numbers which are like normal, but the "operation" - is now part of the operand, e.g -4 + 3
- plus negative value inside brackets, e.g. `5 + (-3)
- negative before brackets, e.g. -(4 + 3). Roughly the same as above, but not really.

I'm fairly confident you can still solve it with two stacks for operands and operations, but I've also seen a few solutions with only 1 stack or two stacks: for operands and for the number of elements in the last bracket. This one requires a bit more diving in to figure it out.

16.08.2022 (28/n)

- 241. Different Ways to Add Parentheses (medium)
- 224. Basic Calculator (hard)
- 96. Unique Binary Search Trees (medium)
- 704. Binary Search (easy)
- 35. Search Insert Position (easy)

And I finally broke the first magic barrier of 150 solved code challenges! Actually, it's 151 (55/83/13). I've heard that the third eye opens around 300, so just repeat it once and I should be good. I don't know, only one way to find out.

Btw, the different parentheses and unique binary search trees are some solid questions. They are simple in nature but require some recursive thinking. The not-so-obvious "do left" => "do right" => "merge results" works here like a charm. I also started the binary search pattern which is one of 6 patterns left and after that, I'll start doing random questions. Might even participate in leetcode monthly challenges!

19.08.2022 (29/n)

- 744. Find Smallest Letter Greater Than Target (easy)
- 228. Summary Ranges (easy)
- 1200. Minimum Absolute Difference (easy)
- 34. Find First and Last Position of Element in Sorted Array (medium)
- 1509. Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
- 852. Peak Index in a Mountain Array (medium)

Binary search leetcode challenges consist of a few subpatterns:
- The classical, where you find the key and then do some calculation with or around the key, e.g. 34
- The "mountain" array (aka "bitonic" array) where you use binary search to find the peak element instead of looking for the key
- The "infinite sorted array" where you still use binary search to find the key but don't know the array's bounds. I have not solved those yet but will try it tomorrow e.g. 1095. Find in Mountain Array.

Some of those will also ask to return not the key, but the element which is close to the key, e.g. as-close-to-the-key-as-possible. In these cases, after a normal binary search is complete, the result is either on the left or right border. If the binary search goes until leftIndex <= rightIndex the leftIndex will be equal to rightIndex + 1 at the end, so the leftIndex shows the element that is greater than the key and the rightIndex shows the element less than the key. Took me some time to figure it out.

21.08.2022 (30/n)

- 1095. Find in Mountain Array (hard)

Not terribly hard hard to be honest. Definitely require a lot of typing though. It's 3 binary searches packed into 1 challenge.

Step 1: find the max element aka the peak of the mountain
Step 2: Get a normal binary search for elements from 0 to peak and a reversed binary search for elements from peak to the last element.
Step 3: Return the index of the lowest match. Take extra care when returning -1 for "not found".

Apart from that, I've finished week 3 of the AWS course and decided to focus on two things at a time. One of which is leetcode and the other is this course. Can't get any shit done by doing multiple things 🤷‍♂️

22.08.2022 (31/n)

- 33. Search in Rotated Sorted Array (medium)
- 81. Search in Rotated Sorted Array II (medium)
- 268. Missing Number (easy)
- 136. Single Number (easy)

Searching in a rotated array is very similar to searching in a mountain/bitonic array in the sense that it's a binary search with extra steps. For a bitonic array, you analyse the elements close to the middle, and with a rotated array you check how the middle relates to the left or right border.

The last two are the beginning of the XOR pattern. That's a tiny pattern which includes 3 more problems on educative So far anything harder than easy is an absolutely insane arcane incantation. It's easy to find one single number like in 136, but e.g. 137. Single Number II (medium) has each number repeated 3 times instead of 2, so the normal XOR no longer works. The same with "find two single numbers" which is not on leetcode apparently, but also uses a similar approach. Guess that one will along with dynamic programming will be in a bag of "please don't ask this on interview" kind of questions

01.09.2022 1/2 (32/n)

I'm alive! Took a bit of a break because I was stressing out with the Amazon interview. Now the first part (2/4 interviews) is done so I can function properly. The last part must be somewhere next week. I bombed it a little already so don't have my hopes up, but let's see how it goes first.

So the first interview was with one of the senior EMs in the same business unit I applied to. The guy is great, we had about 10 mins of intro and then jumped into 2 behaviour questions:

- tell a time when I had significant obstacles to overcome
- tell a time when I needed to influence a peer

One thing to note: they are absolutely brutal on follow-ups. Just preparing a story using STAR method + their leadership principles is not enough. You should be ready for extra questions such as:

- What did you learn from this?
- What would you do different again?
- What was the concrete impact of the decisions made?
- What were the alternatives?

This part took about 20 more minutes. The last 25 were system design + 5 for my questions. The system design is a URL-shortener with slight scalability twist a) must support both CSV-batch and one-off writes and read b) the write volume is 5 billion requests per day. Most of those come in batch mode. c) The data retention is set to 5 years.

I used the good old open-up of a python terminal and turn the numbers into something useful as a first step. The good thing about python is automatic overflows handling. The interviewer didn't mind at all even though I wasn't sharing a screen. 5 billion requests per day are about 57k requests per second. That's a lot of requests! It automatically rules out the obvious solution "treat one-offs the same way as batches". 5 years of retention is also a pretty huge number. Assuming we'd only need to store two strings: short URL and long URL that's about 1KB of data per data item as both are very short strings. Multiple by 5 billion. Multiple by 365 days. That's a whopping 1700 TB of data for 5 years or 4.65 TB/day.

I think I hit the mark pretty good with the next question "what's the access pattern for the data?" Turns out, we'd only expect requests for the last half a year. Half a year out of 5 years means 10 times less data. A big save.

After that, I started drawing out the solution. For the batch requests: store the request in the object store, and feed it into some map-reduce service because regardless of how you split the big enough file, some part of processing will definitely fail. Asking the file size was also important. Turns out it's a single file per hour. Which is with 4.65 TB/day divided by 24 is ~ 0.2 TB file. That's one hell of a fat file. I said that it's probably impossible to even load such a big file directly into a server without using some extra shenanigans, and the interviewer agreed but said that we can assume that we can do that. Bonus point for me I guess 🤷‍♂️

I didn't have the time to finish the one-off part of the processing, but we discussed it anyway. There were a few questions on how to partition the data, what type of DB to use, and what type of caches, but nothing out of the ordinary. Knowing what an index is, what secondary indexes are and how sharding and partitioning work should be enough. We even had a fun discussion around "hot partitions", e.g. you can theoretically detect those and create a specialized solution for those. I'm fairly confident I read about it in some Instagram blog where they do it to handle celebrities.

01.09.2022 2/2 (32/n)

The next interview started pretty much the same way with intro + behaviour questions. This one was from a different company. Apparently, Amazon is split into multiple companies, e.g. one for the website + billing, one for AWS, one for devices, etc. Said that's the common practice in their interview process.

- Tell me about a time when I made a hard decision to sacrifice short-term gain to create a long-term benefit.
- Tell me about a time when I strongly disagree with the manager.

Same hardcode follow-ups, even harder than before because I didn't prepare one of the stories as much as I needed to. But then I almost completely bombed the coding challenge.

I know there are a bunch of topics I have not even started. Those are prefix trees (aka Trie), backtracking, dynamic programming and topological sorts. Guess what? I got a prefix tree! Very similar to 472. Concatenated Words (hard) with a different output. I needed to return a map of all possible combinations to combine a word.

I got stuck like an idiot trying to figure out prefix trees on my own without actually ever seeing one. Don't do that. After about 10 minutes and a nudge from the interviewer, I started to brute force the thing and was done in about 15 minutes. Now I have 5 minutes left and it turned out that a single word could consist of multiple words and not just 2 as my first solution. This was a killing blow, I kinda partially scribbled some possible recursive solution for that too, but needed something like 15 more minutes to finish it and about 90% less stress.

Anyway, it was a nice experience. At least now I know that they'll go an extra mile for behaviour questions and that without knowing a pattern coming up with a brute force may not work simply due to stress. Both interviewers were very laid-back and overall it was a pleasant experience. See If I change my mind after the next week.

05.09.2022 (33/n)

- 1009. Complement of Base 10 Integer (easy)
- 832. Flipping an Image (easy)
- 260. Single Number III (medium)
- 215. Kth Largest Element in an Array (medium)
- 973. K Closest Points to Origin (medium)

I'm slowly trying to get back into the grind with new tactics. Those 5 above I did over a couple of days. It's just easier to not lose motivation after 30 days of the semi-constant grind (at least it feels semi-constant even though I had a break for a whole week + a 4 day break too). I would rather finish a single question most of the days rather than doing nothing for 4 days and then getting 5 in a day.

Also had the third out of four Amazon interviews today which went pretty smooth. Same intro but this time followed by 3 behaviour questions:

- Tell me about a time when you saw an issue inside a team and the approach you used to solve it.
- Tell me about a time when you worked against a tight deadline.
- Tell me about a time when you tried to understand a complex problem and what solution you found.

The interview didn't exactly like my tried story and asked if I can get another example, which I did and that one was enough. So I'm minus 4 stories after that round. They are still trying to poke every story with at least one question. Even if I tell it perfectly there seems to always be something to ask.

If I were crazy I would've already mapped the questions to specific leadership principles and figured out the rest of them, but nah, nobody does that. Assuming the next one tomorrow will also include 2 behaviour questions you would need at least 8 stories you should have prepared. Frankly, I have no idea how a normal SE just doing their job will come up with that. I somehow get by with management/tech-leading experience yet still have to think about something remotely ethical as a story each time. Talk about unrealistic expectations.

Anyway, the next thing was approximately a leetcode medium + a medium follow-up. The first one: design a class which takes an array of integers int[] and supports two operations: update(index: int, value: int) and undo() which undoes the last operation. The follow-up is as obvious as it gets: also add a redo() operations to undo the undo. The first part went smoothly with a single stack for undo, and on the second one I first tried to use a deque to hold both undo and redo stacks but it was hard to deal with edge case: redo() after update(..) is a no-op, so I switched to two stacks. We still have about 3 minutes left for questions after that.

06.09.2022 (34/n)

- ??? Minumum Cost to Connect Sticks (medium). Paywall! Also available on leetcode clone named lintcode (wtf?). Link. Click at your own risk.
- 347. Top K Frequent Elements (medium).

Well, I fucked up big time on the last Amazon interview and got rejected already with "we encourage you to apply after 1 year". After a few more behaviour questions to make a total of 10 over 4 interviews:

- Tell me about a time when you were able to anticipate a solution a customer didn't know they needed
- Tell me about a time when someone on your team challenged you to think differently about something
- Tell me about something you did to improve your effectivity

I got yet another coding challenge. Pretty much exactly 1901. Find a Peak Element II (medium) with a slight twist: return the FIRST peak element if traversing from left to right from top to bottom. By the end of the interview, I didn't even have a brute force solution coded 🤷‍♂️.

This failure is purely on me. I suggested the brute-force approach right away, interviewer then asked me to find something better, which I failed to do for the next 15 minutes. At this point, I was even suggested to write anything but instead, I wasted all the time in the world trying to find an optimal solution, didn't find it and decided to do some bizarre optimization instead of brute force. Turns out 1) this is not an optimization, same complexity as brute force. 2) I failed to deliver even that. Of course, I should've gone with the most basic brute force, but I panicked way too much.

The optimal solution for this problem is absolutely weird and I have no idea how to come up with something like this without prior knowledge. It's a binary search in a sense with 3 differences: 1) we are looking for a local maximum which may not be the global maximum. We move left and right borders around said maximum. 2) we are doing it in a 2D grid so instead of analysing the values themselves, you have to analyse the whole columns or whole rows depending on 2D grid orientation. 3) Somehow when looking for the local maximum you have to also make sure that it's the first you meet when traversing the array in left-right-top-bottom order.

Sup everyone!

I've been on and off with Leetcode practice for the last year but mainly focused on not losing my shit at the $currentJob. The good news: I have a pretty high chance of getting a promotion to Staff engineer in the next half a year 🎉. The bad news: I'm still sitting at ~265 solved on Leetcode and still either hit or miss most of them.

For now, I decided to take a small step back and get the algorithms/data structures background I have been missing. For that I'll use the good old Princeton Algorithms course on Coursera. I have attempted to finish it at least 4 times over the last years, so wish me luck with the 5th attempt. I have gone over the first 3 weeks previously already, so will be starting with week 4 and Binary Heaps possibly tomorrow.

As usual, I log everything I do on GitHub and will share my experience on this journey here as well

Binary Heap

Binary Heap is a data structure commonly used to implement Priority Queue. The Binary Heap provides log(n) for both insert() and deleteMax() operations and also constant peek() operation by keeping the maximum element easily accesable.

The Binary Heap is based on a complete binary tree — a tree which is balanced on all levels apart from possibly the lowest. Complete binary trees could be represented as an array. For example a tree such as this:

9
/ \
6 8
/ \ /
3 4 7

Can be represented as an array layer-by-layer as [9, 6, 8, 3, 4, 7]. If instead we write this array as 1-indexed by pushing a dummy elements at index 0 like this: [null, 9, 6, 8, 3, 4, 7], we get some cool properties to detect parents and children. For node k of 1-indexes array, the parent node will be at index k/2, and two children nodes will be at indexes 2k and 2k+1. Naturally, you don't have to use the 1-indexed array to get this property, but 1-indexed array makes the math trivial.

For example node 8 has a 1-index of 3. It's parent will be at k/2 = 3 / 2 = 1 which is 9. The node 6 with an index 2 has two children. The left child is at index 2k = 2 * 2 = 4 and it's the node 3 and the right child is at index 2k + 1 = 2 * 2 + 1 = 5 and this is the node 4.

To turn a complete binary tree into binary heap, we have to make sure we sattisfy exactly one extra property:

> Parent's key must not be smaller than childrens' keys

The tree from above sattisfy this criteria. Notice how the root of the tree is the largest elements in the tree and it can be retrieved in constant time by getting the array element with index 1. The next thing we want to do is insert a new elements. To preserve the complete binary tree there is only one place where we can insert an element, which is a right child of node 8. Let's assume we want to insert an element 10.

9
/ \
6 8
/ \ / \
3 4 7 10

Now the property of binary tree is not sattisfied and we need to swim the element 10 from the bottom to the top. The algorithms to do so it trivially easy:

1. compare the value of a new node with it's parent
1.1. if new node's value is greater than parent's => swap them, go back to 1
1.2 else, finish processing

The 10 is first swapped with 8. Then the 10 is swapped again with 9, resulting in a tree.

10
/ \
6 9
/ \ / \
3 4 7 8

The last operation we need to support is deleteMax(). The trick to delete max is to first remember the element at the top of a tree, then swap it with the very last elements of a tree and then delete the previously max elements from the bottom.

8
/ \
6 9
/ \ / \
3 4 7 [10] <-- swap with 8, then delete

After this operation however, the tree is no longer a heap. The new element at the top may not sattisfy the heap criteria. We have to sink it to the bottom of a tree. Doing so is also quite easy

1. pick a larger child of a current node.
1.1. If value of child is greater then current node, swap them, go back to 1
1.2. else, finish processing

With this algorithm 8 will first be swapped with 9 (9 is larger child between 6 and 9) and the algorithm stops, because 8 is greater than 7.

9
/ \
6 8
/ \ /
3 4 7

To sumarize:
- to add element to a binary heap: add it to the very bottom, then swim the element to the top, while it is larger than the parent
- to remove the element from the binary heap: remember the element at the top, swap it with the lowest element, delete the new-lowest-element, then sink the new element to the top by swapping it with the largest of it's children. Finally returned remembered element.

Here's my Java implementation of Binary Heap.

Heap Sort

A Heap Sort is a non-stable sorting algorithm based on a Binary Heap data structure. Unlike basic Quick Sort, Heap Sort has a complexity of n * log(n) in the worst case. Unlike Merge Sort, Heap Sort doesn't require extra memory.

Binary Heap allows you to extract the top one (max) element at n * log(n) time. Generally speaking, the extraction happens by swapping the top element with the element at the end of the Heap and then deleting the new end element.

The idea behind Heap Sort is that instead of deleting the top element at the end after swapping, you can keep it at the end and reduce the size of the Heap. This way, the whole array is split into two parts: a Binary Heap in the left part and a sorted array in the right part. Notice that you don't need to allocate extra space because the two parts never interleave. Instead, after iteration K, you will have an array having two parts [0; N-K | K; N]. The [0; N-K] is still a Binary Heap, but [K; N] is a Sorted Array.

The algorithm goes as follows
- Create a Binary Heap from the initial array, a linear operation. This way, you split your array initially into [0; N] Binary Heap and a [] sorted array.
- Extract the max element from the Binary Heap part and place it in the sorted array part. Reduce the size of the Binary Heap part. If there are no more elements, return the sorted array.

With this algorithm, you start with [0; N] & [] Binary Heap & Sorted Array parts. After the first iteration, one element will be moved into sorted parts [0; N-1] & [N; N]. After the second, the split will be [0; N-2] & [N-1; N]. The algorithm continues until you eventually end up with [] Binary Heap and [0;N] sorted array. Congratz!

My Java Implementation of Heap Sort.

1171. Remove Zero Sum Consecutive Nodes from Linked List (link)

An absolutely legendary question. The hint kindly mentions to first turn linked list into an array, then turn in back into linked list, while none of the Editorial solutions even mention an array.

This is one of those reading comprehension tasks, where if you read it incorrectly, the question becomes close to unsolvable. The task asks to remove all consecutive zero-sum sequences of nodes. That’s it. No other requirements.

At first, I read that I have to remove the nodes in a way, that the resulting sequence is minimal in size, which would mean postponing the “removal” step, until a largest sequence could be found. If we don’t need to do it (and we don’t), the question can be solved with a greedy algorithm:

1. Find and remove the first encountered zero-sum sequence
2. If there were no zero sum-sequences, we're done, else restart.

// Rerun while there are zero-sums
while (res.length != arr.length) { 
    arr = res;
    res = removeZeroSumSeq(arr);
}

The rest of the code is boring LinkedList to array and back transformation, and the removeZeroSumSeq function itself is also nothing fun. Find the index of end of zero sum, then copy all elements around it into a resulting array.

Now the coolest solutions do the same with prefix paths, but I haven’t looked at them just yet 😬