Monday, April 9, 2012
20 minute puzzle
You have a list of names and a list of objects. Each object has 1 unique name. Neither list contains duplicates. Write a procedure that determines if every name in the list corresponds to an object.
(Suppose the list never contains more than four names, would you change your program?)
Subscribe to:
Post Comments (Atom)
4 comments:
A simple C# implementation the most obvious way:
public static bool IsComplete(IEnumerable<string> keys, IEnumerable<NamedThing> objects) {
var objNames = new HashSet<string>(objects.Select(o => o.Name));
return keys.All(objNames.Contains);
}
The "same thing" in Clojure:
(defn is-complete? [names objs]
(let [obj-names (set (map :name objs))]
(every? #(contains? obj-names %) names)))
Oh, and I guess the answer is that I wouldn't change my program unless I really cared about squeezing out performance for small collections of names and objects. If so, my first thought would be whether I could arrange to get the objects and names ordered in advance, so that I could zip down the lists and check like that.
You don't say how big the lists are expected to be, which of course controls the sort of algorithms I'd use.
If they are big enough to be in external storage, I'd sort them (mapping the objects to their names with "cut") and then use "comm -13". If they are in memory and I get to use Scheme, I'd use MAP to map the objects to their names, and then use LSET-DIFFERENCE from SRFI 1, on the assumption that Olin Shivers is more likely to get that operation right than I am.
If I knew the length of the list of names was at most four, I'd make sure the other list's length was at most four too, and if not, return false without further work.
I didn't bother loading up SRFI-1 so I wrote an implementation in R5RS Scheme:
https://gist.github.com/2346450
Post a Comment