0

Problem statement:

Design an algorithm that, given two lists of integers, creates a list consisting of those integers that appear in both lists (each integer on the final list should appear only once). Describe your algorithm in terms of a pseudocode focusing on main algorithmic tasks and not on low-level details. Analyze the running time of your algorithm. You will get full credit only if your algorithm achieves an asymptotically better worst-case performance than Θ(n^2), where n is the sum of the lengths of the two input lists

Can someone explain to me what this question is actually asking me to do?

My attempt:

I was under the impression that this question was telling me to make a algorithm that has two lists, idk, so maybe two arrays, one A, one B, where those arrays would be filled with numbers and I would take both of those lists and essentially put them together? I used MergeSort to sort them (which now I think may not be necesarry) then I used Merge to put the two lists actually together.

Question:

I am being told that is wrong. I'm thinking I must be misinterpeting the question. I also used merge sort because its O(nlogn).
What is the problem with my answer, what am I missing?

C8H10N4O2
  • 18,312
  • 8
  • 98
  • 134
  • 1
    "... creates a list consisting of those integers that appear in both lists ..." seems pretty clear to me. The returned list should contain only numbers that exist at least once in both of the input lists. I would suggest a solution that sorts both of the input lists (probably `O(n lg n)`, unless there are additional facts you can guarantee about the inputs), and then a linear scan over both lists to find the intersection (`O(n)`, leaving the overall algorithm at `O(n lg n)`). – twalberg Nov 03 '15 at 21:48

1 Answers1

0

The question asks you to find the intersection set of the two lists, or in other words - a list that contains only the elements that appear both in A and in B (but not elements that appear only in one of them).

It seems your algorithm is just combining the lists, and thus includes elements that appear only in one list.

There are several ways to do it:

  1. Sort both lists, then iterate in parallel
  2. Insert one list to hash table, then iterate the 2nd and print elements in the hash table (remember to remove elements found to avoid printing elements twice)
  3. Same approach as (2), but uses a Tree-Set instead, to ensure O(nlogn) worst case.

I deliberately left the implementation details vague, so you can solve this assignment on your own.

Good luck!

Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333
  • Thank you so much amit, it seems I misinterpreted the question. By using method 1 that you provided, I could use Merge Sort on the first list which would give me O(n), then I could use Merge Sort on the second list which could give me O(n), then I can iterate parallel which will also be O(n) so I will finally have O(n) + O(n) + O(n) = O(n). Does this sound at all on the right track? –  Nov 03 '15 at 23:23
  • @Shammy Sorting using merge sort is `O(nlogn)` – amit Nov 05 '15 at 22:16