The other day someone asked me why I was going through masters curriculum at this age. Their argument:
Most of what you are learning is theoretical and useless. What’s the point of revising data-structures at this point in your life?
Then last week, someone at work was working on a specific problem. In the last release they had 21 check-ins and one of the check-ins had introduced a bug. The team was trying to find which check-in introduced the bug.
To find the erroneous check-in, they were applying each check-in one at a time to the old codebase and then running the application to see if the bug could be reproduced. When I heard that they were doing that I spontaneously responded with:
You’re trying to use linear search algorithms to solve a problem that would be solved much more efficiently and with much less time complexity using a simple binary tree search.
What I meant was that instead of taking each check-in one at a time applying it and then running the code, the team could have just taken the first 11 check-ins together, applied them on the server in a single shot and then tested. Either ways, if the bug was found or not in the first 11 check-ins, we would know if we should look at the left side of the tree or the right side of the tree and with that one attempt, we would have eliminated 10 tests right away. That’s 10 times of applying check-ins, firing a build, running the code and trying to reproduce the bug.
Put simply, you merge 11 check-ins in a single shot and run. If you find the bug, the bug lies in one of the check-ins between check-in 1 to check-in 11 and if you don’t find the bug you know the issue lies with check-in 12 to 20. And then you repeat this process depending on which side of the tree (1-11 or 12-21) the bug lies in. Exactly how the binary tree search algorithm works.
During the times of Covid a collogue of mine had pointed me to an article that showed how you can apply binary tree search to do effective Covid testing and save a bunch of testing kits. It’s the exact same logic. If you have 100 blood samples, mix the first fifty samples and test. If you don’t find Covid in the mixed sample you’ve just saved yourself 50 test kits. If you do find Covid, mix the first 25 samples and do another test. Again, binary tree search.
Of course we don’t hand write code for binary tree search in the real world when we are coding these days. Most modern day languages provide us out of the box search functions which use the most efficient algorithms under the hood.
But that doesn’t mean we can’t see binary tree search as a thought construct. Real world Binary tree search based use-cases exist in our day to day life, and identifying them, helps you solve these problems way faster, even when the problems have nothing to do with writing code. Problems that benefit from binary tree searches, are all around you. The real question is, can you spot them?
Oh and yes, there is a point of revising some of your data structures at any point in your life because that knowledge itself is not as useless or impractical as you might think it is.
Comments are closed.