Skip to content

Instantly share code, notes, and snippets.

@chb0github
Created November 28, 2020 17:44
Show Gist options
  • Save chb0github/5ec290c57aade3c290d22eb8aa80ed48 to your computer and use it in GitHub Desktop.
Save chb0github/5ec290c57aade3c290d22eb8aa80ed48 to your computer and use it in GitHub Desktop.
Functionally generating an ID

When it comes to giving an interview I don't believe in ridiculous brain-benders. You know the ones: how would you implement an NxN tic-tack-toe. I knew that one was ridiculous when my son wanted me to help him implement tic-tac-toe. I said to him "Well, that's great, but what about a 10x10 board?!" To which he quipped: "Dad, there is no such thing!" - So, yeah: I get asked to over-engineer things in interviews :)

I try to keep my interview questions grounded and based on my actual experiences or something I could see being a real problem. To that end, one day I stumbled on a question on codereview stackexchange. In that case, the problem was as follow:

  • Generate a 16 digit random number
  • place a dash between every 4th digit
  • All upper case
  • The same character can't repeat twice
  • Digits must be alpha numeric.

I gave it a quick think, and whipped up something functional:

public static void main(String[] args) {
    String result = new SecureRandom().ints(0,36)
            .mapToObj(i -> Integer.toString(i, 36))
            .map(String::toUpperCase).distinct().limit(16).collect(Collectors.joining())
            .replaceAll("([A-Z0-9]{4})", "$1-").substring(0,19);

    System.out.println(result);
}

I came up with this solution based on the observation that, what we really had were random numbers 0-35 expressed as base 36. With that in mind, I simply leveraged the built in stuff to give me the output I needed.

I gave it some more though along the way and came up with a more efficient alternative (this time in groovy).

def result = (0..16).collect{[
        index: new Random().nextInt(36 - it),
        dest: "",
        src: "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
]}.inject{first, second -> [
        index: second.index,
        dest: first.dest + first.src[first.index -1],
        src: first.src - first.src[first.index -1]
]}.dest.replaceAll("([0-9A-Z]{4})",'$1-')[0..-2]

println(result)

This solution basically has 2 "buckets" - the original character sets (which, can be known a priori and always meets the first criteria of having unique elements, in CAPITAL letters), and the empty, but final bucket. The idea here is to pluck 1 character, at random, from the full list and put it in the other bucket. Then, following seperation of concerns, format it.

The whole solution is a single map/reduce

I have been using this for an interview question for a while now and the number of people who bomb this just makes me scratch my head. I don't see this as particularly challenging; I pride myself in being down-to-earth when it comes to code. But, everyone I interview seems to way overthink or underthink this.

Firstly, not a single one approaches this functionally. It's always imperative; involving several index pointers, buffers, maps, etc. They also don't seem to grasp either a seperation of concern (generate the numbers, format the numbers) or, grasp the fact that to a computer everything is a number and this is just a base 36 number.

Here is the most recent example. 40 minutes on this and it doesn't compile much less solve the problem:

 public static String generateId() {
    Map<Integer, Character> alphabetsMap = new HashMap();
    String alphanumericString = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    char[] randomSequence = new char[16];
    int left = 0; 
    int right = alphanumericString.length;
    int i = 0;
    while (i < 16) {
      Random random = new Random();
      int currentValue = random.nextInt(right);
      if (alphabetsMap.containsKey(currentValue) {
        continue;
      } else {
        alphabetsMap.put(currentValue, alphanumericString[currentValue]);
        randomSequence[i] = alphanumericString[currentValu
      }
    }
    
    return "ABCD-1234-05DF-9876"; // this is just an example
  }

There are 8 seperate variables (any one that can be mis-assigned), and one is an array that's having it's elements written to. There are several branching conditions as well. Bugs can lurk anywhere in this code. You may say: "The ends justifies the means". Hell, a product owner would because they only ever see the end result (remember my axiom about 10 types of applications?).

But he/she will be the first one to get up in arms when the thing catches fire in prod and causes customer facing embarassment. In addition, if you multiply this overly complex programming by 1000s of lines, you get an exceptionally difficult program to manage; which means feature iteration slows down with time. As features slow down, and outages go up, customers walk away.

It's a slow moving trainwrecks and there is never going to be a bright, sharp event horizon of doom. Can you lose 1 customer? Sure. 1 Big customer? Ouch, but sure. How many can you lose before you end up in a death spiral?

It's an analog problem in a digital world

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment