Katkat
Back

Implement common data-structure and JS tasks

SalesforceSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to design a time-aware data structure, manipulate linked structures, and demonstrate mastery over JavaScript's asynchronous execution model and functional programming patterns.

Part 1: Time-Travel Key-Value Store

Design a data structure TimeMap that supports set(key, value, timestamp) and get(key, timestamp). The get method should return the value associated with the largest timestamp less than or equal to the requested timestamp. If no such value exists, return null.

class TimeMap {
  set(key, value, timestamp) { /* implementation */ }
  get(key, timestamp) { /* implementation */ }
}

Part 2: Remove Duplicates from Linked List

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example: 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 becomes 1 -> 2 -> 5.

Part 3: Currying and Asynchronous Execution

  1. Write a function curry(fn) that transforms a function of n arguments into a sequence of n functions, each taking one argument.
  2. Implement a function promisePool(tasks, limit) that runs an array of task-returning functions concurrently, but ensures no more than limit tasks are running at once.

Constraints & Considerations

  • For Part 1, assume timestamps are strictly increasing for each specific key.
  • For Part 2, the linked list structure is standard: class ListNode { constructor(val, next = null) { this.val = val; this.next = next; } }.
  • For Part 3, ensure the promisePool returns an array of results in the order the tasks were provided.

Hints

Hint 1

For the TimeMap, use a hash map where values are arrays of [timestamp, value] pairs, and use binary search to find the correct timestamp.

Hint 2

For the linked list, use a dummy node pointing to the head to simplify cases where the head itself needs to be removed.

Hint 3

For the promise pool, maintain a counter of active tasks and use a queue or recursion to trigger the next task as soon as one completes.

Follow-up questions

  • How would you modify the TimeMap if the timestamps were not strictly increasing?
  • In the currying function, how would you handle cases where the original function expects a variable number of arguments (rest parameters)?
  • What are the memory trade-offs of the promise pool if the task list is extremely large?