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 😬

Unroll String

I ended up in a weird situation recently, where I had an easy-enough OOP coding interview, similar to “design Twitter class capable of creating twits, following, and getting a news feed”. This took about 45 minutes of back and forth discussions with an interviewer, and I was pretty confident I did alright.

And then the guy hits me with an Unroll String question having just under 10 minutes to wrap it up. Little did he know how good am I at coming up with shitty solutions in a short time frame, so here we go!

Given a string s, decode it following the specified encoding rule:

- The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times.
- k is a positive integer. The encoded string can be nested, and the input string is always valid (no extra brackets, and k is always a positive integer).

unrollString(“3[a]”) => “aaa”
unrollString(“2[cd]ef”) => “cdcdef”
unrollString(“3[a2[c]]”) => “accaccacc”

This is not a terribly hard question, and it can be solved optimally with around 20-25 minutes of time. Parsing strings usually takes a stack or two, and some input juggling to get it right, however, when there is 10 minutes left, it’s usually either a brute-force, or no solution at all, so the first important mental shift for me was to focus purely on the dumbest brute-force possible.

The next question is: What is the minimum input we need to know, to reduce the size of a problem? The answer: the position of a closing bracket. This realization comes more from the experience of solving similar problems, but usually, when things are nested, the lowest level of nesting is the smallest piece to iterate on.

Focusing on minimum input, the problems falls into a nice infinite loop

while (true) {
    remember opening bracket position

    // minimum input to reduce size of problem
    if (encountered closing bracket) {
        unpack the bracket; continue;
    }

    // infinite loop exit condition
    if (no open bracket && the end of a string) {
        break;
    }
}

The pseudocode is a solution for all senses and purposes, and for me it took about 5 minutes to come up with, the rest I spent putting it in code, which is a boring part of problem solving.

Sort array, removing duplicates

Recently got this question on Binance interview. This is a variation of 26. Remove Duplicates from Sorted Array, with a small twist: the array is not sorted initially.

It’s not a particularly hard problem, but a fun one, with multiple solutions. The first very obvious one is a fallback to a known problem.

1. Sort the array
2. Solve the “remove duplicates from Sorted Array”

The first part is a standard library function. The second part boils down to re-writing an element, but only if it’s a different element from the previous (unique).

    public int removeDuplicates(int[] nums) {

        Arrays.sort(nums);

        // start with insertIndex = 1, because nums[0] is “unique”
        // on each iteration [0; insertIndex] array contains only unique elements 
        var insertIndex = 1;
        for (int i = 1; i < nums.length; i++) {
            // the element at [insertIndex - 1] is “inserted” into a list of unique elements already, so it’s the only elements we need to compare with due to array being sorted
            if (nums[i] != nums[insertIndex - 1]) {
                nums[insertIndex] = nums[i];
                insertIndex++;
            }
        }
        return insertIndex;
    }

The resulting complexity of sorting + removing duplicates is O(n * log(n)) and O(1) extra memory, and we know that the solution is optimal, because typically the sorting can not happen faster than O(n * log(n)).

However, sometimes it can! If the array elements fall into a specific bound, we can use Radix/Counting sort which happens in O(n) with O(n) extra memory.

Yet another solution if you can not use a library sort / can’t implement effective sort on the interview (neither can I) is based on solving “sorting” and “uniqueness” problems separately by using a set for uniqueness and a priority queue for sorting. Here, we iterate over all the elements adding them to PQ, if it’s the first time we see an element.

    public int removeDuplicates(int[] nums) {
        var pq = new PriorityQueue<Integer>();
        var set = new HashSet<Integer>();

        for (int i = 0; i < nums.length; i++) {
            if (!set.contains(nums[i])) {
                pq.offer(nums[i]);
                set.add(nums[i]);
            }
        }

        var index = 0;
        while (!pq.isEmpty()) {
            nums[index++] = pq.poll();
        }
        return index;
    }

This solution is clearly worse than the in-place sort, it’s O(n * log(n)) complexity with O(n) memory (actually 2n memory). However, it avoids the build-it sort call, and is a nice flex at knowing your data structures.