Question

Triplicates. Given three lists of N names each, devise a linearithmic algorithm to determine if there is any name common to all three lists, and if so, return the first such name

Answer 1

Hi buddy, I can give you two solutions. 1. Using HashMap<String,Integer>. It stores the count of a certain String. If we ever encounter a string of count 3 while dealing with the third list. We will stop processing and return the string as the answer.

Java Program : (Comments have been added for your better understanding)

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
   public static void main (String[] args) throws java.lang.Exception
   {
   //This is list 1
       ArrayList<String> l1 = new ArrayList();
      
       //I'm loading the list with the sample data
       String s1[] = new String[]{"a","b","c","d","b"};
       for(String x : s1){
       l1.add(x);
       }
      
       //This is list2 and loading the list with the sample data
       ArrayList<String> l2 = new ArrayList();
       String s2[] = new String[]{"b","d","b","c","p"};
       for(String x : s2){
       l2.add(x);
       }
      
       //This is list3 and loading the list with the sample data
       ArrayList<String> l3 = new ArrayList();
       String s3[] = new String[]{"z","q","a","b","d"};
       for(String x : s3){
       l3.add(x);
       }
      
       //Initializing the hash map
       HashMap<String,Integer> count = new HashMap();
      
       //This loop iterates through all the elements in the list 1 and assigns a count
       //of 1 to all the Strings in this list
       for(String x : l1){
       if(!count.containsKey(x)){
       count.put(x,1);
       }
       }
      
       //This loop iterates through all the elements in the list 2 and assigns a count of
       //2 If this String already exists in the map
       for(String x : l2){
       if(count.containsKey(x)){
       count.put(x,2);
       }
       }
      
       //This loop iterates through all the elements in the list 3 and Prints the first
       //String whose count in the hash map is 2 (i.e this string exists in all the three lists)
       for(String x : l3){
       if(count.containsKey(x)&&count.get(x)==2){
       System.out.println("The First String common to all the lists is : "+x);
       return;
       }
       }
   }
}

OUTPUT:

The First String common to all the lists is : b

-----------------------------------------------------------------------------------------------------------------------------------------------

2. This is a bit complex and involves another data structure called "Trie" (Suffix Tree). I would suggest you to search for Trie/Suffix tree for further information. It is very useful and important data structure.