StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This is a pretty simple problem since you already have an ordered list.</p> <pre><code>//this is very rough pseudocode stack aList; stack bList; List resultList; char aVal; char bVal; while(aList.Count > 0 || bList.Count > 0) { aVal = aList.Peek; //grab the top item in A bVal = bList.Peek; //grab the top item in B if(aVal < bVal || bVal == null) { resultList.Add(new Tuple(aList.Pop(), null))); } if(bVal < aVal || aVal == null) { resultList.Add(new Tuple(null, bList.Pop())); } else //equal { resultList.Add(new Tuple(aList.Pop(), bList.Pop())); } } </code></pre> <p>Note... this code WILL NOT compile. It is just meant as a guide.</p> <p><strong>EDIT</strong> Based on the OP comments</p> <p>If the ordering algorithm is not exposed, then the lists <em>must</em> be considered unordered. If the lists are unordered, then the algorithm has a time complexity of O(n^2), specifically O(nm) where n and m are the number of items in each list.</p> <p><strong>EDIT</strong> Algorithm to solve this</p> <p>L(a,b,c,d,e) R(b,q,c,d,g,e)</p> <pre><code>//pseudo code... will not compile //Note, this modifies aList and bList, so make copies. List aList; List bList; List resultList; var aVal; var bVal; while(aList.Count > 0) { aVal = aList.Pop(); for(int bIndex = 0; bIndex < bList.Count; bIndex++) { bVal = bList.Peek(); if(aVal.RelevantlyEquivalentTo(bVal) { //The bList items that come BEFORE the match, are definetly not in aList for(int tempIndex = 0; tempIndex < bIndex; tempIndex++) { resultList.Add(new Tuple(null, bList.Pop())); } //This 'popped' item is the same as bVal right now resultList.Add(new Tuple(aVal, bList.Pop())); //Set aVal to null so it doesn't get added to resultList again aVal = null; //Break because it's guaranteed not to be in the rest of the list break; } } //No Matches if(aVal != null) { resultList.Add(new Tuple(aVal, null)); } } //aList is now empty, and all the items left in bList need to be added to result set while(bList.Count > 0) { resultList.Add(new Tuple(null, bList.Pop())); } </code></pre> <p>The result set will be</p> <p>L(a,b,c,d,e) R(b,q,c,d,g,e)</p> <p>Result ((a,null),(b,b),(null,q),(c,c),(d,d),(null,g),(e,e))</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload