Coding test from heck

[chhotii]

Coding test from heck

Recall that I had an on-line assessment for a job application, and on the second coding challenge, I derailed because for the first test case, the expected output was wrong.

Here's the question, as best I recall:

N alumni have been invited to an alumni dinner. Each alumnus is assigned a numerical ID and they are numbered starting from 1. Each alumnus likes exactly one other alumnus (although each alumnus may be liked by zero, one, or more than one other alumnus). You are given an array which gives the ID of the alumnus liked by each alumnus: for example, the array 2, 1 means that alumnus #1 likes alumnus #2 and alumnus #2 likes alumnus #1. Each alumnus will only come to the dinner if they may be seated next to the alumnus that they like. (They won't like the alumnus on their other side but that's OK.) The alumni will be seated at a circular table. Print, as a string, the seating arrangement that includes the largest number of alumni. If there's more than one such possible string, print the string that would be ordered first in lexicographical order.

In the input you are given N on the first line, and the array (space-separated) on the second line.
For example:
Input:
4
2 3 4 1

Output:
1234

Note that this works because the table is round. Alum #4 likes alum #1; they are next to each other because the first and last are adjacent.

My thoughts and solutions (plural!) and commentary below cut. Before you peek, try giving this a whack; I'm curious as to how other people find this problem.


My first thought when I read this problem was to look at it just as a simple problem of finding a circuit in a directed graph. Choose a node, follow the directed vertex to the next node, repeat until you either find yourself back where you started (in which case you've found a circuit) or until things go horribly wrong (in which case the node that you started with can't be a part of a circuit). Slight complications: Obviously there will be many ways of writing the same circuit. 123, 231, and 312 are all equivalent. Solve that problem by choosing the nodes to start from in numeric order; so, 123 is generated before 231; so, displace a circuit that has been found only in the case that a longer one is found (I.e, after finding 123, we go on and find 4567, the solution 4567 will will out because it's longer). Also, reversing the order also makes for a valid table arrangement. If 123 satisfies the constraints, so will 321. (Each alum likes the person to their left, versus each alum likes the person to their right.) So, reverse the order of each solution found and compare those solutions as well.

Afterwards I realized that you could have a solution that's not a circuit. Consider this scenario: #1 and #2 like each other; #3 and #4 like each other; #5 and #6 like each other. Any ordering in which members of the pairs are adjacent is valid: 123456, or 436512, etc. If we have circuits of size 2, all those circuits can just be concatenated, in any order and with any ordering within themselves. Any circuit of larger than size 2 can't be concatenated with other circuits. So, which is longer, the longest circuit, or the concatenation of all the length-2 circuits? Oh, and it gets worse: Since we are representing these circular table arrangements as strings, one can have a pair of buddies as the first and last elements in the string, and that could be the lexicographically first solution.

The product of thinking through all these possibilities in the circuit-finding mindset is FasterSolver. It's called FasterSolver because as I was thinking of all these possibilities and complications, I decided I needed an authoritative reference algorithm that was sure to produce the right answer brute-force, at the cost of being rather inefficient. SlowSolver generates all the combinations of size r, where r starts off as N and decrements; and, for each combination, each permutation of its ordering. Each permutation is examined whether it's a valid table arrangement that satisfies the constraints. Since it's generating permutations, it has the dreaded O(n!) complexity. In spite of being O(n!), SlowSolver could've been a passing response to the coding challenge, maybe; I didn't take note of how big N could be, and I don't know whether programs would fail if they run too slowly (as is sometimes the case on HackerRank). SlowSolver can easily take way too long on input of size 9. Way, way too long. Way, way, way... Factorial complexity: fun! They did say to favor a working and correct solution over an efficient solution, but something that doesn't run in the time allotted can't possibly be okay. SlowSolver is useful for validating the clever solutions for small test cases, though.

After getting FasterSolver working for all the various complications I realized that going at it by always only following the vertices of the graph in the direction that they point is what leads to all these complications down the road. Who should we put to the left of #1: #3, whom they like, or #7, who likes them? Why don't we consider both? Just keep recursively adding various options to the leading edge of the table-- but rather than explore every damn possibility, which is so, so, so slow, add only those persons who satisfy the constraint. You can sit down next to someone if they like you; or, if they are already sitting next to someone they like. This handles both directions, and both a table consisting of one circuit and a table consisting of a bunch of pairs. Since the recursive algorithm can explore the options in lexicographic order, it can find the lexicographically first solution first. Since the recursive algorithm can consider lengthening before it considers the validity of the current string, it can find the longer solutions before the shorter solutions. Thus the search can terminate with the first solution found, which will be the longest and lexicographically first. This train of thought lead to CuteRecurviseSolver, really the most elegant of the bunch. There's a bit of special case where if you're the second person to sit, and the first person doesn't like you, that might be okay because they might like the last person to sit; so, when considering a potential solution, test whether the ends knit together. That's the only part that looks a bit messy.

package org.notthesoccerstar;

import java.util.*;

public class Main {

    public static void main(String[] args) {
        boolean debugMode = true;
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        if (n > 9) {
            throw new Error("n is too big");
        }
        ArrayList<Integer> inputData = new ArrayList<Integer>();
        for (int i = 0; i < n; ++i) {
            int alum = scan.nextInt();
            if (alum < 1 || alum > n) {
                throw new Error("Invalid like");
            }
            inputData.add(alum);
        }
        if (debugMode) {
            showInputData(n, inputData);
        }
        ArrayList<Solver> solvers = new ArrayList<Solver>();
        solvers.add(new SlowSolver(n, inputData));
        solvers.add(new FasterSolver(n, inputData));
        solvers.add(new CuteRecursiveSolver(n, inputData));
        System.out.format("SlowSolver got answer: %s\n", solvers.get(0).getSolution());
        for (int i = 1; i < solvers.size(); ++i) {
            Solver other = solvers.get(i);
            if (!solvers.get(0).getSolution().equals(other.getSolution())) {
                System.out.format("%s got different answer: %s\n", other.getClass().getName(), other.getSolution() );
            }
        }
    }

    // You're not actually supposed to print this. Just as an aid to thinking about a
    // problem during development.
    private static void showInputData(int n, ArrayList<Integer> inputData) {
        for (int i = 0; i < n; ++i) {
            System.out.format("Alumnus %d likes alumnus %d\n", i+1, inputData.get(i));
        }
    }

    private abstract static class Solver {
        int n; // number of alumni
        List<Integer> likeTable; // for each alum, who does that alum like? (ID's count from 1)
        String solution;  // null if we haven't calculated it yet
        public Solver(int n, ArrayList<Integer> inputData) {
            this.n = n;
            likeTable = inputData;
        }
        public String getSolution() {
            if (solution == null) {
                solve();
            }
            return solution;
        }

        protected abstract void solve();

    }

    private static class SlowSolver extends Solver {

        public SlowSolver(int n, ArrayList<Integer> inputData) {
            super(n, inputData);
        }

        /*
            The slooow approach is to generate all possible solutions, filter that set for which solutions
            are valid (satisfying the problem constraints), and then choosing the most favored.
            We are to favor the longest possible solution. So, first generate all solutions of length n, then
            n-1, etc., down to 2, until finding something that works. (I do not think that a table of one
            satisfies the requirements.)
            Generating all the solutions of a given length requires finding all the subsets of that size,
            and for each subset, finding all the permutations. Finding all the permutations is O(n!), so
            be afraid of how long this will take to run. Very, very afraid.
         */
        @Override
        protected void solve() {
            int numberOfAlumToInclude = n;
            while (solution == null && numberOfAlumToInclude > 1) {
                ArrayList<String> candidates = new ArrayList<String>();
                // find all the subsets of size r
                ArrayList<String> combinations = getCombinations(numberOfAlumToInclude);
                for (String c : combinations) {
                    // find all the permutations (orderings) of this combination
                    List<String> permutations = getPermutations(c);
                    for (String p : permutations) {
                        if (satisfiesConstraints(p)) {
                            candidates.add(p);
                        }
                    }
                }
                // I think these are invariably generated in lexigraphic order? But rather than taking the
                // time to prove this right now, I'll just throw in a sort. (Fix for production!!!)
                Collections.sort(candidates);
                solution = candidates.get(0);
                --numberOfAlumToInclude;
            }
            if (solution == null) {
                solution = "none";
            }
        }

        protected boolean satisfiesConstraints(String p) {
            // recall that it's a circular table
            String test = p + p.charAt(0); // so that alum at position 0 appears after last alum
            test = "" + p.charAt(p.length()-1) + test; // so that last alum appears before first alumn
            for (int i = 1; i <= p.length(); ++i) {  // test all the seats in test except first and last
                if (likes(test.charAt(i), test.charAt(i-1))) {
                    // alum likes the person to their left; ok
                    continue;
                }
                if (likes(test.charAt(i), test.charAt(i+1))) {
                    // alum likes the person to their right; ok
                    continue;
                }
                // If we got here then someone didn't like either the person to thier left or right. Invalid!
                return false;
            }
            return true;
        }

        private boolean likes(char liker, char likee) {
            int likerID = liker - '0';
            int likeeID = likee - '0';
            return (likeTable.get(likerID - 1) == likeeID);
        }

        private List<String> getPermutations(String c) {
            ArrayList<String> perms = new ArrayList<String>();
            perms.add("");
            for (int i = 0; i < c.length(); ++i) {
                ArrayList<String> longerPerms = new ArrayList<String>();
                for (String p : perms) {
                    for (int j = 0; j < c.length(); ++j) {
                        if (p.indexOf(c.charAt(j)) == -1) {
                            longerPerms.add(p + c.charAt(j));
                        }
                    }
                }
                perms = longerPerms;
            }
            return perms;
        }

        private ArrayList<String> combinations;

        private ArrayList<String> getCombinations(int numberOfAlumToInclude) {
            combinations = new ArrayList<String>(); // collection of all combinations of this size
            combinationRecurse("", 0, numberOfAlumToInclude);
            return combinations;
        }

        private void combinationRecurse(String data, int start, int r) {
            if (data.length() == r) {
                combinations.add(data);
                return;
            }
            for (int i = start; ((i < n) && (n-i+1 >= r-data.length())); ++i) {
                String newData = data + String.format("%d", i+1);
                combinationRecurse(newData, i+1, r);
            }
        }

    }

    private static class FasterSolver  extends Solver {
        public FasterSolver(int n, ArrayList<Integer> inputData) {
            super(n, inputData);
        }

        @Override
        protected void solve() {
            ArrayList<Integer> longestCircuit = new ArrayList<Integer>(); // zero-length circuit
            ArrayList<ArrayList<Integer>> length2Circuits = new ArrayList<ArrayList<Integer>>();
            for (int start = 1; start <= n; ++start) {
                // If we start with alum whose ID is start, can we make a circuit?
                Set<Integer> chainedAlum = new HashSet<Integer>();
                ArrayList<Integer> circuit = new ArrayList<Integer>();
                int currentAlum = start;
                boolean done = false;
                while (!done) {
                    circuit.add(currentAlum);
                    chainedAlum.add(currentAlum);
                    // Whom does this person like?
                    int nextAlum = likeTable.get(currentAlum-1);
                    if (chainedAlum.contains(nextAlum)) {
                        done = true; // we are not going to keep growing the circuit
                        // likes someone already in the nascent circuit...
                        if (circuit.get(0).equals(nextAlum)) {
                            // and it's the start of the chain...
                            if (circuit.size() == 1) {
                                // Degenerate circuit: Alum likes themself. Discard.
                            }
                            else {
                                // We've found a circuit!
                                // If it's a circuit of length 2: we collect all of those.
                                if (circuit.size() == 2) {
                                    length2Circuits.add(circuit);
                                }
                                else {
                                    if (longestCircuit == null || longestCircuit.size() < circuit.size()) {
                                        longestCircuit = circuit;
                                    }
                                    else {
                                        // it's a circuit, but we've found a better circuit already, so, discard
                                    }
                                }
                            }
                        }
                        else {
                            // this points to an internal position in the chain...
                            // womp-womp, not a circuit; discard
                        }
                    }
                    else {
                        // Alum likes an alum who's not already in the nascent circuit; cool!
                        currentAlum = nextAlum; // queue up liked person for addition
                        // loop will continue after this
                    }
                } // END while growing (or trying to grow) circuit from given start position
            } // END for each possible start position
            boolean usingLongestCircuit;
            if (longestCircuit.size() > length2Circuits.size()) {
                // largest possible table consists of the longest circuit
                usingLongestCircuit = true;
            }
            else if (longestCircuit.size() < length2Circuits.size()) {
                // largest possible table consists of the pairs that like each other
                usingLongestCircuit = false;
            }
            else {
                // Can make an equally big table either way; which one is lexographically smaller?
                if (longestCircuit.get(0) < length2Circuits.get(0).get(0)) {
                    usingLongestCircuit = true;
                }
                else {
                    usingLongestCircuit = false;
                }
            }
            if (usingLongestCircuit) {
                // We started with the lowest-numbered alum in this circuit. But which way to go to
                // give the lexigraphically smaller output?
                if (longestCircuit.get(2) < longestCircuit.get(longestCircuit.size()-1)) {
                    solution = "";
                    for (int a : longestCircuit) {
                        solution = solution + String.format("%d", a);
                    }
                }
                else {
                    // go in reverse direction, but start from index 0 and loop around to end of list
                    solution = String.format("%d", longestCircuit.get(0));
                    for (int j = longestCircuit.size()-1; j > 0; --j) {
                        int a = longestCircuit.get(j);
                        solution = solution + String.format("%d", a);
                    }
                }
            }
            else {
                // Each length-2 circuit is represented twice in the collection. So, as we chain these
                // together, keep track of what we chain, so we can throw out duplicates.
                ArrayList<ArrayList<Integer>> prunedLength2Circuits = new ArrayList<ArrayList<Integer>>();
                for (ArrayList<Integer> circuit : length2Circuits) {
                    int buddy = circuit.get(1);
                    boolean found = false;
                    for (ArrayList<Integer> c : prunedLength2Circuits) {
                        if (buddy == c.get(0)) {
                            found = true;
                        }
                    }
                    if (!found) {
                        prunedLength2Circuits.add(circuit);
                    }
                }
                length2Circuits = prunedLength2Circuits;
                solution = "";
                // Do we first seat both members of the first pair? Or sandwich the whole rest of the ordering
                // between them?
                if (length2Circuits.get(0).get(1) < length2Circuits.get(1).get(0)) {
                    // Higher-numbered buddy in first pair is less than either member of second pair
                    for (ArrayList<Integer> circuit : length2Circuits) {
                        solution = solution + String.format("%d%d", circuit.get(0), circuit.get(1));
                    }
                }
                else {
                    // We will get a lexigraphically smaller result if we sandwich the other pairs between
                    // members of the first pair (table is actually round, so, that's ok)
                    solution = String.format("%d", length2Circuits.get(0).get(0));
                    for (int j = 1; j < length2Circuits.size(); ++j) {
                        ArrayList<Integer> circuit = length2Circuits.get(j);
                        solution = solution + String.format("%d%d", circuit.get(0), circuit.get(1));
                    }
                    solution = solution + String.format("%d", length2Circuits.get(0).get(1));
                }
            }
        } // END solve() method

    } // END FasterSolver class

    private static class CuteRecursiveSolver extends Solver {

        public CuteRecursiveSolver(int n, ArrayList<Integer> inputData) {
            super(n, inputData);
        }

        @Override
        protected void solve() {
            ArrayList<Integer> unchainedAlum = new ArrayList<Integer>();
            for (int i = 1; i <= n; ++i) {
                unchainedAlum.add(i);
            }
            ArrayList<Integer> chain = new ArrayList<Integer>();
            exploreSolutions(chain, unchainedAlum);
        }

        private void exploreSolutions(ArrayList<Integer> chain, ArrayList<Integer> unchainedAlum) {
            if (solution != null) {
                // bail as soon as we've found one solution
                return;
            }
            for (int a : unchainedAlum) {
                if (canAddToChain(chain, a)) {
                    ArrayList<Integer> newChain = (ArrayList<Integer>) chain.clone();
                    ArrayList<Integer> newUnchainedAlum = (ArrayList<Integer>) unchainedAlum.clone();
                    newChain.add(a);
                    newUnchainedAlum.remove(newUnchainedAlum.indexOf(a));
                    exploreSolutions(newChain, newUnchainedAlum);
                }
            } // END for each unchained alum
            // Is the chain we have so far a valid seating arrangement?
            if (chain.size() > 1) {
                // Check if the first and last alum are each sitting next to someone they like (which may wrap)
                int likedByFirst = likeTable.get(chain.get(0)-1);
                if (chain.get(1) == likedByFirst || chain.get(chain.size()-1) == likedByFirst) {
                    int likedByLast = likeTable.get(chain.get(chain.size()-1)-1);
                    if (chain.get(0) == likedByLast || chain.get(chain.size()-2) == likedByLast ) {
                        // It's a valid circular arrangement!
                        // Stringify it
                        solution = "";
                        for (Integer a : chain) {
                            solution += a.toString();
                        }
                    }
                }
            }
        }

        private boolean canAddToChain(ArrayList<Integer> chain, int a) {
            if (chain.size() == 0) {
                // Start the chain with anybody.
                return true;
            }
            if (chain.size() == 1) {
                // Maybe! Depends on what winds up being at the end of the chain.
                // Let's provisionally go in this direction, and be sure to check that the ID
                // at index 0 likes either the next one or the one at the end-- when we get there.
                return true;
            }
            int lastAlum = chain.get(chain.size()-1);
            if (likeTable.get(lastAlum-1) == a) {
                // Previous person likes me.
                return true;
            }
            int pentultimateAlum = chain.get(chain.size()-2);
            if (likeTable.get(lastAlum-1) == pentultimateAlum) {
                // Don't have to worry about whether the previous person likes me. They like the person
                // on their other side.
                return true;
            }
            return false;
        } // END canAddToChain()
    }

}

Comments

[totient]

Posting before expanding the cut.

First thought: this is a cyclic directed graph. Find the largest cycle has a recursive solution, an iterative solution, and a clever tail-recursion solution (I think I have talked about tail recursion here before but if not it's the kind of clever that is much more useful for interview questions than it is for real life, but you'll probably get points for mentioning it anyway. This took about a minute to conceptualize (I have a background in graph theory and also one in asking graph theory based interview questions) and would probably take about 10 minutes to code up, of which the parser would easily be half. The big error an interviewer is looking for is counting paths that lead into the cycle in the cycle length, and the solution there seems like it'd require auxiliary state but also there's a fun solution that doesn't.

Second thought: I wonder if they thought about the case of 2-person cycles, more than one of which can be seated at the round table. The number of alums in mutually affiliated pairs might exceed the size of the largest cycle, and also the entire path leading into a 2-cycle can be seated at a table with another 2-cycle or path-into-2-cycle. This took a couple of minutes to come up with, and another couple of minutes to realize that you can also include potentially two entry paths. That is, this dataset:

6
2 1 4 5 4 5

can be seated as: 1 2 3 4 5 6

Third thought: I wonder if this is given as string input rather than a function API so that an interviewer has a chance to be impressed by input validation. I know I would be.

[chhotii]

Tail recursion isn't a thing in Java. If you were interviewing with a team that uses Java, they probably wouldn't know what you're talking about.

It didn't occur to me during the test to consider 2-person cycles. I only thought of that later. I'll bet they didn't think about that! In further discussion with this company, I have some evidence that maybe they didn't think of that.

I don't think they were looking for input validation. People are, I think, commonly using something like HackerRank to practice for these types of questions, and the stupid thing about HackerRank is that they always explicitly stipulate that the input will be perfectly valid and well-formed and within specified ranges. I've done done dozens, maybe hundreds, of practice problems on HackerRank, and I've never seen a case in which any test case was invalid input. This is possibly the most deplorable thing about HackerRank: it fosters getting into the habit of always assuming that all input is perfect and doesn't need to be validated. I'm not doing input validation in my code above, not because I'm not aware of its importance in real code, but because a) it probably wouldn't have been required to "pass" the coding test and b) just getting straight to the interesting algorithmic questions.

[ceo]

Tail recursion is just a fancy name for making the recursive call after doing the work, which is what exploreSolutions() does.

Do you own notthesoccerstar.org? :-)

[totient]

Well, not quite. And TIL that although the JVM can optimize away the extra stack frame just fine, and will if the language is something like Scala, some of the language features of Java mean that in practice it won't do so for Java code.

[ceo]

*is confused, looks this up* Ah, you're talking about tail call optimization, I think. Which (TIL) C++ might or might not do depending on whether there's things with non-trivial destructors instantiated in the function.