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.