Oso work sample - implementing "Max"

instructions.md

Oso - Work Sample

The goal of this exercise is to show your problem solving ability within a system with specific constraints.

We are not looking for completeness or low-level details in this, but a thoughtful approach to the system. This exercise should (a) give you an idea of the types of problems we work on, and (b) provide a good conversation starter for us to discuss other aspects of the system design.

There are two main chunks of work: Implementing Max and Documenting Min.

Implement "Max"

The first exercise is to build a server that can compute the maximum of a list of values given only the length of the list and an external interface that can compare two indices of the list.

We don't expect the implementation to take more than two hours. You are welcome to spend more time on it if you choose, but we are primarily interested in using this as a basis for a discussion. Focus on making your design extensible. We will discuss how you want to improve the code and design live.

Why is this relevant?

This exercise is designed to replicate the same problem we faced when building the Polar language. We wanted the language to be able to operate over application data coming from any host language (e.g., Python, Java, JavaScript, etc).

This means that when Polar evaluates input it sometimes needs to defer to the host language for answers. However, the host language is also the one driving the evaluation of Polar. To simulate these conditions, we have provided an HTTP client with a similar interface.

Requirements

You may use any language for this task, and can make use of existing libraries where appropriate. We highly recommend that you make use of a web framework that you are already familiar with.

Things we care about:

• How easy it is to understand what the code does.
• The design of the system. In particular, your code should be sufficiently flexible to extend to new operations.

Things we don't care about:

• Implementing data structures.

The server must be exposed via an HTTP interface: a single / endpoint that accepts JSON-encoded POST requests and sends JSON back in response. The expected message format is described below.

Messages

All messages have a type field indicating the message type.

Client

The client sends the following types of messages:

• compute_max, which has a length field indicating the number of values in the list:

  {
      "type": "compute_max",
      "length": 2
  }

• comparison_result, which has a request_id provided by the server and an answer field that is the result of comparing left < right as provided in the server's compare message:

  {
    "type": "comparison_result",
    "request_id": 2,
    "answer": true
  }

Server

The server should respond with the following types of messages:

• compare, with a request_id (an identifier to track the result of the comparison) and left and right fields, which are the indices of the list that it wants to compare:

  {
    "type": "compare",
    "left": 0,
    "right": 1,
    "request_id": 7
  }

• done, which has a result field containing the index of the maximum value in the list:

  {
    "type": "done",
    "result": 2,
  }

Document "Min"

The second exercise is to write documentation explaining how to extend the server you built in the first exercise to support new operations. For example, imagine a coworker wants to add a "compute_min" operation that computes the minimum of a list of values given only the length of the list and the existing external interface for comparing two indices of the list.

This documentation should take no more than thirty minutes to write.

Why is this relevant?

On an increasingly distributed team, written communication is the bedrock of asynchronous collaboration. We do a lot of writing, from ideation and project planning to status updates to customer-facing documentation. This exercise is designed to mirror onboarding a coworker onto the Max Server project.

Requirements

You should write the documentation:

• as a guide walking through how to extend the server with a new operation, using "compute_min" as an example;
• in a separate file (use Markdown, plain text, or whatever you'd like);
• with a technical audience in mind;
• such that a coworker with no prior context on the subject could read the doc and implement the new operation.

Things we care about:

• Clarity.
• Brevity.
• Communicating the high-level design of the server. Focus on how the pieces fit together rather than the minutiae of the code.
• Calling out any quirky or difficult parts of the code that you think might trip up your coworker.

Things we don't care about:

• Spelling/grammar mistakes. We care way more about the content than whether the prose is perfect.
• Testing the code samples. This part of the exercise is about communication.

max_client.py

import argparse
import requests
from dataclasses import asdict, dataclass


@dataclass
class Compare:
    request_id: int
    left: int
    right: int
    type: str = "compare"

@dataclass
class ComparisonResult:
    request_id: int
    answer: bool
    type: str = "comparison_result"

@dataclass
class ComputeMax:
    length: int
    type: str = "compute_max"

@dataclass
class Done:
    result: int
    type: str = "done"

def message_to_struct(message):
    if message["type"] == "compare":
        return Compare(**message)
    elif message["type"] == "comparison_result":
        return ComparisonResult(**message)
    elif message["type"] == "compute_max":
        return ComputeMax(**message)
    elif message["type"] == "done":
        return Done(**message)

class Client:
    def __init__(self, address, log=False):
        self.address = address if address else "http://localhost:5000"
        self.log = log

    def send(self, data):
        response = requests.post(self.address, json=asdict(data))
        json = response.json()
        if self.log:
            print(json)
        return message_to_struct(json)

    def compute(self, values, op):
        req = None
        if op == "max":
            req = ComputeMax(len(values))
        else:
            assert False, "not supported operation: " + op
        next_message = self.send(req)

        while True:
            if next_message.type == "done":
                return values[next_message.result]
            elif next_message.type == "compare":
                request_id = next_message.request_id
                left = next_message.left
                right = next_message.right
                next_message = self.send(ComparisonResult(request_id, values[left] < values[right]))
            else:
                raise Exception("Unexpected message: ", next_message)


if __name__ == "__main__":
    parser = argparse.ArgumentParser(description='Run the max computer')
    parser.add_argument('--address', type=str, required=False,
                        help='address of the max computer (defaults to http://localhost:5000)')

    args = parser.parse_args()
    client = Client(args.address, log=True)
    assert 31 == client.compute([10, 25, 31, 10], op="max")