Simon Green

Posted on

# Special Accounts

## Task 1: Special Bit Characters

You are given an array of binary bits that ends with 0.

Valid sequences in the bit string are:

``````[0] -decodes-to-> "a"
[1, 0] -> "b"
[1, 1] -> "c"
``````

Write a script to print `1` if the last character is an “a” otherwise print `0`.

### My solution

The first observation to make is that a list of bits can only be converted into a single sequence. So I can save a recursive function for a rainy day :)

I create a variable called `last_a` to determine if the last character we found is an `a`. I then go through the supplied list, and remove the first item. If it is a `0`, I set `last_a` to True. If it is a `1`, I set `last_a` to False, and remove the next first item since that will make it a `b` or `c`.

After the list is exhausted, I print `1` if `last_a` is True, or `0` if it is not.

### Examples

``````\$ ./ch-1.py 1 0 0
1

\$ ./ch-1.py 1 1 1 0
0
``````

You are given an array of accounts i.e. name with list of email addresses.

Write a script to merge the accounts where possible. The accounts can only be merged if they have at least one email address in common.

### My solution

This proved trickier than I thought it would be. Or maybe I just didn't think of the best solution. For the input, I take a JSON string, and turn it into a list (arrayref in Perl).

The next step is to create a dict (hash in Perl) called `groups` where the key is the account and the value is a list of sets (array of arrayrefs in Perl) with the addresses in it.

I then create a list called `results` that are going to have the final rows in it. I iterate over the `groups` dict (sorted by the key), and call the `groups_list` function providing the key (account) and values (the lists of e-mail address sets). It returns the rows to add to the `results` list. So far so good, pretty straight forward.

The `groups_list` function works like a stack. I loop until the stack is empty. For each loop, I take the first set of e-mail addresses from the top of the stack. I then compare the remaining items in the stack (if any) to see if they have a common address. If they do, I remove that set from the stack, and add a new value at the top of the stack with the combined set of e-mail addresses. If there is no match, I create an row in the `rows` list, and continue to the next item in the stack.

I chose to use sets rather than a list, because `set1 & set2` is true if there are common items. Additionally `set1 | set2` will produce a new set of all items with no duplicates. For the Perl peeps, a set is like a hash with no values. For the Perl solution, I use Array::Utils intersect and unique functions to provide equivalent features.

Finally, I print the items in the result list as a pretty JSON array.

### Examples

``````\$ ./ch-2.py '[ ["A", "a1@a.com", "a2@a.com"], ["B", "b1@b.com"], ["A", "a3@a.com", "a1@a.com"] ]'
[
[
"A",
"a1@a.com",
"a2@a.com",
"a3@a.com"
],
[
"B",
"b1@b.com"
]
]

\$ ./ch-2.py '[ ["A", "a1@a.com", "a2@a.com"],  ["B", "b1@b.com"], ["A", "a3@a.com"], ["B", "b2@b.com", "b1@b.com"] ]'
[
[
"A",
"a2@a.com",
"a1@a.com"
],
[
"A",
"a3@a.com"
],
[
"B",
"b1@b.com",
"b2@b.com"
]
]
``````