Epic Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
Solution 1:
1. Initialize a HashSet 'set'.
2. set.add(list1.items);
3. set.add(list2.items);
4. return set;
Time: O(m+n);
Space: O(m+n);
Solution 2:
n = list1.size();
m = list2.size();
1. Sort list1. O(nlogn)
2. Sort list2. O(mlogm)
3. Merge (list1,list2). O(n+m)
Time: O(nlogn + mlogm + n + m) = O(nlogn + mlogm)
Space: O(1)
Clarification.
One roommate says 2 bottles of milk, and other says 1 bottle. How to choose?
import java.util.ArrayList;
import java.util.HashSet;
public class CombineLists
{
public static ArrayList<String> getCombinedList(String[] l1, String[] l2)
{
HashSet<String> hashSet = new HashSet<String>();
ArrayList<String> combinedList = new ArrayList<String>();
for (int i = 0; i < l1.length; i++)
{
if (hashSet.add(l1[i].toLowerCase()))
{
combinedList.add(l1[i]);
}
}
for (int i = 0; i < l2.length; i++)
{
if (!hashSet.contains(l2[i].toLowerCase()))
{
combinedList.add(l2[i]);
}
}
return combinedList;
}
public static void main(String[] args)
{
String[] l1 = { "a", "b", "c", "d", "e" };
String[] l2 = { "f", "b", "g", "d", "h" };
ArrayList<String> combinedList = getCombinedList(l1, l2);
for (String item : combinedList)
System.out.println(item);
}
}
Why you need a separate arraylist to print, u can iterate through Hashset itself using Iterator.
Saves space
This can be accomplished using a HashSet as it does not allows duplicate elements. Suppose there are m elements in list1 and n elements in list2; The overall time complexity will be linear and space will be m+n.
- SumitGaur April 25, 2014