Pipes2K - A Pipes Screensaver demo in 2KB of JavaScript

 I'm willing to bet that a good number of people will recognize the below picture almost instantaneously - especially those who grew up in the 90s:

That's a picture from the popular Microsoft Pipes Screensaver - a screenshot of it running natively on a Windows ME laptop I've had since I was a kid.

Funnily enough, there really isn't that much going on in the screensaver: It's just a never-ending animation of interconnecting 3D pipes appearing and growing on screen. Nevertheless, I remember kids in school zoning out in front of it and watching it endlessly. To be fair, the animation was an impressive feat of graphics for the time period - especially when you consider most of the computers back then were falling back to rendering it via software exclusively. It's probably not a surprise then that it left a lasting impression on people and even decades later it's still finding its way into mainstream discussions. As Raymond Chen writes on the Microsoft dev blog, Gizmodo even went so far as to award it the title of  "The Best Screensaver of All Time".

I was thinking recently about what I'd like to codegolf next. I wanted to do something fun and unique. People have crammed a lot of stuff into small amounts of code - but from I can tell, a Pipes Screensaver clone in a *very* small footprint has never been attempted. Sure, there are various demos around online that feature 200-300 hundred or so LOC examples, but all the ones I can find end up importing a library (the JS ones typically use Three.js). Even if I were to spin up my own library using WEBGL, the boilerplate code alone would likely easily chew up a couple of kilobytes of space.

I knew there would be some significant concessions that would have to be made to stuff this into such a condensed script. For starters, the scene features one "Camera" angle that is a fixed Isometric perspective. This is the first trick I used to get away with not having to use any trig functions (cos/sin/tan,etc) that would have likely significantly increased code size. Instead, all 3D points are brute-forced, and as you'll see in the full uncompressed code, this allowed me to recycle a nested loop that's used by different geometries.

Despite its extremely small footprint, it even has a (albeit primitive) lighting system to add the look of depth to the pipes. To conserve even more bites the screen simply resets rather dissolving, but true to the original - it loops on forever. Here's a GIF of my 2KB JavaScript version running in Chrome:

Here's the gist that contains the golfed ~2KB code that runs the animation:

I could write a novel about why some of the design decisions were made the way they were (the first few iterations were hardly able to get golfed down to anything under 5KB). Some of the code just has to get stepped through in order to understand it in a meaningful manner if you intend on modifying or extending it.

That said - there are a few particularly head-scratching and unintuitive functions that are worth analyzing in depth. You'll want to read over the comments in the gist carefully.

Few other things worth mentioning:

- The original screensaver had a mix of pipe connectors: an "elbow", "ball", and occasionally a teapot. Via some more brute-force trickery I was able to get an actual 3D elbow-like curved connector painting. The code to approximate the points around the curve and the logic to determine which rotation and orientation to paint each elbow in added a few hundred bytes to the total code right there - so I removed it. Instead, a 3D sphere "ball" is always the connector, and its just wedged in the corners where 2 pipes meet in a way that makes it look enough like an elbow. 

- The GIF I originally posted on r/codegolf shows a collision of overlapping pipes a little over 2 seconds in to the video. Ironically - I discovered the root cause of the bug while I was typing up the writeup for this blog post. The GIF above was recorded after the bug was fixed and you'll notice there aren't any overlapping pipes. Still - due to the nature of how 3D points are mapped to the 2D raster, there's no guarantee it won't ever happen, but it should be extremely rare.

- There are enough repeating characters (like similarities of function signatures) in the golfed code using a simple replaceAll() and eval() call could get this down just slightly under 2KB. However, even with the assurance of modern sandboxed browser environments, many people are still (understandably) hesitant about running code they can't clearly see the intent of, so I didn't bother to post a version of that to reddit. Besides, for all intents and purposes 1.9K and 2.2K is kind of the same thing from a competitive perspective. If I managed to strip at least a few hundred more bytes from it I'll post a new version.

There were hours of experimentation and trial and error that went in to piecing together parts of the code in such a way that it A. worked, and B. actually fit in such a small footprint. The end state is way more intuitive to me than it would be to a fresh set of eyes. Please feel free to post a comment below if you're playing around with the script and would like to get clarification on any other parts of the code.

The ungolfed verison can be found in this gist: https://gist.github.com/edev90/b48c2684a1127f3eca949a59f465b9cd

Hope you enjoy this little demo clone of a piece of nostalgia and computing history!

The myth of the 10x developer

"10x" developers don't exist. Or at least... not in the way that people think (or hope) that they do. 

In theory a 10x developer is a programmer who is considered to be 10 times better than their peers.

The whole "10 times better" part cracks me up - I'm not really sure how you quantify "10x better". Does that mean the developer completes 10 times more unit tests than their peers? 10 times more comments? 10 times more code reviews? Drinking 10 times more coffee than every other game developer working triple overtime on a rushed AAA video-game? And why even stop at "10x"? Why not skip the 10x engineers and go straight for the 100x ones? Quantifying this thing gets absurd quickly.

I'm unsure of the origin of this myth, and I'm not keen on looking into it much anyway - I feel like during my pursuit of tracing this thing back to its roots I would just unearth even more layers of cringe. Unfortunately, people keep pushing the narrative further despite its outlandish nature for a simple reason: it's appealing. What programmer out there wouldn't want to be part of an exclusive "10x club"? Content creators capitalize on this and promise that watching their videos will answer your burning question: "how do I become a 10x developer?". Which is a bit of a shame, because many of these content creators were, or still are, developers themselves, and have to realize the bogus nature of this. 

Youtubers push the narrative by telling stories of devs who've accomplished seemingly superhuman engineering feats and talk as if the developers behind them are imbued with some mystical hard to attain skillset. These stories usually leave out the parts that talk about the countless hours of coding, trial and error, and learning the developers invested into perfecting their craft before they were able to pull off large-scale projects like the ones talked about in the videos.

Years ago, I built a digital signage application for a client that was synchronized across several of their office locations around New England. They wanted something that could be maintained by Java developers. Up until that point, I hadn't written a single line of code in Java. I familiarized myself with Java and had a prototype done in a little less than 2 months. It pulled data from a SQL server, featured images, played videos (utilizing VLC via JNI), and had a JSP-based control panel HR and Marketing leaders used to manage and refresh content. I recall that it was between 20,000 and 30,000 lines of code - not including the code in 3rd party libraries I used like JFreeChart and FTPClient in Apache Commons.

If my story was dramatized into a 10x dev motivational video, the title would be: "Programmer who never coded before learns Java and builds digital signange app from scratch in 8 weeks". The video would embellish and exaggerate every detail about the development process - all the while ignoring important details about my programming journey: like the more than 2 decades of experience I had coding and all the knowledge I was able to recycle and carry over into the digital signage app project. Not only did I have some intermediate experience with C++ experience (so Java syntax was easier to pick up due to similarities between the two languages), but also the development methodologies, tools, and time management habits I had adopted through the years were extremely helpful in forming a strong foundation for me to build off of.

The biggest problem with this 10x mentality? It can lead to a polarizing mindset.

Devs can be led to believe that they either "have it" or they "don't". They may think exceptional programmers have some "X factor" that enables them to pull off the development feats they do. If they think they "don't have it" they might come to the conclusion that they should just give up before they even try. It's beneficial and can even be a good motivating factor to aspire to being an amazing programmer, but you're going to get exhausted if you try to meet that expectation too quickly (especially for devs starting out in programming). 

On the other extreme side of the spectrum, someone might recognize in themselves a natural affinity to programming and assume they possess the magic "10x" trait - and develop an attitude of laziness and complacency: in their mind - there's nothing more they need to work at or improve to get better at. Not only this - but when people make this their entire identify they get frustrated when their "elite status" gets challenged.

I remember growing up there was a kid in my hometown that by all accounts certainly would have been what most people today would consider 10x: even as early as elementary school he was pretty good at C and Python. Once high school rolled around, some other programmers started to surpass him. This frustrated him, and he decided the best course of action was to move to another continent. Not another town or another state, but another continent. He believed (for some reason) that he wouldn't get challenged as much where he was going.

According to people from his inner circle, the relocation apparently didn't mitigate the issue for him. I guess he found himself going up against even greater competition at his new home, and went back to school with the new goal of being a "literary scholar" - a new field he was sure that, this time - he would definitely be better than the majority of his peers at. This might have been a rare coping mechanism... and in a way, sadly also a little comical, but its basically a disaster story about the "10x" mentality running amuck before the 10x term was even a thing.

It's impossible to find... or be, a "10x dev" because it's impossible to exactly measure programming skills in some sort of numerical fashion. There are, however, exceptional developers - devs who are extremely productive and know how to get stuff done.

Exceptional developers are creative and resourceful. They don't let a lack of resources or manpower get in the way: when they don't have what they need - they build what they need. If they're hindered by the tools or processes that were implemented before them, they'll code new scripts and tools themselves to speed those processes up.

It's not a dev who has all the answers - it's someone who knows how to find all the answers. Whenever I've helped to screen developers in hiring processes, I personally never cared about candidates that stumbled a bit remembering the proper syntax during a coding assessment - we all have the occasional mental block. What I did care about was their ability to ask good questions and synthesize creative solutions, even if it resulted in pseudocode that didn't compile.

Extremely productive coders are those who think before diving into coding - they've adopted a "work smarter, not harder" approach to problem solving. They've completed enough projects to know that its better to spend a little more time upfront mapping things out, white-boarding components, and doing their best to foresee and tackle edge cases before they're even encountered in the testing phases. 

Highly productive developers have also perfected a balance between impatience and patience. They'll persevere longer than most to solve a problem - but also know when its time to pivot to a new strategy when one particular path to solving a problem isn't yielding fruitful results.

Stop asking yourself, "How do I become a 10x developer?". Focus on making valuable contributions and get better and better at shipping them in an efficient manner. Learn and diversify your skill set and find new ways to solve problems. Tune out the noise and stop concerning yourself with trying to live up to fairy-tail expectations. Be competitive, but compete against yourself. Set the bar higher for yourself with each project. 

If you're waiting to hire a "10x" developer - you should forget about it because they simply don't exist. Every so often an organization will get lucky and stumble upon someone they deem worthy of the "10x" title and craft an interview template to detect more purple squirrels. Ironically, instead of finding more gifted developers, they'll just find more people who are good at gaming and passing those specific tests.

Hard-working, talented, productive, and resourceful developers, do exist, and they're everywhere - you just have to know the right ways to find them. The majority of modern day interview processes aren't conducted in a way conducive to finding such talented developers. But, well.... that's a topic that deserves a separate post on its own.

Make every project yield value

You can't guarantee that every product will be a major success - but you can guarantee that the development process of each one creates value for your organization every time. 

I've been consulting a lot over the past couple of years. One of the things I do is help leaders within smaller organizations make informed decisions regarding their tech stacks and the necessary tooling that should be in place to ensure their development processes and workflows are in line with their business needs and requirements. 

One trend that I've noticed an uptick in is with companies shifting their tech stack from Java and migrating over to Golang (often times I think this is more in response to evolving trends than actual necessity... but I digress...). Often times, these companies have a lot of legacy code written in Java that needs to be managed by Java devs. 

One of the groups I'm working with recently expressed interest in a new software project. Going forward, they want future features and microservices to be built in Go. There are 7 Java devs, and 2 dedicated Go devs currently on this group.

The initial group consensus was that both of the dedicated Go devs should handle the experimental project while the Java devs would cover the maintenance side of things on the Java side of their code base.

After analyzing their dev allocation, it was clear to me that there was ample Java resources allocated to the maintenance side of things - an area area where, frankly - the day-to-day work centered around bug fixes and occasional "change the color of some label or button" type 2-point sprint work. Feature requests had pretty much stalled, and there really weren't any signs pointing to a reversal in that trend.

I proposed an idea: pull a couple of the Java devs off the maintenance work and re-assign them over to the Go side of things. Now the Java devs will gain exposure to the Go tech stack and who knows - might even end up liking and excelling in that area more and find a fit on that team.

Going even further: The 2 Java devs that are being mentored by the Go programmers are senior developers. The Go developers, on the other hand, are entry to junior level. This dynamic might not seem intuitive at first if you're thinking about things from a hierarchical perspective - but I wasn't thinking strictly in terms of a hierarchical perspective - I was thinking in terms of what each side had to offer the other. The senior and lead developers are senior for a reason: they already have significant experience leading other engineers and working closely with stakeholders to ensure proper alignment of design decisions with business needs - why not offer the chance for the junior Go devs to get some experience in this area as well? 

The process I've outlined here isn't exactly groundbreaking - it's been thought of before: I've seen it proposed many times in the past by not only me, but other devs I've worked with. It is unique though in the sense that in reality, it's rarely implemented. When there's a new project, leaders will often hyper-focus on which developers can get certain parts of the project done the fastest. There should be an emphasis on structuring the project around fostering career development and a climate of talent diversification - building a more flexible team that can support multiple sides of an organization if need be. From my perspective, there's no better time to let other's break into different sides of the product than during a new speculative endeavor.

The project is still in the earliest phases of production and only time will tell how much money it's going to bring in. In a lot of ways though, it's already a success: the organization now has Go devs with heightened leadership abilities, and an added layer of insurance with Java devs that now have enough insight into the Go codebase that they can assist with a hotfix or other high-priority fixes as they arise.

Some products skyrocket, others barely break even, and inevitably, some will even fail without ever yielding a dime; then there are others that provide just enough cash flow to cover opportunity costs of the resources poured into those projects. Regardless - it's entirely possible to derive value from the project regardless of the monetary value it yields. 

This isn't to say, of course, that a company should just leap into a new product idea even if they think it won't make them money. However, once the green light has been given to proceed with a new idea that has a high chance of turning profit and things have progressed to the implementation and design phase, there should be other decisions besides simply determining which engineers can complete which tasks the fastest. Engineering talent and resources should be arranged in a way that not only maximizes development efficiency, but also learning and talent dispersion. This will lead to a more robust, flexible, and agile engineering environment equipped to respond more swiftly to evolving expectations. 

Finding the square root of a number using binary search

The other day I was going through a hard drive full of homework assignments I did years ago in college.

I found one of the assignments interesting enough that I thought I would include the solution on here. The goal of the assignment was to write a function that didn't use any built in math library calls to calculate the square root of a number. 

The instructions stated that 1000 test cases would be performed, and they ALL had to pass in less than a second. In other words: the sum of all the runtimes of each of the test cases had to total less than a second -- which is pretty much to force the coder to get creative and not write a brute force solution (a bruteforce solution.. while easy to code, would perform horrendously). 

For reference, a brute force solution would look something like this:

public static double bruteForceSQRT(double num) {
    final double precision = 0.00000001D;
    double result = num;
    if (num < 1.0D) {
        if (num == 0) {
            return 0;
        } else if (num < 0) {
            // Handle these cases Like Math.sqrt() does it
            return Double.NaN;
        }
        result *= 2;
    } else {
        result /= 2;
    }
    while(result*result > num) {
        result -= precision;
    }
    return result;
}

In the brute force approach we halve the number we are given and then decrement that by a certain precision decimal value until we reach an approximated value that is extremely close to the square root of that number. Unfortunately, the greater the accuracy that you desire, the drastically slower the runtime is going to be. It took more than 2 seconds! for the bruteforce code to calculate the square root of 25 - which of course is ridiculous. 

The approach I went with for the homework assignment utilized binary search instead. Binary search provides superior performance and accuracy, and looks something like this:

public static double bin_sqrt(double num) {

double left = 0.0D, right = num;

if (num < 1.0D) {

if(num == 0) {

return 0;

}

else if (num < 0) {

// Handle these cases Like Math.sqrt() does it

return Double.NaN;

}

// If we got to here then 0 < num < 1

// so we want to actually set LEFT to num, and RIGHT to 1

// The resulting square root value will be GREATER than num

// (i.e: the square root of 0.25 is 0.50)

left = num;

right = 1.0D;

}

double middleNumber = (right + left) / 2;

double lastMiddleNumber = num;

double mSquared = middleNumber * middleNumber;

while (lastMiddleNumber != middleNumber) {

if (mSquared > num) {

right = middleNumber;

} else if (mSquared < num) {

left = middleNumber;

}

lastMiddleNumber = middleNumber;

middleNumber = (right + left) / 2;

mSquared = middleNumber * middleNumber;

}

return middleNumber;

}

The binary search method is clearly faster than the bruteforce approach - but you might be wondering -  how does it stack up against the built in Math.sqrt() function? 

Below is a table I put together which shows the results of runtimes for the binary search version (bin_srt) vs. the standard Math.sqrt();

As you might expect, Math.sqrt() in almost all cases is still significantly faster than the binary search method - sometimes almost 5 times as fast (on modern day systems, Math.sqrt() is likely to execute the square root hardware instructions directly - which is likely going to beat any homegrown software solution any day). 

Nevertheless - I could see the binary search method being useful in some niche cases: like if you can't or don't want to include a standard math library due to size constraints for a game jam, or solving an algorithm question, or, as in my original case - solving a homework problem. In those cases this is a perfectly fine solution that offers a good balance between speed, efficiency, and accuracy. 

Lastly (and arguably most importantly), this example stands as another testament to the power and efficiency of binary search and the many use cases it can be applied to.

A Java version of the binary search square root implementation can also be found on my github here: https://gist.github.com/edev90/bda51627b722a0d825453b3d797b7283

Adding two binary strings together

I was recently mentoring a junior dev who was sharing some stories with me regarding his interview experience for the current role he's in. He recalled that he was thrown some "curve balls" when it came time to the coding challenge portion of the interview. He was faced with three questions: the first was an inverting binary tree question - and the second was a binary search problem. Pretty common and typical questions. He aced the first two... but had a little trouble with the third one: adding two binary strings together. 

This problem is generally regarded as "easy", but some of the easy problems require more planning and understanding the underlying mechanics more than others - and this is one of them. In retrospect, he realized that jumping right into coding prior to thinking about the edge cases and logic is what made this feel more like a medium or hard question.

The goal of the Add Binary Strings problem is to write a function that takes two binary strings a and b and returns a third binary string that contains the sum of a and b.

The problem has multiple variations depending on who's asking, but typically one of the commonalities is that the binary strings can be hundreds of digits long - which is pretty much to force you to get creative and not just convert the strings to integers, add them together, and then convert the integer sum back to a string of bits. 

A sub-10 line solution

Many of the common programming languages supported by coding interview platforms all bundle their own variation of BigInteger - functionality that allows us to perform bitwise and mathematical operations on large numbers outside the bounds of the typical 32 or 64 bit data types that standard variables are capped at.

If we go down the BigInteger route, we can literally code a solution in just a few lines (code snippet examples in Java, Golang, Javascript, respectively):

// Java

public String addBinary(String a, String b) {

return new BigInteger(a, 2).add(new BigInteger(b, 2)).toString(2);

}

// Go

func addBinary(a string, b string) string {

aAsBigInt := new(big.Int)

aAsBigInt.SetString(a, 2)

bAsBigInt := new(big.Int)

bAsBigInt.SetString(b, 2)

return aAsBigInt.Add(aAsBigInt, bAsBigInt).Text(2)

}

//JavaScript

var addBinary = function(a, b) {

return (BigInt("0b"+a) + BigInt("0b"+b)).toString(2)

};

This works, but we're kind of cheating because we didn't actually implement any of the logic ourselves - so let's see how we would roll our own algorithm to achieve the same result.

Implementing the algorithm ourselves

Take the example below - we are adding two numbers: 15 (1111 in binary) and 12 (1100 in binary):

At any given iteration, we have two things we need to do: figure out the current output bit, and the current carry bit that we pass over to the next iteration of the loop. The carry bit will be set to 1 if a column's sum is greater than or equal to 2 (meaning we have an overflow).

This is actually rather straightforward. In each column (starting from the far right) we add all three bits together (carryBit + bitA + bitB). The sum for each column is shown in an orange and blue 2-bit pair. The right bit (blue) is the output bit for that column. The left bit (orange) is the carry bit that overflows to the next column.

Translating over to code

Remember that the addBinary function accepts 2 strings - and the two strings may not be the same lengths as each other. Therefore, we'll create two variables - aLen and bLen, to hold the lengths of each string, and set a variable named maxLen to the value of whichever value is the largest. 

func addBinary(a string, b string) string {

aLen, bLen := len(a), len(b)

maxLen := aLen

if bLen > aLen {

maxLen = bLen

}

We'll create a couple more variables - carryBit (which again, at the beginning is 0 since we don't have an overflow of anything yet), and sumStr, which will hold the entire resulting sum binary string.

carryBit := 0

sumStr := ""

Next we set up the loop - initializing a counter i starting at 1 and increasing that value until we reach maxLen OR while carryBit is not zero:

for i := 1; i <= maxLen || carryBit > 0; i++ {

The offsets for which characters we want to look at each iteration are calculated like so:

bitA, bitB := 0, 0

aOffset := aLen - i

bOffset := bLen - i

You'll probably notice that since we're looping until at least the length of the longest string (OR while we still have a remaining carry bit), it's possible at some point aOffset or bOffset (whichever is the smaller of the two) or both, is going to become negative, which means we've scanned as far to the left as we can and now we're "outside" the bounds of one or both of the strings. The next following lines of code handles these cases:

if aOffset >= 0 && a[aOffset:aOffset+1] == "1" {

bitA = 1

}

if bOffset >= 0 && b[bOffset:bOffset+1] == "1" {

bitB = 1

}

If aOffset is greater than or equal to 0 and the character value at that position in string a is '1' then we set bitA to 1 - otherwise if either of those conditions is false we just keep bitA set to 0.

Same logic for bOffset: If bOffset is greater than or equal to 0 and the character value at that position in string b is '1' then we set bitB to 1 - otherwise we just keep bitB set to 0.

Now we sum carryBit, bitA, and bitB altogether, convert the first bit (rightmost bit) of the sum to a character, and concatenate to the beginning of sumStr.

sum := carryBit + bitA + bitB

if sum & 1 == 0 {

sumStr = "0" + sumStr

} else {

sumStr = "1" + sumStr

}

Finally, we discard the first bit of sum but extract the carry bit to pass over to the next iteration of the loop, which can be done by simply bit shifting sum to the right by 1: 

carryBit = sum >> 1

The full code for the addBinary function (Go implementation):

func addBinary(a string, b string) string {

aLen, bLen := len(a), len(b)

maxLen := aLen

if bLen > aLen {

maxLen = bLen

}

carryBit := 0

sumStr := ""

for i := 1; i <= maxLen || carryBit > 0; i++ {

bitA, bitB := 0, 0

aOffset := aLen - i

bOffset := bLen - i

if aOffset >= 0 && a[aOffset:aOffset+1] == "1" {

bitA = 1

}

if bOffset >= 0 && b[bOffset:bOffset+1] == "1" {

bitB = 1

}

sum := carryBit + bitA + bitB

if sum & 1 == 0 {

sumStr = "0" + sumStr

} else {

sumStr = "1" + sumStr

}

carryBit = sum >> 1

}

return sumStr

}

Java version can be found here: https://gist.github.com/edev90/9bc7010845daea8c7f13f260f274f1a3

JavaScript version can be found here: https://gist.github.com/edev90/93fb814b4de2d15129530f4e1e2cf412

As we can see, the answer shouldn't be complex. If you're working on this and come to a solution that has multiple loops, arrays, and nested conditionals all over the place and/or tons of bugs due to mishandled edge cases - it's likely a sign that you need to reevaluate your logic and see how it can be condensed further.

Coding a fast O(n) solution for the TwoSum problem

One of the more common problems asked during tech interviews is 'Two Sum'.

You are given an array (or list) of integer values, along with a target integer, and must return the two indices of the two integer values that add up to the given target value. 

Here are a couple of examples:

Example #1:
---------------------
Input array:             [2, 5, 7, 15, 22]
Target value:           29
Expected output:    [2, 4]

Example #2:
---------------------
Input array:             [1, 4, 9, 6]
Target value:           5
Expected output:    [0, 1]

The easiest and fastest solution is a brute-force approach, where we have a nested loop scanning the array, and checking every possible pair to see if it adds up to our target sum. Such a solution would be coded like this (Java version):

public int[] twoSum_Bruteforce(int[] nums, int target) {

int numsLen = nums.length;

for(int indexA = 0; indexA < numsLen; indexA++) {

for(int indexB = indexA + 1; indexB < numsLen; indexB++) {

int numA = nums[indexA];

int numB = nums[indexB];

if(numA + numB == target) {

return new int[]{indexA, indexB};

}

}

}

return new int[]{-1, -1};

}

As a first-time approach to this problem, it's not bad - but its far from ideal. If you were to supply this solution during an actual coding interview, you'd get some credit since there's no denying it actually works, but the interviewer will most likely coax you into writing a more optimized solution. 

Here's why: although our brute-force method works perfectly fine for smaller array inputs, it's extremely inefficient for larger arrays.

Below is a graph that illustrates the speed issues for larger arrays. Size of the array is represented on the X-Axis, while runtime (in seconds) is on the Y-Axis. Each runtime was measured with the worst-case scenario - meaning that the correct pair is always located at the end of the array (the last 2 integers). Runtime is measured in seconds, so the results are going to vary a bit from one device to the next (and also from one langauge to another) - but for all intents and purposes - assuming a typical standard Desktop PC running Java... it's going to be about the same. The goal here was to use a inutitive metric to drive the point home.

For relatively small arrays with only a couple to a few thousand integers, the runtime is respectable and pretty much "fast" enough. However, once we get into the several thousands, and north of 10,000 elements, the runtime starts to increase exponentially. By the time we get to 100,000 elements, the worst-case runtime is close to 2 seconds! This is expected since the brute-force approach runs with a O(n^2) time complexity. In a real-world environment this type of runtime speed would simply be downright unacceptable - especially for the simple purpose of what this algorithm is trying to achieve to begin with. 

The main bottleneck here is that nested loop, which, if we study the problem a little harder, we find that we can actually get rid of it altogether.

Let's look at one of our examples from the top again (Example #1), and see what we can do to find the correct output without needing a nested loop.

The array input is: [2, 5, 7, 15, 22], our target sum is 29, and the expected output is [2, 4] (Remember: we want to return the 2 indices of the solution pair, so 2 is the index of 7, and 4 is the index of 22)

This time, we'll use one loop, and we'll do the following for each integer in the list until we've found the solution:

-> Current Integer: 2, Current Index: 0
     Subtract 2 from our target sum (29) = 29 - 2 = 27.
     Have we seen 27 before? No.
     Store someplace that we have seen the integer 2 at index 0.
     Continue

-> Current Integer: 5, Current Index: 1
     Subtract 5 from our target sum (29) = 29 - 5 = 24
     Have we seen 24 before? No.
     Store someplace that we have seen the integer 5 at index 1.
     Continue

-> Current Integer: 7, Current Index: 2
     Subtract 7 from our target sum (29) = 29 - 7 = 22
     Have we seen 22 before? No.
     Store someplace that we have seen the integer 7 at index 2
     Continue

-> Current Integer: 15, Current Index: 3
     Subtract 15 from our target sum (29) = 29 - 15 = 14
     Have we seen 14 before? No.
     Store someplace that we have seen the integer 15 at index 3
     Continue

-> Current Integer: 22, Current Index: 4
     Subtract 22 from our target sum (29) = 29 - 22 = 7
     Have we seen 7 before? Yes - we saw 7 at index 2
     Stop loop and return 2 along with the current index of 4 -> Return [2, 4]

To summarize the above steps: Each time we encountered an integer we hadn't seen yet, we stored that integer along with its respective array index somewhere so we could retrieve it later. We do this every iteration of the loop. If we come across an integer X and see that we've already encountered the value of (target sum - x), then we're done!

Then we just have to figure out what data structure to store the (integer, index) pairs in, and a good choice for that is a Map, since we can easily map Integer -> Index of integer.

Below are two versions of the same implementation of the above approach - one coded in Java, and the other in Go:

Java implementation of fast solution using a map:

public int[] twoSum_Fast(int[] nums, int target) {

Map<Integer, Integer> numsSeen = new HashMap();

for(int index = 0; index < nums.length; index++) {

int otherNum = target - nums[index];

if(numsSeen.containsKey(otherNum)) {

return new int[]{numsSeen.get(otherNum), index};

}

numsSeen.put(nums[index], index);

}

return new int[]{-1, -1};

}

Link to gist: https://gist.github.com/edev90/1d4c1c01cf4d1aec5040078eec6fbf33

Go implementation of fast solution using a map:

func twoSum(nums []int, target int) []int {

numsSeen := make(map[int]int)

for index := 0; index < len(nums); index++ {

otherNum := target - nums[index]

if indexOfOtherNum, isValidKey := numsSeen[otherNum]; isValidKey {

return []int{indexOfOtherNum, index}

}

numsSeen[nums[index]] = index

}

return []int{-1, -1}

}

Link to gist: https://gist.github.com/edev90/4228c5fd3e447e27ff3be6d60f42591c

As we can see, the HashMap solution is faster on average by multiple times more than the brute-force solution. The graph below shows the runtimes and performance for the Two Sum solution using one loop and a HashMap:

Large arrays - even up to 100,000 elements in size are well below sub-tenth of a second in runtime. This is drastically faster than the brute-force approach. In fact, on my machine I had to bump the array size up to 75 million elements to get a runtime with the fast method that matched the 2 second runtime of the brute-force approach for 100,000 elements - which in this case makes the HashMap solution about 500 times faster than the brute-force one.

In the end, we were able to write a solution to this problem with worst case O(n) time complexity. There is a trade-off of course, as we increased the space complexity to track integers we had already seen along with their corresponding index for later retrieval. However, most versions of the Two Sum question are asked with the assumption that time is the most important factor to be optimized. That being said, if you encounter this question in an interview it's always best to ask the interviewer(s) what aspect of the problem you should be optimizing on, and adjust your approach accordingly.

If you'd like to see more of these algorithm/data structure posts, or would like me to cover a specific problem, please drop a comment below letting me know what you'd like to see covered in a future post.

Returning multiple values in Java - My preferred approach

Java does not natively support the ability to return multiple values from a method.

It would be nice if we could do something like this: could

public int, int methodThatReturnsMultipleValues() {

return 1, 2;

}

But we can’t. You’ll likely find this particularly bothersome if you’ve migrated over to Java from another language that supports returning multiple values out of the box (like Golang, for instance).

Thankfully, there are workarounds we can use to emulate this behavior. One of the more common workarounds is to simply return an array that contains the return values, like below:

public int[] methodThatReturnsMultipleValues() {

return new int[]{1, 2};

}

In order to retrieve both integer values we returned, we read both elements of the array:

int[] returnValues = methodThatReturnsMultipleValues();

int firstValue = returnValues[0];

int secondValue = returnValues[1];

For smaller use cases this works fine, but it gets messier with scale — and that’s why I don’t like to use it. 

It’s easy to introduce errors that won’t be exposed until the application is running, such as issues pertaining to:

Array Indexing

Let’s say you forget to make your code zero-based and attempt to pull from returnValues[1] and returnValues[2] instead. At some point an ArrayIndexOutOfBoundsException is going to get thrown when this code executes.

Additionally, by only using indexes to identify which array element corresponds to which return value, you could inadvertently assign returnValue[1] to firstInteger, and returnValue[0] to secondInteger.

Casting

In a lot of situations where it’s handy to return multiple values, the values are of different types. Since Object is a parent class of all other classes in Java (the topmost class), we can have an Object[] array that returns anything we want:

public Object[] methodReturnsMultipleValuesDifferentTypes() {

String a = "This is a string";

int[] b = {1, 2};

return new Object[] {a, b};

}

We can put any object of any type into that array. Here, I’m putting a string and an integer array into the Object[] array.

But we then need to employ casting when we want to read those values back and assign to their appropriate type(s):

Object[] returnValues = methodReturnsMultipleValuesDifferentTypes();

String firstReturnValue = (String)returnValues[0];

int[] secondReturnValue = (int[])returnValues[1];

And therein lies the possibility for casting mistakes to be made. If you mistakenly cast a value as the wrong type, a ClassCastException will occur during runtime.

My Preferred Approach: 

Because of all the considerations I mention above, I almost never use the array approach.

Instead, I use a generic class to store whatever values I need to return from my method.

I create a generic class named “ResultPair" (or something that clearly conveys what the class is used for), and then place it somewhere accessible to every other class in the project. 

I have a type parameter for every return value, and a constructor that accepts each return value that we want the ResultPair to store:

public class ResultPair <T1, T2> {

public T1 firstValue;

public T2 secondValue;

public ResultPair(T1 firstValue, T2 secondValue) {

this.firstValue = firstValue;

this.secondValue = secondValue;

}

}

Instead of using a convoluted array, now we just pass the values to our ResultPair constructor, and return that from a method:

public ResultPair<String, int[]> methodThatReturnsResultPair() {

String a = "This is a string";

int[] b = {1, 2};

return new ResultPair(a, b);

}

Now accessing the return values is much cleaner:

ResultPair<String, int[]> returnValues = methodThatReturnsResultPair();

String firstReturnValue = returnValues.firstReturnValue;

int[] secondReturnValue = returnValues.secondReturnValue;

There’s no need now to read from an Array, so ArrayIndexOutOfBounds exceptions are no longer a concern. We also don’t need to cast anymore, and if we even attempt to assign one of the return values to the wrong type (assigning the String return value to a Double, for example), we’ll get a heads up with IDE warnings we can resolve before running the application:

The other really nice thing about this approach is that you have a clear indication of how many, and what type of values you’re getting back from a method. In this case when I see ResultPair<String, int[]> in the method signature, I know that I’m getting a String and an Integer back from the method I called — whereas when dealing with an Object[] array I might have to trace through the method to discover what types of values I’ll be given.

When I did some quick benchmark tests, I found no significant speed impairments with this approach — and in fact often times the generic class approach was faster than the array method. 

Everything considered, unless there’s some niche case that calls for using an array, I highly encourage using the generic class approach to return multiple values in Java.