AND Product

Yesterday morning I watch most of the Association for Computing Machinery (ACM) webinar “OOPS! Learning from Surprise at Netflix”. The presenter was Lorin Hockstein who is a senior software engineer at Netflix. For what I was able to get out from the presentation is that when an issue in production appears, it is important to learn from it to make sure the code is updated to prevent the issue from ever happening again. That may require from simple changes to deeper design or even architectural modifications.

I had to answer a phone call from my boss during the 1-hour presentation so I missed about half of the webinar. ACM makes available all webinars after a couple days. I will watch the presentation in its entirety when it becomes available.

Last evening I received a HackerRank email which is part of their campaigns to get people like me using their site. The proposed challenge is named “AND Product”. I was the message after breakfast this morning. If you are interested take a look at the requirements.

The idea is that you are given two positive integers, one less than or equal that the other (a <= b). We need to produce the results for the AND operation of all numbers from a to b inclusive.

The brute force would be to do exactly what the requirements call and process the entire sequence. I decided to skip that part and think about what could be done to get to the results in a few steps.

1
10 14

8


3
12 15
2 3
8 13

12
2
8


2
17 23
11 15

16
8

The HackerRank site provides three examples. They provided enough info to come up with a better approach than brute force.


  // **** open scanner ****
  private static final Scanner scanner = new Scanner(System.in);

  public static void main(String[] args) throws IOException {

    // **** ****
    // BufferedWriter bufferedWriter = new BufferedWriter(new
    // FileWriter(System.getenv("OUTPUT_PATH")));
    BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

    // **** ****
    int n = scanner.nextInt();
    scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

    // *** ****
    for (int nItr = 0; nItr < n; nItr++) {

      // **** ****
      String[] ab = scanner.nextLine().split(" ");
      long a = Long.parseLong(ab[0]);
      long b = Long.parseLong(ab[1]);

      // **** ****
      long result = andProduct(a, b);

      // **** ****
      bufferedWriter.write(String.valueOf(result));
      bufferedWriter.newLine();
    }

    // **** close buffered writer ****
    bufferedWriter.close();

    // **** close scanner ****
    scanner.close();
  }

As usual I try to understand the requirements. It is important to read them a few times to make sure you are not missing something of interest. Then look in different ways what is being requested and how to achieve with a simpler and more elegant approach.

I copied the test scaffolding to Visual Studio Code IDE and edited by making a change in the output and adding comments. All seems very clear.

 /**
   * Complete the andProduct function below.
   */
  static long andProduct(long a, long b) {

    // **** ****
    long result = 0;

    // **** compute difference between numbers ****
    long diff = b - a;

    // **** determine highest power of 2 in the difference ****
    int n = 0;
    for (; Math.pow(2.0, n) < diff; n++) {
    }

    // **** generate mask ****
    long mask = 0xffffffffffffffffL;
    mask <<= n;

    // **** generate result ****
    result = b & a & mask;

    // **** return result ****
    return result;
  }

We are provided two long integers. If you look at the bits for both numbers and the difference, it seems we could eliminate a set of lower bits. The reason is that if two consecutive integers are ANDed (not sure this is an acceptable word) we will always loose the lowest bit (e.g., 5 = 0101 AND 6 = 0110 == 0100). We then need to address the rest of the bits. Try different examples and you will see that if we compute the difference between b and a, we just need to clear a set of lower bits and AND the remaining bits. This holds true no matter how big the difference between a and b is.

The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address:  john.canessa@gmail.com. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!

John

Twitter:  @john_canessa

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.