5
\$\begingroup\$

A few months ago I got rejected at the technical interview for a position.

The problem that they gave me is the following:

From a binary file, parse two shorts, x and y and build a Point object with these coordinates.

Repeat the process until there is no more shorts to parse. From all those points, return the 10 closest points to the point -200,300 and the furthest points from the point 1000,25.

Could you help me to identify what I can do different to increase the performance of my program?

Also, please give me any general suggestions or pointers to improve my code.

public class Main {

    private static final Point closest = new Point(-200, 300);
    private static final Point furthest = new Point(1000, 25);
    private static final int POINTS_IN_FILE = 10000000;

    private static final Comparator<Point> closestComparator = new Comparator<Point>() {
        @Override
        public int compare(Point o1, Point o2) {
            Double firstDistance = o1.distance(closest);
            Double secondDistance = o2.distance(closest);

            return - firstDistance.compareTo(secondDistance);
        }
    };

    private static final Comparator<Point> furthestComparator = new Comparator<Point>() {
        @Override
        public int compare(Point o1, Point o2) {
            Double firstDistance = o1.distance(furthest);
            Double secondDistance = o2.distance(furthest);

            return firstDistance.compareTo(secondDistance);
        }
    };

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

        String pathToFile;

        for (String arg : args) {

            pathToFile = arg;

            try (DataInputStream stream = new DataInputStream(
                    new BufferedInputStream(new FileInputStream(new File(pathToFile))))) {

                Point[] pointArray = new Point[POINTS_IN_FILE];
                readPointsIntoArray(pointArray, stream);
                calculateFirstPoints(pointArray, false, 10);
                calculateFirstPoints(pointArray, true, 20);
            }
        }
    }

    private static void calculateFirstPoints(Point[] pointArray, boolean furthest, int size) {
        Comparator<Point> pointComparator = furthest? furthestComparator : closestComparator;
        LimitedPriorityQueueWrapper<Point> pointWrapper = new LimitedPriorityQueueWrapper<>(size, pointComparator);
        pointWrapper.bulkInsertToQueue(pointArray);
        List<Point> resultList = pointWrapper.getElements();
        printPoints(resultList);
    }

    private static void readPointsIntoArray(Point[] points, DataInputStream stream) {
        int index = 0;
        while (true) {
            try {
                Point currentPoint = new Point(stream.readShort(), stream.readShort());
                points[index] = currentPoint;
                index++;
            } catch (Exception e) {
                break;
            }
        }
    }

    private static void printPoints(List<Point> points) {
        for (Point point : points) {
            System.out.println(point.toString());
        }
    }
}

This is a helper class that I created with an inner priority queue. Its purpose is to insert the points in the correct order so I don't have to sort the collection later.

public class LimitedPriorityQueueWrapper<T> {

    private PriorityQueue<T> queue;
    private int size;
    private boolean sizeReached = false;

    public LimitedPriorityQueueWrapper(int size, Comparator<T> comparator) {
        this.queue = new PriorityQueue<T>(comparator);
        this.size = size;
    }

    public void insertIntoQueue(T t) {
        queue.add(t);
        if (sizeReached) {
            queue.poll();
            return;
        }
        if (queue.size() >= size) {
            sizeReached = true;
        }
    }

    public void bulkInsertToQueue(T[] array) {
        for (int i=0; i<array.length; i++) {
            insertIntoQueue(array[i]);
        }
    }

    public List<T> getElements() {
        return new ArrayList<T>(queue);
    }


}

All the advice that you can give me will be very appreciated.

Improve this question
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Please do not destroy content or change the code on answered questions. Thank you! \$\endgroup\$
    – Mathieu Guindon
    Sep 13, 2016 at 20:53

2 Answers 2

Reset to default
8
\$\begingroup\$

Given that this was for an interview I'll refrain from saying that Javadoc is missing.

 private static final Point closest = new Point(-200, 300);

That's a violation of the Java Style Guidelines, constants are to be named UPPER_CAMELCASE. Not to mention that the name could be better.

private static final Point CLOSEST_POINT = new Point(-200, 300);

private static final int POINTS_IN_FILE = 10000000;
...
Point[] pointArray = new Point[POINTS_IN_FILE];

I'm just at line five and I can tell you that I would have failed you at this point. Your specs do not say that there are 10 million points, right? You're allocating at least 190 megabyte with this declaration (I just tried it) for an array which is superfluous. A List would be much better suited as it can grow as needed. Even better would be two Lists which only hold 10 points each, the closes and farthest points.

Even though the spec you posted says something like "parse all floats...return the closest and farthest" I'd actually combine these two steps:

  1. Read Point from input.
  2. Check if Point is further or closed than the already gathered ten points.
  3. Drop the "least fitting" Point from the list.
  4. Add the new Point.

This way your memory usage is roughly for 20 Point instances, and you are only comparing each Point against 20 other values. This can be further speed up by caching the "furthest" and "closest" point separately, because then you only must compare each read Point against two other Points, and only if it farther or closer you must compare against the other ten.

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

Your main should not throw Exceptions, it should handle them and fail gracefully.

String pathToFile;
for (String arg : args) {
     pathToFile = arg;

Declare variables where they are used, in this case inside the loop, to limit its scope.

for (String arg : args) {
     String pathToFile = arg;

try (DataInputStream stream = new DataInputStream(new BufferedInputStream(new FileInputStream(new File(pathToFile))))) {

You're not performing any sort of checks here. What if the arg is empty? What if it is not a valid path? What if the file does not exist?

for (String arg : args) {
    if (arg != null && arg.length > 0) {
        File file = new File(arg);
        if (file.exists()) {
            // Continue here with the logic.
        }
    }
}

private static void calculateFirstPoints(Point[] pointArray, boolean furthest, int size) {
    Comparator<Point> pointComparator = furthest? furthestComparator : closestComparator;
    LimitedPriorityQueueWrapper<Point> pointWrapper = new LimitedPriorityQueueWrapper<>(size, pointComparator);
    pointWrapper.bulkInsertToQueue(pointArray);
    List<Point> resultList = pointWrapper.getElements();
    printPoints(resultList);
}

I have no idea what you're doing here...

Why not pass the "correct" comparator as parameter? Would get rid of the boolean and would be more expressive.

int index = 0;
while (true) {
    try {
        Point currentPoint = new Point(stream.readShort(), stream.readShort());
        points[index] = currentPoint;
        index++;
    } catch (Exception e) {
        break;
    }
}

Every time you write while(true) I want you, from now on, to lift your hands from the keyboard, place them on the back of your head and think at least for a minute about why you just did that and if there might be another way to do this. Note how your code never checks if there are too many shorts available for the array to hold.

try {
    for (int index = 0; index < points.length; index++) {
        points[index] = new Point(
            stream.readShort(),
            stream.readShort());
    }
} catch (IOException e) {
    // Ignore the exception, we will assume that the stream
    // ended and therefor we will stop reading.
}

Alternatively with a List:

try {
    while(true) {
        points.add(new Point(
            stream.readShort(),
            stream.readShort());
    }
} catch (IOException e) {
    // Ignore the exception, we will assume that the stream
    // ended and therefor we will stop reading.
}

Ideally, your code would look something like this (pseudo-code):

class PointFinder
    List<Point> farthestPoints
    List<Point> closestPoints
    Point farthestPoint
    Point closestPoint

    PointFinder(farReferencePoint, nearReferencePoint)

    void findPoints(InputStream)
        Point point = getPointFromStream()
        if (point < closestPoint)
            if (compareWithClosestPoints(point)
                closesPoints.removeFarthest()
                closestPoints.add(point)
        if (point > farthestPoint)
            if (compareWithFarthestPoints(point)
                farthestPoints.removeClosest()
                farthestPoints.add(point)

class Main
    void main(Args)
        PointFinder pointFinder = new PointFinder(farReferencePoint, nearReferencePoint)

        foreach arg
            perform checks
                pointFinder.findPoints(InputStream from arg)
                print pointFinder.furthestPoints
                print pointFinder.closestPoints
                pointFinder.reset()

Or something like this. You encapsulate all the logic required for reading, comparing and gathering points into an instance class which can be reused.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Really good review and really helpful. Keep it up! \$\endgroup\$
    – Javier Ventajas Hernández
    Jul 21, 2016 at 22:32
3
\$\begingroup\$

Unit testing!

There are some problems with our code that can be found with some unit testing. pointArray is a huge array used to store the points. The size is fixed, so there will be some Points ans some nulls most of the time (Unless the file has equal or more points that the size constant. By the way, if the file has more values than your constant, some values are being silently ignored), reviewing the code, you are going to have problems processing the array:

private static void calculateFirstPoints(Point[] pointArray, boolean furthest, int size) {
    Comparator<Point> pointComparator = furthest? furthestComparator : closestComparator;
    LimitedPriorityQueueWrapper<Point> pointWrapper = new LimitedPriorityQueueWrapper<>(size, pointComparator);
    pointWrapper.bulkInsertToQueue(pointArray); // <-- Inserting all elements, nulls included. 
    List<Point> resultList = pointWrapper.getElements();
    printPoints(resultList);
}

public void bulkInsertToQueue(T[] array) {
    for (int i=0; i<array.length; i++) {
        insertIntoQueue(array[i]); <-- Insert each element in the Priority Queue (nulls included)
    }

public void insertIntoQueue(T t) {
    queue.add(t); <-- Adding elements, PriorityQueue doesn't admit nulls and throws a NullPointerException
    if (sizeReached) {
        queue.poll();
        return;
    }
    if (queue.size() >= size) {
        sizeReached = true;
    }
}
Improve this answer
\$\endgroup\$

Your Answer

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

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