bigO2018Nov20.md

https://gist.github.com/johntran - > bigO2018Nov20.md

Algorithm & System Design 2018 11 20

Problem Set

Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true
Example 2:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

function searchMatrix(matrix, target) {
 // fill me
}

Object-Oriented Design: Deck of Cards

Vague, high-level problem statement, as delivered in an interview: Design/Model a deck of cards

Start with a simplified standard deck of cards. Such a deck has 4 suits (Diamond, Spade, Club, Heart) and 13 cards of each suite (1 to 13 or ace, 2 , 3, ... jack, queen, king). Now design a library which can be used by a 3rd party developer, to design a simple card game like Blackjack.

Deliverables:

1. A set of classes, showing relationships with each other where appropriate. Classes should show state and methods. Use any convenient notation.
2. Main() method, showing how you'll initialize your system and use it.
3. (Optional, only if it helps understanding): A flow chart of main use-cases and state-diagram.

Possible questions after implementation:

1. What assumptions are you making and how will your design change if those assumptions change?
2. If you provide this library as a service, how will you scale it?