Friday programming quiz
-
I promised a programming quiz a couple weeks ago, so here's one: Given an array of integers, select the integer in the array that is the closest to the average of all integers in the array; you must use nothing but a single LINQ lambda statement. If more than one integer is the closest, then any of the closest integers will do. For example, the following code should assign "14" to the int "closest":
int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = // put a LINQ lambda expression hereIf you're up for actually figuring out your own solution, ignore the rest of this post. OR If you're lazy and unethical, feel free to copy-paste the sample solution in the small text below and claim it as your own. inputs.Where(x => Math.Abs(x - inputs.Average()) == inputs.Select(y => Math.Abs(y - inputs.Average())).Min()).First();
-
int closest = inputs.OrderBy(i => Math.Abs(i - inputs.Average())).FirstOrDefault();
This is O(N²) as Average() gets called for every sort key that gets calculated. We can do better by storing the average in a variable. And we can use LINQ to introduce variables within an expression:
int closest = (from avg in new[] { inputs.Average() }
from i in inputs
orderby Math.Abs(i - avg)
select i).FirstOrDefault();This is O(N log N), but note that instead of sorting, we just need to find the minimum. Sadly, all the Min() methods compare the element itself, not just a key. However, we can build a suitable implementation using Aggregate():
int closest = (from avg in new[] { inputs.Average() }
select inputs.Aggregate((a, b) => Math.Abs(a - avg) < Math.Abs(b - avg) ? a : b)
).Single();This runs in linear time, and does pretty much the same as an implementation using a loop would do.
Great answer. Can use let rather than that new []{} however: int closest = (from i in inputs
let avg = inputs.Average()
select inputs.Aggregate((a, b) => Math.Abs(a - avg) < Math.Abs(b - avg) ? a : b)
).Single();
That is actually wrong, but this works and average is called just once:int closest = (from c in "A" //just to get it to loop once let avg = inputs.Average() select inputs.Aggregate((a, b) => Math.Abs(a - avg) < Math.Abs(b - avg) ? a : b) ).Single();Does anyone know of a nicer way to cause just one loop in linq than my 'from c in "A"' trick?
-
Great answer. Can use let rather than that new []{} however: int closest = (from i in inputs
let avg = inputs.Average()
select inputs.Aggregate((a, b) => Math.Abs(a - avg) < Math.Abs(b - avg) ? a : b)
).Single();
That is actually wrong, but this works and average is called just once:int closest = (from c in "A" //just to get it to loop once let avg = inputs.Average() select inputs.Aggregate((a, b) => Math.Abs(a - avg) < Math.Abs(b - avg) ? a : b) ).Single();Does anyone know of a nicer way to cause just one loop in linq than my 'from c in "A"' trick?
This little change you suggest puts the perfomance back to O(N^2) and not linear. inputs.Average() gets called for each element in the inputs array. Daniel's solution is the correct one. --- Adar Wesley
-
I promised a programming quiz a couple weeks ago, so here's one: Given an array of integers, select the integer in the array that is the closest to the average of all integers in the array; you must use nothing but a single LINQ lambda statement. If more than one integer is the closest, then any of the closest integers will do. For example, the following code should assign "14" to the int "closest":
int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = // put a LINQ lambda expression hereIf you're up for actually figuring out your own solution, ignore the rest of this post. OR If you're lazy and unethical, feel free to copy-paste the sample solution in the small text below and claim it as your own. inputs.Where(x => Math.Abs(x - inputs.Average()) == inputs.Select(y => Math.Abs(y - inputs.Average())).Min()).First();
Here's a good couple of questions to give programmers you're thinking of hiring -- if they can answer these, it's a good bet you've found yourself someone who can think a bit...: 1. In C, what does this do (and no, it doesn't matter what types the variables are as long as they're the same type)? a^=b^=a^=b; 2. In SQL, given the following tables (relationships being obvious), write a query which returns the names of the people who play *every* sport: People PersonID int PersonName varchar(50) Sports SportID int SportName varchar(50) PeopleSports PersonID int SportID int
-
I promised a programming quiz a couple weeks ago, so here's one: Given an array of integers, select the integer in the array that is the closest to the average of all integers in the array; you must use nothing but a single LINQ lambda statement. If more than one integer is the closest, then any of the closest integers will do. For example, the following code should assign "14" to the int "closest":
int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = // put a LINQ lambda expression hereIf you're up for actually figuring out your own solution, ignore the rest of this post. OR If you're lazy and unethical, feel free to copy-paste the sample solution in the small text below and claim it as your own. inputs.Where(x => Math.Abs(x - inputs.Average()) == inputs.Select(y => Math.Abs(y - inputs.Average())).Min()).First();
Could be simplified to:
int closest = inputs.First(x => Math.Abs(x - inputs.Average()) == inputs.Min(y => Math.Abs(y - inputs.Average())));
but I don't like to perform the same calculation twice, so I'd be more comfortable with:
double avg = inputs.Average();
int closest = inputs.First(x => Math.Abs(x - avg) == inputs.Min(y => Math.Abs(y - avg))); -
I promised a programming quiz a couple weeks ago, so here's one: Given an array of integers, select the integer in the array that is the closest to the average of all integers in the array; you must use nothing but a single LINQ lambda statement. If more than one integer is the closest, then any of the closest integers will do. For example, the following code should assign "14" to the int "closest":
int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = // put a LINQ lambda expression hereIf you're up for actually figuring out your own solution, ignore the rest of this post. OR If you're lazy and unethical, feel free to copy-paste the sample solution in the small text below and claim it as your own. inputs.Where(x => Math.Abs(x - inputs.Average()) == inputs.Select(y => Math.Abs(y - inputs.Average())).Min()).First();
int closest = inputs.OrderBy(x => Math.Abs(inputs.Average() - x)).First();
-
I promised a programming quiz a couple weeks ago, so here's one: Given an array of integers, select the integer in the array that is the closest to the average of all integers in the array; you must use nothing but a single LINQ lambda statement. If more than one integer is the closest, then any of the closest integers will do. For example, the following code should assign "14" to the int "closest":
int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = // put a LINQ lambda expression hereIf you're up for actually figuring out your own solution, ignore the rest of this post. OR If you're lazy and unethical, feel free to copy-paste the sample solution in the small text below and claim it as your own. inputs.Where(x => Math.Abs(x - inputs.Average()) == inputs.Select(y => Math.Abs(y - inputs.Average())).Min()).First();
Here are two alternate implementations. Two might be cheating a bit, but it satisfies the "only one semi-colon" rule. :-) As others have pointed out, the answer you gave is pretty slow. To those who say LINQ can't be fast, algorithm choice makes a huge difference. I ran tests for the three implementations over the original input set, the values 1-99 and -499 to 499. To help average out timing inconsistencies, the tests were run 10,000 times. Values are in ms.
Quiz inputs
100 items
1000 items
Quiz solution
284
84,573
Unknown. I stopped it after about 6 hours.
Alternate 1
80
1,945
167,099
Alternate 2
75
479
7,246
Alternate 1
int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = inputs
.Select(i => new {val = i, dist = Math.Abs(i - inputs.Average())})
.OrderBy(a => a.dist)
.First().val;Alternate 2
int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = (from x in new []{1}
let avg = inputs.Average()
from i in inputs
select new { val = i, dist = Math.Abs(i-avg)})
.OrderBy(a => a.dist)
.First().val -
Not a very efficient approach (and hope I'm not cheating, there is only one semi-colon!) but here goes:
int closest = (from t in
from i in inputs
let avg = inputs.Average()
select new { Number = i, Delta = Math.Abs(i - avg) }
orderby t.Delta
select t.Number).FirstOrDefault();I'm not familiar with linq nor lambda, but I really like this solution over the original suggested one. Am I right that t is an implied class that contains 2 fields? 1. It doesn't take work to understand the logic. 2. Rather than N^4 loops, this has N^2. (Like you said, not efficient, but much better than the original.)
-
maybe I've found an alternative inputs.Select(x => new { OriginalValue = x, Distance = Math.Abs(x - inputs.Average()) }).OrderBy(a => a.Distance).First().OriginalValue;
-
I'm not familiar with linq nor lambda, but I really like this solution over the original suggested one. Am I right that t is an implied class that contains 2 fields? 1. It doesn't take work to understand the logic. 2. Rather than N^4 loops, this has N^2. (Like you said, not efficient, but much better than the original.)
Actually, if I was doing it again I would use Daniel Grunwald trick to calculate the average only once:
int closest = (from avg in new [] { inputs.Average() }
from i in inputs
orderby Math.Abs(i - avg)
select i).FirstOrDefault();Using the lambda format (as per the rules :) ) I believe this translates to:
int closest = new[] { inputs.Average() }
.SelectMany(avg => inputs.OrderBy(i => Math.Abs(i - avg)))
.FirstOrDefault();I believe this solution will iterate over the original collection twice - once for the average, once for the ordering, but have no idea what the big O number is for the ordering.
-
I promised a programming quiz a couple weeks ago, so here's one: Given an array of integers, select the integer in the array that is the closest to the average of all integers in the array; you must use nothing but a single LINQ lambda statement. If more than one integer is the closest, then any of the closest integers will do. For example, the following code should assign "14" to the int "closest":
int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = // put a LINQ lambda expression hereIf you're up for actually figuring out your own solution, ignore the rest of this post. OR If you're lazy and unethical, feel free to copy-paste the sample solution in the small text below and claim it as your own. inputs.Where(x => Math.Abs(x - inputs.Average()) == inputs.Select(y => Math.Abs(y - inputs.Average())).Min()).First();
We saw fairly eye to eye.. Here was my first go:
int closest = inputs.FirstOrDefault(num => Math.Abs((Math.Abs(num) - (int)inputs.Average())) == inputs.Min(diff => Math.Abs(Math.Abs(diff) - (int)(inputs.Average()))));
And with some visual optimization
int closest = inputs.FirstOrDefault(num => Math.Abs(num - inputs.Average()) == inputs.Min(diff => Math.Abs(diff - inputs.Average())));
[EDIT] And thinking a bit more about it
int closest = inputs.Select(input => new
{
input,
diff = Math.Abs(input - inputs.Average())
}).OrderBy(x => x.diff).FirstOrDefault().input; -
Actually, if I was doing it again I would use Daniel Grunwald trick to calculate the average only once:
int closest = (from avg in new [] { inputs.Average() }
from i in inputs
orderby Math.Abs(i - avg)
select i).FirstOrDefault();Using the lambda format (as per the rules :) ) I believe this translates to:
int closest = new[] { inputs.Average() }
.SelectMany(avg => inputs.OrderBy(i => Math.Abs(i - avg)))
.FirstOrDefault();I believe this solution will iterate over the original collection twice - once for the average, once for the ordering, but have no idea what the big O number is for the ordering.
I really can't judge LINQ, nor lambda statements because I don't have the experience with them. The original rule was "you must use nothing but a single LINQ lambda statement." Someone else complained that the original poster used two lambda statements. As far as I can tell, the original poster used two lambda variables in a single statement. My complaint about the original statement was that it was too hard to read. Then I complained about the efficiency of the original which would loop between N^3 and N^4 times. That was after taking the time to really understand what the first statement said. I came up with a set of C# commands that would find the answer in N*2 loops. Using two if statements and either one or three more statements per loop. Once I get over the "You define the variable, then you assign a statement's value to it" prejudice, your lambda statement is very readable, more elegant than my solution and with internal optimizations going on, your N*3 loops may be as fast or faster than my N*2 loops. I may even find the "Define the statement, then assign the variable" process enjoyable in time. Daniel still gets credit for first finding a good lambda expression. :)
-
This little change you suggest puts the perfomance back to O(N^2) and not linear. inputs.Average() gets called for each element in the inputs array. Daniel's solution is the correct one. --- Adar Wesley