New Relic Backend Engineer Interview Experience — String Compression, Longest Increasing Path, and a Kafka Trace-Grouping Design

Question 1:

Implement a method that does basic string compression by counting consecutive repeated characters. If the compressed string is not shorter than the original string, return the original string.

1. Discuss time complexity and space complexity
2. Discuss edge cases
3. Discuss code optimization

Question 2:

Longest Increasing Path in a Matrix.

1. You can only move in four directions (up, down, left, right)
2. No diagonal moves
3. No going out of bounds (no wrap-around)
4. The interviewer asked me to use a DFS approach first, then optimize it and run the code

System Design

Design a distributed event processing system that consumes trace events from Kafka and groups all events belonging to the same trace together for processing.

Design premises and assumptions:

1. Events are received through Kafka
2. Every event contains a traceId
3. Events that belong to the same trace share the same traceId
4. A trace can last anywhere from a few seconds to a few hours
5. The specific processing logic doesn't matter; assume there is already a method that processes all of a trace's events together

Core discussion and follow-up questions:

1. How to group events by traceId
2. Whether an in-memory approach can scale
3. Using an external datastore to hold trace state
4. Memory constraints caused by long-running traces
5. How to determine that a trace has finished
6. How to retrieve the grouped events for downstream processing
7. Handling traces that may keep running for hours
8. Trade-offs between the different designs