5. Longest Palindromic Substring

My friend is solving some LeetCode problems now, and I couldn't help but join him.

I know, I know... LeetCode is dead, all this is trash, and we shouldn't solve it. But for now the standards of interviews in Big Tech are settled, and you can, at least, laugh at us, who spend tons of time performing cargo cult rituals.

First of all, it's like a 20-minute problem. In these 20 minutes you have to:

— 0 min
✒️ read the problem statement
✒️ come up with a few test cases - it helps both to understand the problem better and to have test cases for the later testing session
✒️ figure out a working solution for the problem
✒️ explain your approach to the interviewer, give them T=O(...), M=O(...) estimations
✒️ get approval from the interviewer to go on with this solution

- 5 min
✒️ implement your approach
✒️ test your implementation on your test cases
✒️ fix it, if necessary
✒️ check that your T=O(...), M=O(...) are true

- 18 min
✒️ discuss pros and cons

- 20 min

I'm not a quick thinker, and in order to be able to take part in this competition, I thought a lot and came up with some tricks which I want to share. First of all, how to read the statement and how to approach a solution.

"the longest palindromic substring" - if you, like me, start to think "I read really beautiful algorithms which solve it in linear time, what was that book..." - poof, you have already lost this game. Nice thought. But you have to mention it really quickly and move on. What is the real complexity you want to aim at? Check s.length <= 1000 and think about the naive approach. All substrings - n squared, palindrome check - n => n cubed. Rough estimation for time - 10 secs in Python - doesn't look good.

Here you have to recall at least a glimpse of that wonderful algorithm you read about. There was something... about... middle points of palindromes! Let's check. n middle points, linear check => n squared. 0.01s for n = 1000. Sounds promising.

In the program I want to share a trick: decomposition. Of course, you can try to write a program in one long sheet of text. But if you split it into logical parts, it's better for you. Python gives you a great opportunity - iterators. In the function you can generate candidates and then select the best using just the max function.

In order to use just max, we are to be careful about an empty sequence. It is not a case here, because n >= 1. If an empty sequence is possible, default = ... in the max function is your friend.

For odd-length palindromes, candidate generation is quite boring. We start with the trivial one-letter palindrome and extend it, if it is possible. No problem.

Even-length palindromes have a real chance to be absent at all. One more trick - make a step back and set up variables in the previous position before they form a valid even palindrome. Then we can check whether the variables are still in this weird initial position. If they are, we don't have a candidate.

So, here we are. A few tricks, and the problem is solved.

3D-printed Dragon Curve

Once I stumbled upon a big glass box in the middle of the App in the Air office. I asked, "What is it?" Turned out it was a 3D printer. An expensive one. I didn't get a believable answer about what this thing was for, but I got permission to play with it.

One day I'll tell you the story of my first 3D model in life - it's epic. Now the small story is about the Dragon Curve. Unfortunately, I'm not educated enough to write the whole story about this object, but it is certainly worth your time if you are a fan of math. The Dragon Curve can be obtained by folding and unfolding a strip of paper, as a recursive procedure, as powering up complex numbers...

This model I created myself by writing a small Python program which calculates the path for a Dragon Curve - the easy part - and makes a 3D model out of it - the slightly trickier part. The output of this program was an .stl file, then conversion to gcode, and finally printing this thing out.

I really appreciate the chance to play with this machine. Thanks, Sergey, Bayram!

The Water Tower

Earlier I mentioned my old project: a water tower from an ancient DIY pioneer book, which turns 60 years old this year.

I decided that the pyramids were too simple project and I needed to do something a little bit more interesting, so I started a new project in Blender. The second picture shows my models in PrusaSlicer. Now we are waiting for the tower to be finished, and then the experiment will be conducted.

Meanwhile, I found exactly the book I read half of a lifetime ago. You can compare the neuroslop version of the water tower with the real thing. I totally like these black-and-white schemes.

The text is hilarious. "You can use these tin cans, they are the best. Green pea cans worse, but will do." I don't know why, but it sounds... really, I don't know exactly how. Like a magical chant?

Looking forward to pouring water into the tower.

Friday shitposting

Sometimes you say "Thanks, Cap" as if stating the obvious is a bad thing. But in our fast-paced reality, maybe it's exactly the anchor that keeps us afloat. (pun intended)