7
\$\begingroup\$

I just got rejected at the tech interview of a job application. They gave me the following exercise for me to complete:

They gave me a binary file with 10 million pairs of 16-bit signed integers. From those 10 million, I had to find the 10 closest points to (-200, 300) and the 20 furthest points to (1000, 25).

I finished my implementation and I created a zip file with my "src" directory (I did it using IntelliJ IDEA). Since I could not ship the binary file too, because it was too big, I made a PATH_TO_FILE constant so they could write their own path to file.

They rejected me on the basis that I didn't include any tests (which I should have, in retrospect) and that my packing and commenting didn't conform to their standards.

My question is, if you can help me identify:

  • How to improve the code's performance (it takes 3 seconds to run on my machine).
  • How I could have "packed and commented" my code better.
  • Any implementation tips that you can give me.

I created a command-line program that prints the answer to the console, which consisted of these two classes:

Main class:

package com.company;

import java.awt.*;
import java.io.*;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.util.Comparator;

public class Main {

    //TODO: Please, assign the variable below to the actual path to the file in your filesystem
    static String FILENAME = "path/to/file";

    private static final int OFFSET = 0;
    private static final int LENGTH = 2;

    // We declare the points that will be used in the comparison
    static Point mPoint1 = new Point(-200,300);
    static Point mPoint2 = new Point(1000,25);
    // Params for amount of nodes we need to retrieve
    static int CLOSEST_NODES_NUMBER = 10;
    static int FURTHEST_NODES_NUMBER = 20;

    // User feedback strings
    static String START = "Computing the desired nodes, please wait...";
    static String SEPARATOR = "\n****************************************************\n";
    static String END = "Thanks for your patience, here are your results: " + SEPARATOR;
    static String COMPUTATION_TIME = "The process took %s milliseconds";
    static String PRINT_CLOSEST = SEPARATOR + "These are the closest nodes to the point -200,300" + SEPARATOR;
    static String PRINT_FURTHEST = SEPARATOR + "These are the furthest nodes to the point 1000,25" + SEPARATOR;
    static String NODE_PRESENTATION = "Node n° %d : %s  with distance to the target node: %f\n";

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

        System.out.println(START);

        long startTimeInMillis = System.currentTimeMillis();

        Point currentPoint;
        BufferedInputStream stream = null;

        /*PriorityQueue with custom comparator. The order of the points will depend on their distance
        to our member point mPoint1 (-200,300).
         */
        LimitedPriorityQueue<Point> closestQueue = new LimitedPriorityQueue<>(
                CLOSEST_NODES_NUMBER,
                new Comparator<Point>() {
            @Override
            public int compare(Point firstPoint, Point secondPoint) {
                return firstPoint.distance(mPoint1) > secondPoint.distance(mPoint1) ? -1 : 1;
            }
        });

        /*PriorityQueue with custom comparator. The order of the points will depend on their distance
        to our member point mPoint2 (1000,25).
         */
        LimitedPriorityQueue<Point> furthestQueue = new LimitedPriorityQueue<>(
                FURTHEST_NODES_NUMBER,
                new Comparator<Point>() {
            @Override
            public int compare(Point firstPoint, Point secondPoint) {
                return firstPoint.distance(mPoint2) < secondPoint.distance(mPoint2) ? -1 : 1;
            }
        });


        try {

            // BufferedInputStream increases performance compared to DataInputStream
            stream = new BufferedInputStream(new FileInputStream(FILENAME));


            // We create a Point Object reading two values from the BufferedInputStream
            try {

                byte[] byteArray = new byte[2];
                int numberOfBytes;
                ByteBuffer bb;
                short x;
                short y;

                do {
                    numberOfBytes = stream.read(byteArray,OFFSET,LENGTH);
                    x = extractShort(byteArray);
                    numberOfBytes = stream.read(byteArray,OFFSET,LENGTH);
                    y = extractShort(byteArray);
                    currentPoint = new Point(x,y);


                    closestQueue.add(currentPoint);
                    furthestQueue.add(currentPoint);

                } while (numberOfBytes > 0);

            } catch (IOException e) {
                System.out.println(END);
            }

        } catch (Exception e) {
            e.printStackTrace();
        } finally {    // We close the stream to liberate resources
            if (stream != null) {
                stream.close();
            }
        }

        long finalTimeInMillis = System.currentTimeMillis();
        long computeTime = finalTimeInMillis - startTimeInMillis;

        System.out.printf(COMPUTATION_TIME,computeTime);

        Point node;

        // Printing the closest nodes.
        System.out.println(PRINT_CLOSEST);

        for (int i=CLOSEST_NODES_NUMBER;i>0; i--) {
            node = closestQueue.poll();
            System.out.printf(NODE_PRESENTATION,i,node,node.distance(mPoint1));
        }

        // Printing the furthest nodes.
        System.out.println(PRINT_FURTHEST);

        for (int i=FURTHEST_NODES_NUMBER;i>0; i--) {
            node = furthestQueue.poll();
            System.out.printf(NODE_PRESENTATION,i,node,node.distance(mPoint2));
        }
    }

    // We retrieve a short from the two bytes that we have read
    private static short extractShort(byte[] byteBuffer) {
        ByteBuffer bb = ByteBuffer.wrap(byteBuffer);
        return bb.getShort();
    }


}

A custom implementation of PriorityQueue to avoid holding more than the needed amount of values:

package com.company;

import java.util.Comparator;
import java.util.PriorityQueue;

/* We extend the PriorityQueue class so we can override the add method.
   Our add method checks for Queue length and removes an element if the max size is exceeded.
   This way, insertion is much faster (3.5 secs faster in my laptop)
 */

public class LimitedPriorityQueue<T> extends PriorityQueue<T>{

    private int mMaxSize;

    public LimitedPriorityQueue(int maxSize, Comparator<T> comparator) {
        super(comparator);
        mMaxSize = maxSize;
    }

    private boolean isMaxCapacityReached() {
        return this.size() > mMaxSize;
    }

    @Override
    public boolean add(T t) {
        super.add(t);
        if (isMaxCapacityReached()) {
            this.remove();
            return true;
        }
        return false;
    }
}

Thank you very very much in advance.

\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

The good:

  1. You defined static variables for everything, making it more easy to change the values.
  2. You created your own queue simplifying the logic of the algorithm

The bad:

  1. You put almost all of your code in the main method.
  2. (Related to point 1) You didn't define a method to return the points needed
  3. (Related to point 1) You didn't separate concerns (showing the points from displaying them)
  4. You swallow an exception and you do not rethrow it. Java (and almost every other language that is aware of exceptions) already displays the stack strace when an exception is raised, there wasn't a need for you to do the same

What you missed:

  1. Scanner would make your job a lot easier since it provides a nextShort method
  2. Try-with-resources is now the prefered way to clean-up
  3. If the file has 0 elements or any odd number of numbers it will print an error
  4. You were not consistent on the naming and declaration of your variables namely mPoint1 and mPoint2
  5. Some of your messages do not adjust to different points if needed

I would redo it as follows:

//TODO: Please, assign the variable below to the actual path to the file in your filesystem
private static String FILENAME = "path/to/file";

private static final int OFFSET = 0;
private static final int LENGTH = 2;

// We declare the points that will be used in the comparison
private static Point POINT_1 = new Point(-200,300);
private static Point POINT_2 = new Point(1000,25);
// Params for amount of nodes we need to retrieve
private static int CLOSEST_NODES_NUMBER = 10;
private static int FURTHEST_NODES_NUMBER = 20;

// User feedback strings
private static String START = "Computing the desired nodes, please wait...";
private static String SEPARATOR = "\n****************************************************\n";
private static String END = "Thanks for your patience, here are your results: " + SEPARATOR;
private static String COMPUTATION_TIME = "The process took %s milliseconds";
private static String PRINT_CLOSEST = SEPARATOR +  String.format("These are the closest nodes to the point %d,%d", POINT_1.x, POINT_1.y) + SEPARATOR;
private static String PRINT_FURTHEST = SEPARATOR + String.format("These are the furthest nodes to the point %d,%d", POINT_2.x, POINT_2.y) + SEPARATOR;
private static String NODE_PRESENTATION = "Node n° %d : %s  with distance to the target node: %f\n";

public static LimitedPriorityQueue<Point>[] getClosestAndFurthestPoints(String file, Point pointClose, int nClosest, Point pointFurther, int nFurther){

    /*Prepare queues with a custom comparator, comparing the distance relative to `pointClose` and `pointFurther` respectivly */
    LimitedPriorityQueue<Point> closestQueue = new LimitedPriorityQueue<>(nClosest,
        new Comparator<Point>() {
            @Override
            public int compare(Point firstPoint, Point secondPoint) {
                return firstPoint.distance(pointClose) > secondPoint.distance(pointClose) ? -1 : 1;
            }
    });

    LimitedPriorityQueue<Point> furthestQueue = new LimitedPriorityQueue<>(nFurther,
        new Comparator<Point>() {
            @Override
            public int compare(Point firstPoint, Point secondPoint) {
                return firstPoint.distance(pointFurther) < secondPoint.distance(pointFurther) ? -1 : 1;
            }
    });

    try(Scanner scanner = new Scanner(new FileInputStream(file))){
        short x, y;
        do{
            if(scanner.hasNextShort()){
                x = scanner.nextShort();
            }else{
                break;
            }
            if(scanner.hasNextShort()){
                y = scanner.nextShort();
            }else{
                break;
            }

            Point currentPoint = new Point(x, y);
            closestQueue.add(currentPoint);
            furthestQueue.add(currentPoint);
        }while(true)
    }

    //for simplicity I am returning an array ideally this would be an instance of a class perhaps
    return new LimitedPriorityQueue<Point>[]{
        closestQueue,
        furthestQueue
    };
}


public static void main(String[] args) throws IOException {
    System.out.println(START);
    long now = System.currentTimeMillis();

    LimitedPriorityQueue<Point>[] allPoints = getClosestAndFurthestPoints(FILENAME, POINT_1, CLOSEST_NODES_NUMBER, POINT_2, FURTHEST_NODES_NUMBER);

    long elapsed = System.currentTimeMillis() - now;
    System.out.printf(COMPUTATION_TIME, elapsed);

    LimitedPriorityQueue<Point> closestQueue = allPoints[0];
    System.out.println(PRINT_CLOSEST);
    for (int i = CLOSEST_NODES_NUMBER; i > 0; i--) {
        Point node = closestQueue.poll();
        System.out.printf(NODE_PRESENTATION, i, node, node.distance(POINT_1));
    }

    LimitedPriorityQueue<Point> furthestQueue = allPoints[1];
    System.out.println(PRINT_FURTHEST);
    for (int i = FURTHEST_NODES_NUMBER; i > 0; i--) {
        Point node = furthestQueue.poll(); System.out.printf(NODE_PRESENTATION, i, node,n ode.distance(POINT_2));
    }
}
\$\endgroup\$
3
\$\begingroup\$

If they didn't tell you their coding standards (or you not us) it's impossible to say how well they aligned with the code as presented. It could go from "the source is the documentation" to "JavaDoc all the things."

Same goes for "packing", which without a bit further explanation doesn't say much. If you just zipped the folder with sources, i.e. in the expected structure

myfolder/com/company/Main.java
                     LimitedPriorityQueue.java

and while preserving the folder structure in the ZIP file I can't see how there's anything to change there.

In general you want to make it as easy as possible for reviewers. In particular if your job prospects hinge on that.

This means, in this example, that it would've been better to pass in the file to process as the first command line parameter. Even if you wrote the code in their office or so, it makes things much easier to test instead of having to recompile (yes, even in an IDE, that's what the run configurations are there for). It also means that you don't have to explain (in which README file? That's another that's good to add in any kind of situation) where to change some value in the code to get the program to run.


There are a couple of things in the code that are a bit inconsistent and/or suboptimal though, e.g.

  • mPoint1 - it's used consistently, but just don't use a/that prefix, it looks annoying and serves not much purpose.
  • Package private visibility for the constants and so on is a matter of principle - I'd usually expect to have the most strict level of visibility as a matter of policy (everything private unless there's a need to open it up).
  • The spacing is inconsistent. Sometimes there's a space between arguments, sometimes there isn't.
  • I'm not sure about it, but the distance comparisons should probably be able to return an equal result too, no? The anonymous class could've been factored out in some way I think (have the same Comparator class, but have an "invert" wrapper that simply multiplies the compare result by -1 or so), but that's not terribly important I think.
  • Pre-declaring variables like it's done with currentPoint and stream is not necessary most of the time, certainly not here.
  • The print loops are duplicated code.
  • Catching all exceptions just to print the stacktrace is unnecessary, that will happen anyway and secondly there's no return after the catch block. That would warrant a nice comment about how that's expected and dealt with.
  • The code to extract a short is duplicated and not efficient. If you really need to use a ByteBuffer, just construct it once and read four bytes at once and check the return value of the read before processing the numbers. Also call .rewind() to reset the buffer to the start. I think it would also be defensible to do the byte to short manually instead.
  • The OFFSET and LENGTH shouldn't be extracted as constants in this case since they aren't magic enough. You could potentially use 0 and byteArray.length

Off the top of my head I can't tell how the queues handle remove, but I'll believe you that it's the correct item to remove :)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.