Posted by & filed under Coding.

Earlier this week I was working on a JUnit test for one of the AP free response questions from 2016 where you’re given an array of Strings and need to implement a class that randomly pulls one out using a getNext method. You’re basically writing an iterator without calling it that.

But since it was random I needed a way to check that the right values were there, even though they probably weren’t going to be in the same order. So I needed to check that one String array was a permutation of another. And I really didn’t want to have to go through every permutation of one to see if one matched. That seemed horribly inefficient.

Google brought me to this page of interview questions with a cool solution for int arrays. The TL;DR version is that you get the sum and product of both arrays, and if they match they’re permutations of each other.

And here’s a bit of Java code to do that.

First check is to make sure the two arrays are the same length. If they’re not, there’s no reason to go on. Then it’s just a loop to get all the values and do a bit of math.

But what about Strings

That was close, but I needed to do the same with a String array. Enter hashCode.

And it worked, at least for the short arrays I threw at it. I assume it’d fail with either long strings or longer arrays since eventually multiplying a bunch of ints together is going to overflow a long. But it worked well enough for what I needed.

Leave a Reply

Your email address will not be published. Required fields are marked *