Find the Duplicates
Sometimes you need to compare lists of number, but sorting each one normally will take too much time. Instead you can use alternative methods to find the differences between each list. Try to find a faster way to do this challenge than sorting two entire lists.
Challenge
Numeros The Artist was arranging two identical lists of numbers A and B into specific orders. While it seemed like two random arrangements to everyone else, Numeros was very proud of his arrangements. Unfortunately, some numbers got left out of List A. Can you find the missing numbers from A without messing up his order?
Details
There are many duplicates in each list, but you need to find the extra numbers in B that remain once all the AB "matches" have been found. The numbers are all within a range of 100 from each other.
Guideline
Don't sort the lists to solve this problem. In fact, you can solve it with one pass through each of the lists.
Input
The first line will contain T, the number of test cases. Each test case will contain
four lines of input:
n - the size of the first list
This is followed by n numbers that makes up the first list.
m - the size of the second list
This is followed by m numbers that makes up the second list.
Sample Input
1 2 10 203 204 205 206 207 208 203 204 205 206 13 203 204 204 205 206 207 205 208 203 206 204 205 206
Sample Output
204 205 206
These numbers are extra in the 2nd list. Note each list can be in any order and the extra numbers can appear anywhere in the list.
Note
The boilerplate code needs to be modified so you can get both lists of numbers in each case.
Challenge
Find all the 'extra' numbers that are in B but not in A, and output them in ascending order.
Please sign in or sign up to submit answers.
Alternatively, you can try out Learneroo before signing up.
Comments
Kendall Ponder
Jun 24, 5:40 PMAm I supposed to change the boilerplate code? Can I pass two arrays to doStuff or do I have to combine both lists in one array?
Learneroo
Jun 24, 5:54 PM@Kendall, you can modify the method however you want. I created boilerplate that does that here: http://www.learneroo.com/user_answers/6879587411
Kendall Ponder
Jun 25, 5:19 PMThe two arrays don't appear to match up at all on the second run. I printed out the first 10 and they didn't match. What am I missing? Thanks!
Learneroo
Jun 25, 9:00 PM@Kendall, the numbers are in different orders in each list. You need to find the extra numbers in list B, preferably without sorting the lists. I added another test case to make it clearer.
Kendall Ponder
Jun 25, 9:44 PMGot it, I interpreted identical lists to mean identical orders. Thanks!