3
\$\begingroup\$

We have a list of string arrays i.e. List<String[]> (which we got from a csv) which follows the hierarchy:

0000

3000
   5000
   5000
   5000
    .
    . 
    .
3900

3000
   5000
   5000
   5000
    .
    .
    .
3900

.
.
.

9999

As you can see, it will always start with 0000 and end with 9999 (think of them as header and footer respectively)

Furthermore, it has equal numbers of 3000 and 3900, with zero to many 5000 records in between.

Input Example:

{
    ["0000","entry A", entry B", "entry C"....], 
    ["3000","entry1", entry2", "entry3"....],            ---
    ["5000", "entry4", entry 5", "entry 6"...],            |
    ["5000", "entry 7", entry 8", "entry 9"...],           |
    ["5000", "entry 10", entry 11", "entry 12"...],        | -> This is one group
    ["5000", "entry 13", entry 14", "entry 15".....],      |
    ["3900", "entry 16", entry 17", "entry 18"....],     ---
    ["3000","entry19", entry20", "entry 21"....],
    ["5000", "entry 22", entry 23", "entry 24"...],
    ["3900", "entry 25", entry 26", "entry 27"...],
    ["3000","entry 28", entry 29", "entry 30"...],
    ["3900", "entry 31", entry 32", "entry 33"...],
    ["9999", "entry X", entry Y", "entry Z"...]
}

The first and last row (i.e. 0000 and 9999) are useless and will not be used.

we have to split this List<String[]> into List<List<String[]>> such that it contains rows from 3000 to 3900

Output:

{
    {
        ["3000","entry1", entry2", "entry3", ...],
        ["5000", "entry4", entry 5", "entry 6", ...],
        ["5000", "entry 7", entry 8", "entry 9", ...],
        ["5000", "entry 10", entry 11", "entry 12", ...],
        ["5000", "entry 13", entry 14", "entry 15", ...],
        ["3900", "entry 16", entry 17", "entry 18", ...],
    },
    {
        ["3000","entry19", entry20", "entry 21", ...],
        ["5000", "entry 22", entry 23", "entry 24", ...],
        ["3900", "entry 25", entry 26", "entry 27", ...],
    },
    {
        ["3000","entry 28", entry 29", "entry 30", ...],
        ["3900", "entry 31", entry 32", "entry 33", ...],
    }
}

This is my code so far:

 private List<List<String[]>> splitIntoBlocks(List<String[]> rows) {

        //get all position of 3000
        List<Integer> l1 = IntStream.range(0,rows.size())
                .filter(i->rows.get(i)[0].equals("3000"))
                .boxed()
                .collect(Collectors.toList());

        //get all position of 3900
        List<Integer> l2 = IntStream.range(0,rows.size())
                .filter(i->rows.get(i)[0].equals("3900"))
                .boxed()
                .collect(Collectors.toList());

         List<List<String[]>> res=null;

        //split list<string[]> rows into blocks that start with 3000 and end with 3900 and store it in a list
        if(l1.size() == l2.size()) {
            res = IntStream.range(0, l1.size())
                    .mapToObj(i->rows.subList(l1.get(i),l2.get(i)+1))
                    .collect(Collectors.toList());
        }
        return res;
    }

As you can see, I have solved it using streams in roughly 3 stream statements, but I'm not very good at java 8 features. I'm looking for someone to solve this in perhaps 1 or 2 statements. I feel that it is very much possible

P.S. - This is not an interview question, but something I will be using at work.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ is there a performance reason to be using stream? The way you're using them seems odd, and IDK if it's for contextual reasons of if this just the first way you found of iterating. \$\endgroup\$ Oct 28, 2021 at 20:56
  • 2
    \$\begingroup\$ Why would you not use a BufferedReader and keep a state where a 3 has been seen and if not skip any line that doesn’t start with a 3? Is efficiency not a factor? \$\endgroup\$ Oct 29, 2021 at 4:23
  • \$\begingroup\$ Also, your input and output look ill-formed \$\endgroup\$ Oct 29, 2021 at 4:34
  • \$\begingroup\$ @ShapeOfMatter The reason for using stream was to do it using functional programming. I wanted a solution that uses functional programming rather than for loop with if else (which I was initially using and is also suggested in janos's answer). I'm quite aware that the time complexity of my code is very bad. Therefore, I was hoping whether this question can be solved with a good tradeoff between using functional programming and code efficiency. If not, then I'll be happy to proceed with the code suggested by janos. \$\endgroup\$ Oct 29, 2021 at 11:08
  • 3
    \$\begingroup\$ @HarshitDang I think you've fallen prey to the allure of streams. The whole point of them is to allow for independent parallel processing. That's only really appropriate when the data to be processed doesn't have internal dependencies. With your data, the internal ordering is a crucial part of the data structure, so (in my opinion at least) streams are not an appropriate approach. \$\endgroup\$ Oct 29, 2021 at 14:28

3 Answers 3

6
\$\begingroup\$

Motivations for improvement

I think "solving in 1 or 2 statements" is not a good target. Aiming for Java 8 features for the sake of using Java 8 features is also not a good target. A better target would be a combination of:

  • correct and reasonably robust
  • easy to understand
  • reasonably efficient

Here's a bit shorter and more efficient, but pretty bad solution:

private List<List<String[]>> splitIntoBlocks(List<String[]> rows) {
    List<List<String[]>> blocks = new ArrayList<>();

    int start = 0;
    for (int index = 0; index < rows.size(); index++) {
        String marker = rows.get(index)[0];
        if (marker.equals("3000")) {
            start = index;
        } else if (marker.equals("3900")) {
            int end = index + 1;
            blocks.add(rows.subList(start, end));
        }
    }

    return blocks;
}

This is bad (as bad as the original code), because it doesn't validate the input. It will only work correctly with input in the assumed format, which it doesn't verify, and it doesn't detect or signal when something is wrong, which could lead to nasty bugs.

Validating inputs

The posted code assumes the input follows a certain format. It should at least document the assumptions, and state if the caller can be trusted to enforce those assumptions.

As you mentioned, the input comes from CSV files. Since the expected format is not captured by the List<String[]> type, I would be very cautious. A verification is needed somewhere to avoid bugs or undefined behavior, for example the following checks come to mind:

  • There are the same number of START and END markers (you already did this one)
  • The START and END markers don't overlap
  • (optional?) There are no garbage records after an END and before the next START
  • The rows are not empty (avoid crashing due to index out of bounds exceptions)

When any of these assumptions fail, I would either raise a custom exception that the caller can handle, or else throw IllegalArgumentException to fail fast.

So in fact, instead of making the posted code shorter, I'm suggesting to actually make it longer, by adding more validation logic.

Making the code easier to understand

Another answer already mentioned to improve the variable names. (I suggest following Java conventions with camelCase names, so startIndices and endIndices.)

The values "3000" and "3900" are magic strings. It would be better to use private static final constants for such values, so that they stand out, and with a descriptive name.

Building the lists of startIndices and endIndices use the same logic, duplicated. It would be good to extract to a helper method.

When returning a container type, it's usually more practical to return an empty container instead of null.

\$\endgroup\$
5
  • \$\begingroup\$ Thank you for the suggestions on validation part. I had skipped the validation logic for now to keep the focus of this question on the main logic of splitting. My bad. Let's say that we add the validation logic in the code that you've provided, would that turn this "bad" code into "good" code? Furthermore, is the code provided by you the most efficient when it comes to "splitting" logic? \$\endgroup\$ Oct 29, 2021 at 7:48
  • 1
    \$\begingroup\$ The bad code I provided is efficient because it splits the list in a single pass. I don't think it can be more efficient. It's also easy to read, for now. If you implement validation in that same method, I think it will become complex and hard to read, because the validation itself will be an added responsibility. I think a good tradeoff is to have a separate method that performs validation, and call that function at the top of this one. It won't be the most efficient solution, because it will mean 2 passes over the input. But readability is important, so I think that will be a good tradeoff. \$\endgroup\$
    – janos
    Oct 29, 2021 at 7:55
  • 1
    \$\begingroup\$ @janos - I don't see any need for a 2 pass approach. At each "row" of input you can firstly determine whether the input constraints have been met, then process the row appropriately. \$\endgroup\$ Oct 29, 2021 at 14:30
  • 1
    \$\begingroup\$ @MarkBluemel I think that's opinionated. It certainly can be done in a single pass, which will do validation and splitting. Doing 2 things at the same time adds mental burden, and it's probably difficult to write in a way that's as easy to understand as when separated. Since we're on the same order of complexity regardless of 1 or 2 passes, I would first write it so it's easiest to read, and if later it's identified as a bottleneck, it could be merged into one. If the author insists on combining, and it's reasonably easy to read, I would not object. \$\endgroup\$
    – janos
    Oct 29, 2021 at 14:46
  • 1
    \$\begingroup\$ @janos We're all opinionated ;-) My sample solution is in my answer to the OP's post and I don't think it's particularly difficult to understand, and I do think it's fairly robust, and well-suited to subsequent amendment. For me, the key thing was to regard the input processing more like reading a file than like making passes over an array - as I remark in my answer, if the structure had been any more complicated I'd probably have used a Finite State Machine - my current solution is only a little different from one, in that the states are more or less implicit. \$\endgroup\$ Oct 29, 2021 at 14:51
4
\$\begingroup\$

Low hanging fruit

l1 and l2 are very opaque variable names. start_indices and end_indices would be much more descriptive.


        //get all position of 3000
        List<Integer> l1 = IntStream.range(0,rows.size())
                .filter(i->rows.get(i)[0].equals("3000"))
                .boxed()
                .collect(Collectors.toList());

This code takes int indices, boxes them into Integer indices, and collects them into a List<Integer>. This results in many small objects in memory.

We can avoid the boxing, by replacing .boxed().collect(Collectors.toList()) with .toArray() and changing the variable type to int[].

        // get positions of all "3000"'s
        int[] start_indices = IntStream.range(0,rows.size())
                .filter(i->rows.get(i)[0].equals("3000"))
                .toArray();

Apply similar change to the group end indices, and corresponding changes to the final res construction.

Single Pass

The above is still passing over the rows input 3 times; the first to collect the starting indices, the second to collect the ending indices, and the third time to assemble the result. Three passes means you cannot apply this grouping operation on an ephemeral stream; it requires a concrete collection that can be repeatedly iterated over.

Moreover, an IntStream is being used to generate indices into the rows list -- a hack -- which requires an ArrayList or similar \$O(1)\$-indexable collection to avoid quadratic time complexity.

It would be much better to perform a single pass over the stream of data, and collecting the required groups along the way:

private List<List<String[]>> splitIntoBlocks(List<String[]> rows) {
   return rows.stream().collect(Block.collector());
}

Well, the above clearly solves the "looking for someone to solve this in perhaps 1 or 2 statements" request, but clearly additional work is still required. The Block.collector() class is required, writing of which (to handle possible splitting & parallel stream handling) is a non-trivial exercise. See Collector.of(...)

\$\endgroup\$
1
  • \$\begingroup\$ I think the approach of writing a custom collector is a very good one. \$\endgroup\$ Oct 29, 2021 at 16:36
2
\$\begingroup\$
  • The input data seems to me to naturally fit a sequential process, and all the processing can be achieved in a single pass, so I fail to see how using streams and making 3 passes is a sensible approach, especially with the amount of boxing used
  • The approach taken assumes, rather than checks, that the input data is well-formed, which seems a little optimistic. Defensive programming principles suggest that you should check the data meets expectations.
  • The naming issues have already been addressed. There's little restriction on variable names, and the typing saved in naming a variable "l1" is a poor exchange for readability against "subListStartOffsets" or something similar.

For this sort of processing, I'd often write a little Finite State Machine, but this exercise doesn't seem quite to warrant it. The natural processing pattern seems to me to be this.

For the first array, check that it starts with "0000". If not, throw an Exception as the input is badly-formed.

Assign a List<List<String[]>> for the result. Let's call this outputList.

Also allocate an int to hold the start of the current subList. Let's just call this subListStart. Initialise it to a "flag" value, say -1. (This probably should be a constant).

Now process a row at a time.

  • If it starts with "3000" it marks the start of a subList. Check subListStart, if it is -1 then store the current offset in it, if not the input data is badly formed, and you should throw an Exception.
  • If it starts with "3900" it marks the end of a subList. Extract the subList from subListStart to the current offset, and add it to your outputList. Set subListStart to -1 again, to indicate we're looking for a new start...
  • If it starts with "5000" it's just data, but you should check that you've seen a start of list marker, so if subListStart is -1 you should throw an Exception.
  • If it starts with "9999" it marks the end of the input data. You should check that the last subList was closed, by checking subListStart is -1.

Here's an example of how I might implement this (far from fully tested, I must point out).

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

public class SubListProcessor {

  private static final String HEADER = "0000";
  private static final String START_OF_SUBLIST = "3000";
  private static final String END_OF_SUBLIST = "3900";
  private static final String FOOTER = "9999";
  private static final String PLAIN_DATA = "5000";

  public class BadlyFormedListException extends IllegalArgumentException {

    public BadlyFormedListException(String message) {
      super(message);
    }
  }

  public List<List<String[]>> processList(List<String[]> inputList) {
    List<List<String[]>> outputList = new ArrayList<>();

    int subListStart = -1; // Magic number, could/should make this a constant
    int currentOffset = 0;
    boolean seenFooter = false;
    Iterator<String[]> inputListIterator = inputList.iterator();

    String[] firstLine = inputListIterator.next();
    if (firstLine == null) {
      throw new BadlyFormedListException("Input List is empty");
    }
    if (firstLine.length == 0) {
      throw new BadlyFormedListException("Empty line at offset " + currentOffset);
    }
    if (!firstLine[0].equals(HEADER)) {
      throw new BadlyFormedListException("No header in input List");
    }

    while (inputListIterator.hasNext()) {
      String[] inputLine = inputListIterator.next();
      currentOffset += 1;
      if (inputLine.length == 0) {
        throw new BadlyFormedListException("Empty line at offset " + currentOffset);
      }
      switch (inputLine[0]) {
        case (START_OF_SUBLIST) : {
          if (subListStart == -1) {
            subListStart = currentOffset;
          }
          else {
            throw new BadlyFormedListException("Unclosed sub-list at offset " + currentOffset);
          }
          break;
        }
        case (PLAIN_DATA) : {
          if (subListStart == -1) {
            throw new BadlyFormedListException("Unopened sub-list at offset " + currentOffset);
          }
          break;
        }
        case (END_OF_SUBLIST) : {
          if (subListStart == -1) {
            throw new BadlyFormedListException("Unopened sub-list at offset " + currentOffset);
          }
          outputList.add(inputList.subList(subListStart, currentOffset + 1));
          subListStart = -1;
          break;
        }
        case (FOOTER) : {
          if (subListStart != -1) {
            throw new BadlyFormedListException("Unclosed sub-list at offset " + currentOffset);
          }
          seenFooter = true;
          break;
        }
        default :
          throw new BadlyFormedListException("Unrecognised line at offset " + currentOffset);

      }
    }

    if (!seenFooter) {
      throw new BadlyFormedListException("No footer in input list");
    }

    return outputList;
  }

  public static void main(String[] args) {
    List<String[]> inputList = Arrays.asList(
        new String[]{"0000", "entry A", "entry B", "entry C"},
        new String[]{"3000", "entry1", "entry2", "entry3"},
        new String[]{"5000", "entry4", "entry 5", "entry 6"},
        new String[]{"5000", "entry 7", "entry 8", "entry 9"},
        new String[]{"5000", "entry 10", "entry 11", "entry 12"},
        new String[]{"5000", "entry 13", "entry 14", "entry 15"},
        new String[]{"3900", "entry 16", "entry 17", "entry 18"},
        new String[]{"3000", "entry19", "entry20", "entry 21"},
        new String[]{"5000", "entry 22", "entry 23", "entry 24"},
        new String[]{"3900", "entry 25", "entry 26", "entry 27"},
        new String[]{"3000", "entry 28", "entry 29", "entry 30"},
        new String[]{"3900", "entry 31", "entry 32", "entry 33"},
        new String[]{"9999", "entry X", "entry Y", "entry Z"});

    List<List<String[]>> result = new SubListProcessor().processList(inputList);

    for (List<String[]> subList : result) {
      System.out.println("<");
      for (String[] value : subList) {
        System.out.format("\t%s%n", Arrays.toString(value));
      }
      System.out.println(">");
    }
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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