Grammarly Software Engineer Onsite Coding Questions

LeetCode #56: Merge Intervals. Difficulty: Medium. Topics: Array, Sorting. Asked at Grammarly in the last 6 months.

LeetCode #1047: Remove All Adjacent Duplicates In String. Difficulty: Easy. Topics: String, Stack. Asked at Grammarly in the last 6 months.

LeetCode #966: Vowel Spellchecker. Difficulty: Medium. Topics: Array, Hash Table, String. Asked at Grammarly in the last 6 months.

LeetCode #380: Insert Delete GetRandom O(1). Difficulty: Medium. Topics: Array, Hash Table, Math, Design, Randomized. Asked at Grammarly in the last 6 months.

LeetCode #35: Search Insert Position. Difficulty: Easy. Topics: Array, Binary Search. Asked at Grammarly in the last 6 months.

LeetCode #359: Logger Rate Limiter. Difficulty: Easy. Topics: Hash Table, Design, Data Stream. Asked at Grammarly in the last 6 months.

LeetCode #404: Sum of Left Leaves. Difficulty: Easy. Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree. Asked at Grammarly in the last 6 months.

LeetCode #150: Evaluate Reverse Polish Notation. Difficulty: Medium. Topics: Array, Math, Stack. Asked at Grammarly in the last 6 months.

LeetCode #435: Non-overlapping Intervals. Difficulty: Medium. Topics: Array, Dynamic Programming, Greedy, Sorting. Asked at Grammarly in the last 6 months.

## Problem Merge or correct overlapping text edits or corrections in a document, handling conflicting spans of text changes. ## Likely LeetCode equivalent No direct unambiguous LC equivalent. ## Tags strings, sorting, intervals

## Problem Review the following Java code for a thread-safe counter. Identify all bugs, concurrency issues, and code quality problems. For each issue, explain the fix. ```java public class SharedCounter { private int count = 0; private List<Integer> history = new ArrayList<>(); public void increment() { count++; // (1) history.add(count); // (2) } public int getCount() { return count; // (3) } public List<Integer> getHistory() { return history; // (4) } public void reset() { count = 0; history.clear(); // (5) } } ``` **Issues to find:** - (1) Non-atomic read-modify-write on `count`. - (2) `ArrayList` is not thread-safe; concurrent adds cause data corruption. - (3) Stale read - no visibility guarantee without `volatile` or lock. - (4) Returning mutable reference leaks internal state. - (5) Non-atomic compound reset allows torn reads between `count=0` and `history.clear()`. ## Follow-ups 1. Rewrite using `AtomicInteger` and `CopyOnWriteArrayList`. What are the tradeoffs? 2. When would you use `synchronized` vs `ReentrantLock` vs `AtomicInteger`? 3. How would you write a unit test that reliably exposes the race condition in the original code? 4. Describe a scenario where `CopyOnWriteArrayList` performs poorly.

## Problem Implement a `Subject` class (observable) and a `Subscription` class (observer handle) following the observer pattern. Multiple observers can subscribe to a subject; each receives emitted values. Subscribers can unsubscribe at any time. ```python class Subscription: def unsubscribe(self): ... class Subject: def subscribe(self, on_next, on_error=None, on_complete=None) -> Subscription: ... def next(self, value): ... def error(self, err): ... def complete(self): ... ``` **Example:** ``` subj = Subject() values = [] sub = subj.subscribe(on_next=lambda v: values.append(v)) subj.next(1) subj.next(2) sub.unsubscribe() subj.next(3) # not received print(values) # [1, 2] ``` **Additional requirement:** After `complete()` or `error()` is called, subsequent `next()` calls are no-ops and new subscribers immediately receive the terminal event. ## Follow-ups 1. How would you add back-pressure support if the subscriber is slower than the producer? 2. Implement a `pipe(operator)` method that applies a transform (e.g., `map`, `filter`) to the subject's stream. 3. How does this pattern differ from Python's `asyncio` event streams? 4. How would you make `subscribe` and `next` thread-safe?