In this video, we will walk through the Find Intersection Challenge. We'll analyze various solutions, their time complexities and how to find a linear time solution using hash tables.
Link to challengeLink to an article walkthrough
1.What if 2 strings are of different length, 10,20,30,40 10,20,25,30,40 or vise versa, by pushing longer string in to a map, we will miss possible elements in intersection set. 2. Resulting array could be just a string builder.Thanks
@NerseKirjak You bring up some great points on how we can further explore this problem. The current implementation makes assumptions that 1. both arrays of strings are sorted 2. each string has unique numbers 3. both strings are of equal length We could do a few things to account for this:
Instead of saving true in the map, we instead save the count to account for duplicates
We can check the lengths of the two strings and use the smaller string to make the map
Any further thoughts on what you could do with this?
this solution is iterating through the array multiple times to get to the actual problem. while we can create the numbers and compare them just in 1 time and to lower the time complexity we can push the starting index of nested loop to the last index we found a match, since the list is sorted.
For me, a simpler approach would be to add the 2 strings, create a set of unique numbers from the concatenated string and then loop through the set checking for strings that appear more than once in the string and voila!
functionFindIntersection(strArr) {
let singleItems = [];
let repeatItems = [];
strArr = strArr
.join(",")
.split(",")
.sort((a, b) => {
return a - b;
});
strArr.forEach((str) => {
if (singleItems.indexOf(str) > -1) repeatItems.push(str);
singleItems.push(str);
});
repeatItems.join(",");
return repeatItems;
}
Also, the main method code needs to be changed. I get a syntax error stating that FindIntersection method type (String[]) is not applicable for the arguments (String). Does anyone else see it?
We could do a few things to account for this:
Any further thoughts on what you could do with this?
function FindIntersection(strArr) { let singleItems = []; let repeatItems = []; strArr = strArr .join(",") .split(",") .sort((a, b) => { return a - b; }); strArr.forEach((str) => { if (singleItems.indexOf(str) > -1) repeatItems.push(str); singleItems.push(str); }); repeatItems.join(","); return repeatItems; }
package basic; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; public class StringRetain { public static String FindIntersection(String[] strArr) { try { String list1 = strArr[0]; String[] list1Array = list1.split(", "); String list2 = strArr[1]; String[] list2Array = list2.split(", "); Collection<String> listOne = new ArrayList<String>(Arrays.asList(list1Array)); Collection<String> listTwo = new ArrayList<String>(Arrays.asList(list2Array)); listOne.retainAll(listTwo); // System.out.println("listOne----->" + listOne); if (!listOne.isEmpty()) { String separatedStr = String.join(",", listOne); // System.out.println("separatedStr----->" + listOne); return separatedStr; } else { return "false"; } } catch (Exception e) { return "false"; } } public static void main(String[] args) { String[] strArr = new String[] { "11, 12, 14, 16, 20", "11, 12, 13, 18, 21" }; System.out.println("strArr--->" + FindIntersection(strArr)); } }
function FindIntersection(strArr) { let chooseArray = 0; let result = []; let arr1 = strArr[0].split(',').map(a => Number(a)); let arr2 = strArr[1].split(',').map(a => Number(a)); if (arr1.length > arr2.length) { chooseArray = 0; } else { chooseArray = 1 } let n = chooseArray === 0 ? arr1.length : arr2.length; for (let i = 0; i < n; i++) { if (chooseArray === 0) { if (arr2.includes(arr1[i])) { result.push(arr1[i]); } } else if (chooseArray === 1) { if (arr1.includes(arr2[i])) { result.push(arr2[i]); } } } // code goes here return result && result.length ? result.join(',') : false; } // keep this function call here console.log(FindIntersection(readline()));
public static string FindIntersection(string[] strArr) { try { string list1 = strArr[0]; string[] list1Array = list1.Split(','); string list2 = strArr[1]; string[] list2Array = list2.Split(','); Collection<string> listOne = new Collection<string>(list1Array); Collection<string> listTwo = new Collection<string>(list2Array); listOne.Intersect(listTwo); if(listOne.Count > 0) { string separatedStr = string.Join(",", listOne); return separatedStr; } else { return "false"; } } catch (Exception) { return "false"; } } public static void main(string[] args) { string[] strArr = new string[] { "11, 12, 14, 16, 20", "11, 12, 13, 18, 21" }; Console.WriteLine("strArr--->" + FindIntersection(strArr)); }