Friday Programming Quiz (It's back) [modified]
-
Back on Popular demand You are given two lists. List 1 contains certain strings in a particular order. List 2 contains all the allowed values in List 1. List 1, however, can contain some elements not in List 2. The objective is to generate a List 3 which will have elements from List 1 in exactly the same order specified in List 1 followed by elements not in List 1 but present in List 2. Any elements not in List 2 should not be included. Example: List 1:
A,B,C,D
List 2:
B,A,X,S,L,D
Output:
A,B,D,X,S,L
Last modified: 10mins after originally posted --
Proud to be a CPHog user
If list 1 and list 2 are both size of an order 'n': 1. Create a sorted List 2 (n*log n) 2. Binary search the sorted list 2 for each element in list 1 and append the findings to list 3 (n*log n) 3. Create a sorted List 1 (n*log n) 4. Binary search the sorted list 1 for each element in list 2 and append the missing ones to list 3 (n*log n) 5. Output list 3 O(n*log n) time with O(n) extra memory allocated
-
Rama, Shouldn't the
CinList1be included inList3? PJC"The clue train passed his station without stopping." - John Simmons / outlaw programmer "Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
No
Proud to be a CPHog user
-
Rama Krishna Vavilala wrote:
List 2 contains all the allowed values in List 1. List 1, however, can contain some elements not in List 2.
can you rephrase this? if list 2 contains the values which are allowed in list 1, how can list 1 contain values which aren't in list 2?
Chris Losinger wrote:
how can list 1 contain values which aren't in list 2?
Those should not have been there but are there so they need to be taken out. So at one point of time the value was allowed but then at a further point the value is not allowed. The real life case where the situation occurred: List 1 was a subset of column names in a table. List 2 was all the column names. At one point someone may add or remove columns in a table (List 2). In that case List 1 *may* have some invalid values.
Proud to be a CPHog user
-
Sweet! I love these! Is it cheating to use LINQ?
var list1Allowed = from element in list1
where list2.Contains(element)
select element;var list2ElementsNotInList1 = from element in list2
where !list1.Contains(element)
select element;var result = list1Allowed.Concat(list2ElementsNotInList1);
Alternately, since we're not doing any fabulous let clauses, we could just call the extension methods directly for a more terse syntax:
var list1Allowed = list1.Where(el => list2.Contains(el));
var list2ElementsNotInList1 = list2.Where(el => !list1.Contains(el));
var result = list1Allowed.Concat(list2ElementsNotInList1);Nifty! I :heart: LINQ. :)
Life, family, faith: Give me a visit. From my latest post: "The themes and truths of the Jewish holidays follow God's complete plan for this world. They are the root from which Christianity sprang and the historical reasons the church had for leaving them behind were unsound." Judah Himango
Judah Himango wrote:
Is it cheating to use LINQ?
No LINQ is definitely one of the reasons for these quizzes.:)
Proud to be a CPHog user
-
Sweet! I love these! Is it cheating to use LINQ?
var list1Allowed = from element in list1
where list2.Contains(element)
select element;var list2ElementsNotInList1 = from element in list2
where !list1.Contains(element)
select element;var result = list1Allowed.Concat(list2ElementsNotInList1);
Alternately, since we're not doing any fabulous let clauses, we could just call the extension methods directly for a more terse syntax:
var list1Allowed = list1.Where(el => list2.Contains(el));
var list2ElementsNotInList1 = list2.Where(el => !list1.Contains(el));
var result = list1Allowed.Concat(list2ElementsNotInList1);Nifty! I :heart: LINQ. :)
Life, family, faith: Give me a visit. From my latest post: "The themes and truths of the Jewish holidays follow God's complete plan for this world. They are the root from which Christianity sprang and the historical reasons the church had for leaving them behind were unsound." Judah Himango
Also all these questions are based on real life situations I faced and where I(or some other team member) had to use LINQ to objects.
Proud to be a CPHog user
-
Also all these questions are based on real life situations I faced and where I(or some other team member) had to use LINQ to objects.
Proud to be a CPHog user
Hey man, you're preaching to the choir. We've been using our own LINQ-like library for .NET 2 (uglier b/c no extension methods, less type inference), and even there it's been invaluable to us where we have to gather parts of a collection, or parts of objects in a collection.
Life, family, faith: Give me a visit. From my latest post: "The themes and truths of the Jewish holidays follow God's complete plan for this world. They are the root from which Christianity sprang and the historical reasons the church had for leaving them behind were unsound." Judah Himango
-
Back on Popular demand You are given two lists. List 1 contains certain strings in a particular order. List 2 contains all the allowed values in List 1. List 1, however, can contain some elements not in List 2. The objective is to generate a List 3 which will have elements from List 1 in exactly the same order specified in List 1 followed by elements not in List 1 but present in List 2. Any elements not in List 2 should not be included. Example: List 1:
A,B,C,D
List 2:
B,A,X,S,L,D
Output:
A,B,D,X,S,L
Last modified: 10mins after originally posted --
Proud to be a CPHog user
Simple, how about a hard one? Given a tic-tac-toe board where the board can be represented by a one-dimensional array of chars with 'X' being x, 'Y' being y, and all others being empty such that the top left most square is the 0 index, followed by the middle square on the top row as the 1 index ....
0 | 1 | 2
_____________
3 | 4 | 5
_____________
6 | 7 | 8Write an algorithm to display the number of winning combination available for each X and O based on the game state when passed an array in under n^2.
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway -
Simple, how about a hard one? Given a tic-tac-toe board where the board can be represented by a one-dimensional array of chars with 'X' being x, 'Y' being y, and all others being empty such that the top left most square is the 0 index, followed by the middle square on the top row as the 1 index ....
0 | 1 | 2
_____________
3 | 4 | 5
_____________
6 | 7 | 8Write an algorithm to display the number of winning combination available for each X and O based on the game state when passed an array in under n^2.
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway -
Simple, how about a hard one? Given a tic-tac-toe board where the board can be represented by a one-dimensional array of chars with 'X' being x, 'Y' being y, and all others being empty such that the top left most square is the 0 index, followed by the middle square on the top row as the 1 index ....
0 | 1 | 2
_____________
3 | 4 | 5
_____________
6 | 7 | 8Write an algorithm to display the number of winning combination available for each X and O based on the game state when passed an array in under n^2.
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest HemingwayHa! I think I did this in first year uni :) Wow, I did some scary (but still cool) code back then, in C!
Ennis Ray Lynch, Jr. wrote:
under n^2.
What is n suppose to be?
xacc.ide - now with TabsToSpaces support
IronScheme - 1.0 alpha 4a out now (29 May 2008) -
Ha! I think I did this in first year uni :) Wow, I did some scary (but still cool) code back then, in C!
Ennis Ray Lynch, Jr. wrote:
under n^2.
What is n suppose to be?
xacc.ide - now with TabsToSpaces support
IronScheme - 1.0 alpha 4a out now (29 May 2008)That is the efficiency of the algorithm, as in O(n^2) or less. It is a large topic that I cannot explain here.
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway -
Back on Popular demand You are given two lists. List 1 contains certain strings in a particular order. List 2 contains all the allowed values in List 1. List 1, however, can contain some elements not in List 2. The objective is to generate a List 3 which will have elements from List 1 in exactly the same order specified in List 1 followed by elements not in List 1 but present in List 2. Any elements not in List 2 should not be included. Example: List 1:
A,B,C,D
List 2:
B,A,X,S,L,D
Output:
A,B,D,X,S,L
Last modified: 10mins after originally posted --
Proud to be a CPHog user
var list1 = ['A','B','C','D'];
var list2 = ['B','A','X','S','L','D'];var result = list1.filter(function(i) list2.indexOf(i) >= 0)
.concat( list2.filter(function(i) list1.indexOf(i) < 0 ) );Javascript 1.8 (tested on Firefox 3.0.1)
You must be careful in the forest Broken glass and rusty nails If you're to bring back something for us I have bullets for sale...
-
That is the efficiency of the algorithm, as in O(n^2) or less. It is a large topic that I cannot explain here.
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest HemingwayEnnis Ray Lynch, Jr. wrote:
That is the efficiency of the algorithm, as in O(n^2) or less. It is a large topic that I cannot explain here.
Jeez. I hope you being sarcastic... :| What is n, the size of the input? Size of the board?
xacc.ide - now with TabsToSpaces support
IronScheme - 1.0 alpha 4a out now (29 May 2008) -
Ennis Ray Lynch, Jr. wrote:
That is the efficiency of the algorithm, as in O(n^2) or less. It is a large topic that I cannot explain here.
Jeez. I hope you being sarcastic... :| What is n, the size of the input? Size of the board?
xacc.ide - now with TabsToSpaces support
IronScheme - 1.0 alpha 4a out now (29 May 2008)your kidding right?
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway -
Ennis Ray Lynch, Jr. wrote:
That is the efficiency of the algorithm, as in O(n^2) or less. It is a large topic that I cannot explain here.
Jeez. I hope you being sarcastic... :| What is n, the size of the input? Size of the board?
xacc.ide - now with TabsToSpaces support
IronScheme - 1.0 alpha 4a out now (29 May 2008):eek:
"The clue train passed his station without stopping." - John Simmons / outlaw programmer "Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
-
Sweet! I love these! Is it cheating to use LINQ?
var list1Allowed = from element in list1
where list2.Contains(element)
select element;var list2ElementsNotInList1 = from element in list2
where !list1.Contains(element)
select element;var result = list1Allowed.Concat(list2ElementsNotInList1);
Alternately, since we're not doing any fabulous let clauses, we could just call the extension methods directly for a more terse syntax:
var list1Allowed = list1.Where(el => list2.Contains(el));
var list2ElementsNotInList1 = list2.Where(el => !list1.Contains(el));
var result = list1Allowed.Concat(list2ElementsNotInList1);Nifty! I :heart: LINQ. :)
Life, family, faith: Give me a visit. From my latest post: "The themes and truths of the Jewish holidays follow God's complete plan for this world. They are the root from which Christianity sprang and the historical reasons the church had for leaving them behind were unsound." Judah Himango
Judah Himango wrote:
var list2ElementsNotInList1 = list2.Where(el => !list1.Contains(el));
Hey Judah, I would probably replace that with :
var list2ElementsNotInList1 = list2.Except(list1);
Regards, Nish
Nish’s thoughts on MFC, C++/CLI and .NET (my blog)
My latest book : C++/CLI in Action / Amazon.com link -
Sweet! I love these! Is it cheating to use LINQ?
var list1Allowed = from element in list1
where list2.Contains(element)
select element;var list2ElementsNotInList1 = from element in list2
where !list1.Contains(element)
select element;var result = list1Allowed.Concat(list2ElementsNotInList1);
Alternately, since we're not doing any fabulous let clauses, we could just call the extension methods directly for a more terse syntax:
var list1Allowed = list1.Where(el => list2.Contains(el));
var list2ElementsNotInList1 = list2.Where(el => !list1.Contains(el));
var result = list1Allowed.Concat(list2ElementsNotInList1);Nifty! I :heart: LINQ. :)
Life, family, faith: Give me a visit. From my latest post: "The themes and truths of the Jewish holidays follow God's complete plan for this world. They are the root from which Christianity sprang and the historical reasons the church had for leaving them behind were unsound." Judah Himango
In fact this would be even more straightforward :
var result = list1.Intersect(list2).Concat(list2.Except(list1));
Regards, Nish
Nish’s thoughts on MFC, C++/CLI and .NET (my blog)
My latest book : C++/CLI in Action / Amazon.com link -
In fact this would be even more straightforward :
var result = list1.Intersect(list2).Concat(list2.Except(list1));
Regards, Nish
Nish’s thoughts on MFC, C++/CLI and .NET (my blog)
My latest book : C++/CLI in Action / Amazon.com link -
:cool:
You must be careful in the forest Broken glass and rusty nails If you're to bring back something for us I have bullets for sale...
Thank you :-)
Regards, Nish
Nish’s thoughts on MFC, C++/CLI and .NET (my blog)
My latest book : C++/CLI in Action / Amazon.com link -
var list1 = ['A','B','C','D'];
var list2 = ['B','A','X','S','L','D'];var result = list1.filter(function(i) list2.indexOf(i) >= 0)
.concat( list2.filter(function(i) list1.indexOf(i) < 0 ) );Javascript 1.8 (tested on Firefox 3.0.1)
You must be careful in the forest Broken glass and rusty nails If you're to bring back something for us I have bullets for sale...
Ah you have a one-liner too I see - in fact the same algorithm as the one in mine.
Regards, Nish
Nish’s thoughts on MFC, C++/CLI and .NET (my blog)
My latest book : C++/CLI in Action / Amazon.com link -
Ah you have a one-liner too I see - in fact the same algorithm as the one in mine.
Regards, Nish
Nish’s thoughts on MFC, C++/CLI and .NET (my blog)
My latest book : C++/CLI in Action / Amazon.com link