Microsoft Interview Question
Software Engineer / DevelopersI think if space complexity is allowed, we can go for TRIES
1. assuming that the input arrays themselves wont have duplicates, we will print all the elements of the first array..
2. Also construct a TRIE using all the elements of the first array..
3. While printing the second array check if the element you are printing now is present in the TRIE. This check will be O(l) where l is the length of the particular string for which you are doing the check.
4. Do this for all the elements in the second array. If not found in the trie, print it else skip it..
complexity: O(n1*l) + O(n2*l) where l is the avg length of a string and n1 and n2 are the number of elements in the 2 arrays resp.
There is another way I have solved this issue. Can you please some one suggest me which is betterway and what is the alternative way to solve this problem?
string[] mergeUnsortedArrayusingHashTable(string[] array1, string[] array2)
{
int arr1len = array1.Length, arr2len = array2.Length;
int i = 0;
string[] outArray = new string[arr1len + arr2len];
Hashtable ht = new Hashtable();
//insert all the element from first array
for (i = 0; i < arr1len; i++)
{
if (!ht.Contains(array1[i]))
ht.Add(array1[i], array1[i]);
}
//insert all the element from second array
for (i = 0; i < arr2len; i++)
{
if (!ht.Contains(array2[i]))
ht.Add(array2[i], array2[i]);
}
i = 0;
foreach (object key in ht.Keys)
{
outArray[i++] = key.ToString();
}
return outArray;
}
sometimes i feel annoying to visit this site as every body posts only code solutions, no one posts the algo or pseudo code which makes it easy to understand the code,
anyways i think we can join to arrays and use merge sort on this and delete all the repeating values from it, the complexity will be nlogn(n+nlogn)
if extra memory is allowed we can merge all the strings of Arr1 into str1 and Arr2 in str2.
str1 = "are you there"
str2 = "How are you".
now we can easily get
str3 = "How are you there" in one pass.
then split str3 and return.
It will not be as efficient as hash table approach but just another approach.
Can't we use a hash table?
- Anonymous March 16, 20111) Take array 1 push all the elements into the Table.
2) Take array 2 before we push keep checking if the key already exists if it does discard the element of array 2. Else insert into the table
3) Print out values in the table.