Data structures and algorithms I actually used while working at tech companies

To filter out naive people that don't have proper understanding of fundamentals and just having some framework plumbing knowledge, I guess.

These are considered pretty basic stuff that every programmer should know..

It's a great showcase of how a flashy looking solution is the wrong approach. A good candidate will know it can be written in 2 lines recursively, but that the stack will explode with a fairly low term number, and that iterating with a for loop is more efficient.

I remember, when starting university, with no real programming knowledge, making a little game in my spare time (a clone of Pang if you know it) but it was before I knew what a linked list is. I implemented things like the balls which bounce around the level in an array, and just gave that array a max size. I was very unsatisfied by this, and then later finding out about linked lists was an ah-hah moment, very satisfying.

Next project was making a "Countdown" game, where you are given 9 pseudo random letters and have to make the longest word you can. I found a dictionary as a text file, so could see if the word you entered existed. The game was on Gameboy Advance, so not a huge amount of space or very fast CPU. As you can imagine, walking the entire dictionary file from start to end looking for a word was far too slow. So there was another ah-hah moment when binary search was introduced.

Next I worked on a rendering engine for this device called GP32, you basically got a pointer to the screen buffer and could put what you liked in it, so I learned how to write polygon fill routines, back face call, etc but didn't know what perspective projection was or how to find out about it. I finally found a book, Game Programmers Black Book or something like that, which explained perspective projection, at least to some extent, another ah-hah moment (previously I was dividing my XY by Z as I knew I wanted things smaller in the distance but this doesn't give a nice result by itself).

These are just very early examples when I first started programming, when information was harder to find, and when a lot of games development involved DIY, if you want a polygon you need to pixel fill a polygon! Even when PS2 came out you still had to write ASM render programs to take an array of vertices and transform them, their UVs, etc and send them to the Graphics Interface.

But I haven't found later tech developments have stopped me finding and needing to use other algorithms and structures. Just last week I had to diagnose a crash which resulted with the target device and debugger showing a nonsensical callstack, so I enabled the profile options in GCC/Clang so I had an epilogue / prologue for every function that is called, so I could store my own call graph history, and then, on crash, display it nicely, with indentation etc. This allowed me to see what happened just before the crash (turned out to be a system UTF16 conversation routine stomping over a pointers boundaries as the NULL termination of the string was incorrectly done as if the string was a normal char*, effectively NULL terminating half of a UTF16 pair, which wasn't treated as a terminate, so the actual bug was bad string termination done by the off the shelf engine we use). As the profile code ran twice for every single function that was run, it had to be pretty efficient, using appropriate data structures, etc.

So I guess the point of this post is to say I believe having a good knowledge of algorithms and data structures always seems beneficial to me. The extent which some companies push them is too much for me, but I don't think this should lead to us thinking it is all pointless. There is a nice balance out there.

For me, I have spent many years, writing code that presents UI, or controls devices.

That has some aspects of software development that I rarely hear discussed, like testing, usability, accessibility, aesthetics, graphic design, error handling and recovery, documentation, support, configuration management, and lots of system framework knowledge.

If I am supposed to be writing apps for iOS devices, then I’d think knowledge of UIKit would be a heck of a lot more important than balancing a binary tree. I can tell you, from personal experience, that it takes a long time to learn, and is very important, if you want actual, shipping apps.

Even so, I have often encountered obsession with “büzzwürd du jour,” and people get hung up on things like MVVM/MVP, VIPER, etc.

I remember once, getting a “take home” test that asked me to implement an iOS app that employed MapBox, which is an excellent library, but, at the time, I had never used. I was instructed to use MVVM. I have no idea why.

In four hours, I had a completely functional, localizable, well-code-documented, nearly ship-ready (including a custom app icon and splash screen), high-quality app that implemented MapBox (again, I had never even looked at MapBox before this test), using Dependency Injection (basically, the “D” in “SOLID”). If I incorporate dependencies, I always encapsulate the dependency, and DI is an excellent way to do that.

Oh, also, while I was working on the app, we had a household emergency that required urgent attention. The app would have taken less time to write, otherwise.

It was not received well. To this day, I have never learned why. I suspect that I was supposed to spend a couple of days, creating some kind of chimera that illustrated every buzzword on Earth. No matter. I wasn’t what they wanted, and, after that experience, I realized I would probably not enjoy working with them; which was a bit disappointing, as I liked their product. I felt that I could have had a fairly significant impact on their Apple software.

In my experience, I have found it’s always best to use the development model a framework is designed to support; even if it isn’t particularly “buzzwordy.” If we use UIKit, then MVC is the most practical and simplest approach, as that is how the SDK was designed. If we use SwiftUI, then we have a great deal more flexibility with our models, but very few companies are willing to ship SwiftUI apps (yet).

Shipping is all about practical approach. Ship software should be done quickly, as simply as possible, and needs to be robust, well-documented, organized, testable, Extensible, and maintainable. If we are talking Apple apps, then they should also be performant, responsive, secure, highly usable, intuitive, aesthetically pleasing, accessible, and that employ familiar (to the user) idioms. They also need to pass App Store Review muster, so that means being careful about how we incorporate dependencies and frameworks, as well as not using private APIs.

Since I’ve had over twenty apps in the App Store that I’ve written from scratch (but I'm down to seven, right now: https://littlegreenviper.com/AppDocs/), this is something I do know a bit about.

That usually requires a great deal of frugality, practicality, user empathy, experience, and self-discipline. It’s difficult to figure that out with “Draw Spunky” binary tree tests.

Be careful, 'persistent' is used with different meanings in different contexts.

See eg https://en.wikipedia.org/wiki/Persistent_data_structure and immediately notice the warning 'Not to be confused with persistent storage.'