Mryntu

Background

I got this interview test and got declined due to not meeting their expectations, but never got a reason on what was bad and how they solved it. I want to improve and learn something out of it.

Question
How can this be better written and what is badly written?

Assignment description

To optimize the amount of data sent between the web browser to the web server
a "clever" Javascript developer came up with the idea to translate JSON objects
into binary format in the application and send them to the server. Faced with
the fact that the Javascript is released in its final version to the customer
it is now your task to develop the parser on the back end system.

A JSON object is a hierarchy of key-value pairs where a value in its turn can
contain new key-value pairs. It consists of four basic types: numbers, strings,
arrays and dictionaries. An array is a list of values and a dictionay is a list
of key-value pairs. The key can only be of the type number or string while a
value can be of any type.

A JSON object always starts with a value.

An example JSON object can look like:

 'firstName': 'John',
 'lastName': 'Smith',
 'age': 25,
 'address': 
 'streetAddress': '21 2nd Street',
 'city': 'New York',
 'state': 'NY',
 'postalCode': '10021'
 ,
 'phoneNumber': [
 'type': 'home', 'number': '212 555-1234' ,
 'type': 'fax', 'number': '646 555-4567' 
 ]

A number is printed in decimal without any decoration.
Example: 25

A string is printed in ASCII with single quotes in the start and end of the
string.
Example: 'test'

A key-value pair is printed as key followed by colon (:), a space ( ) and the
value.
Example: 'a': 67

A dictionary starts and ends with curly brackets ( and ) and then has a
comma (,) separated list of key-value pairs.
Example: 'name': 'Joe', 'age': 31

An array starts and ends with square brackets ([ and ]) and then has a
comma (,) separated list of values.
Example: [ 'hello', 56, 'world' ]

The binary representation of the JSON object contains a one byte identifier
that describes the type of the data to follow and is then immediately followed
by the data.

The identifiers and their types are as follows:

Identifier Type Description
0x01 Number 4 bytes signed integer in big endian byte order.
0x02 String N ASCII characters terminated by 0x00.
0x05 List Amount of items as a number followed by N values
0x06 Dictionary Amount of items as a number followed by N
 key-value pairs

The program's task is to parse a binary file and prints it as human readable
text. It should read the data from standard input and writes it the result to
standard output.

Look at the files 'input_x' and their respective 'result_x' for examples of
input and output. More background can be found on e.g. www.json.org

Input_4 binary

firstsecondvalue for seconddeepinteger as keymixit is possible to mix integers and strings#Eg

My solution

public class Main 

 private static String INPUT_FILENAME = "input_4";
 private static String OUTPUT_FILENAME = "result_4";

 private static String RESOURCE_INPUT_PATH = "src/main/resources/input/";
 private static String RESOURCE_OUTPUT_PATH = "src/main/resources/output/";

 public static void main(String[] args) 
 File resourcesDirectory = new File(String.format("%s%s", RESOURCE_INPUT_PATH, INPUT_FILENAME));
 File file = new File(resourcesDirectory.getAbsolutePath());

 try 
 byte[] byteArray = Files.readAllBytes(file.toPath());

 RecursiveParser recursiveParser = new RecursiveParser();

 try 
 String result = recursiveParser.parse(byteArray, 0, false).toString();

 String prettyPrinted = prettyPrint(result);
 BufferedWriter writer = new BufferedWriter(
 new FileWriter(
 new File(
 String.format("%s%s%s", RESOURCE_OUTPUT_PATH, OUTPUT_FILENAME, ".json")
 )
 )
 );
 writer.write(prettyPrinted);

 writer.close();
 catch (JSONException e) 
 e.printStackTrace();
 
 catch (IOException e) 
 e.printStackTrace();
 
 

 private static String prettyPrint(String data) throws JSONException 
 Object json = new JSONTokener(data).nextValue();
 if (json instanceof JSONObject)
 return (new JSONObject(data)).toString(4);
 
 else if (json instanceof JSONArray)
 return (new JSONArray(data)).toString(4);
 else 
 return data; // nothing to pretty print
 
 

class RecursiveParser 
 private static int TERMINATE = 0x00;

 private static int NUMBER = 0x01; // Number 4 bytes signed integer in big endian byte order.
 private static int STRING = 0x02; // String N ASCII characters terminated by 0x00.
 private static int LIST = 0x05; // List Amount of items as a number followed by N values
 private static int DICTIONARY = 0x06; // Dictionary Amount of items as a number followed by N key-value pairs

 Object parse(byte[] byteArray, int index, boolean hasSub) throws JSONException 
 for(; index < byteArray.length; index++)
 if(byteArray[index] == NUMBER)
 return getNumber(byteArray, index);
 
 if(byteArray[index] == STRING)
 return getString(byteArray, index);
 
 if(byteArray[index] == LIST)
 return getList(byteArray, index, hasSub);
 
 if(byteArray[index] == DICTIONARY)
 return getDictionary(byteArray, index, hasSub);
 
 
 return null; // should never get here
 

 private Object getDictionary(byte[] byteArray, int index, boolean hasSub) throws JSONException 
 index++; // move to size after type because dictionary size

 int dictionarySize = (int)parse(byteArray, index, hasSub);
 index += ByteBuffer.allocate(4).putInt(dictionarySize).array().length;

 JSONWriter jsonWriter = new JSONStringer()
 .object();

 for(int i = 0; i < dictionarySize; i++)

 jsonWriter
 .endObject();

 return hasSub && index != (byteArray.length - 1) ? new AbstractMap.SimpleEntry<>(index, new JSONObject(jsonWriter.toString())) : new JSONObject(jsonWriter.toString());
 

 private Object getList(byte[] byteArray, int index, boolean hasSub) throws JSONException 
 index++; // move to size after type because list size

 int listSize = (int)parse(byteArray, index, hasSub);
 index += ByteBuffer.allocate(4).putInt(listSize).array().length;

 JSONWriter jsonWriter = new JSONStringer().array();
 for(int i = 0; i < listSize; i++)
 index++;

 // check if sub-array or sub-dictionary
 hasSub = hasSub 
 jsonWriter.endArray();

 return hasSub && index != (byteArray.length - 1) ? new AbstractMap.SimpleEntry<>(index, new JSONArray(jsonWriter.toString())) : new JSONArray(jsonWriter.toString());
 

 private String getString(byte[] byteArray, int index) 
 int start = index + 1; // move to next value after type
 StringBuilder value = new StringBuilder();
 for(int i = start; i < byteArray.length; i++)
 if(byteArray[i] == TERMINATE)
 break;
 
 value.append((char)byteArray[i]);
 
 return value.toString();
 

 private int getNumber(byte[] byteArray, int index) 
 int start = index + 1; // move to next value after type
 int offset = start + 4;

 byte[] numberByteArray = Arrays.copyOfRange(byteArray, start, offset);

 return new BigInteger(numberByteArray).intValue();
 

Result_4 output

 "5": 25,
 "deep": 
 "1": "integer as key",
 "2": "4": 19088743,
 "mix": "it is possible to mix integers and strings"
 ,
 "first": 16777216,
 "second": "value for second"

There are two points that showed up immediately when looking at your implementation:

• You missed one of the goals of the task: It should read the data from standard input and writes it the result to standard output.


• You are reading in the complete binary data into memory and process it from there.

The latter is a no go, if we're talking about large structures of JSON-data, e.g. containing Base64-encoded binary data of a DVD-image (don't ask ;-) It might be unlikely in a real world example but it might let them come to the conclusion that you're not familiar with stream based processing and had another one how showed that ability which might have led to their decision.

Some remarks about the actual code:

Your reading-number-implementation:

private int getNumber(byte[] byteArray, int index) 
 int start = index + 1; // move to next value after type
 int offset = start + 4;

 byte[] numberByteArray = Arrays.copyOfRange(byteArray, start, offset);

 return new BigInteger(numberByteArray).intValue();

The specification said that a number is a signed integer in big endian order which is exactly how a Java int is defined, so instead of creating temporary arrays and a BigInteger you could simply have used an int and used bit-shifting:

private int getNumber(byte[] byteArray, int index) = (byteArray[index + 2] & 0xff) < 16;
 ret 

If you had implemented a stream based processing and used a DataInputStream the implementation would have been

private int getNumber(DataInputStream source) 
 return source.readInt();

Your reading-text-implementation:

private String getString(byte[] byteArray, int index) 
 int start = index + 1; // move to next value after type
 StringBuilder value = new StringBuilder();
 for(int i = start; i < byteArray.length; i++)
 if(byteArray[i] == TERMINATE)
 break;
 
 value.append((char)byteArray[i]);
 
 return value.toString();

Not much that can be changed here but for good measure, I'd change (char)byteArray[i] to (char) (byteArray[i] & 0xff). For ASCII-characters that's irrelevant but still ;-)

In getDictionary:

private Object getDictionary(byte[] byteArray, int index, boolean hasSub) throws JSONException else if (value instanceof AbstractMap.SimpleEntry) 
 valueLength = (int) ((AbstractMap.SimpleEntry) value).getKey() - index;
 jsonWriter.value(((AbstractMap.SimpleEntry) value).getValue());

This code block is duplicated in getList, you should put that into its own method and call it from the two methods. Same is true for the logic with the return-statement. This should be put into its own method so you only need to fix it once in case you find a bug in it.

General stuff:

You had to cope with the fact that your get-methods had to return a value and should change the value of the index. That's not possible, so you decided to change the index value in the calling method in dependence of the type of the returned parsed value. This is "not optimal" to say the least.