Estimations

“Build projects around motivated individuals. Give them the environment and support they need, and trust them to get the job done.”¹

When I initially started writing this post long ago, I originally named it “No Estimates!”². And while I still agree with most of what I wrote back then, I feel that the title less reflects my current stance on the subject. We live in a less-than-ideal world. Being pragmatic and working within the current framework is more important than being a purist and complain about what’s wrong.
But before we delve into pragmatism, we need to understand what is the problem with estimates in the first place. So here are my thoughts on giving time estimations in the software engineering industry.

You can’t have it both ways

As developers, we often need to choose between different trade-offs. Whether it’s choosing your distributed data storage model, acknowledging CAP theorem constraints, and choosing either consistency or availability in a distributed system, choosing a technology that maximizes either throughput or latency, choosing a randomness model (Las-Vegas vs. Monte-Carlo), or building a predictive model that favors precision over recall, etc…
But when it comes to development culture, we often fail to recognize different trade-offs in our day to day work. Ignoring a technical trade-off may result in malfunctioning software. When it comes to an organizational culture trade-off that is being ignored, it can cause much more harm.

A trade-off

Organizational life is full of trade-offs. Let me focus just on one: Release cycles should either commit to deliver on time, or on content, but never both. This seems intuitive and simple, obviously everyone agree, no?
No! Have you ever been asked to provide an “effort estimate”, or “time estimate” on a task? If so, whoever asked you for the estimate did not make a conscious choice regarding the on-time vs. on-content trade-off. They implicitly delegated a different decision down to you, whether they (or you) were even aware to it. But more on that later.

On time means that you don’t promise on content delivery, but commit on a release date. And you release, even if the change is minimal, or even if not apparent to clients at all (only internal changes & bug fixes)³.

On content means you plan for specific functionality to be delivered, but you can’t promise when to deliver it. No doubt you will encounter many sub-tasks you did not thought of initially, and which you should (must) do prior to the content promised for delivery⁴.

Either case, there no need to get an estimate on a specific task.

Why not actually?

“This seems to work for our org…”
Let’s disregard the fact that forcing an estimate from the developer gives you an educated guess at best⁵, and a mere fortune telling⁶ at worst, and focus on how it affects the dev team, and how it perceived by management/product.

When we give an estimate, we implicitly “commit” to both time AND content, whether we know it, or not. But something has to give. We can’t have it all. Let’s rephrase the trade-off:

We can deliver on time, on content, or on quality: choose 2.

What does quality has to do with this?

Most organizations have a backlog of tasks, probably prioritized. One should try not to care how long a single task will take. The reasoning behind it is something most developers have a gut feeling about, but might not be fully aware to. When working on a task, you often find out peripheral area’s that require changes. A good developer should know when such peripheral changes are becoming “Yak Shaving”, and when it’s likely gonna pay off to just do it.
Developers can then feed a healthy backlog with “TODOs” they encounter on the fly and don’t want to “inline” within their current subtask. Such work flow is flexible, and leaves room for gradual fine-tuning by developers. Not only that, but it has the merits of allowing the developers take smaller tasks, sometimes purely technical, and offload to their future self, knowing it will get done. Smaller tasks means easier reviews, higher confidence on every increment, and faster delivery cycles in general.
The fact that we get things done faster, and all “TODOs” - aka maintainance work gets done, means higher quality software.

But, whoever in your organization is in charge on prioritizing the backlog of tasks, may have different views and preferences than the actual team doing all the coding. That’s alright.

Even if they prioritize solely based on external needs, e.g: bugs reported by clients, feature requests, etc…
The dev team can, should, and (hopefully) will adjust.
They will take on more maintenance tasks inlined within other tasks. This is not ideal, but it is a workable environment. So long as we make sure to “let them” inline such maintainance work.

When there’s a high level of trust towards the dev team, prioritization of tasks is made in a way that maintenance work get a fair share in every cycle. We trust the developers to not spam JIRA (et al) with redundant work. Or in the second scenario, we trust them to not waste time, to “raise flags” when unforseen issues pop up, and we let them do their thing without pressuring imaginary time constraints.

On the other hand, when you ask for an estimate on a task, you’re effectively asking for a deadline. Or in other words, a time AND content constraint.
Even if you declare that it’s not a binding commitment, and just a rough estimate to reflect for the management or product owners, the developer giving that estimate will implicitly accept this as a deadline (and don’t even get me started on hard deadlines!).

Now, that we’ve understood the fundamental trade-off, let’s take a deeper look into why estimates often fail in practice.

What’s in an estimate?

Allow me to offer a glimpse into the mind of a developer being asked for an estimate:

We need to account for “unknown unknowns” (aka “TODOs” / inilined maintainance).
And we don’t want to be “way off”, or else… (will we be held accountible?)
But also, we don’t want to be that person who always gives an overly exagerated estimate.
We’re “pleasers” so we’ll probably just say what you want to hear.
We’ll then try our best to make it.

This means we don’t offload “TODOs” nor inline maintenance work enough (if at all).
Even if we try to prioritize maintenance work post-delivery (be honest. will you? really?), the maintainance itself is more expensive. Solving an issue you just discoverred, and have full context on, is much easier than coming back to it after a while, not to mention maybe other stuff that didn’t exist before already depend on your faulty code. So no, a “promise” from management to pay off “tech debt” in the next cycle/quarter/whatever… isn’t good enough.

So, yeah. maybe an estimate is not a “deadline”, but it has a very similar effect. It still causes software rot due to neglecting maintainance work, which in turn causes stress, fatigue, weariness, and de-motivating the dev team.

By not caring at all how long a task will take, you actually say you have confidence in your dev team to take as much time as needed to close the task. You trust them not to take too long (or “slack off”), and trust them to raise flags if some tasks prolong beyond the scope of a “regular task” they’re used to. This trust is empowering, motivating, and creates a healthier dev environment.

“We’re not using estimates, we do story points.”

oh really..?
Story points are estimates. And a bad one. Ask the guy who invented them⁷.

Becoming a healthy organization

It’s important to note that no one is asking time estimates in ill intent⁸. It’s obvious that time estimates make the job of the dev manager, product owner, or project manager much easier. Clients are happy (in short term), since they have (an illusion of?) transparency on progress, which are good reasons overall. And yes, working without estimates is going to be harder. Sort of like how writing multi threaded async code is harder than single threaded blocking code, or how working with a distributed NoSQL database is harder than a single node relational database. But eventually, much like in these examples, it is often becomes necessary in the long run.

Being pragmatic

Your organization currently relies on estimates for planning. “We can’t ditch this. That’s impractical”, they may say.
OK then, what is the essence of the need to provide estimates?

Transparency of progress for management? Ability to plan ahead? Ensuring development stays “on track” and doesn’t stray off in irrelevant directions?

I think all of these can be achieved by estimating without asking developers for estimates.

Wait, what…?

If you read carefully the previous sections, you’ll see I say nothing is inherently bad with estimations on their own. I advocate for not forcing them out from developers. I’ll also add, risking stating the obvious, that we should take estimations for what they are: Estimations! Not predictions. Not a commitment.

Lets unpack this:

accountability - a developer giving an estimation feels accountable for it, and would be tempted to take shortcuts implicitly. Better to have these shortcuts made into an explicit choice. Either way (taking the shortcut, or spending the extra time to do something the “right way”), we lift the pressure from developers feeling accountable for either not making “on time”, or on-time delivery of a buggy second grade lousy solution.
transparancy - despite the reputation management/PMs usually have in the eyes of development teams, I don’t think anyone wants to compromise on quality. But this is usually a “black box”. Management usually only knows a feature can be delivered in a week “the hacky way”, or a month “the right way”. Given this opaque repeated choice, I’d bet everyone would be tempted to choose the fast way once in a while.
planning - more often then not, estimates are asked for making a decision. Having several business goals, they may not all fit in our capacity to deliver. We need to pick a subset of “big rocks” to focus on in the next cycle.

My suggestion?

Management/PMs should try to estimate how long a task might take without asking the developers. Not even “t-shirt size”. Not even get “approval” - no “Do you think its doable within…?” kind of questions!
Estimations should be kept by management/PMs to themselves, and not even share with most developers. We need to remove any sense of “accountability” on the dev team. real, or perceived.

But how?

Management/PMs can “interrogate” developers for the “what” (and sometimes “how”) instead of asking for “when” or “how long”. I wrote above, that experienced developers have a “gut feeling” about what needs to be done.
But what if not? How can we tell whether our developers has the “right” kind of gut feelings?
A task, any task, is pottentially an infinite tree of subtasks. Some are essential, others I called out as “yak shaving” before. An experienced developer will know when to stop “unfolding” this infinite fractal tasks tree.
But, by having a PM “interrogate” the developer, they’re basically unfolding the tree together. Each developer has its own pace, and different prefferences for the ideal “resolution” of breaking into subtasks. This is very individual, so spending little time, pairing 1:1 with every developer is needed. I think an hour every week or 2 should usually be sufficient. If the team has 5 developers, each requires such 1:1 sessions to unfold what & how they’re about to do in detail⁹, it means 5 hours every week or 2 of “extra work” for the PM.

You’re probably not very excited to read this, but here’s the silver lining: How much time does the PMs in your organization already spend in grooming/planning sessions? The suggested sessions are actually private 1:1 detailed grooming & planning. And after those sessions, the estimation that the PM comes up with, is as good as an estimation asked from the developers - if not better (no hidden encapsulated inlined work PM is not aware of…)

Over time, the PM “learns” through their 1:1 sessions how much time tasks are likely to take for each developer in their team. Over time, they’ll acquire a sense for when things stray off into the realm of yak shaving, and be able to push back when needed. Over time they’ll learn about the implicit tradeoffs (now made explicit) developers make, and learn to account for them.
This is much harder (at least at start) for the PM, but it pays off.

Whatever estimations the PM has, they should keep it to themselves, and not even share with the devs. This is essential for 2 main reasons. I’ve already mentioned the need to remove sense of time accountibility from developers (how can one be accountible for a “wrong” estimation they did not even knew about?). I’ll also add that for the PM to actually adjust and learn to refine their estimates, they must not rely on estimations comming from developers, which encapsulate too much (all the implicit tradeoffs we want to make explicit). This is a learning and refining process that takes time.

Probabillity

I may be stating the obvious here, but estimates are guesses. As such, there’s always a chance we’re wrong. That should be OK for a guess.
When developers estimate, they take into account the chance of possible problems. Sometime they occur, sometimes not.
The PM will learn to account for these as well.

Another (hopefully) obvious statement: since estimates are probabilities, a sum of probabilities makes no sense. You might sum the time, but you also should multiply for the chance the guess was correct¹⁰. Meaning very quickly that guess would be as good as guessing the lottery winning numbers.

Consider this as a guideline for the PM who learns how to adjust their estimates - don’t estimate on too many tasks at once.

Summing up

In conclusion, navigating the complexities of modern software development requires a shift away from rigid, un-nuanced time estimates that force developers to make unnecessary compromises. A more flexible, trust-based approach can be achieved by eliminating the pressure of strict deadlines and fostering an environment where developers can focus on quality and gradual improvements. This leads to higher quality software and a more motivated team.

As the Agile Manifesto wisely states:

“Build projects around motivated individuals. Give them the environment and support they need, and trust them to get the job done.”

The Manifesto for Agile Software Development ↩︎
I’m picking up oin an old draft that has been lying around for quite a while ↩︎
For an on-time delivery cycle example, take a look at how canonical plan their releases.↩︎
This is how most open source releases happen. No hard commitments on release dates. New versions are released when done.↩︎
Given that the developer is well versed in the code, fully understand the task, and have enough experience in that organization to also encapsulate in his guess the time needed from peers - be it devops / QA / code reviewers / UI designers / etc…↩︎
I’ve taken “estimates are fortune telling” idea from Andy Hunt, when he mentioned it on the co-recursive podcast. Great episode BTW, you should go listen to it.↩︎
Ron Jefferies: Story Points Revisited ↩︎
Well… Depends on who you ask. I bet if you’ll ask Erik Meijer, he’ll probably tell you it’s a form of abusive subtle controll.↩︎
I mean of course unfolding only 1 level deep in the current sub-tree - the immediate next thing to do. Not the whole pottentially infinite fractal.↩︎
This is very simplistic, but if we assume a task never takes less than what we guessed it would take - which makes sense when you think about it, one can always continue refining infinitely until time is up. Then the statement holds. Let’s assume we’re 50% right on our guesses. Given 3 guesses for 3 tasks that’ll take 3, 2, & 5 days. Guessing right on all 3 means 10 days. The chance of actually being right is 0.5×0.5×0.5 = 12.5%. The more you guess, less likely you’ll guess right.↩︎

Osteoclasts vs. Osteoblasts

I used to feel as this carmudgeon developer, somewhat angry at all these keyboard monkeys who can’t or won’t write decent code. And then I found myself working with such “keyboard monkeys¹”, perhaps even being one myself. At least à la the current carmudgeon developer².

Being on different side of the fence made me realise that sometimes we must stir things up to make progress. Even at the cost of “breaking stuff”.

Nowadays, instead of an old and wise carmudgeon vs reckless keyboard monkeys, I tend to think of the situation as more of a “osteoblasts vs. osteoclasts”, and actually think this is a healthy situation for a software organization to be in³.

what are “osteoblasts” and “osteoclasts” anyway?

osteoclasts vs. osteoblasts search results summary.

tl;dr: osteoblasts build bone tissue while osteoclasts destroy it.

Where am I going with this analogy?

When software gets enough mileage and accumulate enough “tech debt⁴”, it tends to become more “rigid”. It gets hard to make changes, introduce new features, etc’…

Similarly, our bones gets more rigid as we grow old. A child’s bones are more flexible and tend to bend or “bow” instead of breaking. An adult’s bones are harder and more brittle. The way our bones grow, is largely thanks to the work of osteoblasts and osteoclasts in our body. To help bones grow as they become more and more rigid, the osteoclasts dissolve and damage the bones, allowing the osteoblasts to mend the bones with new and better bone tissue.

Back to software developement: The “reckless” works of the young and darring might anger the old and wise who feel they need to “clean up” after the monkeys. But if we don’t have our reckless osteoclasts to break the software in the right places, we won’t be able to make important adjustments to our software. We need the old and wise menders to make sure everything is working properly. We also need some recklessness and darring to “get shit done”.

It is a delicate balance, and each organization has a different “right” ratio of preservation vs. innovation oriented developers.

Not really. They are all awesome people and great developers. You’ll see where I’m heading with this soon enough.↩︎
Brilliant fellow TBH. Had been around from the product’s early days, and had very deep and vast knowledge of the system.↩︎
Assuming you have the “right” balance of old and wise carmudgeons to reckless keyboard monkeys ratio.↩︎
I actually don’t like that term. I prefer “software rot” over “tech debt” - but that’s an issue for another post.↩︎

Balance your team skills RPG style

All developers¹ feel they are “above average”.
That can’t be true, right?
Or maybe it can?

Well, depends on how you measure.
A while ago I recruited a new team, and in this post I want to share some of my newly acquired insights.

The analogy

Remember those role playing games of the nineties? You had to form a party of heroes for a quest. Where for each chosen character, you could also adjust their stats. Strengthening some of the character’s attributes at the expance of other attributes.

pool of radiance - ruins of myth drannor: character creation; assign ability scores screen

It was not a good strategy to have all your heroes optimize for the same attribute. Enhancing only strength, for example, and neglecting wisdom, dexterity, etc’… would not get you far in the game.

pool of radiance - ruins of myth drannor: character creation; select party screen

It’s also a bad strategy to average all your characters on all attributes, making them mediocre at everything. Diversity was key to advance in these games.

Same goes for engineering teams.
Some people have more of a “hacker mindset”, some are “builders”, other “menders”, or “enablers”, and so on…

And like in these games, where some missions can only be passed with a combination of (for example):
Characters that are very strong and specializes in melee attacks, together with characters that are agile & accurate and specializes in range attacks. We need to assemble an engineering team with different types of “experts”. And much like the games, not all expertises are essential to all tasks.

Optimize your team for the job at hand

When building a new team, ask yourself questions like:
Does the goal leans more towards exploration, where fast feedback & market validation are key to success? Or more towards long term stability and maintainability in a well established product?

Obviously, the perfect team for the job would look different based on the goal. If I want to explore, release POCs, demos and experiment fast, I would lean more towards a “hacker mindset” team that works in a “quick & dirty” style (hopefully more quick than dirty). If the team’s task is to maintain a viable product, then “doing things right” becomes a much more desireable mindset than “quick & dirty” (which is probably even harmful in such scenarios).

You may (probably) still want a “hacker” on your “maintaining a legacy product” team, or a “maintainer” on your “hacking a POC” team, as no task is ever “pure”. Much like in these games, more often than not, you’ll need to asign tasks to the appropriate “expert”. So make sure you got one on your team.

The “like-minded” trap; or how to diversify?

It’s very easy, when building a new team, to favor people that “think” like us. This is a hard one: how to identify the skills & strengths we lack (and need) in candidates? I don’t have the answer, and sometimes I only notice my blindspots post-mortem. Best I can advise is: do your homework! Be explicit on the teams goals. Try to identify the skills needed (& currently lacking). Then, Optimize for those.

Most people are “above average”

It may have sounded a paradoxal claim when you first started reading this post. But it’s true. Most people ARE above average, just not in everything. Some people are better at hacking stuff - à la “move fast and break things”, others might be methodical & thorough, perhaps working TDD style. We all have our strengths and weaknesses. If you focus on people’s strengths, you’ll soon find out that indeed, there is no paradox.

Sure seems so. I never met anyone admitting they’re “below average”↩︎

The aquarium analogy, or: Is it all about the fish?

~~Recently~~¹ A couple of years ago, I got into the fantastic world of aquariums. At first, I thought there’s not much to know about it. You buy a fish tank, You put water in, some equipment - filters and such, buy some fish, and that’s it. Oh boy, was I wrong…

This is actualy a post about software development. really…!

So why am I blabbering about fish? Well, it occurred to me, that growing a software developement organization is much like maintaining an aquarium. my aquarium

How so?

Well, first I need to bore you with some more “fish talk”².

A bit more “fish talk”

An aquarium is a closed eco-system. And much of what happens in nature, needs to happen also in your little home aquarium. Experienced fish keepers know this as the nitrogen cycle. In short:

fish produce waste
waste deteriorates into toxic ammonia
bacteria consume ammonia and turns it into (toxic) nitrites
nitrates (not very toxic, yet can harmful in very high amounts) are formed from the breakdown of nitrites by nitrifying bacteria
plants & algea consume nitrates
fish eat the algea

illustration taken from aquacadabra.com, if you want to learn more about the nitrogen cycle, pay them a visit.

OK, back to “software development talk”

In the same way I want to show off colorful fish, and thriving plants in my living room’s aquarium. An organization would want to show off with (and sell!) their wonderful products.

And much like fish, the product (software) “deteriorates” and needs to be constantly maintained. google explains why software deteriorates

How do we deal with software rot? Should we ~~throw in more bacteria~~ hire more developers to clean up the mess? Probably not. The thing is, that much like in an aquarium where you can’t just throw in bacteria and expect everything to just work, you can’t just blindly hire more developers and expect them to be on top of everything from day one.

Cultivating bacteria

In a newly set up aquarium, there is no nitrogen cycle, since there are no bacteria & no algea…
You’ll need to “jump start” the cycle. There are starter kits, where you just pour bacteria into the aquarium. But it’s not a magic solution. The bacteria takes time to acclimate. If you add too many fish too early, they produce too much waste, and there’s not enough bacteria to consume it. The fish will die.
Instead, you’ll need to slowly build the fish population in parallel to the bacteria population that grows. You do this by taking care of water quality (doing frquent water changes) and making sure ammonia/nitrites levels are kept low. Then, bacteria population will slowly increase, which in time will be able to handle larger bio-loads (more fish).

Cultivating developement teams

You can’t rush building a developement team either. A small, already “acclimated” team, may work well in its domain of expertise. You may even “jump start” a new team by hiring a bunch of experienced senior engineers. But it would be unwise to frequently pivot the team from one product to the next. It takes time until a team starts working together efficiently, and it takes time to gain expertise in a new domain.
You can’t overwhelm a new aquarium with little bacteria with too many fish at once.

Cultivating individuals

Its not just the team you’d want to cultivate. It’s important to grow individuals as well. Investing in personal growth means growing the teams capacity without hiring more people. I.e: scale up vs. scale out. Both are important.

Focus

Up until now, I’ve talked mostly about the “capacity” that an organization can burden its engineering department with, and the fact you need to “cultivate” your engineering department in parallel to developing the product. This is one side of the coin (cultivating the ~~bacteria~~ engineering). The other side is making the work itself more “friendly”, by being more focused. The point is, that capacity increses with focus. If the organization is focused on the product vision, it gives the developers the “expertise path” in the domain, which in time scales up (more capacity).

This is true for aquariums as well. You need to focus on your “type of aquarium”. One cannnot just blindly add different species of fish to the same tank. Different species has different temprature ranges they are able to leave in. Different pH (acidity), different KH/GH (hardness), etc’…
But even if all environmental parameters match, you still cannot mix species that are likely to be eaten by a different type of fish you have in the same tank. Same goes for fish that are territorial & aggressive.

No team can handle all products, and no aquarium can handle all fish combinations.
Point is: if you’re focused, you can deliver more. If you’re leaning towards exploration mode (which is totally legit), do it moderately and take into account the hit you’re taking in delivering production grade code.

In summary

The organization is the tank
The product is the fish
The Developers are the bacteria

And you need to take special care balancing everything in order for this eco-system to thrive.

I started writing this post when the aquarium was still a “recent” thing for me…↩︎
I assume many readers are not aware of the fish keeping hobby details, much like the clueless couple-of-years-younger me didn’t. And it is important for the analogy ¯\_(ツ)_/¯↩︎

Face-lift

The blog gets a face lift

Why?

Well… initially the blog was written as simple markdown posts. Markdown is an obvious choice for a blog, easy to write and maintain. I decided to render the markdown ad-hoc, so I used pagedown extra¹. I also added syntax highlighting using highlight.js. This was simple and easy. Integrating with blogger was not too much of a fuss, I just wrapped every markdown post with:

<div class="markdown" style="display: none;">
  # markdown content went here
</div>

And added a small js snippet to the theme HTML editor:

// Yup! jquery was still a thing back then.
$(document).ready(function () {
  var converter = new Markdown.Converter();
  Markdown.Extra.init(converter);
  $(".markdown").each(function(index, element) {
    var md = element.textContent;
    var formatted = converter.makeHtml(md);
    element.textContent = "";
    element.innerHTML = formatted;
    $(element).find('code').each(function(i, block) {
      hljs.highlightBlock(block);
    });
    $(element).css('display','inline-block');
  });
});

I also added there the <script> tags with src of the libraries I used, directly hosted from my github account through rawgit. It worked out as expected.

The plot thickens

Throughout the years, blogger made all sorts of changes, that occassionaly caused my blog to break in weird ways. Patching it every couple of years was not such a big deal. But at some point, I decided I want to ~~shoot myself in the foot~~ add $\LaTeX$ in my posts, so I added MathJax to the mix.

At that point, all the patching I did throughout the years, together with adding MathJax, turned the cute little snippet above into some serious dumpster fire.

Unsuprisingly, the blog became unusable in recent years. Rawgit service has been shutdown. libraries became outdated. And my script broke in weird ways.

Time to refactor

OK then, obviously maintaining the blog with scripts to render markdown + syntax highlighting + $\LaTeX$ inside blogger is not something I want to continue doing. So I was thinking: what are my options?

Ditch blogger and host the blog somewhere I fully control.
Use blogger with pre-rendered HTML. Without any scripting shenanigans.

I didn’t want to ditch blogger. It’s convenient, support out of the box to some nice stats with google analytics. No need to care about hosting. etc’…

So I tried converting all my posts to HTML.

Attempt #1

I needed $\LaTeX$ for all the nifty equations and I only used markdown to format the text nicely. Well… that’s exactly what $\LaTeX$ is for. So I figured I can just reformat all my posts to $\LaTeX$, and then convert the .tex files to HTML using htlatex. Obviously, I’ll write future posts directly in $\LaTeX$ instead of markdown. All I needed was to figure out how to do the syntax highlighting for code blocks.

I’ve used syntax highlighting in $\LaTeX$ before, but needed something simpler and easier to maintain. I went for Listings, as it seemed the most suitable solution. The result was… ok. The scala language² support was not ideal. The parser/lexer did not recognized stuff like class names, or types. But it’s possible to “help” it a bit, by providing extra tokens with their style. The code blocks themselves were not as nice as I hoped: glitch-lines between the rows But the real deal breaker, was the fact that htlatex was not able to export listings as HTML.

Attempt #2

Even before the last experiment, I had a gut feeling against it. The “pipeline” was not very simple. Export markdown to $\LaTeX$ → fix $\LaTeX$ & syntax highlights manually → export to HTML using htlatex → maybe even fix HTML itself?

Well, MathJax already works great, and if I only add MathJax, the integration with blogger should be simple enough. So I went for direct markdown → HTML, and left MathJax inlined in the HTML.

I used pandoc to convert the markdown files to HTML. Unfortunately, syntax highlight for scala code with pandoc isn’t great as well, but I figured I could easily just patch the HTML output directly. I decided this is good enough for now and I should stop shaving this yak. Since I need to touch the HTML output a bit³, I figured I should commit it to the blog repo as well.

What’s next?

So now the blog is up and running again. All posts were converted, and everything works well. I will probably change the theme sometime soon (I chose the first thing just to get on with the tweaks). I also noticed some “inacuracies⁴” I should fix in some old posts. Perhaps archive the less relevant topics. But I also noticed many drafts I started and never finished over the years⁵: draft posts I guess we’ll see soon.

I can no longer find the original sources, but I do give credit (with mostly broken links) in the first blog post.↩︎
Which is by far the most frequent on my blog↩︎
Some MathJax expressions contained stuff that pandoc “rendered” as HTML wrongly, and I needed to “undo” these.↩︎
I guess the blog stays true to is name ;)↩︎
There’s some interesting ideas in these drafts I should definately write about.↩︎

Trick or Trait

tl;dr

Scala’s traits are tricky. There are many pitfalls. especially, if you’re dealing with composed/stacked traits. I recently had an interesting conversation on whether it is best to extend a trait in another trait, or enforce a mixin with self typing (which apparently, can be done in several ways). This led me to some new findings (for me at least), and insights, on how and when to use the different approaches.

What’s wrong with the good old abstract class?

Scala has abstract classes, but they are limited. You cannot inherit more than one class or abstract class. Scala’s way to achieve “multiple inheritance” is via “trait mixins”. It also allows you to extend a trait with another trait, but according to the specs:

… A template $sc \text{ with } mt_1 \text{ with } \ldots \text{ with } mt_n \{ stats \}$ consists of a constructor invocation $sc$ which defines the template’s superclass, trait references $mt_1,\ldots,mt_n (n≥0)$, which define the template’s traits, and a statement sequence stats which contains initialization code and additional member definitions for the template.

Each trait reference $mt_i$ must denote a trait. By contrast, the superclass constructor $sc$ normally refers to a class which is not a trait. It is possible to write a list of parents that starts with a trait reference, e.g. $mt_1 \text{ with } \ldots \text{ with } mt_n$. In that case the list of parents is implicitly extended to include the supertype of $mt_1$ as first parent type. The new supertype must have at least one constructor that does not take parameters. In the following, we will always assume that this implicit extension has been performed, so that the first parent class of a template is a regular superclass constructor, not a trait reference.

This is not something you would normally do. And there’s a good reason for it.

When should you use `extends` on a trait?

Scala’s traits are “stackable”, and can be used for “stackable modifications”. This feature is well blogged on, and not the main purpose of this current post, so go ahead and take a look at the basic example from Programming in Scala book.

The reason it works so well, is because each trait stacked extend IntQueue, and thus enforcing it’s own place in class linearization to the left of the implementing class, so super calls are always called in proper order. If we would not have extended, but merely enforce a mixin with self type, we wouldn’t be able to call super, thus not be able to stack operations.

import scala.collection.mutable.ArrayBuffer

abstract class IntQueue {
  def get(): Int
  def put(x: Int)
}

trait Doubling extends IntQueue {
  abstract override def put(x: Int) = { super.put(2 * x) }
}

trait Incrementing extends IntQueue {
  abstract override def put(x: Int) = { super.put(x + 1) }
}

// replacing definition with commented out
// self typing code won't compile:
//
// trait Filtering { this: IntQueue =>
trait Filtering extends IntQueue {
  abstract override def put(x: Int) = {
    if (x >= 0) super.put(x)
  }
}

class BasicIntQueue extends IntQueue {
  private val buf = new ArrayBuffer[Int]
  def get() = buf.remove(0)
  def put(x: Int) = { buf += x }
}

Usage:

scala> val q = new BasicIntQueue with Doubling with Filtering with Incrementing
q: BasicIntQueue with Doubling with Filtering with Incrementing = $anon$1@5e3dd1f3

scala> q.put(-3);q.put(0);q.put(-1);q.put(1)

scala> q.get()
res1: Int = 2

scala> q.get()
res2: Int = 0

scala> q.get()
res3: Int = 4

scala> q.get()
java.lang.IndexOutOfBoundsException: 0
  at scala.collection.mutable.ResizableArray.apply(ResizableArray.scala:46)
  at scala.collection.mutable.ResizableArray.apply$(ResizableArray.scala:45)
  at scala.collection.mutable.ArrayBuffer.apply(ArrayBuffer.scala:49)
  at scala.collection.mutable.ArrayBuffer.remove(ArrayBuffer.scala:173)
  at BasicIntQueue.get(IntQueue.scala:30)
  ... 36 elided

class linearization?

The specs define linearization according to the following formula:

$$ \mathcal{L}\big(\mathcal{C}\big)=\mathcal{C},\mathcal{L}\big(\mathcal{C_n}\big)\vec{+}\ldots\vec{+}\mathcal{L}\big(\mathcal{C_1}\big) $$

Where $\vec{+}$ means you add new traits to the right, but only keep the right most appearance of the trait.

$$ \begin{alignat*}{3} a,A\vec{+}B&= a,\big(A\vec{+}B\big) && \textbf{ if }a\notin B \\\\ &= A\vec{+}B && \textbf{ if }a\in B \end{alignat*} $$

This means a class $\mathcal{C}$, or in our case q, is linearized as:

val q = new BasicIntQueue with Doubling with Filtering with Incrementing

q = $\mathcal{C}$
BasicIntQueue = $\mathcal{L}\big(\mathcal{C}_1\big)=\{BasicIntQueue,IntQueue,AnyRef,Any\}$
Doubling = $\mathcal{L}\big(\mathcal{C}_2\big)=\{Doubling,IntQueue,AnyRef,Any\}$
Filtering = $\mathcal{L}\big(\mathcal{C}_3\big)=\{Filtering,IntQueue,AnyRef,Any\}$
Incrementing = $\mathcal{L}\big(\mathcal{C}_4\big)=\{Incrementing,IntQueue,AnyRef,Any\}$

$$ \begin{aligned} & q,\mathcal{L}\big(\mathcal{C}_4\big) \vec{+} \mathcal{L}\big(\mathcal{C}_3\big) \vec{+} \mathcal{L}\big(\mathcal{C}_2\big) \vec{+} \mathcal{L}\big(\mathcal{C}_1\big) \\ & q,\mathcal{L}\big(\mathcal{C}_4\big) \vec{+} \big(\mathcal{L}\big(\mathcal{C}_3\big) \vec{+} \big(\mathcal{L}\big(\mathcal{C}_2\big) \vec{+} \mathcal{L}\big(\mathcal{C}_1\big)\big)\big) \\ & q,Incrementing,\mathcal{L}\big(\mathcal{C}_3\big) \vec{+} \big(\mathcal{L}\big(\mathcal{C}_2\big) \vec{+} \mathcal{L}\big(\mathcal{C}_1\big)\big) \\ & q,Incrementing,Filtering,\mathcal{L}\big(\mathcal{C}_2\big) \vec{+} \mathcal{L}\big(\mathcal{C}_1\big) \\ & q,Incrementing,Filtering,Doubling,\mathcal{L}\big(\mathcal{C}_1\big) \\ & q,Incrementing,Filtering,Doubling,BasicIntQueue,IntQueue,AnyRef,Any \end{aligned} $$

Why should you care?

Well, to understand the subtle differences between extending or enforcing a mixin, you need to know about how class linearization is performed. Now, notice how when we defined the traits with extends, the linearization of that trait transitively contained the extended other trait. e.g: Doubling class linearization, contained IntQueue. This means, that as a user, no matter how I mix Doubling in my bottom type, in the linearization, IntQueue will always going to be found right to Doubling, and will always be the super. More importantly, IntQueue is going to be initialized prior to Doubling since initialization order takes effect from the right most element in the linearization, and advancing to the left. This is of-course not a problem with IntQueue case, and exactly what we want and expect, but sometimes, you would want to let the end user be in charge of initialization order.

The weird case of the `val` in the `trait`

As you probably know, traits are not interfaces. A trait can hold non abstract members, whether defs, vals, etc’… normally, you shouldn’t care about the linearization of your class. But if your traits interact with each other, and contain (possibly uninitialized) vals, you might (depends on how you defined your class hierarchy and inter-trait interaction) encounter some puzzling NullPointerExceptions. In these cases, since scalac prohibits any form of circular inheritance, a user can re-arrange mixins order of the bottom type, and carry on. Given of-course the user has full control of the class linearization. When you enforce a mixin using self typing, your trait, and the trait you enforce mixin with, can appear in any order once linearized. The user is in full control. And you can (though not necessarily should) use anything from the enforced mixin, as if it was “extended regularly”. As long as you also type alias this.

`this` aliasing?

this aliasing isn’t something new or unknown. There are many good reasons to do so¹, but for now, just know there are several ways to do it, with very subtle differences between them.

trait A { self => ... }
trait A { self: B => ... }
trait A { this: B => ... }
trait A { _: B => ... }

In the first option, you give an alias to this, usually, so you would be able to refer to it from an inner class (which is quite handy if you utilize path dependent types). The second is interesting, it will force implementing classes to also mix in B trait. Options 3 & 4 are equivalent as much as I know (please correct me if I’m wrong).

conclusion

Adhering to the principle of least power, you should choose the most restrictive approach you can get by with. If all you need is to know your trait is always mixed with another trait², use only a type (option 4). Also if you need to use another trait capabilities, but only from within a method, or in any way not during initialization, use self typing (options 2, 3, 4). If you also have inner classes and refers to this in the code, alias it as something else (convention is “self”) to ease readability. If you depend on another trait during initialization, then extend it to ensure correct ordering in class linearization. But do it only if you really must.

maybe more on that in a future post.↩︎
you may think what would be a good usecase. Well, I’m wondering about it myself. Maybe if you have a sealed trait, and you want the implementing classes to have some functionality, but you don’t want any other class to have that functionality and still want to put it in a different file. This way you enforce a trait from another file can only be mixed in with your sealed trait, and offer functionality without overloading too much logic in a single file. got any better idea? I’d love to hear :)↩︎

FP-ish patterns

Background

My twitter feed is becoming more and more (pure) FP oriented. Many of the people I follow from the Scala community are advocating for Haskell over Scala lately. To be honest, I was always intrigued about pure FP, but never got to use it in the “real world”¹. I always worked in teams that had OOP mindset, and codebase. With Scala I was able to shift the balance a little bit towards FP. I advocated for referential transparency, strongly typed over stringly typed code, higher order functions, higher kinded types, typeclasses, etc’… I aimed to be more FP in an OO world. But I never managed to get my peers into learning together, and using, “pure FP” with libraries like cats or scalaz. So I wonder, does pure FP really is the answer - the silver bullet - I’m looking for, or should we tilt the balance less towards purity in Scala?

Harsh criticism against impure Scala

In the latest scalapeno conference, I attended John De Goes’ keynote “The Last Hope for Scala’s Infinity War”. In the talk, John claimed that: > “Some of the proposed features in Scala 3 are targeting someone who doesn’t exist”

He referred to features like Type Classes & Effect System. features for no one

But the truth is, that john was wrong. There is at least one person that wants such features². There is a middle-ground. And I want to believe I’m not alone, and some other people see the value Scala has to offer for FP lovers (wannabes?) working with traditional OO programmers, trying to make a difference. neither

Like John, I love Scala. but unlike John, I don’t think we need to sacrifice half the community

And I don’t want to see all the crossed out features removed from Scala: liabilities?

Scala is expressive

I was recently asked, why I love Scala. I answered that with Scala, It’s very easy for me to express exactly what I mean for the program to do, and that it’s easy to expose beautiful (and safe) functional interface, while encapsulating impure logic and gaining the benefit of both worlds. I was then asked to give an example, of short code that I find easy to express in Scala, and hard(er) to write in other languages. I choose something I’ve written a while ago, and I find as a nice example for such FP-ish pattern.

def mapr[A,B](as:         Vector[A])
             (f:    A  => Future[B])
             (g: (B,B) => Future[B]): Future[B]

So… what’s so special about mapr? A quick scala thinker will implement it with something like³:

Future.traverse(as)(f)
      .flatMap(_ reduce g) // if g were (B,B) => B

And it can be fine, considering the usecase. It wasn’t fine in our case.

The “real world” case

Consider A to be file names to fetch from a S3 bucket. But not just any file, it’s a CSV with time series events. B is a time based aggregated states series of the events. f can be “fetch & aggregate” a single file. But since many “sources” (S3 files) can add data, we should think about merging (reducing) multiple sources into one uber states series⁴. Thus we need g to “merge” two time based aggregated states into a single time based state series. Now, file sizes range from a few MBs, up to ~10GB. And this is important, because in the simple solution, we cannot start reduce-ing the small files, until we are done fetching and transforming the bigger 10GB files. Also, if the first A in the Vector is also mapped to the heaviest B, the reduce will be expansive since we always merging ~10GB B.

Lawful properties

In this case, there are interesting things to note about g⁵:

g is assocciative, it doesn’t matter how we group and merge two time based series states.
g is commutative, order is irrelevant. switch LHS with RHS, and get exactly the same result.

So now, our random pure-FP dude might say: great! your category B sounds very similar to a semilattice. Let’s also prove that g abides the idempotency law, and that g(b,b) == b for any $b$, and maybe we’ll find a useful abstraction using semilattice properties.

Well, that FP-programmer is actually right. and all that high gibberish talk actually has solid foundations. And in fact, that function g over B I just described does define a semilattice. Bs has partial ordering⁶, g acts as the “join” operation, and we even have an identity element (the empty time series), so it is even a “Bounded Semilattice”.

But this is totally irrelevant and out of the question’s scope. Remember, we are working in an OO organization. If we start defining abstractions over semilattices (or maybe there are ones in cats or scalaz libraries? I really don’t know), The code will become one giant pile of gibberish in the eyes of my coworkers. And we don’t even need it. What is needed, with the realization that g is associative & commutative, is a very natural optimization that pops to mind: why wait for all A => B transformations? whenever 2 Bs are ready, any 2 Bs, we can immediately apply g and start the merge process.

So, without over abstracting, I came up with the following piece of code (brace yourselves):

def unorderedMapReduce[A, B](as: Vector[A])
                            (f: A => Future[B], g: (B,B) => Future[B])
                            (implicit executor: ExecutionContext): Future[B] = {

  val promises = Array.fill(2 * in.size - 1)(Promise.apply[B])
  var i = 0 // used for iteration optimization
            // (not needing to search for uncompleted
            // promise from start every time)

  def completeNext(tb: Try[B]): Unit = tb match {
    case Failure(e) => promises.last.tryFailure(e) // fail fast
    case Success(b) =>
      // We're not synchronizing i, since we can guarantee we'll always
      // get an i that is less than or equal to latest i written by any
      // other thread. But we cannot use i += 1 inside the loop,
      // since it may result with skipping a cell in 2 threads doing
      // the increment in parallel, so each thread get's an initial copy
      // of i as j, and only increment it's own copy. eventually,
      // we replace i with a valid value j (less than or equal to
      // first not used promise)
      var j = i
      var p = promises(j)
      while ((p eq null) || !p.trySuccess(b)) {
        j += 1
        p = promises(j)
      }
      i = j
  }

  as.foreach { a =>
    f(a).onComplete(completeNext)
  }

  promises
    .init
    .zipWithIndex
    .sliding(2,2)
    .toSeq
    .foreach { twoElems =>
      val (p1, i1) = twoElems.head
      val (p2, i2) = twoElems.last

      // andThen side effect is meant to release potentially heavy
      // elements that otherwise may stay for potentially long time
      val f1 = p1.future.andThen { case _ => promises(i1) = null }
      val f2 = p2.future.andThen { case _ => promises(i2) = null }
      failFastZip(f1,f2)
        .flatMap(g.tupled)
        .onComplete(completeNext)
    }
  promises.last.future
}

// regular Future.zip flatMaps first future, so it won't
// fail fast when 2nd RHS future completes first as failure.
def failFastZip[A,B](l: Future[A], r: Future[B])
                    (implicit executor: ExecutionContext): Future[(A,B)] = {
  val p = Promise[(A,B)]()
  l.onComplete(_.failed.foreach(p.tryFailure))
  r.onComplete(_.failed.foreach(p.tryFailure))
  for {
    a <- l
    b <- r
  } p.success(a -> b)
  p.future
}

I can imagine the horror on the face of our random FP-dude, an Array (mutable), vars, nulls, side effects,… OMG. John would not approve such abomination. But before you panic, bare with me and let’s break it down.

The what & how

The goal is to have a “bucket” of ready B elements, and whenever we have 2 or more Bs in the “bucket”, we take a pair out of the bucket, compute g on it, and when g returns with a new B, we put it right back in the “bucket”, and we continue to do so, until only a single finite B element is left in the bucket. this is our return value.

The way it is done, is simple. we have $n$ A elements in the original sequence, each will be mapped to a single B, and since every 2 Bs are used to generate a new B, we need room for another $n-1$ Bs in the bucket. Overall, $2n-1$ elements, and our “bucket” can be just a simple Array. We also want to parallelize the computation as much as we can, so some construct to handle the asynchronous nature of the computation is needed. I used a Promise[B] to store the result. So our “bucket” is simply an Array[Promise[B]] of size $2n-1$.

Have a look at the following figure: This illustrates the order of computation, when the order is:

as(2)
as(1)
g(as(2),as(1))
as(3)
as(0)
g(g(as(2),as(1)),as(3))
g(as(0),g(g(as(2),as(1)),as(3)))

In the simple FP approach (traverse + reduce), same execution will result with the following computation order:

as(2)
as(1)
as(3)
as(0)
g(as(0,as(1))
g(g(as(0,as(1)),as(2))
g(g(g(as(0,as(1)),as(2)),as(3))

Which means we don’t take advantage of the early completed computations.

More benefits

Using early completed computations isn’t the only reason I argue the suggested code is superior. It’s not just we start computations eagerly, implicitly it also means that heavy elements are left to be dealt in in the end, and we don’t need to reduce 10GB files at every step of the way⁷. We also get “fail fast” semantics; for example, if g fails for whatever reason on as(2) input, in the code I suggest, you fail fast since it is mapped directly as a failed Future result. Also, whenever a future completes, we have a side effect to clean up values that are not needed anymore, so we don’t leak.

Bottom line

What I try to emphasize using the example I showed, is that there are good reasons to write impure functional code. In cases like this, you enjoy both worlds. The interface is functional, it is referential transparent (as much as Future is considered referential transparent). Perhaps the above is achievable using pure functional style (I would love to know how. really!), but my gut is telling me it won’t be so simple. And as someone who works mostly in hybrid FP-OO teams, I can’t go full FP. Not at first anyway… Using Scala enables me to introduce a smoother transition into FP without getting my peers too angry or confused. It enables me to break the rules if I really need to. I wouldn’t sacrifice the impure parts of the language. I truly think they are too valuable.

Other than maybe a tiny PR to coursier which uses scalaz.↩︎
You are reading that person’s blog. Obviously :)↩︎
Actually, I’d bet he would use Traversable and Task over std lib’s Future.traverse↩︎
There are multiple ways to approach that problem, and actually, we ended up with another solution, that utilized akka-streams, merging multiple sources with a custom stage & scaning to output a stream of aggregated state in time order.↩︎
Whenever I encounter such realization, I automatically translate it to property checks tests. So to test that g is lawful, all I needed is a very simple scalacheck test to test associativity & commutativity.↩︎
think about b1 != b2, which means that either g(b1,b2) > b1 and also g(b1,b2) > b2, or that b1 and b2 already has order relation between them. It may be more obvious in some situations (and it was obvious in our case).↩︎
Kind of reminds me of the matrix chain multiplication problem.↩︎

The worst interview question

tl;dr

We, the software development industry people, seek new job opportunities every now and then. Those of us who are in the game long enough, have seen all kinds of interviews. Maybe even conducted interviews for others. As someone who has been on both sides of the fence, I’d like to share some insights, mostly aimed for those conducting the interview, and I’ll do it by sharing a real example.

Assume nothing

Every interview conductor has been interviewed by someone else at some point. This is how we get in. It seems like some people tend to forget how it looks from the other end of the table. When asking technical or theoretical questions, one should be very clear, and verify the person standing in front of him understood the question. More often than not, we assume people understand what we meant for them to understand, only to find out later it wasn’t the case. We also tend to assume people think similarly to us about the problems we present to them. Obviously, those assumptions are wrong.

The trick is to not use any tricks

When we ask a question, it should be clear to us what information can we infer on the candidate standing before us from the way he answers. Some questions has no value at all. Usually, “trick questions”, for example, has no value. Either the candidate knows the question, and the trick to solve it, or they don’t. Asking such question yields nothing meaningful if the candidate knows the answer by heart. And have little value if they don’t (you do get to see how they think, and how they approach the problem). Thing is, it hurts the candidate confidence if you present a question they fail to answer, and it will affect them for the rest of the interview. Some trick answers, are not even the (most) correct answers to the question. A (very) good candidate might know better, and a fixed minded interviewer, who has his mind set on the trick answer, might not understand it.

The worst interview question

I was once asked to solve such trick question. I also knew the trick and that it wasn’t the best approach. The question was (essentially¹): > given a shuffled sequence of $n - 1$ numbers, all distinct and part of an arithmetic sequence range of $n$ numbers, find the missing number in the sequence.

There are many ways to answer that question. I will present 4 solutions in rising complexity order, but eventually, you will see that the simple solutions I discuss here have gentle flaws, and best answer, is actually the most complicated one. Disclaimer: after writing this post, it occured to me that there is an elgant and correct solution, simply XOR all the numbers and the full range itself. Since all numbers cancel each other, we are left with the one number in the range that is not present in the sequence. But neither I nor the interviewer have thought of that at the moment. Moreover, I feel it’s also important to note (though not the main goal of the post) that abstracting the question too much, like what was done here, only increases the gap between the understanding of the interviewer (and what he meant), and the understanding of the candidate². Anyway, we are aiming for linear (time) complexity answer³.

1st Answer (the trick)

We are talking about an arithmetic sequence, so let’s use the formula: we can scan the sequence, and find $min$, $max$, & $sum$ of given numbers, and compute the difference: $$result=\frac{n(min + max)}{2}-sum$$ Simple. Elegant. And flawed to the core! So what’s wrong with it? Well… The implicit assumption here, is that adding 2 numbers is done at constant time. Isn’t it? NO! it’s only constant if you use primitives such as 32 bit int, or 64 bit long, etc’… But we have no restrictions on the length of the given sequence. If we use primitives, we risk arithmetic overflow, and get a wrong answer. So we need to use something like BigInteger, which has addition operation in linear complexity with the numbers of digits (bits) of the number. I.e: logarithmic in terms of $n$. So either it’s wrong, or we ended up with implicitly $n\log(n)$ complexity.

2nd Answer

OK, let’s try again. we have an arithmetic sequence, so it means we have a bijective function⁴ $f$ into $\mathbb{N}$⁵. This means we also have the reversed function $f^{-1}$. We can initialize a boolean array a with size of $n$ and false values in all cells. On the next step, we iterate over the original sequence, and for every number $k$ we encounter, we compute the index $i=f\big(k\big)$, and set a[i]=true. Once we are done, the boolean array will be filled with true values in all cells, besides in the cell corresponding to the missing number. We can easily iterate over that array, and find that index j, and compute the result with $f^{-1}\big(j\big)$. Is this better? well… not so much… we basically traded our $O\big(n\log(n)\big)$ time complexity and $O\big(1\big)$ space complexity with linear time & space complexity. This feels like cheating. Trading time complexity with space complexity isn’t really improving. And we can easily think of scenarios where we don’t have the luxury of allocating so much memory.

3rd Answer

From now on I’m going to explain the solutions in terms of numbers in the range $\big[1,n\big]$ instead of speaking about our bijective function $f$ and it’s reversal $f^{-1}$, for simplicity. Trying again, we can come up with a slightly more complex solution, but more “memory friendly” (pseudo code):

i,j ← 0
while(i < n - 1) {
  j ← a[i]
  while(j > i) {
    swap(a[i],a[j])
    j ← a[i]
    if(j == n) {
      return i
    }
  }
  i++
}
return n - 1

So what’s going on here? we scan the sequence a, and as long as a[i]==i we do nothing. When it’s not equal, it means it is larger⁶. In this case, we look at the cycle a[i] → a[a[i]] → … → i, and swap elements as we go until we finished the cycle, and all the elements we’ve seen, are now properly placed in their corresponding indices. There is one special “cycle” though. The “cycle” (list actually) containing $n$ itself. This list will start with the missing element’s index, and will end when we reach the cell containing $n$. Why? I’ll leave it as an exercise for you to figure out. you can check out the hint if you want⁷. So, is this better? well yes. but still not perfect. we still used an assumption implicitly, without realizing the question does not allow it. I’m talking about RAM. The ability to hop between indices back and fourth in $O\big(1\big)$ time is not explicitly given, and we cannot assume it. In case we do have RAM access, we use $O\big(n\big)$ time & $O\big(1\big)$ space. So we’re half way there. But since in our world, we may talk about a linked model only (think about distributed graphs, scattered files on some cloud, etc’…), we can try to do better.

4th Answer

In this last answer, I’m gonna count on the reader having some basic CS 101 knowledge (don’t worry too much if you don’t, I’ll link to resources where necessary), and will only describe the idea in higher level, since it’s gonna be too terse to delve into all the lower level details. Take a moment to refresh your memory on quicksort algorithm. We’ll tear it apart, and use the building blocks to solve our problem. Wikipedia’s high level description of the algorithm is as follows:

Pick an element, called a pivot, from the array.

Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.

Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Wikipedia is speaking in terms of “array”, but quicksort also works perfectly well on linked lists. What we will do, is similar:

Pick a GOOD pivot

Use partition

After partition, check if index(pivot) == pivot or index(pivot) == pivot - 1 ⁸

If equal recurse only on > pivot part of the sequence

If pivot is larger (by 1) than it’s index, recurse only on < pivot part of the sequence

When sequence is small enough (e.g. < 5), sort it, and check sorted sub-sequence together with next index’s element (if exist, could be a pivot from previous iteration). the gap will be there.

What are we aiming at here? well, before we go into complexity analysis, we need to explain why it works. It’s not a formal proof, but good enough. We know we have all the numbers except one in the range $\big[1,n\big]$. And we know the indices are $\big[1, \dots, n-1\big]$. So if we would’ve sorted the sequence, all the elements before the gap would’ve been found at the correct index (a[i] == i), and all the elements larger than the missing element would’ve been at an offset of one from their index (a[i - 1] == i). So if we place the pivot at exactly the correct index, we can tell by looking at the offset if we are higher or lower than the missing element. So we do something very similar to quickselect, only instead of knowing up front the index $k$ we want, we iterate according to the index offset. When we finish, the gap might be at a neighboring cell (if missing element index was chosen as pivot at a previous round of the iteration), and we check $O\big(1\big)$ sorted elements containing the gap for the missing element. I claim that if we choose a good pivot, this process will take linear time. But before I explain why, I’ll give you a minute to see that good pivots can be chosen in linear time. The tl;dr of it, is that we can choose a pivot that will be in the range $\big[0.3n,0.7n\big]$, so we avoid the worst case leading to $O\big(n^2\big)$ running time. in the worst case, we are always left with 70% of our sequence to check. Each iteration is $O\big(n'\big)$ where $n'$ is the size of the subsequence we iterate on. This is because choosing a good pivot takes $O\big(n'\big)$ and partition takes another $O\big(n'\big)$. in total, we’ll get $$\sum_{i=0}^{log_{10/7}{n}}{2{\Big(\frac{7}{10}\Big)}^{i}}n=2n\sum_{i=0}^{log_{10/7}{n}}{{\Big(\frac{7}{10}\Big)}^{i}}\lt2n\sum_{i=0}^{\infty}{{\Big(\frac{7}{10}\Big)}^{i}}=2n\cdot{3\frac{1}{3}}=O\big(n\big)$$

There is so much I’m not explaining here, and many short cuts taken (especially in the math). Like, why (and how) does it work on linked lists, why it’s OK to compare numbers and assume it’s $O\big(1\big)$, but not ok to assume this for addition (actually, it’s not. but in the first solution we summed up $n$ elements, meaning $n^2$ must be less than our primitive max value. when we compare primitives without summing, we can use the entire primitives range [think of unsigned 64 bit long…], which is still better than using $\sqrt{primitive\ max\ value}$ ), etc’… But I want to cut to the point.

The point

This is a very bad question to ask in job interviews. But what I wish for you to take from this, is not the fact that some questions are more suited than others for job interviews (well, that too). It is the fact that in most cases there is a huge gap between the candidate and the interviewer. I’m not talking about intelligence here. I’m talking about the fact that any question can be misunderstood very easily, as any answer can be misunderstood very easily as well⁹. So neither the interviewer, nor the candidate should be taken lightly. We tend to disrespect who we don’t understand too easy. Try to overcome the urge, and try to put yourselves in the other side of the table. Of course this is aimed more for the interviewer, than the candidate. And keep in mind, you as the interviewer, want to hire the best and smartest person for the job. So don’t be hasty and give up one someone who might be that perfect candidate. Force yourself to understand. And remember, in our industry, it’s very possible you’ll find yourself in the candidate shoes in the future.

they did not actually use the term “arithmetic sequence” since that would give hint to the trick they were after. Instead, they gave a vague definition of numbers spaced evenly between two arbitrarily large numbers $m$ & $M$↩︎
candidate might understand exactly what he’s being asked. In this example, and since the interviewer was obviously after the trick answer, he could’ve present the question as numbers in the range $\big[1,n\big]$, instead vaguely defining an arithmetic sequence without naming it↩︎
because sorting in $O\big(n\log{n}\big)$ and scanning for the gap is trivial, and we can obviously do better↩︎
meaning one‑to‑one correspondence↩︎
$\mathbb{N}$ stands for the naturals numbers↩︎
Why? well… let’s leave it as an exercise for the reader ;)↩︎
This is not easy or trivial (even with the hint), and the only reason I’m leaving it out and not explaining in full, is because it’s not this post’s goal, and it is getting lengthier than I thought already.↩︎
That’s the only 2 possible options.↩︎
And as you probably understand, this is exactly what happened to me on that occasion. I should’ve taken the understanding gap into consideration.↩︎

Search This Blog

You can’t have it both ways

A trade-off

Why not actually?

What does quality has to do with this?

What’s in an estimate?

“We’re not using estimates, we do story points.”

Becoming a healthy organization

Being pragmatic

My suggestion?

But how?

Probabillity

Summing up

what are “osteoblasts” and “osteoclasts” anyway?

Where am I going with this analogy?

The analogy

Optimize your team for the job at hand

The “like-minded” trap; or how to diversify?

Most people are “above average”

This is actualy a post about software development. really…!

How so?

A bit more “fish talk”

OK, back to “software development talk”

Cultivating bacteria

Cultivating developement teams

Cultivating individuals

Focus

In summary

The blog gets a face lift

Why?

The plot thickens

Time to refactor

Attempt #1

Attempt #2

What’s next?

tl;dr

What’s wrong with the good old abstract class?

When should you use extends on a trait?

class linearization?

Why should you care?

The weird case of the val in the trait

this aliasing?

conclusion

Background

Harsh criticism against impure Scala

Scala is expressive

The “real world” case

Lawful properties

The what & how

More benefits

Bottom line

tl;dr

Assume nothing

The trick is to not use any tricks

The worst interview question

1st Answer (the trick)

2nd Answer

3rd Answer

4th Answer

The point

When should you use `extends` on a trait?

The weird case of the `val` in the `trait`

`this` aliasing?