5
\$\begingroup\$

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();
        }
    }

}
\$\endgroup\$
4
\$\begingroup\$

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();
}
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Can you please explain more about how to use counters? \$\endgroup\$ – Waleed Abdalmajeed Nov 19 '18 at 9:37
  • \$\begingroup\$ Choose a granularity, a measurement epoch size, e.g. 1000ms. Then you'd allocate N=61 integer counters: cnt[]. For current time T, truncated down to integer seconds, compute index I = T mod N. Then cnt[I] is current counter which POST increments and which GET ignores since it's a partial count for a 1-second epoch that has not yet finished. The GET completes in constant time by adding sixty integers. Take care to zero the minute-old slot as time goes by and I advances to point at subsequent slot. \$\endgroup\$ – J_H Nov 19 '18 at 18: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.