# Spotify Cat vs. Dog Challenge

I implemented an algorithm to solve a constraint satisfaction problem. It is a non-trivial one, so I do not intend to take your time with its details. I am mainly looking for good code suggestions rather than the specific details on the logic.

package com.muratdozen.playground.spotify;

import java.io.PrintWriter;
import java.util.*;

/**
* Spotify Challenge, Cat vs. Dog
*
* @author Murat Derya Ozen
* @since: 10/2/13 10:47 AM
* @see <a href="https://www.spotify.com/us/jobs/tech/catvsdog/">
*      https://www.spotify.com/us/jobs/tech/catvsdog/</a>
*/
public class CatVsDog {

public static class Vote {
public final boolean catLover;
public final int keep;
public final int throwout;

public Vote(final boolean catLover, final int keep, final int throwout) {
this.catLover = catLover;
this.keep = keep;
this.throwout = throwout;
}

public boolean isConflicting(Vote vote) {
return this.catLover != vote.catLover
&& (this.keep == vote.throwout || this.throwout == vote.keep);
}
}

// some kind of a bipartite graph matching
private static final int maxMatchings(final Map<Vote,Set<Vote>> conflictingVotes,

// assign each cat lover vote to a conflicting dog lover vote
// we need to find out the maximum number of such assignments (matchings)
// we assign each cat lover vote to a conflicting vote by starting from
// the cat lover vote that has the least number of options (conflicting votes)

// list of cat lover votes sorted by the number of options each vote has
@Override
public int compare(Vote vote, Vote vote2) {
return Integer.valueOf(set1.size()).compareTo(set2.size());
}
});

int result = 0;

// assign each cat lover vote
for (int i = 0; i < len; ++i) {
// when choosing which conflicting dog lover vote to assign,
// choose the one that affects the least amount of remaining cat lover voters
if (choices == null || choices.isEmpty())
continue;
Vote minAffectingVote = null; /* dog lover vote that is to be assigned */
int min = Integer.MAX_VALUE;
for (Vote choice : choices) {
if (set == null || set.isEmpty())
continue;
final int numAffecting = set.size();
if (numAffecting < min) {
min = numAffecting;
minAffectingVote = choice;
}
}
if (minAffectingVote != null) {
++result;
}
}

return result;
}

private static final <T> void addToMap(final Map<T,Set<Vote>> map, final T key, final Vote vote) {
} else {
}
}

final Set<Vote> catLovers = new HashSet<Vote>();
final Map<Integer, Set<Vote>> dogLoversIndexedByKeep = new HashMap<Integer, Set<Vote>>();
final Map<Integer, Set<Vote>> dogLoversIndexedByThrowout = new HashMap<Integer, Set<Vote>>();

// parse and collect data from input

if (v == 1) return 1;

// fill in catLovers, dogLoversIndexedByKeep and dogLoversIndexedByThrowout
for (int j = 0; j < v; ++j) {
final int keep = Character.getNumericValue(keepStr.charAt(1));
final int throwout = Character.getNumericValue(throwoutStr.charAt(1));
final boolean catLover = keepStr.charAt(0) == 'C';
final Vote vote = new Vote(catLover, keep, throwout);
if (catLover) {
} else {
}
}

// build a map of conflicting votes
// conflictingVotes has cat lovers' votes as keys. each key maps to a set of
// dog lovers' votes that conflict with key.
final Map<Vote, Set<Vote>> conflictingVotes = new HashMap<Vote, Set<Vote>>(catLovers.size());
final Map<Vote, Set<Vote>> reverseConflictingVotes = new HashMap<Vote, Set<Vote>>();
for (Vote catLover : catLovers) {
final Set<Vote> conflicts = new HashSet<Vote>();
if (dogLoversIndexedByKeep.containsKey(catLover.throwout)) {
}
if (dogLoversIndexedByThrowout.containsKey(catLover.keep)) {
}
for (Vote dogLoverVote : conflicts) {
}
}

// match as many conflicting votes as possible
// and return number of votes - number of matches
}

public static final void main(String[] args) {

final PrintWriter writer = new PrintWriter(System.out);
final String LINE_SEPARATOR = System.getProperty("line.separator");

for (int i = 0; i < numTestCases; ++i) {
writer.write(Integer.toString(result));
writer.write(LINE_SEPARATOR);
}

writer.flush();
writer.close();
}
}


The code is hosted on GitHub if anyone's interested. I will commit changes if necessary.

private static final <T> void addToMap(final Map<T,Set<Vote>> map, final T key, final Vote vote) {
} else {
}
}


Alternative:

private static final <T> void addToMap(final Map<T,Set<Vote>> map, final T key, final Vote vote) {

if (null == map.get(key)) {
map.put(key, new HashSet<Vote>());
}

}


Edit to my preferred syntax:

private static final <T> void addToMap(final Map<T,Set<Vote>> map, final T key, final Vote vote) {
if (!map.containsKey(key)) {
map.put(key, new HashSet<Vote>());
}
}

• Good point and thanks for the answer. However, I wanted to avoid 2 map.get operations for performance reasons. Oct 6, 2013 at 18:03
• @Murat Then you can still move votes.add(vote); out of the branches (save 2 lines and make clear that vote gets always added). Jun 15, 2014 at 20:37
• @Murat I know this is a very old topic, but I think your performance concerns were unfounded. Map.get appears to be on average an O(1) operation. See: stackoverflow.com/q/1055243/3230218 Nov 24, 2016 at 12:27

I have not read your code in detail, but a lot of extra complexity comes from handling Map<Vote, Set<Vote>>. I'm a big fan of guava's Multimap<K, V>.

• +1 for that. I like Guava and I include it in most of my projects. For this piece of code, however, I wasn't able to use 3rd party libraries. Oct 5, 2013 at 22:12

Your methods are enormous. I would start by breaking them down into small segments that only do a single thing.

You also have lots of comments around. This is needed because your methods are so big. In my opinion, ideally, you do not need inline comments because the methods should explain themselves, often by their name alone.

• Welcome to Code Review! Your answer came up in the "First Posts" queue. You passed the test! Jun 13, 2014 at 20:53

• Javadoc is missing. For instance, what is the expected input format of the program?
• Missing {} after a if statement is not recommended
• I'd place LINE_SEPARATOR as static, but it's just a matter of taste
• The use of static methods make it impossible to mock up in tests
• You can shorten a bit addToMap

.

private static final <T> void addToMap(final Map<T,Set<Vote>> map, final T key, final Vote vote) {

• You create an instance of comparator at each call of maxMatchings, ie one per line. You need only one instance for the full program, as a field.