BACKGROUND
A Java java.util.Map or a C++ std::map consist of pairs of keys (unique) and
values (not necessarily unique) that are associated with those keys.
Operations are provided that can add a new key/value pair to the map, update
the value associated with an existing key, or remove a key and the value
associated with it.
When building a distributed application, it is often desirable to maintain
identical copies of a map at both ends of a slow connection. If a change is
made to the map, it may be much more efficient to just transmit a list of
deltas (records that describe an operation that transforms the old map into the
new) instead of transmitting an entire copy of the map. For example, if the
key/value pair ("A","123") is added to a map that contains 100 entries, sending
only the delta "add A=123" might require almost two orders of magnitude less
network traffic than resending the entire map.
PROBLEM STATEMENT
You are to create a class MapDelta that contains the method compute. The
method should take a String[] that corresponds to a series of deltas (to be
applied in order by increasing index), and it should return a String[] that
corresponds to the minimal series of deltas that would accomplish the same
effect.
There will be three types of deltas: addition, update, and removal,
representing respectively adding a key/value pair to the map, updating the
value associated with an existing key, and removing an existing key and the
value associated with it. Both keys and values will be strings of length 1 to
10 (inclusive) made up of upper and lower case letters and numeric digits (A-Z,
a-z, and 0-9 inclusive). The three forms are:
"add KEY=VALUE"
"update KEY=VALUE"
"remove KEY"
Each of the three forms contains exactly one space and exactly one equals sign.
TopCoder will verify that all input is properly formed and that there are no
inconsistent deltas (duplicate removals, update of keys that have been removed
but not re-added, adding of keys that must already be present).
The deltas returned from your method should have the same form as the input
data, with the additional constraint that deltas should be returned in order
sorted by key (lexicographical sorting with the smallest first).
All comparisons are case-sensitive ("A" is less than "a").
DEFINITION
Class name: MapDelta
Method name: compute
Parameters: String[]
Returns: String[]
Here is the method signature (be sure your method is public): String[]
compute(String[] deltas)
INPUT CONSTRAINTS
TopCoder will ensure that the input is a valid list of deltas. A delta list is
valid if all of the following are true:
- The list contains between 0 and 50 (inclusive) deltas.
- Each delta is exactly of the form "add KEY=VALUE", "update KEY=VALUE", or
"remove KEY" (each delta contains exactly one space character).
- Each KEY and VALUE consists of between 1 and 10 (inclusive) characters from
the set comprising lower case letters (a-z, inclusive), upper case letters
(A-Z, inclusive), and numeric digits (0-9, inclusive).
- For a particular key K, if the delta "remove K" is present in the delta list,
the next delta, if any, to reference K must be "add K".
- For a particular key K and value V, if the delta "add K=V" is present in the
delta list, the next delta, if any, to reference K must not be an add delta.
- For a particular key K and value V, if the delta "update K=V" is present in
the delta list, the next delta, if any, to reference K must not be an add delta.
NOTE
The map may already be populated, so it is possible for the first delta to be
of type "update".
EXAMPLES
If the list of deltas is {"add X=1", "update Y=2", "update X=11", "remove Y"},
we can replace the add and the update of X with a single "add X=11", and we can
discard the update of Y because it is removed later in the list. Sorting the
return values by key gives us the return value of {"add X=11", "remove Y"}.
{"add X=1", "remove Y", "remove X", "add Y=10"} returns {"update Y=10"}.
{"update x=abc", "update x0=def"} returns {"update x=abc", "update x0=def"}.
{"update revision=247", "update revision=249"} returns {"update revision=249"}.
{"add temp=XX", "remove temp"} returns {}.
{} returns {}.