Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've taken a coding challenge as part of a job interview and the recruiting process. Sadly I didn't get through it and couldn't secure the job. I am wondering if anyone can help me out here and show me how it could've been done better.

The problem described by interviewer was:

The purpose of the class is to register aliases for a value. For example 'Dave, Davey and Davy are aliases for David" I'm looking for working tests and some thought around edge cases, usability (i.e. what that api would be like to use), and a reasonably efficient implementation (does not need to be extremely high performance). Thread safety is optional.

Provided skeleton:

public class Aliases {

    public Aliases addAliases(String value, String... aliases) {
            throw new UnsupportedOperationException();
        }

        public String lookup(String name) {
            throw new UnsupportedOperationException();
        }

    }




public class AliasesTest {

    private final Aliases nameAliases = new Aliases()
            .addAliases("david", "dave", "davey", "davie", "davy")
            .addAliases("thomas", "tom", "tommy")
            .addAliases("michael", "mike", "micky")
            .addAliases("elizabeth", "liz", "beth", "lizzie", "bettie", "lizbeth");

    @Test
    public void canLookupExactMatches() {
        assertEquals("elizabeth", nameAliases.lookup("liz"));
        assertEquals("david", nameAliases.lookup("davy"));
        assertEquals("michael", nameAliases.lookup("michael"));
    }

    @Test
    public void canLookupCaseInsensitiveMatches() {
        assertEquals("elizabeth", nameAliases.lookup("Liz"));
        assertEquals("david", nameAliases.lookup("DAVIE"));
        assertEquals("michael", nameAliases.lookup("Mike"));
    }


    /* Add more test methods as required, feel free to remove/rename these if you prefer different terminology */

    @Test
    public void cannotFindLookupForAlias() {
        // ....
    }


    @Test
    public void edgeCases() {
        // ....
    }


    @Test
    public void moreEdgeCases() {
        // ....
    }


    /* If you think the class would benefit from other convenience methods please add/test them */


    /* If anything is unclear please contact Dave W. */

}

Here is my solution:

import java.util.Collections;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;

public class Aliases {

    private Map<String, Set<String>> aliasesMap = Collections.synchronizedMap(new ConcurrentHashMap<>());

    //public Aliases addAliases(String value, String... aliases) {
    //changed due to better understability and to avoid mistakes
    public Aliases addAliases(String value, Set<String> aliases) {
        if (aliases.contains("") || aliases.contains(null)) {
            throw new IllegalArgumentException("Name set can't contain nulls");
        }
        aliasesMap.put(value, aliases);
        return this;
    }

    public String lookup(final String name) {
        if (null == name) {
            return null;
        }
        Set<String> keySet = aliasesMap.keySet();
        if (setContainsString(keySet, name)) {
            return name;
        }

        for (Map.Entry<String, Set<String>> entry : aliasesMap.entrySet()) {
            Set<String> set = entry.getValue();
            if (setContainsString(set, name)) {
                return entry.getKey();
            }
        }
        return null;
    }

    private static boolean setContainsString(Set<String> set, String str) {
        return set.stream().map(String::toUpperCase).anyMatch(str.toUpperCase()::equals);
    }
}


public class AliasesTest {

    private Aliases nameAliases = new Aliases()
            .addAliases("david", new HashSet<>(Arrays.asList("dave", "davey", "davie", "davy")))
            .addAliases("thomas", new HashSet<>(Arrays.asList("tom", "tommy")))
            .addAliases("michael", new HashSet<>(Arrays.asList("mike", "micky")))
            .addAliases("elizabeth", new HashSet<>(Arrays.asList("liz", "beth", "lizzie", "bettie", "lizbeth")));

    @Test
    public void canLookupExactMatches() {
        assertEquals("elizabeth", nameAliases.lookup("liz"));
        assertEquals("david", nameAliases.lookup("davy"));
        assertEquals("michael", nameAliases.lookup("michael"));
    }

    @Test
    public void canLookupCaseInsensitiveMatches() {
        assertEquals("elizabeth", nameAliases.lookup("Liz"));
        assertEquals("david", nameAliases.lookup("DAVIE"));
        assertEquals("michael", nameAliases.lookup("Mike"));
    }

    @Test
    public void cannotFindLookupForAlias() {
        assertNull(nameAliases.lookup("123"));
        assertNull(nameAliases.lookup("BOO"));
        assertNull(nameAliases.lookup("Foo"));
    }

    @Test
    public void edgeCases() {
        assertNull(nameAliases.lookup(null));
        assertNull(nameAliases.lookup(""));
    }

    @Test(expected = IllegalArgumentException.class)
    public void addNullAliasesTest() {
        new Aliases().addAliases("david", new HashSet<>(Arrays.asList("dave", null)));
    }

    @Test(expected = IllegalArgumentException.class)
    public void addEmptyAliasesTest() {
        new Aliases().addAliases("david", new HashSet<>(Arrays.asList("dave", "")));
    }

}

The feedback I got from the interviewer:

  • Code looks up values by walking the entire data-structure looking for a match (major)
  • Usage of concurrent map structure but not it’s methods, therefore adds little/nothing (major)
  • Unclear what would happen if more aliases were registered to a value (minor)
  • Each walk also performs the lowercasing on each item every time (why not store lowercased) (major)
  • addAliases rejects nulls in the alias list but accepts nulls as a value (medium)
  • change of api from varargs to set seems simply to make it easier for the given implementation, not necessarily the api (minor)
  • failed to test giving nulls as values (major)
share|improve this question
1  
Did you understand the feedback provided ? Do you have question about it ? Are you looking for more feedback ? – Marc-Andre Feb 23 at 20:26
    
@Marc-Andre I guess I'm a bit lost with the feedback and wondering if more clarity can be provided. – Mantichora Feb 23 at 20:28
    
Your code edit was rolled back. Please see What should I do when someone answers my question? – Phrancis Feb 23 at 22:04
up vote 5 down vote accepted

The first point in the feedback was

Code looks up values by walking the entire data-structure looking for a match (major).

If you turn your logic around you can fix this easily. The requirement is basically for a mapping alias => name. How about using the aliases as keys and the full name as the value? The code below also deals with another major feedback point also, storing the names in lower case, not doing the conversion on every lookup.

import java.util.Objects;
import java.util.Map;
import java.util.HashMap;

public class Aliases {

    public Aliases addAliases(String value, String... aliases) {
        for (String alias : aliases) {
            this.aliases.put(alias.toLowerCase(), value);
        }
        this.aliases.put(value, value);
        return this;
    }

    public String lookup(String name) {
        Objects.requireNonNull(name, "Name must not be null");
        return aliases.get(name.toLowerCase());
    }

    public static void main(String[] args) {
        final Aliases nameAliases = new Aliases()
            .addAliases("David", "dave", "davey", "davie", "davy")
            .addAliases("Thomas", "tom", "tommy")
            .addAliases("Michael", "mike", "micky")
            .addAliases("Elizabeth", "liz", "beth", "lizzie", "bettie", "lizbeth");

        String alias = "Liz";
        System.out.printf("%s is an alias for %s%n", alias, nameAliases.lookup(alias));

        alias = "dave";
        System.out.printf("%s is an alias for %s%n", alias, nameAliases.lookup(alias));
    }

    // PRIVATE //
    private Map<String, String> aliases = new HashMap<>();
}
share|improve this answer
    
If the interview question provides the assumption that there's a 1-1 mapping of an alias to a full name, this is a good approach. Just need to be thorough with such edge cases. ;) – h.j.k. Feb 24 at 3:25

Using the right methods

Usage of concurrent map structure but not it’s methods, therefore adds little/nothing (major)

Pre-Java 8, ConcurrentHashMap only offers a handful of extra methods, more notably putIfAbsent() such that sometimes you may see it in use solely for that, in a single-threaded context.

Now that you're on Java 8...

ConcurrentHashMaps support a set of sequential and parallel bulk operations that, unlike most Stream methods, are designed to be safely, and often sensibly, applied even with maps that are being concurrently updated by other threads; for example, when computing a snapshot summary of the values in a shared registry. There are three kinds of operation, each with four forms, accepting functions with Keys, Values, Entries, and (Key, Value) arguments and/or return values. Because the elements of a ConcurrentHashMap are not ordered in any particular way, and may be processed in different orders in different parallel executions, the correctness of supplied functions should not depend on any ordering, or on any other objects or values that may transiently change while computation is in progress; and except for forEach actions, should ideally be side-effect-free. Bulk operations on Map.Entry objects do not support method setValue.

  • forEach: Perform a given action on each element. A variant form applies a given transformation on each element before performing the action.
  • search: Return the first available non-null result of applying a given function on each element; skipping further search when a result is found.
  • reduce: Accumulate each element. The supplied reduction function cannot rely on ordering (more formally, it should be both associative and commutative). There are five variants:
    • Plain reductions. (There is not a form of this method for (key, value) function arguments since there is no corresponding return type.)
    • Mapped reductions that accumulate the results of a given function applied to each element.
    • Reductions to scalar doubles, longs, and ints, using a given basis value.

(emphasis mine)

In other words, don't short-change yourself. :p

public String lookup(String nameOrAlias) {
    if (nameOrAlias == null || nameOrAlias.isEmpty()) {
        return null;
    }
    // aliasesMap renamed as aliases,
    // and obviously typed as ConcurrentHashMap, instead of Map
    return aliases.search(1, (k, v) -> Stream.concat(Stream.of(k), v.stream())
                    .anyMatch(nameOrAlias::equalsIgnoreCase) ? k : null);
}
  1. If nameOrAlias is invalid, return null.
  2. Stream on our key and values by concat()-enating them and test if anyMatch()-es the predicate nameOrAlias::equalsIgnoreCase.
  3. If so, we return the key aka name, else we return null as specified by the method's Javadoc.

Case-sensitiveness

Each walk also performs the lowercasing on each item every time (why not store lowercased) (major)

If I were you, my answer will be that it is entirely plausible we want to preserve the case of aliases while performing case-insensitive searches. That's not to say your approach can't be improved: in fact, that's what String.equalsIgnoreCase(String) is for, as demonstrated in the above section.

APIs

change of api from varargs to set seems simply to make it easier for the given implementation, not necessarily the api (minor)

I'm not sure why this is labelled as a minor point, as changing public APIs (which I presume from your 'provided skeleton') should not be done liberally.

Sticking with addAliases(String value, String... aliases), you do need to check for:

  • value is null or "" (is trimming required too?)
  • aliases is null (i.e. (String[]) null)
  • aliases is empty (ignore value completely, or map value -> value?)
  • any of aliases is null (e.g. "a", null, "b")
  • any of aliases is "" (is trimming required too?)

These are the edge cases that should go in your tests. :)

On a related note, there are two approaches for adding aliases. One, convert String... into a Set and do a normal aliases.put(value, set) within the method. Two, derive a Map<String, Set<String>> from the arguments and you can use aliases.putAll(map). While the second approach may seem more complex, it's more 'portable' in the sense that one can also choose to apply a search on the resulting Map too (albeit not using ConcurrentHashMap.searchEntries()).

Intended functionality

Unclear what would happen if more aliases were registered to a value (minor)

Hint: Map.computeIfAbsent() is a feasible approach for combining a new Set of aliases into the existing Set inside the aliases map.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.