Ayende @ Rahien

Alex commented on A challenge: Getting a list of products

Wed, 16 Apr 2008 23:33:33 GMT

SELECT TOP 10 * FROM product WHERE product_id NOT IN (SELECT product_id FROM product_tag WHERE tag_id IN ({tagList})) You guys are Architecture Astronauts. http://www.joelonsoftware.com/articles/fog0000000018.html http://www.joelonsoftware.com/items/2005/10/21.html

alberto commented on A challenge: Getting a list of products

Fri, 11 Apr 2008 19:31:35 GMT

So, did I get the job? :D

Michael Minutillo commented on A challenge: Getting a list of products

Fri, 11 Apr 2008 08:48:37 GMT

I had a quick go with LINQ to SQL. Given the way LINQ to SQL works does the Pipes and Filters Pattern begin to converge with the Specification Pattern in anyone elses mind? http://wolfbyte-net.blogspot.com/2008/04/pipe-and-filters-fluent-apis-and-linq.html

alberto commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 20:55:26 GMT

Ayende, THEN I would refactor (in fact, if it were a face-to-face interview I would have asked you a few questions to get some insight in what you were expecting from me, but since this is not so fluent, I opted for KISS). Anyway, I have posted my solution in my blog (it was a little longer and I can format it a little there ;)) http://sharpbites.blogspot.com/2008/04/ayendes-challenge.html

Frans Bouma commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 20:28:36 GMT

@alex: whoops! :X

Alex Simkin commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 20:27:52 GMT

Interesting that none paid attention to the first requirement: "listing the first 10 products"

Frans Bouma commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 18:33:02 GMT

I hope this all fits in the post using System; using System.Collections.Generic; namespace Challenge { public enum Aspect { Pg, ContainsMeat, // etc. } public class Product { public Product(HashSet initialAspects) { this.Aspects = new HashSet(); foreach(Aspect a in initialAspects) { this.Aspects.Add(a); } } public string Name { get; set;} public decimal Price { get; set;} public HashSet Aspects { get; private set;} } public class ListProducts { public static void Main(string[] args) { List products = BuildProducts(); List> predicates = ParseArguments(args); List filteredProducts = FilterProducts(products, predicates); ShowProducts(filteredProducts); } private static void ShowProducts(List toShow) { Console.WriteLine("Products found:"); foreach(Product p in toShow) { Console.WriteLine("{0}\t\t${1}", p.Name, p.Price); } } private static List FilterProducts(List products, List> predicates) { List toReturn = new List(); foreach(Product p in products) { bool acceptProduct = true; foreach(Func predicate in predicates) { acceptProduct &= predicate(p); if(!acceptProduct) { break; } } if(acceptProduct) { toReturn.Add(p); } } return toReturn; } private static List> ParseArguments(string[] args) { List> toReturn = new List>(); foreach(string argument in args) { Func toAdd = null; switch(argument) { case "-pg13": toAdd = p=>!p.Aspects.Contains(Aspect.Pg); break; case "-vegetarian": toAdd = p=>!p.Aspects.Contains(Aspect.ContainsMeat); break; default: throw new ArgumentException(string.Format("Unknown argument: {0}", argument)); } toReturn.Add(toAdd); } return toReturn; } private static List BuildProducts() { List toReturn = new List(); toReturn.Add(new Product(new HashSet()) { Name="Milk", Price=1.0M}); toReturn.Add(new Product(new HashSet()) { Name="Bread", Price=1.3M}); toReturn.Add(new Product(new HashSet() { Aspect.ContainsMeat}) { Name="Sausage", Price=2.5M}); toReturn.Add(new Product(new HashSet() { Aspect.Pg}) { Name="Horror Movie", Price=5M}); return toReturn; } } }

Ayende Rahien commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 17:21:59 GMT

Frans, Most people would implement this using ifs until the cow comes home. Choosing an approach that fits the open close principal is what I was aiming at.

Ayende Rahien commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 17:20:49 GMT

Dimitar, Very nice, and what I would strive for in these sort of situations This is also pipe and filters, but your filter build a query, which fits my definition

Frans Bouma commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 17:05:23 GMT

"The actual code, sure. The design, no." - argument parsing. The biggest challenge. Argument parsing is error prone. - filtering a set using multiple predicates. erm... if that's hard, one hasn't passed 1st year of a CS course, IMHO. -> parse every argument into a predicate. The argument parser then builds a predicate expression with these predicates, with solely AND operators. So this is very easy: you simply execute all predicates in the expression. if they all are true, you have a match. The predicates are simple classes. You simply pass in the object to filter on and you interpret the predicate with the object. This can be done for example by creating Func instances, like the pg age delimiter. Func f = p=>(p.Aspects[Aspect.Pg] !=null) && (bool)p.Aspects[Aspect.pg]; the predicate is then simply the Func. The predicate expression is then simply a list of Func instances. A product is an instance of a Product class which has Aspects, which is a Dictionary, so you can store aspects of it inside the product. Otherwise you can't filter on it in a generic way and have to build custom code per type in the set. You then traverse the complete set from front to back, applying the predicate expression on all products. If the predicate expression returns true, it's a match, otherwise you move on to the next. The _code_ is actually more challenging than the design. The crucial thing the participant has to realize is that it has to traverse the set by applying a predicate expression. But that's basic database theory. So the challenge is actually: how to implement this? I therefore disagree that the code is 'simple' and the design isn't. THe design is straight forward, the code has some irritating aspects because you have to parse arguments. This always sucks 8)

Dimitar E Dimitrov commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 15:55:38 GMT

Applying some kind of Pipe processing seems nice from design point of view, but when it comes to reading and filtering data, which always comes from relational database I think it is better to let the database do the work, that it supposed to do – find the data, that you need the fastest way. I don’t accept the argument, that you can’t always use database - even for a sample app with 100 records I would use Sqlite and still have feature a complete database at my disposal. Reading all data in memory and filtering with line of pipes isn't that feasible to me. What is wrong doing to most obvious thing like: public interface IDatabase { IList ListProducts(IList filters); } If you want to take this further here a little more code in case my point isn't that clear: public class Filter { public string CmdSwtich { get; private set;} public string DBColumn { get; private set;} public virtual string GetCondition(); } public class BooleanFilter : Filter { public override string GetCondition() { return DBColumn + "=1 "; } } public class Query { string query; public IList Filters { get; private set;} public Query(string query, IList filters) { this.query = query; Filters = filters; } public string GetSql() { if (Filters == null || Filters.Count == 0) return query; string result = query; result += " WHERE "; for(int i = 0; i < Filters.Count; i++){ result += Filters[i].GetCondition(); if (i < Filters.Count - 1) result += ", "; } return result; } }

Ralf Kretzschmar commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 13:50:40 GMT

Full code, test, and testdata for the dos solution can be found on http://www.filedropper.com/ayendechallenge

Alex Simkin commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 13:41:42 GMT

So, did Ralf pass the test?

Ayende Rahien commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 13:39:38 GMT

The goggles, they do nothing! :-) That is an unexpected solution, which is utterly unreadable to me,

Ralf Kretzschmar commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 13:35:31 GMT

How about a solution using a windows command line batch? :-) here is the code: -------------------------------------------------------------------- @echo off if "%echo%" neq "" echo %echo% set prodGroupSearch= set vegCodeSearch= :nextArg if "%1"=="" goto :process set arg=%1 if "%arg:~0,3%"=="-pg" set prodGroupSearch=%arg:~1,5% if "%arg%"=="-vegetarian" set vegCodeSearch=veg shift goto :nextArg :process for /F "eol=# delims=;# tokens=1-4" %%i in (prods) do call :output "%%i" %%j %%k %%l exit /b :output set prod=%~1 . set prod=%prod:~0,15% set price=%2 set prodGroup=%3 set vegCode=%4 set query= set val= if "%prodGroupSearch%" neq "" (set query=%prodGroupSearch%& set val=%prodGroup%) if "%vegCodeSearch%" neq "" (set query=%query%%vegCodeSearch%& set val=%val%%vegCode%) if "%val%" neq "%query%" goto :skip echo %prod% %price% :skip exit /b ---------------------------------------------------------------------------- The products file looks like this: ---------------------------------------------------------------------------- Milk;$1.0;pg13;veg# Bread;$1.3;pg13;veg# Sausage;$2.5;pg13;nonveg# Horror Movie;$5.0;pg31;veg# ---------------------------------------------------------------------------- Btw: I did it TDD. Here are my tests ---------------------------------------------------------------------------- @echo off call list_products.bat > out.txt fc out.txt case1.txt > nul || @echo case1 failed call list_products.bat -pg13 > out.txt fc out.txt case2.txt > nul || @echo case2 failed call list_products.bat -vegetarian >out.txt fc out.txt case3.txt > nul || @echo case3 failed call list_products.bat -pg13 -vegetarian >out.txt fc out.txt case4.txt > nul || @echo case4 failed ----------------------------------------------------------------------------

alwin commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 11:34:03 GMT

If it is small scale / demo purpose, i would use the Filter thing. But without the Linq and with the CanProcess as bool. Just 'yield' everything, and the processing order depends on the order in the registration list. For larger scale where you need to make a db query, maybe a i would use a specification. I've used this in my last project after a tip from Ayende on the castle user list :) Dictionary> specModifiers; specModifiers.Add("vegetarian", spec => spec.Vegetarian = true);

Ayende Rahien commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 11:32:04 GMT

If we have 1000 parameters, we need a completely different approach

Tuna Toksoz commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 11:27:12 GMT

Well, I thought you would ask "what if we had 10000 parameters" if i wouldn't care about the complexity(even I cared, I was wrong and can still be wrong)

Ayende Rahien commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 11:16:06 GMT

Tuna, Assume that there will be 100 filters (very high). Using the CanExecute, Execute approach, you would have at most 200 iterations. Since they only add filters, we don't care about that.

Tuna Toksoz commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 11:12:08 GMT

Sorry, I was wrong in complexity of the case, there will be a need for priority queue. There will be n parameters and m filters. m*n will be required for iterating and finding the right filter. n parameter&filter pair will be placed into priority queue, nlogn will be required. and then they will be popped. O(mn) wasn't right

Tuna Toksoz commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 11:05:14 GMT

Needless to say, I would implement filters for paging , and so. The problem would be the order of parameters, I mean if person first enters parameter for page, then types the vegetarian, it would be the problem. Well, I would change the interface to public interface IFilter { int CanProcess(string parameter); //returns the order of filter, if it is Integer.Max, it will be processed in the end bool Process(IOrderedQueryable queryable,string parameter); } and use something like priority queue. This would require double-iteration of filters, so it is O(m.n) where m is the number of filters and n is the number of parameters.

Tuna Toksoz commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 10:59:10 GMT

public interface IFilter { bool Process(IOrderedQueryable q,string parameter); } And I loop every item entered from the console. If the process method returns false, i would try this parameter with next filter, if it returns true, i will reiterate the filter list for the next parameter.

Benny Thomas commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 10:43:38 GMT

I would say you should handle the args as IEnumerable. Lets have a registerfase thats register all args we could handle first.

Ayende Rahien commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 10:31:34 GMT

alberto, Now imagine that you have 15 of those, how would you scale the problem to handle this?

Ayende Rahien commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 10:30:02 GMT

Frans Bouma, The actual code, sure. The design, no.

alberto commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 09:13:55 GMT

Seems like a good candidate for LINQ. Here's a first and dirty approach to it (excuse possibles mistakes in my syntax, these are my very first lines on LINQ and your textbox's intellisense is broken :)).

  
IEnumerable FilterByPG13Compliance(IEnumerable products)
  
{
  
	var result = from product in products
  
		select where product.RequiredAge <= 13;
  
	return result;
  
}
  
  
IEnumerable FilterByVegetarianFriendliness(IEnumerable products)
  
{
  
	var result = from product in products
  
		select where product.VegetarianFriendly
  
	return result;
  
}
  
  
  
//main
  
var result = from product in products select product;
  
int i;
  
for (i = 1; i < args.Length; i++)
  
{
  
	switch(args[i])
  
	{
  
		case "-pg13":
  
			result = FilterByPG13Compliance(result);
  
			break;
  
		case "-vegetarian":
  
			result = FilterByVegetarianFriendliness(result);
  
			break;
  
		...
  
	}
  
}
  
  
foreach (Product p in result)
  
{
  
Console.WriteLine("{0}\t{1}",product.Name, product.Price);
  
}

Frans Bouma commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 07:48:13 GMT

isn't this 1st year CS course material?

Paul Cowan commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 07:06:12 GMT

So by vegetarian you mean everything that is not meat. Surely you would just select everything that is vegetarian or are you looking for the candidate to only look at the requirements and not what the candidate can read between the lines. I like the IEnumerable of operations approach as well or why stop there why not provide your own linq provider. How many days does the test take? I could maybe get a beta out in a week

Evan commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 03:25:14 GMT

A trickier version might be 30k products, against an average of 6 filters per query, and a hard response deadline of 30ms..

Evan commented on A challenge: Getting a list of products

Wed, 09 Apr 2008 03:20:21 GMT

Given that the number of products in an average ecommerce site is very low, you can solve it in a number of ways and do "good enough". Now, if you are amazon, it's going to be a bit trickier.. Did you have something large scale in mind, or just an average app with 50-100 products?