algorithm - Interview: lists intersection with limited memory -


you given 2 sets of integers, sizes m , n m < n. perform inner equal join on these 2 sets (i.e., find intersection of 2 lists). how perform if both lists in files , available memory of size k < m < n

using in-place sorting algorithm sort both lists first.

once both m n sorted, calculating intersection race. place 2 markers a , b @ beginning of each list. these steps until marker reaches end of list. in pseudocode:

until > m.size or b > n.size     if m[a] < n[b]         a++         continue     if n[b] < m[a]         b++         continue     print m[a] // common element     // advance both indexes avoid infinite loop     a++     b++ 

given decent in-place sorting algorithm, complexity of o(nlogn).


Comments

Popular posts from this blog

windows - Why does Vista not allow creation of shortcuts to "Programs" on a NonAdmin account? Not supposed to install apps from NonAdmin account? -

c++ - How do I get a multi line tooltip in MFC -

unit testing - How to mock PreferenceManager in Android? -