Cfrtjryk

The following code is my solution to a code challenge I submitted a few weeks ago. I got rejected straight away with no feedback and I've wondering why.

I'm interested in hearing if there is any design pattern I should have clearly used or if there is any best practice I completely violated.

Requirements

Build a restful API that calculates realtime statistics from the last 60 seconds. There will be two endpoints, one of them, POST /transactions is called to register a new transaction (unique input of this application). The other one, GET /statistics , returns the statistic based of the transactions of the last 60 seconds.

Both endpoints have to execute in constant time and memory (O(1)).

Include an in-memory DB.

Solution

My approach to fulfilling the O(1) requirement was to use a cache to hold the transactions received in the last 60s:

• When a new transaction is received, it's added to the cache. All transactions newer than 60s are added, older than 60 seconds ones are discarded by the controller.


• The queue is sorted on timestamp, so that transactions with the oldest timestamp are at the top. The refresh rate is configured at 1ms.


• A periodic task gets rid of transactions older than 60 seconds. Because the queue is ordered, we don't need to go through all of the entries.

I've omitted the test classes because the code is already long enough. It can also be found at Github.

It's a standard Spring Boot application, run with mvn spring-boot:run. Example endpoint calls with curl:

curl localhost:8080/statistics

curl -XPOST -H "Content-Type:application/json" -d'{"amount":100, "timestamp":1503323242441}' localhost:8080/transactions (the timestamp needs to be newer than 60s or it'll be ignored, you can get one with new Date().getTime()).

pom.xml

<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"

         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">

    <modelVersion>4.0.0</modelVersion>



    <groupId>statistics</groupId>

    <artifactId>n26</artifactId>

    <version>1.0-SNAPSHOT</version>

    <packaging>jar</packaging>



    <name>n26</name>

    <url>http://maven.apache.org</url>



    <parent>

        <groupId>org.springframework.boot</groupId>

        <artifactId>spring-boot-starter-parent</artifactId>

        <version>1.5.4.RELEASE</version>

    </parent>



    <properties>

        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>

        <maven.compiler.source>1.8</maven.compiler.source>

        <maven.compiler.target>1.8</maven.compiler.target>

        <lombok.version>1.16.16</lombok.version>

        <hibernate.validator.version>5.4.1.Final</hibernate.validator.version>

        <junit.version>4.12</junit.version>

        <rest-assured.version>2.9.0</rest-assured.version>

    </properties>



    <dependencies>

        <!-- Spring Boot -->

        <dependency>

            <groupId>org.springframework.boot</groupId>

            <artifactId>spring-boot-starter-web</artifactId>

        </dependency>

        <dependency>

            <groupId>org.springframework.boot</groupId>

            <artifactId>spring-boot-starter-data-jpa</artifactId>

        </dependency>



        <!-- H2 -->

        <dependency>

            <groupId>com.h2database</groupId>

            <artifactId>h2</artifactId>

        </dependency>



        <!-- Constraints validation -->

        <dependency>

            <groupId>org.hibernate</groupId>

            <artifactId>hibernate-validator</artifactId>

            <version>${hibernate.validator.version}</version>

        </dependency>



        <!-- Lombok -->

        <dependency>

            <groupId>org.projectlombok</groupId>

            <artifactId>lombok</artifactId>

            <version>${lombok.version}</version>

            <scope>provided</scope>

        </dependency>

    </dependencies>



    <build>

        <plugins>

            <plugin>

                <groupId>org.springframework.boot</groupId>

                <artifactId>spring-boot-maven-plugin</artifactId>

            </plugin>

        </plugins>

    </build>



    <profiles>

        <profile>

            <id>development</id>

            <activation>

                <activeByDefault>true</activeByDefault>

            </activation>

            <dependencies>

                <dependency>

                    <groupId>org.springframework.boot</groupId>

                    <artifactId>spring-boot-devtools</artifactId>

                    <optional>true</optional>

                </dependency>

            </dependencies>

        </profile>

        <profile>

            <id>production</id>

        </profile>

    </profiles>

</project>

App.java

package statistics;



import org.springframework.boot.SpringApplication;

import org.springframework.boot.autoconfigure.SpringBootApplication;

import org.springframework.scheduling.annotation.EnableScheduling;



@SpringBootApplication

@EnableScheduling

public class Application {



    public static void main(String args) {

        SpringApplication.run(Application.class, args);

    }

}

TransactionTimestampComparator.java

package statistics.comparator;



import java.util.Comparator;



import statistics.model.Transaction;



public class TransactionTimestampComparator implements Comparator<Transaction> {



    @Override

    public int compare(Transaction o1, Transaction o2) {

        return o1.getTimestamp().compareTo(o2.getTimestamp());

    }

}

StatisticsController.java

package statistics.controller;





import org.springframework.beans.factory.annotation.Autowired;

import org.springframework.http.ResponseEntity;

import org.springframework.stereotype.Controller;

import org.springframework.web.bind.annotation.RequestMapping;

import org.springframework.web.bind.annotation.ResponseBody;



import statistics.dto.Statistics;

import statistics.service.StatisticsService;



import static org.springframework.http.HttpStatus.OK;



@Controller

public class StatisticsController {



    @Autowired

    private StatisticsService statisticsService;



    @RequestMapping("/statistics")

    @ResponseBody

    public ResponseEntity<Statistics> getTransactions() {

        return new ResponseEntity<>(statisticsService.getStatistics(), OK);

    }

}

TransactionController.java

package statistics.controller;





import org.springframework.beans.factory.annotation.Autowired;

import org.springframework.http.ResponseEntity;

import org.springframework.stereotype.Controller;

import org.springframework.web.bind.annotation.RequestBody;

import org.springframework.web.bind.annotation.RequestMapping;



import javax.validation.Valid;

import javax.validation.constraints.NotNull;



import statistics.model.Transaction;

import statistics.service.TransactionService;



import static java.lang.System.currentTimeMillis;

import static org.springframework.http.HttpStatus.CREATED;

import static org.springframework.http.HttpStatus.NO_CONTENT;

import static org.springframework.web.bind.annotation.RequestMethod.POST;

import static statistics.service.TransactionService.TIME_LIMIT;



@Controller

public class TransactionController {



    @Autowired

    private TransactionService transactionService;



    @RequestMapping(value = "/transactions", method = POST)

    public ResponseEntity<Void> create(@Valid @NotNull @RequestBody Transaction transaction) {

        if (currentTimeMillis() - transaction.getTimestamp() > TIME_LIMIT) {

            // Assume that we are to save a transaction only if it happened within the last minute

            return new ResponseEntity<>(NO_CONTENT);

        } else {

            transactionService.create(transaction);

            return new ResponseEntity<>(CREATED);

        }

    }



}

Statistics.java

package statistics.dto;



import java.util.Collection;

import java.util.List;



import lombok.EqualsAndHashCode;

import lombok.Getter;

import lombok.Setter;

import lombok.ToString;

import statistics.model.Transaction;



import static java.util.stream.Collectors.toList;



@Getter

@Setter

@EqualsAndHashCode

@ToString

public class Statistics {



    private Double sum;



    private Double avg;



    private Double max;



    private Double min;



    private Long count;



    public Statistics() {

    }



    public Statistics(Collection<Transaction> transactions) {

        final List<Double> amountsLastMinute = transactions.stream().map(Transaction::getAmount).collect(toList());

        final Long count = amountsLastMinute.stream().count();

        this.setCount(count);

        if (count > 0) {

            this.setSum(amountsLastMinute.stream().mapToDouble(Double::doubleValue).sum());

            this.setAvg(amountsLastMinute.stream().mapToDouble(Double::doubleValue).average().getAsDouble());

            this.setMax(amountsLastMinute.stream().max(Double::compareTo).get());

            this.setMin(amountsLastMinute.stream().min(Double::compareTo).get());

        }

    }

}

Error.java

package statistics.exception;



import org.springframework.validation.FieldError;



import java.util.ArrayList;

import java.util.List;



import lombok.Getter;

import lombok.Setter;



@Getter

@Setter

class Error {



    private final int status;



    private final String message;



    private List<FieldError> fieldErrors = new ArrayList<>();



    Error(int status, String message) {

        this.status = status;

        this.message = message;

    }



    public void addFieldError(String objectName, String path, String message) {

        FieldError error = new FieldError(objectName, path, message);

        fieldErrors.add(error);

    }



}

GlobalControllerExceptionHandler.java

package statistics.exception;



import org.springframework.core.annotation.AnnotationUtils;

import org.springframework.http.converter.HttpMessageNotReadableException;

import org.springframework.validation.BindingResult;

import org.springframework.web.bind.MethodArgumentNotValidException;

import org.springframework.web.bind.annotation.ControllerAdvice;

import org.springframework.web.bind.annotation.ExceptionHandler;

import org.springframework.web.bind.annotation.ResponseBody;

import org.springframework.web.bind.annotation.ResponseStatus;

import org.springframework.web.servlet.ModelAndView;



import java.util.List;



import javax.servlet.http.HttpServletRequest;



import static org.springframework.http.HttpStatus.BAD_REQUEST;



@ControllerAdvice

public class GlobalControllerExceptionHandler {



    public static final String DEFAULT_ERROR_VIEW = "error";



    @ExceptionHandler(Exception.class)

    public ModelAndView defaultErrorHandler(HttpServletRequest req, Exception e) throws Exception {

        // If the exception is annotated with @ResponseStatus rethrow it and let

        // the framework handle it

        if (AnnotationUtils.findAnnotation

                (e.getClass(), ResponseStatus.class) != null) {

            throw e;

        }



        // Otherwise setup and send the user to a default error-view.

        ModelAndView mav = new ModelAndView();

        mav.addObject("exception", e);

        mav.addObject("url", req.getRequestURL());

        mav.setViewName(DEFAULT_ERROR_VIEW);

        return mav;

    }



    /**

     * Exception handler for bad requests

     */

    @ResponseStatus(BAD_REQUEST)

    @ResponseBody

    @ExceptionHandler({MethodArgumentNotValidException.class, HttpMessageNotReadableException.class})

    public Error methodArgumentNotValidException(MethodArgumentNotValidException ex) {

        BindingResult result = ex.getBindingResult();

        List<org.springframework.validation.FieldError> fieldErrors = result.getFieldErrors();

        return processFieldErrors(fieldErrors);

    }



    private Error processFieldErrors(List<org.springframework.validation.FieldError> fieldErrors) {

        Error error = new Error(BAD_REQUEST.value(), "validation error");

        for (org.springframework.validation.FieldError fieldError : fieldErrors) {

            error.addFieldError(fieldError.getObjectName(), fieldError.getField(), fieldError.getDefaultMessage());

        }

        return error;

    }



}

Transaction.java

package statistics.model;



import com.fasterxml.jackson.annotation.JsonIgnore;



import javax.persistence.Entity;

import javax.persistence.GeneratedValue;

import javax.persistence.GenerationType;

import javax.persistence.Id;

import javax.validation.constraints.NotNull;



import lombok.EqualsAndHashCode;

import lombok.Getter;

import lombok.Setter;

import lombok.ToString;

import statistics.validation.Past;



import static java.lang.System.currentTimeMillis;

import static statistics.service.TransactionService.TIME_LIMIT;



@Entity

@Getter

@Setter

@EqualsAndHashCode

@ToString

public class Transaction {



    @Id

    @GeneratedValue(strategy = GenerationType.AUTO)

    private Long id;



    @NotNull

    private Double amount;



    @NotNull

    @Past

    private Long timestamp;



    @JsonIgnore

    public boolean isNewerThanTimeLimit() {

        return currentTimeMillis() - timestamp <= TIME_LIMIT;

    }



}

TransactionDao.java

package statistics.persistance;



import org.springframework.beans.factory.annotation.Autowired;

import org.springframework.stereotype.Repository;



import javax.persistence.EntityManager;



import statistics.model.Transaction;

import statistics.service.StatisticsService;

import statistics.service.TransactionService;



@Repository

@org.springframework.transaction.annotation.Transactional

public class TransactionDao {



    @Autowired

    private EntityManager entityManager;



    /**

     * Important: When directly invoking this method, the given transaction will NOT be added to the queue of transactions in {@link

     * StatisticsService}, thus it won't be reflected in the statistics that service provides. To get it added, use {@link

     * TransactionService#create(Transaction)} instead of this method

     */

    public void save(Transaction transaction) {

        getEntityManager().persist(transaction);

    }



    public EntityManager getEntityManager() {

        return entityManager;

    }

}

StatisticsService.java

package statistics.service;



import org.springframework.scheduling.annotation.Scheduled;

import org.springframework.stereotype.Service;



import java.util.concurrent.PriorityBlockingQueue;



import lombok.Getter;

import statistics.comparator.TransactionTimestampComparator;

import statistics.dto.Statistics;

import statistics.model.Transaction;



@Service

public class StatisticsService {



    private static final int QUEUE_INITIAL_CAPACITY = 1000;

    private static final int POLLING_INTERVAL_RATE_MILLIS = 1;



    private final PriorityBlockingQueue<Transaction> transactionsLast60Seconds =

            new PriorityBlockingQueue<>(QUEUE_INITIAL_CAPACITY, new TransactionTimestampComparator());



    @Getter

    private Statistics statistics = new Statistics(transactionsLast60Seconds);



    @Scheduled(fixedRate = POLLING_INTERVAL_RATE_MILLIS)

    private void evictOldEntries() {

        while (!transactionsLast60Seconds.isEmpty() && !transactionsLast60Seconds.peek().isNewerThanTimeLimit()) {

            transactionsLast60Seconds.poll();

        }

        updateStatistics();

    }



    public void addTransaction(Transaction transaction) {

        transactionsLast60Seconds.add(transaction);

        updateStatistics();

    }



    private void updateStatistics() {

        statistics = new Statistics(transactionsLast60Seconds);

    }



}

TransactionService.java

package statistics.service;



import org.springframework.beans.factory.annotation.Autowired;

import org.springframework.stereotype.Service;



import statistics.model.Transaction;

import statistics.persistance.TransactionDao;



@Service

public class TransactionService {



    public static final int TIME_LIMIT = 60000;



    @Autowired

    private TransactionDao transactionDao;



    @Autowired

    private StatisticsService statisticsService;



    public void create(Transaction transaction) {

        transactionDao.save(transaction);

        statisticsService.addTransaction(transaction);

    }



}

Past.java

package statistics.validation;



import java.lang.annotation.Documented;

import java.lang.annotation.ElementType;

import java.lang.annotation.Retention;

import java.lang.annotation.Target;



import javax.validation.Constraint;

import javax.validation.Payload;



import static java.lang.annotation.RetentionPolicy.RUNTIME;



@Target({ElementType.FIELD, ElementType.METHOD, ElementType.PARAMETER, ElementType.ANNOTATION_TYPE})

@Retention(RUNTIME)

@Constraint(validatedBy = PastValidator.class)

@Documented

public @interface Past {



    String message() default "Must be in the past";



    Class<?> groups() default {};



    Class<? extends Payload> payload() default {};



}

PastValidator.java

package statistics.validation;



import javax.validation.ConstraintValidator;

import javax.validation.ConstraintValidatorContext;



import static java.lang.System.currentTimeMillis;



public class PastValidator implements ConstraintValidator<Past, Long> {



    @Override

    public void initialize(Past constraintAnnotation) {

    }



    @Override

    public boolean isValid(Long value, ConstraintValidatorContext context) {

        if (value == null) {

            return true;

        } else {

            return value < currentTimeMillis();

        }

    }



}

Gathering statistics

The DoubleSummaryStatisticsClass class will be a perfect replacement for your bespoke Statistics class, seeing how it has everything you need. That beats having to stream() multiple times.

Using more method references

You have demonstrated good usage of some method references already, but I can't help but feel you missed out one more, to use Comparator.comparing(Function):

// Comparator<Transaction> comparator = new TransactionTimestampComparator();

Comparator<Transaction> comparator = Comparator.comparing(Transaction::getTimestamp);

boolean logic

In PastValidator.isValid(Long, ConstraintValidatorContext), you can just short-circuit the return statement:

@Override

public boolean isValid(Long value, ConstraintValidatorContext context) {

    return value == null || value < currentTimeMillis();

}

Both endpoints have to execute in constant time and memory (O(1)). Include an in-memory DB.

You ignored all four complexity constraints.

Even if for some reason we needed to store queued transaction logs, choosing PriorityBlockingQueue (which can take arbitrarily long to access) over PriorityQueue would be an odd choice.

But there is no such requirement, so simple counters would suffice. You just need a currentCounter and recentCounters, plus a timer or a timestamp telling you when the "current" count will be downgraded to "recent". Protect with a lock so concurrent updates are non-interfering. If you fire a maintenance timer once a minute then you don't even have to worry about ageing them during web requests.

You wrote lots and lots of code to accomplish a simple task, and consumed lots and lots of memory to do it, much more than a pair of counters use. The data structure you chose couldn't possibly conform to the spec. since a PQueue access needs O(log n) time rather than O(1) constant time. Avoid complexity, do the simplest thing that could possibly work.