2
\$\begingroup\$

I got this question as a coding challenge and was unable to get it done under 50 milliseconds (my solution takes >100 ms) :D

Would you please review my code and share any idea how to do this within 50ms?

Problem Description One of our customers, a multinational company that manufactures industrial appliances, has an internal system to procure (purchase) all resources the company needs to operate. The procurement is done through the company's own ERP (Enterprise Resource Planning) system.

A typical business process represented by the ERP system is procure-to-pay, which generally includes the following activities:

  • create purchase request
  • request approved
  • create purchase order
  • select supplier
  • receive goods
  • pay invoice

Whenever the company wants to buy something, they do so through their ERP system.

The company buys many resources, always using their ERP system. Each resource purchase can be considered a case, or single instance of this process. As it happens, the actual as-is process often deviates from the ideal to-be process. Sometimes purchase requests are raised but never get approved, sometimes a supplier is selected but the goods are never received, sometimes it simply takes a long time to complete the process, and so on. We call each unique sequence of activities a variant.

The customer provides us with extracted process data from their existing ERP system. The customer extracted one of their processes for analysis: Procure-to-pay. The logfiles contain three columns:

activity name case id timestamp We want to analyse and compare process instances (cases) with each other.

Acceptance Criteria

  • Aggregate cases that have the same event execution order and list the 10 variants with the most cases.
  • As that output is used by other highly interactive components, we need to be able to get the query results in well under 50 milliseconds.

Notes:

  • The sample data set is not sorted, please use the timestamp in the last column to ensure the correct order.
  • The time required to read the CSV file is not considered part of the 50 milliseconds specified in the acceptance criteria.

Sample data: the actual file contains 62,000 rows is here

CaseID;ActivityName;Timestamp
100430035020241420012015;Create purchase order item;2015-05-27 12:44:47.000
100430035020261980012015;Create MM invoice by vendor;2015-07-13 00:00:00.000
100430035020119700012015;Reduce purchase order item net value;2015-02-13 10:24:02.000
100430035020066380012015;Change purchase order item;2015-01-23 09:39:33.000
100430035020232560012015;Change purchase order item;2015-05-11 07:58:29.000
100430031000134820012015;Clear open item;2015-07-28 23:59:59.000
100430035020241250012015;Remove payment block;2015-06-04 16:36:26.000
100430035020193960012015;Enter goods receipt;2015-03-12 20:00:06.000
100430031000151590012015;Clear open item;2015-11-24 23:59:59.000
100430031000129230012015;Post invoice in FI;2015-06-01 12:00:37.000
100430035020228280012015;Create MM invoice by vendor;2015-04-07 00:00:00.000
100430031000113630012015;Clear open item;2015-03-24 23:59:59.000
100430035020260940012015;Enter goods receipt;2015-07-16 15:07:49.000
100430035020244540012015;Create purchase order item;2015-06-02 11:06:11.000

my rejected code

fun main(args: Array<String>) {
    val eventlogRows = CSVReader.readFile("samples/Activity_Log.csv")

    val begin = System.currentTimeMillis()

    val grouped = eventlogRows.groupBy { it.caseId }
    val map = hashMapOf<String, Int>()
    grouped.forEach {
        val toSortedSet = it.value.toSortedSet(compareBy { it.timestamp })
        val hash = toSortedSet.joinToString { it -> it.eventName }
        map[hash] = map[hash] ?: 0 + 1
    }
    
    val sortedByDescending = map.entries.sortedByDescending { it.value }
    
    val end = System.currentTimeMillis()

    println(String.format("Duration: %s milliseconds", end - begin))
}

CSVReader.java

import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.time.LocalDateTime;
import java.time.ZoneId;
import java.time.ZoneOffset;
import java.time.format.DateTimeFormatter;
import java.util.List;
import java.util.stream.Collectors;

import org.apache.commons.csv.CSVFormat;
import org.apache.commons.csv.CSVParser;

public class CSVReader {

    public static List<EventlogRow> readFile(String fileName) {
        DateTimeFormatter formatter = DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss.SSS").withZone(ZoneId.of("UTC"));
        try (InputStreamReader reader = new InputStreamReader(new FileInputStream(fileName))) {
            try (CSVParser csvParser = new CSVParser(reader, CSVFormat.newFormat(';').withFirstRecordAsHeader())) {
                return csvParser.getRecords().stream()
                        .map(record -> new EventlogRow(
                                record.get(0),
                                record.get(1),
                                LocalDateTime.parse(record.get(2), formatter).atOffset(ZoneOffset.UTC)))
                        .collect(Collectors.toList());
                    
                }
        } catch (IOException e) {
            throw new RuntimeException("IOException while reading file", e);
        }
    }
}

EventlogRow.java

import java.time.OffsetDateTime;

public class EventlogRow {
    
    String caseId;
    String eventName;
    OffsetDateTime timestamp;
    
    public EventlogRow(String caseId, String eventName, OffsetDateTime timestamp) {
        this.caseId = caseId;
        this.eventName = eventName;
        this.timestamp = timestamp;
    }
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Aggregate cases that have the same event execution order and list the 10 variants with the most cases - this phrase is not clear to me. Your method doesn't return anything and prints just duration, what is the purpose of it? \$\endgroup\$
    – Flame239
    Jun 3 at 8:45
  • \$\begingroup\$ as far as I understand, this phrase means to aggregate the cases by its id and then find the 10 variants (variant is sequence of events for one case ) thats showed the most \$\endgroup\$
    – David Meik
    Jun 3 at 8:56
  • \$\begingroup\$ and yes you are right my code should return the first 10 items of sortedByDescending \$\endgroup\$
    – David Meik
    Jun 3 at 8:59
3
\$\begingroup\$

Disclaimer: I do not know Kotlin, only a bit of Java.

Extract the solution to a function

private fun topTenCaseFlows(eventLogRows: List<EventLogRow>): List<Pair<String, Int>> {
    val grouped = eventLogRows.groupBy { it.caseId }
    val map = hashMapOf<String, Int>()
    grouped.forEach {
        val toSortedSet = it.value.toSortedSet(compareBy { it.timestamp })
        val hash = toSortedSet.joinToString { it -> it.eventName.orEmpty() }
        map[hash] = map[hash] ?: 0 + 1
    }

    val sortedByDescending = map.entries.sortedByDescending { it.value }
    return sortedByDescending.take(10).map { Pair(it.key, it.value) };
}

Now you have something that takes in the data and returns the top 10.

If you look at the top 10 at this point you may be surprised that the counts are all 1.

Bugs

map[hash] ?: 0 + 1 is interpreted as map[hash] ?: (0 + 1) so parentheses are needed: (map[hash] ?: 0) + 1

The top 10 counts are now much larger than 1 but there's still more.


Look at case 100430035020119700012015:

100430035020119700012015;Reduce purchase order item net value;2015-02-13 10:24:02.000 
100430035020119700012015;Enter goods receipt;2015-02-13 10:35:18.000 
100430035020119700012015;Change purchase order item;2015-02-13 10:24:02.000 
100430035020119700012015;Change purchase order item;2015-02-13 10:24:02.000 
100430035020119700012015;Create purchase order item;2015-01-28 06:05:07.000 
100430035020119700012015;Reduce purchase order item quantity;2015-02-13 10:35:54.000 
100430035020119700012015;Change purchase order item;2015-02-13 10:35:54.000 
100430035020119700012015;Change purchase order item;2015-02-13 10:35:54.000 
100430035020119700012015;Reduce purchase order item quantity;2015-02-13 10:24:02.000 
100430035020119700012015;Create MM invoice by vendor;2015-02-11 00:00:00.000 
100430035020119700012015;Reduce purchase order item net value;2015-02-13 10:35:54.000 
100430035020119700012015;Post invoice in MM;2015-02-23 07:41:59.000 
100430035020119700012015;Clear open item;2015-03-10 23:59:59.000 

Some events have identical timestamps, 2015-02-13 10:24:02.000 and 2015-02-13 10:35:54.000 .

It's debatable (and underspecified) what happens first when the timestamps are identical, but all the events certainly happened.

val hash1 = it.value.toSortedSet(compareBy { it.timestamp }).joinToString { it.eventName.orEmpty() }
val hash2 = it.value.sortedWith(compareBy(EventLogRow::timestamp, EventLogRow::eventName)).joinToString { it.eventName.orEmpty() }

hash1 and hash2 are not identical. Using a sortedSet discards the entries with duplicate timestamps.

Timing

Timing Java methods is not straight forward. Typically a single run is not representative of the actual time in real usage.

Kotlin has a built-in function to time a block, measureTimeMillis.

Doing a bit of warmup allows the Java jit to do its thing and reduce the run time significantly:

fun main(args: Array<String>) {
    val eventlogRows = CSVReader.readFile("samples/Activity_Log.csv")

    for (i in 0 until 10) {
        topTenCaseFlows(eventLogRows)
    }

    var counts: List<Pair<String, Int>> = listOf()
        val timeInMillis = measureTimeMillis {
            counts = topTenCaseFlows(eventLogRows)
        }

    println(String.format("Duration: %s milliseconds", timeInMillis))
    println(counts.joinToString(separator = "\r\n") { String.format("%s: %d", it.first, it.second)  })
}

private fun topTenCaseFlows(eventLogRows: List<EventLogRow>): List<Pair<String, Int>> {
    val grouped = eventLogRows.groupBy { it.caseId }
    val map = hashMapOf<String, Int>()
    grouped.forEach {
        val hash = it.value.sortedWith(compareBy(EventLogRow::timestamp, EventLogRow::eventName)).joinToString { it.eventName.orEmpty() }
        map[hash] = (map[hash] ?: 0) + 1
    }

    val sortedByDescending = map.entries.sortedByDescending { it.value }
    return sortedByDescending.take(10).map { Pair(it.key, it.value) };
}

In my testing it goes from >100ms to <50ms

Style

I prefer the method chaining style from LINQ so this is how I would write it:

private fun topTenCaseFlows(eventLogRows: List<EventLogRow>): List<Pair<String, Int>> {
    return eventLogRows.groupBy { it.caseId }
        .map { case ->
            case.value.sortedWith(compareBy(EventLogRow::timestamp, EventLogRow::eventName))
                .joinToString { it.eventName.orEmpty() }
        }
        .groupingBy { it }.eachCount()
        .entries.sortedByDescending { it.value }
        .take(10)
        .map { Pair(it.key, it.value) }
}

Note: You can remove EventLogRow::eventName if you would prefer use the event order from the file. According to the documentation both groupBy and sortedWith guarantee stable ordering with regards to entry order on duplicate keys.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you @Johnbot for taking the time to review my code and for the bugs and style suggestions. I appreciate! one more question, do you see another way to implement the logic (different algorithm, data structure,.. ) under 50ms without the warmup of the Java jit trick? \$\endgroup\$
    – David Meik
    Jun 4 at 17:43

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.