# Stripe电面分享

Stripe家的经典电面题，database记录，论坛里最详细最全的，面试官说一共6步，楼主只做到了第4步。

``````/**
* # Step 1
* Throughout this interview, we'll pretend we're building a new analytical
* database. Don't worry about actually building a database though -- these will
* all be toy problems.
*
* Here's how the database works: all records are represented as maps, with string
* keys and integer values. The records are contained in an array, in no
* particular order.
*
* To begin with, the database will support just one function: min_by_key. This
* function scans the array of records and returns the record that has the minimum
* value for a specified key. Records that do not contain the specified key are
* considered to have value 0 for the key. Note that keys may map to negative values!
*
* Here's an example use case: each of your records contains data about a school
* student. You can use min_by_key to answer questions such as "who is the youngest
* student?" and "who is the student with the lowest grade-point average?"
*
* Implementation notes:
* * You should handle an empty array of records in an idiomatic way in your
* language of choice.
* * If several records share the same minimum value for the chosen key, you
* may return any of them.
*
* ### Java function signature:
* ```
* public static Map<String, Integer> minByKey(String key, List<Map<String, Integer>> records);
* ```
*
* ### Examples (in Python):
* ```
* assert min_by_key("a", [{"a": 1, "b": 2}, {"a": 2}]) == {"a": 1, "b": 2}
* assert min_by_key("a", [{"a": 2}, {"a": 1, "b": 2}]) == {"a": 1, "b": 2}
* assert min_by_key("b", [{"a": 1, "b": 2}, {"a": 2}]) == {"a": 2}
* assert min_by_key("a", [{}]) == {}
* assert min_by_key("b", [{"a": -1}, {"b": -1}]) == {"b": -1}
* ```
*/
/**
* # Step 2
* Our next step in database development is to add a new function. We'll call this
* function first_by_key. It has much in common with min_by_key. first_by_key
* takes three arguments:
*
* 1. a string key
* 2. a string sort direction (which must be either "asc" or "desc")
* 3. an array of records, just as in min_by_key.
*
* If the sort direction is "asc", then we should return the minimum record,
* otherwise we should return the maximum record. As before, records without a
* value for the key should be treated as having value 0.
*
* Once you have a working solution, you should re-implement min_by_key in terms
* of first_by_key .
*
* ### Java function signature:
* ```
* public static Map<String, Integer> firstByKey(String key, String direction, List<Map<String, Integer>> records);
* ```
*
* ### Examples (in Python):
* ```
* assert first_by_key("a", "asc", [{"a": 1}]) == {"a": 1}
*
* assert first_by_key("a", "asc", [{"b": 1}, {"b": -2}, {"a": 10}]) in [{"b": 1}, {"b": -2}]
* assert first_by_key("a", "desc", [{"b": 1}, {"b": -2}, {"a": 10}]) == {"a": 10}
* assert first_by_key("b", "asc", [{"b": 1}, {"b": -2}, {"a": 10}]) == {"b": -2}
* assert first_by_key("b", "desc", [{"b": 1}, {"b": -2}, {"a": 10}]) == {"b": 1}
*
* assert first_by_key("a", "desc", [{}, {"a": 10, "b": -10}, {}, {"a": 3, "c": 3}]) == {"a": 10, "b": -10}
* ```
*/
/**
* # Step 3
* As we build increasingly rich orderings for our records, we'll find it useful
* to extract the comparison of records into a comparator. This is a function or
* object (depending on your language) which determines if a record is
* "less than", equal, or "greater than" another.
*
* In object-oriented languages, you should write a class whose constructor
* accepts two parameters: a string key and a string direction. The class should
* implement a method compare that takes as its parameters two records. This
* method should return -1 if the first record comes before the second record
* (according to key and direction), zero if neither record comes before the
* other, or 1 if the first record comes after the second.
*
* In functional languages, you should write a function which accepts two
* parameters: a string key and a string direction. The function should return
* a function that takes as its parameters two records. This function should return
* -1 if the first record comes before the second record (according to key and
* direction), zero if neither record comes before the other, or 1 if the first
* record comes after the second.
*
* You should then use your comparator in your implementation of first_by_key.
*
* ### Java skeleton class:
* ```-baidu 1point3acres
* class RecordComparator implements Comparator<Map<String, Integer>> {
* public RecordComparator(String key, String direction) {
* }
*
* public int compare(Map<String, Integer> left, Map<String, Integer> right) {
* return 0;
* }
* }
* ```
*
* ### Examples (in Python):
* ```
* cmp = Comparator("a", "asc")
* assert cmp.compare({"a": 1}, {"a": 2}) == -1
* assert cmp.compare({"a": 2}, {"a": 1}) == 1
* assert cmp.compare({"a": 1}, {"a": 1}) == 0
* ```
* # Step 4. check 1point3acres for more.
*
* Time to take this "first-by" functionality further, to sort by more than one
* key at a time.
*
* Consider an array of records like this one:
* ```
* [{"a": 1, "b": 1}, {"a": 1, "b": 2}, {"a": 2, "b": 1}, {"a": 2, "b": 2}]
* ```
*
* Using first_by_key with this array of records with key "a" might not give us as
* much control as we'd like over the result, since more than one record has the
* same value for "a" (similarly for "b"). More generally, we might say "order by
* the first key, in the first direction. Break ties according to the second key,
* in the second direction. Break remaining ties by the third key, in the third
* direction, and so on." Note that the sort direction for different keys need not
* be the same.
*
* We might represent this ordering with a list of pairs like
* ```
* [
* ("a", "asc"),
* ("b", "asc"),
* ("c", "desc"),
* ]
* ```
*
* We'll call this type of representation a sort_order.
*
* You'll need to write a function first_by_sort_order. It takes two arguments:
*
* * a sort_order
* * an array of records
*
* It returns the first record according to the given sort_order.
*
* (first_by_key) in terms of first_by_sort_order.
*
* Hint: can you construct a "sort order" comparator using your comparator from
* the previous step? How might constructing a sort order comparator be helpful?
*
* ### Java function signature:
* ```
* public static Map<String, Integer> firstBySortOrder(LinkedHashMap<String, String> sortOrder, List<Map<String,
Integer>> records);
* ```
*
* ### Examples (in Python):
* ```
* assert(
* first_by_sort_order(
* [("a", "desc")],
* [{"a": 5.0}, {"a": 6.0}],
* ) == {"a": 6.0}
* )
*
* assert(
* first_by_sort_order(
* [("b", "asc"), ("a", "asc")],
* [{"a": -5, "b": 10}, {"a": -4, "b": 9}],
* ) == {"a": -4, "b": 9}
* )
*
* assert(
* first_by_sort_order(
* [("b", "asc"), ("a", "asc")],
* [{"a": -5, "b": 10}, {"a": -4, "b": 10}],
* ) == {"a": -5, "b": 10}
* )
* ```
*/
``````

We are working with a simple database. Each row associates column names (strings) with integer values (for example: 5, 0, -3, and so on). Here’s a table with three rows:

`````` a   b   c   d
---------------
1   0   0   0
0   2   3   0
0   0   0   4
``````

We can choose to represent a database table in JSON as an array of objects. For example, the previous table could be written as:

[ {“a”: 1, “b”: 0, “c”: 0, “d”: 0},
{“a”: 0, “b”: 2, “c”: 3, “d”: 0},
{“a”: 0, “b”: 0, “c”: 0, “d”: 4} ]
(There is no need to use JSON in your solutions – the notation is just used to introduce and explain the problems.)

Write a function minByColumn that takes a database table (as above), along with a column, and returns the row that contains the minimum value for the given column. If a row doesn’t have any value for the column, your function should behave as though the value for that column was zero.

In addition to writing this function, you should use tests to demonstrate that it’s
correct, either via an existing testing system or one you create.

## Examples

table1 = [
{“a”: 1},
{“a”: 2},
{“a”: 3}
]
minByColumn(table1, “a”) # returns {“a”: 1}

table2 = [
{“a”: 1, “b”: 2},
{“a”: 3, “b”: 0},
]
minByColumn(table2, “b”) # returns {“a”: 3, “b”: 0}

table3 = [
{“a”: 1, “b”: -2},
{“a”: 3}
]
minByColumn(table3, “b”) # returns {“a”: 1, “b”: -2}

table4 = [
{“a”: 1, “b”: 2},
{“a”: 3}
]
minByColumn(table3, “b”) # returns {“a”: 3}