# Counting the number of unique IP addresses in a very large file

I made a test job to the position of Junior Java Developer. I did not receive any answer from the employer, so I would like to get a review here.

A simple text file with IPv4 addresses is given. One line is one address, something like this:

145.67.23.4
8.34.5.23
89.54.3.124
89.54.3.124
3.45.71.5.
...


The file size is not limited and can occupy tens and hundreds of gigabytes.

It is necessary to calculate the number of unique IP addresses in this file, consuming as little memory and time as possible. There is a "naive" algorithm for solving this task (we read strings and put it in HashSet), it is desirable that your implementation is better than this simple, naive algorithm.

## Test case

WARNING! This file is about 20GB, and is unpacking approximately 120GB. It consists of 8 billions lines.

## My approach

I emerge from the fact that there are 2 ^ 32 valid unique ip addresses. We can use a bit array of 2 ^ 32 bits (unsigned integer) and put each bit of this array in line with one ip address. Such an array will take exactly 512 megabytes of memory and will be allocated once at the start of the program. Its size does not depend on size of the input data.

Unfortunately, Java does not have an unsigned int type and also there are no convenient bit operations in it, so I use BitSet for my purposes.

## Thank you!

Please feel free to tell me all the flaws that you can find.

## Code

Main class

public class IpCounterApp {

private static String parseFileName(String[] args) {
String fileName = null;
if (args.length == 2 && "-file".equals(args[0])) {
fileName = args[1];
}
return fileName;
}

public static void main(String[] args) {
String fileName = parseFileName(args);
if (fileName == null) {
System.out.println("Wrong arguments. Use '-file file_name' to specify file for processing");
return;
}

UniqueIpCounter counter = new BitSetUniqueIpCounter();
long numberOfUniqueIp = counter.countUniqueIp(fileName);
if (numberOfUniqueIp != -1) {
System.out.println("Found " + numberOfUniqueIp + " unique IP's");
} else {
System.out.println("Some errors here. Check log for details.");
}
}
}



UniqueIpCounter interface

public interface UniqueIpCounter {

/*
In total there are 2 ^ 32 valid IP addresses exists.
*/
long NUMBER_OF_IP_ADDRESSES = 256L * 256 * 256 * 256;

/*
Map string representing the IP address in format 0-255.0-255.0-255.0-255 to number
in the range of 0..2^32-1 inclusive.
It is guaranteed that the input string contains a valid IP address.
*/
static long toLongValue(String ipString) {
StringBuilder field = new StringBuilder(3);
int startIndex = 0;
long result = 0;

for (int i = 0; i < 3; i++) {
int spacerPosition = ipString.indexOf('.', startIndex);
field.append(ipString, startIndex, spacerPosition);
int fieldValue = Integer.parseInt(field.toString());
field.setLength(0);
result += fieldValue * Math.pow(256, 3 - i);
startIndex = spacerPosition + 1;
}
result += Integer.parseInt(ipString.substring(startIndex));

return result;
}

/*
Returns the number of unique IP addresses in the file whose name is pass by the argument.
Returns the number from 0 to 2 ^ 32 inclusive.
Returns -1 in case of any errors.
*/
long countUniqueIp(String fileName);
}


BitSetUniqueIpCounter implementation

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.BitSet;
import java.util.logging.Level;
import java.util.logging.Logger;

public class BitSetUniqueIpCounter implements UniqueIpCounter {

private final Logger logger = Logger.getLogger("BitSetUniqueIpCounter");

/*
To count unique IP's use a bit array, where each bit is set in accordance with one IP address.
In Java, there is no unsigned int and maximum BitSet size is integer.MAX_VALUE therefore we use two arrays.
*/
private final BitSet bitSetLow = new BitSet(Integer.MAX_VALUE); // 0 - 2_147_483_647
private final BitSet bitSetHi = new BitSet(Integer.MAX_VALUE); // 2_147_483_648 - 4_294_967_295
private long counter = 0;

private void registerLongValue(long longValue) {
int intValue = (int) longValue;
BitSet workingSet = bitSetLow;
if (longValue > Integer.MAX_VALUE) {
intValue = (int) (longValue - Integer.MAX_VALUE);
workingSet = bitSetHi;
}

if (!workingSet.get(intValue)) {
counter++;
workingSet.set(intValue);
}
}

@Override
public long countUniqueIp(String fileName) {
logger.log(Level.INFO, "Reading file: " + fileName);
long linesProcessed = 0;
String line;
// If already counted 2 ^ 32 unique addresses, then to the end of the file there will be only duplicates
registerLongValue(UniqueIpCounter.toLongValue(line));
linesProcessed++;
}
logger.log(Level.INFO, "Total lines processed: " + linesProcessed);
} catch (FileNotFoundException e) {
counter = -1;
} catch (IOException e) {
logger.log(Level.WARNING, "IOException occurs", e);
counter = -1;
}
return counter;
}
}


• I'm not a Java pedant, so I don't have a review for you. IMO, you've done a pretty good job, and if I were looking for a junior developer, I'd be happy with that code (assuming you wrote it and didn't scrape it from somewhere). I think you could probably increase the performance by doing your own parsing of the IP #s directly, and you might get good mileage by writing your own bitarray class as you started writing about. On the other hand, what you show here does a good job of implementing a fairly low-level approach using mid-level classes, which can be individually performance tuned later. – aghast Apr 5 at 15:43
• @nick012000 You're suggesting loading a 120GiB file into memory all at once?! – Konrad Rudolph Apr 7 at 13:54
• @KonradRudolph Works on my machine. (Swaps a bit, but that's barely noticeable.) Let's ship it. – wizzwizz4 Apr 7 at 22:21
• I would've told the potential employer: "If you want the results in 10 minutes, and allow me to use something other than Java, give me a server with a huge /tmp mount point, and type in sort --unique ip.txt | wc -l – Mark Stewart Apr 7 at 22:33
• Is not IPv6 ready :P – Hagen von Eitzen Apr 7 at 22:49

I'm being extra pedantic as this is a job interview question. Your code is better than 90% of what I have seen in job interviews. It shows that you have a fairly good understanding of how to solve the problem but there are improvements to be made in both minor details and the overall design of the solution. (This answer is a bit unstructured as I just make observations as I read through the code.)

The file name parsing employs unnecessary variables and the boolean statements changes logical order mid sentence. The reversed order is used when guarding against null values but I find it difficult to read (increases cognitive complexity). You have also already gone through all possible error conditions by referencing args when checking its length, so the reverse comparison order does not have any functional purpose any more. A more readable way to guard against nulls would be Objects.requireNonNull(args).

private static String parseFileName(String[] args) {
Objects.requireNonNull(args, "args must not be null");
if (args.length == 2 && args[0].equals("-file")) {
return args[1];
}
return null;
}


Variables that are not intended to be changed should always be final.

Error messages should be written to System.err. Also, you're inconsistently using System.out in one place and java.util.logging.Logger in another place and logging fatal errors as warnings.

You should avoid placing constants in interfaces as it leaks implementation details into the interface's API.

You're writing comments but not using the standard JavaDoc formatting. This reduces the usability of the comments as they will not be copied to automatically produced documentation or IDE tool tips.

The static toLongValue method for converting the input tries to force the UniqueIpCounter implementation to work with long values. I would not want to see static methods in interfaces and the internal representation of the data should not be exposed here. Leave the conversion to the responsibility of the specific implementation.

Forcing the UniqueIpCounter implementation to work with files, represented by file names, unnecessarily limits the reusability of the implementation and loads the implementation with multiple responsibilities, which violates the single responsibility principle. Reading the file should have been placed in a separate class. Parsing the read strings into IP addresses should have been another standalone class. The IP counter should thus only deal with the parsed input. Also, placing the responsibility of reading the file on the UniqueIpCounter you make unit testing the class very hard because now every test input has to be represented by a physical file on the disk.

The registerLongValue(long) seems an odd method in an interface named UniqueIpCounter. The naming should be consistent. So either registerIpAddress(...) or UniqueLongValueCounter.

Manuel suggested using InetAddress for parsing the input. When presented with a task of minimizing running time, you should read the source code of the libraries you use. It is obvious that InetAddress is a generic class that trades usability to performance. So you should implement a specialized string parsing algorithm and document why you wrote one instead of using a ready made library. You might even consider skipping the conversion to strings in between and create an InputStream reader that produces long values directly. In the end, the most important part is that you document why you did not choose to go with an easily readable and maintainable code. That said... your parsing algorithm is incredibly inefficient. To parse an IPv4 address to long you only need to read characters and append the digit value into an "accumulator":

Set parsedIpAddress and currentByte to 0;
If digit, multiply currentByte by 10 and add digit.
If dot or new line, multiply parsedIpAddress by 256 and add current byte.
If new line, parsedIpAddress is complete.
Otherwise repeat from line 2.


Using BitSet was, in theory, the correct choice but as Manuel pointed out, even having two sets does not cover the whole address range. Thus you have to reimplement it without the size limitation. That being said, the variable names need improvement. lowAddresses and highAddresses would tell the reader that they are used to store addresses already found. Use normal JavaDoc comments instead of end-of-line comments. EOL-comments are hard to read and maintain and you always have to make a compromise on the usefulness of the content to make it fit.

"Return -1 on error" is an anti-pattern inherited from C, which should not be repeated. The correct way to handle errors is to throw an exception. I'm not sure it it was required in the task but there was no error handling in the input parsing.

Generic advice for job interview code

Job interview programming tasks are always too vague. It's either because they want to see how you handle incomplete specifications or because they don't know what they are doing. Regardless of the reason, this puts you into a position where you have to either ask for clarifications (which is usually a good thing) or make assumptions if you are not allowed to ask. When you make assumptions you have to document that you had multiple choices and list the reasons why you chose the one you implemented. If the reviewer does not agree with your approach they at least know that you made an intentional choice between several options instead of "doing the only one thing you knew."

• Hmm, you call using BitSet correct and still recommend two names even though two BitSets can't cover all IPs, making their program wrong? – Manuel Apr 6 at 8:49
• @Manuel The alternative is to reimplement BitSet without the limitation. Since it does not provide any performance or storage improvement I don't think it would make sense. – TorbenPutkonen Apr 6 at 9:07
• Making the program correct and working would not be an improvement? I disagree. – Manuel Apr 6 at 9:34
• @Manuel Sorry, I overlooked that part while reviewing. You have indeed a valid point and I have improved my answer. – TorbenPutkonen Apr 6 at 11:33
• It could be done with more than two, let's say with four, but the extra logic above them seems about as much as with a single int[] (implemented in my answer now) and requires more initalization code. – Manuel Apr 6 at 11:47

The maximum int value is $$\2^{31}-1\$$, so your BitSets have $$\2^{31}-1\$$ entries each, so together they only cover $$\2^{32}-2\$$ IPs, missing two. And you documented their ranges incorrectly. If the file contains 255.255.255.255, you crash like this:

Exception in thread "main" java.lang.IndexOutOfBoundsException: bitIndex < 0: -2147483648
at java.base/java.util.BitSet.get(BitSet.java:624)
at BitSetUniqueIpCounter.registerLongValue(BitSetUniqueIpCounter.java:29)
at BitSetUniqueIpCounter.countUniqueIp(BitSetUniqueIpCounter.java:43)
at IpCounterApp.main(IpCounterApp.java:19)


I'd instead use a single int[] seen = new int[1 << 27] ($$\2^{27}\$$ ints with $$\2^{5}\$$ bits each, so $$\2^{32}\$$ bits total) and treat it like this:

    private void registerLongValue(long longValue) {
int index = (int) (longValue >> 5);
int bit = 1 << (longValue & 31);
if ((seen[index] & bit) == 0) {
counter++;
seen[index] |= bit;
}
}


Your toLongValue is rather complicated, you could use InetAddress (might also be faster):

    static long toLongValue(String ipString) throws UnknownHostException {
long result = 0;
result = (result << 8) | (b & 255);
return result;
}

• BitSet​(int nbits) Creates a bit set whose initial size is large enough to explicitly represent bits with indices in the range 0 through nbits-1. docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/… so my BitSet contains exactly 2^31 elements from index 0 to 2^31-1. Thanks for InetAddress hint – chptr-one Apr 5 at 19:35
• @chptr-one Wrong, your nbits is 2^31-1, not 2^31. And see the update to my answer that demonstrates the error. – Manuel Apr 6 at 8:35
• now i see it, thank you. I need to test my code more carefully. – chptr-one Apr 6 at 12:44
• The 27 and 5 are quite clever. It took me a while to understand where they come from. – Eric Duminil Apr 6 at 16:11
• @EricDuminil That wasn't supposed to be clever or a riddle :-). Added a note now. – Manuel Apr 6 at 19:48

I'm agree with TorbenPutkonen's considerations about your code and with Manuel's observation about edge ipaddresses cases like 255.255.255.255 that can break your code, I focused about your method toLongValue translating your ipv4 address to an unique long:

static long toLongValue(String ipString) {
StringBuilder field = new StringBuilder(3);
int startIndex = 0;
long result = 0;

for (int i = 0; i < 3; i++) {
int spacerPosition = ipString.indexOf('.', startIndex);
field.append(ipString, startIndex, spacerPosition);
int fieldValue = Integer.parseInt(field.toString());
field.setLength(0);
result += fieldValue * Math.pow(256, 3 - i);
startIndex = spacerPosition + 1;
}
result += Integer.parseInt(ipString.substring(startIndex));

return result;
}


Your method can be rewritten dividing your String ipv4 address with String.split and left shifting the octets with the logical | operator like below:

public static long toLongValue(String ipString) {
String[] octets = ipString.split("\\.");
return Long.parseLong(octets[0]) << 24 |
Long.parseLong(octets[1]) << 16 |
Long.parseLong(octets[2]) <<  8 |
Long.parseLong(octets[3]);
}


The absence of a primitive type unsigned int in java forces to use the primitive long type, so your BitSet will break when you pass your long converted to a negative int. The idea in itself for me is a correct choice but it has to be refined to include all the addresses. My first idea for performance was about the construction of a trie, it seems that as usual Knuth solved the problem creating the Patricia tree, you can check wikipedia notes for more details.

Since it's a job interview question, you probably want to:

• specify a package instead of using the default one. E.g. package chpter.one;
• put only the necessary code (BitSetUniqueIpCounter.java, IpCounterApp.java, UniqueIpCounter.java) in src/main/java. Anything that is only used for tests should be in src/test/java or src/test/resources/.
• Don't forget to close the file, even if Files.lines fails.
• Don't dump the whole stacktrace during a test which is expected to fail: tests are green but the console is still full of java.io.FileNotFoundException: no file....
• use a linter (e.g. SonarLint) to clean up the code and look for potential bugs.

├── pom.xml
└── src
├── main
│   ├── java
│   │   ├── BitSetUniqueIpCounter.java
│   │   ├── IpCounterApp.java
│   │   ├── NaiveStreamApiUniqueIpCounter.java
│   │   ├── TestFileGenerator.java
│   │   └── UniqueIpCounter.java
│   └── resources
│       └── million.txt
└── test
└── java
├── BitSetUniqueIpCounterTest.java
└── UniqueIpCounterTest.java


And it could look like:

├── pom.xml
└── src
├── main
│   └── java
│       └── chpter
│           └── one
│               ├── BitSetUniqueIpCounter.java
│               ├── IpCounterApp.java
│               └── UniqueIpCounter.java
└── test
├── java
│   └── chpter
│       └── one
│           ├── BitSetUniqueIpCounterTest.java
│           ├── NaiveStreamApiUniqueIpCounter.java
│           ├── TestFileGenerator.java
│           └── UniqueIpCounterTest.java
└── resources
└── million.txt


Note that the test folder looks fuller, and src/main is much leaner.

• Thank you. sir! I don't know about the need to close the file in case Files.lines() – chptr-one Apr 6 at 17:37
• @chptr-one: That's also one advantage of SonarLint. There's always an explanation for each improvement, and an indication if it's critical or not. You're free to decide what's important or not. That being said, it's not too hard to always close files, and not doing it can lead to weird bugs. – Eric Duminil Apr 6 at 19:47
• I already installed SonarLint to my IDEA and it looks very cool. Thanks for this recommendation, it is very useful for newbie. – chptr-one Apr 7 at 20:08
• "Don't dump the whole stacktrace during a test which is expected to fail" -- how do i do it? – chptr-one Apr 7 at 20:26
• @chptr-one: Keep up the good work, your work seems to indicate you're not a noobie. It's possible to learn new stuff about software development every day, anyway. One way to not dump the stacktrace would be to not catch the exceptions inside the method, and let them propagate. Inside the test, you can then check that an exception is raised when no such file is found. – Eric Duminil Apr 7 at 20:33

I see one little problem with the code you gave, even though I feel like it's a pretty good take at the problem you have.

Best case/worst case, you always ask for 512Mb memory. Say I give you a file that has 1 million times the same address, the code still initialized a 514 megabytes array.

Instead of using an array structure, I believe a tree structure would be more appropriate. I will not write it, as I've not written Java in awhile, but let's look at this.

There are 256 possible values for each of the 4 parts of an IP address, which leads you 256^4 possibilities (the 512 megabytes you use).

So, what if we had a tree structure with four levels of depth and 256 leafs per node?

In the worst case scenario where you'd use all possible values-ish (256^4 - 255 different addressed), you would require 512 megabytes.

But, depending on the distribution of the addresses you have in your file, you could take as little as 256*4 bits of memory.

The pseudo-algorithm I'd use would look something like this:

treeStructure = new treeStructure()
countUnique(list):
for element in list:
part1, part2, part3, part4 = parseIPString(element)

if doesnt exist treeStructure[part1]:
treeStructure[part1] = new treeStructure()

if doesnt exist treeStructure[part1][part2]:
treeStructure[part1][part2] = new treeStructure()

if doesnt exist treeStructure[part1][part2][part3]:
treeStructure[part1][part2][part3] = array[256]

if treeStructure[part1][part2][part3][part4] == 0:
treeStructure[part1][part2][part3][part4] = 1
counter++


Now, I know this code is poorly written and I wouldn't show this in a job interview. It should be pretty easy to make it clean by yourself as you've done quite well in your original post. The goal of the pseudo-code is to show the algorithm.

This way, you allocate memory in chunks of 256 bits when you need it instead of allocating a whole 512 megabytes at first.

• I was going to put up a tree structure suggestion, but you beat me to it. Dictionaries (like language dictionaries, not data structure dictionaries) are commonly stored this way. – gregsdennis Apr 6 at 20:38
• @gregsdennis I feel like if you want to post it again with more explanation than my post it'd be a good addition! – IEatBagels Apr 6 at 21:36
• If your worst case is still only 512 megabytes... how do you get all the inner tree node data for free? – Manuel Apr 7 at 9:26
• That code looks like it would have rather bad caching behavior which would trash performance by a good bit. And given that the worst case scenario is still the same max memory I don't see anything that really recommends this method. If you're worried about physical memory usage, you could easily use memory mapped files (or similar approaches to only allocate virtual memory from your OS) and let the OS worry about when to actually allocate the memory. – Voo Apr 7 at 9:34

consuming as little memory and time as possible

While your one bit per possible address is decent, it's not as little as possible. I actually have to run Java with -Xmx to allow it to take more heap space than usual.

An alternative idea: Go through the file, parse the addresses, and store them in temporary files. For example the address 1.2.3.4 goes into the file 0x0102.dat, and you store only two bytes (0x03 and 0x04). The eight billion addresses thus will take 16 GB disk space (less than the compressed input). Afterwards, process the files individually (you can for example do it with a BitSet of just 8 KB) and add their counts together. (Note: I don't know Java much, and don't know whether opening $$\2^{16}\$$ files is an issue. If it is, another option would be to create just 256 files (using an address's first number, and storing its lower three bytes).)

Or you could use external sorting and then don't need any data structure to count (just compare each address to the previous one). You could even make the sorting remove duplicates in the process, which saves disk space and makes the counting afterwards even more trivial.

• Comments are not for extended discussion; this conversation has been moved to chat. – Malachi Apr 9 at 19:19

In my opinion, your code is too long to solve this specific problem.

I'm not much into Java, but I would try the following methods:

1. Use "Trie" like data structure. As the length of the IP is always less than or equal to 12, so it should also do the job. This method will require a very small amount of memory. First of all, build the trie, insert all the IPs(skip when the character is a dot) to the trie. When you are done, just count the number of end flags. Or you can also keep a counter flag. Increase the counter flag whenever an end flag appears.

I'm sorry, I'm not good at Java. That's why I only added the instructions, no codes.

• The naive solution of storing Strings in a HashSet was explicitly forbidden in the problem description. – TorbenPutkonen Apr 7 at 6:40
• @TorbenPutkonen Although the slightly more memory-friendly option of an integer hashset isn't explicitly forbidden :) – Corey Apr 7 at 6:56
• @Corey Why do you need to spend whole int for each IP if you can spend just one bit? HashSet<Integer> will takes 32 times more memory then bit array. In addition Integer is wrapper. Primitive types will consume less memory and work faster. – chptr-one Apr 7 at 20:18
• A Trie would be simply worse for this problem than a HashSet. What a Trie is good at is prefix searches. But we don't need to do prefix searches here. We need to store things efficiently. A Trie is a memory pig, having to allocate a pointer for each digit. Even assuming we use a hexadecimal representation (to give fewer digits than the twelve digit decimal representation), that is still eight pointers (each at least four bytes to store) to store a thirty-two bit (four bytes) number. And good luck in trying to implement a Trie alone in less code than the three files here. – mdfst13 Apr 25 at 20:19
• @mdfst13 A trie would require 30-35 lines code maximum to solve this problem. No luck needed. And yes, we are not bound to implement any algorithm directly, we can always customize according to our needs. – Nazmul Hasan Apr 27 at 7:49