Hands On Session

problem_statement.md

Problem statement

Suppose, you have these input list of tuples (an ‘old’ one and a ‘new’ one):

_old = [
    ('A', 1, 2, 3),
    ('B', 1, 2, 3),
    ('D', 1, 2, 3),
    ('E', 1, 3, 3),
    ('F', 1, 2, 3),
    ('G', 1, 2, 3),
    ('H', 1, 3, 3)
]
_new = [
    ('B', 1, 2, 3),
    ('C', 1, 2, 3),
    ('D', 1, 2, 3),
    ('E', 1, 2, 3),
    ('G', 1, 2, 3),
    ('H', 1, 2, 3)
]

We want a simple algorithm, that compares the two lists of tuples by a given ‘key’ (in the current example, the key should be the first ‘column’ of each tuple) and prints out, whether a tuple is ‘new’, ‘deleted’, ‘identical’ or changed. The output of the algorithm should be like so:

_out = [
    ('deleted', ('A', 1, 2, 3)),
    ('identical', ('B', 1, 2, 3)),
    ('new', ('C', 1, 2, 3)),
    ('identical', ('D', 1, 2, 3)),
    ('changed', ('E', 1, 2, 3), ('E', 1, 3, 3)),
    ('deleted', ('F', 1, 2, 3)),
    ('identical', ('G', 1, 2, 3)),
    ('changed', ('H', 1, 2, 3), ('H', 1, 3, 3))
]
assert merge(_old, _new, 0) == _out
# no mutation ...
assert merge(_old, _new, 0) == _out

General Constraints/Questions

• How would you compute the time complexity of your algorithm?
• Can the algorithm be implemented to not have computataion time more than big O(n)?
• Demonstrate how such an algorithm can be added to a rest end point?