Amazon Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
Very trick question to code. I am not very happy because of many conditional checks...
package problems;
import java.util.*;
/**
* Created by fsantos on 2/9/17.
*/
public class Prob149 {
public static void merge(List<String> l1, List<String> l2, List<String> l3) {
int i1 = 0;
int i2 = 0;
int i3 = 0;
while (i1 < l1.size() && i2 < l2.size() && i3 < l3.size()) {
if (l1.get(i1).compareTo(l2.get(i2)) < 0) {
// l1 < l2
if (l1.get(i1).compareTo(l3.get(i3)) < 0) {
// l1 < l3
System.out.println(l1.get(i1));
if (l2.get(i2).compareTo(l1.get(i1)) == 0) i2++;
if (l3.get(i3).compareTo(l1.get(i1)) == 0) i3++;
i1++;
} else {
// l3 < l1
System.out.println(l3.get(i3));
if (l1.get(i1).compareTo(l3.get(i3)) == 0) i1++;
if (l2.get(i2).compareTo(l3.get(i3)) == 0) i2++;
i3++;
}
} else {
// l2 < l1
if (l2.get(i2).compareTo(l3.get(i3)) < 0) {
// l2 < l3
System.out.println(l2.get(i2));
if (l1.get(i1).compareTo(l2.get(i2)) == 0) i1++;
if (l3.get(i3).compareTo(l2.get(i2)) == 0) i3++;
i2++;
} else {
// l3 < l2
System.out.println(l3.get(i3));
if (l1.get(i1).compareTo(l3.get(i3)) == 0) i1++;
if (l2.get(i2).compareTo(l3.get(i3)) == 0) i2++;
i3++;
}
}
}
if (i3 < l3.size()) {
if (i1 > l1.size()) {
i1 = i2;
l1 = l2;
} else {
i2 = i3;
l2 = l3;
}
}
while (i1 < l1.size() && i2 < l2.size()) {
if (l1.get(i1).compareTo(l2.get(i2)) < 0) {
System.out.println(l1.get(i1));
if (l2.get(i2).compareTo(l1.get(i1)) == 0) i2++;
i1++;
} else {
System.out.println(l2.get(i2));
if (l2.get(i2).compareTo(l1.get(i1)) == 0) i2++;
i2++;
}
}
if (i2 < l2.size()) {
i1 = i2;
l1 = l2;
}
while (i1 < l1.size()) {
System.out.println(l1.get(i1++));
}
}
public static void main(String[] args) {
merge(Arrays.asList("aaa", "bbb", "ddd", "xyxz"),
Arrays.asList("bbb", "ccc", "ccc", "hkp"),
Arrays.asList("ddd", "eee", "ffff", "lmn"));
}
}
Output:
aaa
bbb
ccc
ccc
ddd
eee
ffff
hkp
lmn
xyxz
Now I am a little bit happier with the code. It is using additional space to do 2 steps of merge but the code is clean:
package problems;
import java.util.*;
/**
* Created by fsantos on 2/9/17.
*/
public class Prob149 {
public static void mergeUsingAdditionalSpace(List<String> l1, List<String> l2, List<String> l3) {
List<String> l4 = merge(l1, l2);
List<String> l5 = merge(l4, l3);
for (String s: l5)
System.out.println(s);
}
private static List<String> merge(List<String> l1, List<String> l2) {
List<String> t = new ArrayList<>();
int i1 = 0;
int i2 = 0;
while (i1 < l1.size() && i2 < l2.size()) {
int cmp = l1.get(i1).compareTo(l2.get(i2));
if (cmp == 0) {
t.add(l1.get(i1));
i1++;
i2++;
} else if (cmp < 0) {
t.add(l1.get(i1++));
} else {
t.add(l2.get(i2++));
}
}
if (i2 < l2.size()) {
i1 = i2;
l1 = l2;
}
while (i1 < l1.size())
t.add(l1.get(i1++));
return t;
}
public static void main(String[] args) {
mergeUsingAdditionalSpace(Arrays.asList("aaa", "bbb", "ddd", "xyxz"),
Arrays.asList("bbb", "ccc", "ccc", "hkp"),
Arrays.asList("ddd", "eee", "ffff", "lmn"));
}
}
Output:
aaa
bbb
ccc
ccc
ddd
eee
ffff
hkp
lmn
xyxz
This question has deep formulation problem - of speaking in English.
Observe the following :
l1 = [ 1,1,1,1,1,1,2]
l2 = [1,2]
l3 = [ ]
What is the expected output?
Now, coming back again :
l1 = [ 1,1,1,1,1,1,2]
l2 = [1,2,2,2,2,2,2]
l3 = [ ]
what will be the output?
Moreover :
l1 = [ 1,2]
l2 = [2,3]
l3 = [1,3]
what will be the output?
The terms *repeated across* is not properly defined - in conjunction with
*it is ok to have repeated item in a list*.
I think we should remove duplicate strings if be in more than one list, so bbb can not be in the output
package com.company;
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
String[] list1 = new String[]{"aaa","bbb","ddd","xyxz"};
String[] list2 = new String[]{"bbb","ccc","ccc","hkp"};
String[] list3 = new String[]{"ddd","eee","fff","lmn"};
solutionProblem(list1,list2,list3);
}
static int index1 =0;
static int index2 =0;
static int index3 =0;
private static void solutionProblem(String[] list1, String[] list2, String[] list3) {
ArrayList<String> outputArray = new ArrayList<>();
while(true){
String outputInfo = FetchCondidate(list1,list2,list3);
if(outputInfo!=""){
outputArray.add(outputInfo);
}
if(index1>=list1.length && index2>=list2.length && index3 >=list3.length){
break;
}
}
System.out.println(outputArray.toString());
}
private static String FetchCondidate(String[] list1, String[] list2, String[] list3) {
String str1="",str2="",str3="";
if(index1<list1.length){
str1 = list1[index1];
}
if(index2<list2.length){
str2 = list2[index2];
}
if(index3<list3.length){
str3 = list3[index3];
}
return FindMinValueAndSetIndexes(str1,str2,str3);
}
private static String FindMinValueAndSetIndexes(String str1, String str2, String str3) {
int findedIndex =0;
findedIndex = Compaire(str1,str2,str3);
switch (findedIndex){
case 1:
index1++;
return str1;
case 2:
index2++;
return str2;
case 3:
index3++;
return str3;
}
return "";
}
private static int Compaire(String str1, String str2, String str3) {
int returnVal =0;
returnVal = Compaire(str1,str2,1,2);
if(returnVal ==1){
return Compaire(str1,str3,1,3);
}
if(returnVal ==2){
return Compaire(str2,str3,2,3);
}
return returnVal;
}
private static int Compaire(String str1, String str2,int si1,int si2) {
if(str1 == "")
return si2;
if(str2 =="")
return si1;
int cmpVal = str1.compareTo(str2);
if(cmpVal ==0){
if(si1 == 1 || si2 ==1){
index1++;
}
if(si1 == 2 || si2 ==2){
index2++;
}
if(si1 == 3 || si2 ==3){
index3++;
}
return 0;
}
if(cmpVal<0)
return si1;
return si2;
}
}
The Time Order is O(N), outputArray is not necessary.
Here is the code in the most simplified version I guess
public class ListWords {
public static void main(String[] args) {
ArrayList<String> list1 = new ArrayList<String>();
list1.add("aaa");
list1.add("bbb");
list1.add("ddd");
list1.add("xyxy");
ArrayList<String> list2 = new ArrayList<String>();
list2.add("bbb");
list2.add("ccc");
list2.add("ccc");
list2.add("hkp");
ArrayList<String> list3 = new ArrayList<String>();
list3.add("ddd");
list3.add("eee");
list3.add("fff");
list3.add("lmnn");
ArrayList<String> list = new ArrayList<String>();
list.addAll(list3);
list.addAll(list2);
list.addAll(list1);
Collections.sort(list);
System.out.println(list);
for (int i = 0; i < list.size(); i++) {
if(list1.contains(list.get(i)) &&
(list2.contains(list.get(i)) ||
list3.contains(list.get(i)))){
list.remove(list.get(i));
}if(list2.contains(list.get(i)) &&
(list1.contains(list.get(i)) ||
list3.contains(list.get(i)))){
list.remove(list.get(i));
}if(list3.contains(list.get(i)) &&
(list2.contains(list.get(i)) ||
list1.contains(list.get(i)))){
list.remove(list.get(i));
}if(list1.contains(list.get(i)) &&
list2.contains(list.get(i)) &&
list3.contains(list.get(i))){
list.remove(list.get(i));
}
}
System.out.println(list);
}
}
def merge(l1: List[String], l2: List[String], l3: List[String]): List[String] = {
def mergeTwo(xs1: List[String], xs2: List[String], r: List[String]): List[String] =
if (xs1.isEmpty && xs2.isEmpty) r
else {
val union = Seq(xs1.headOption, xs2.headOption).flatten
val nextOpt = if (union.size != union.distinct.size) None else Some(union.min)
val newR = nextOpt.map(r :+ _).getOrElse(r)
val tail1 = if (xs1.isEmpty) xs1 else if (nextOpt.isEmpty || nextOpt.contains(xs1.head)) xs1.tail else xs1
val tail2 = if (xs2.isEmpty) xs2 else if (nextOpt.isEmpty || nextOpt.contains(xs2.head)) xs2.tail else xs2
mergeTwo(tail1, tail2, newR)
}
val tmp = mergeTwo(l1, l2, Nil)
mergeTwo(tmp, l3, Nil)
}
private static List<String> merge(String [] arr1,String [] arr2,String [] arr3){
int n1=arr1.length; int n2=arr2.length; int n3=arr3.length;
int l1=0,l2=0,l3=0;
List<String> res=new ArrayList<String>();
while(l1<n1 || l2<n2 || l3<n3){
String s1=l1<n1?arr1[l1]:"";
String s2=l2<n2?arr2[l2]:"";
String s3=l3<n3?arr3[l3]:"";
if(s1!="" && s2!="" && s3!=""){
if(s1.equals(s2) && s2.equals(s3)){ l1++;l2++;l3++;}
else if(s1.equals(s2)){ l1++; l2++;}
else if(s2.equals(s3)){ l1++; l3++;}
else if(s1.equals(s3)){ l1++; l3++;}
else{
int i1=s1.compareTo(s2); int i2=s1.compareTo(s3);
if(i1<0 && i2<0){ res.add(s1); l1++;}
i1=s2.compareTo(s3); i2=s2.compareTo(s1);
if(i1<0 && i2<0){ res.add(s2); l2++;}
i1=s3.compareTo(s2); i2=s3.compareTo(s1);
if(i1<0 && i2<0){ res.add(s3); l3++;}
}
}
else if(s1!="" && s2!=""){
if(s1.equals(s2)){ l1++; l2++;}
else{
int i1=s1.compareTo(s2);
if(i1<0){ res.add(s1); l1++;}
else{ res.add(s2); l2++;}
}
}
else if(s2!="" && s3!=""){
if(s2.equals(s3)){ l1++; l3++;}
else{
int i1=s2.compareTo(s3);
if(i1<0){ res.add(s2); l2++;}
else{ res.add(s3); l3++;}
}
}
else if(s1!="" && s3!=""){
if(s1.equals(s3)){ l1++; l3++;}
else{
int i1=s1.compareTo(s3);
if(i1<0){ res.add(s1); l1++;}
else{ res.add(s3); l3++;}
}
}
else{
if(s1!=""){ res.add(s1); l1++;}
if(s2!=""){ res.add(s2); l2++;}
if(s3!=""){ res.add(s3); l3++;}
}
}
return res;
}
import java.util.*;
public class DuplicateStrings {
public static void main(String[] args) {
ArrayList<String> list1 = new ArrayList<String>();
list1.add("aaa");
list1.add("bbb");
list1.add("ddd");
list1.add("xyxy");
ArrayList<String> list2 = new ArrayList<String>();
list2.add("bbb");
list2.add("ccc");
list2.add("ccc");
list2.add("hkp");
ArrayList<String> list3 = new ArrayList<String>();
list3.add("ddd");
list3.add("eee");
list3.add("fff");
list3.add("lmnn");
ArrayList<List<String>> list = new ArrayList<>();
ArrayList<String> finalList = new ArrayList<String>();
list.add(list1);
list.add(list2);
list.add(list3);
System.out.println(list1);
System.out.println(list2);
System.out.println(list3);
for (int i = 0; i < list.size()-1; i++) {
System.out.println("List Number :"+i);
List<String> firstList = list.get(i);
String removedItem = "";
for(int j = 0; j < firstList.size(); j++) {
String item1 = firstList.get(j);
System.out.println("Current List "+firstList);
System.out.println(j+" Current item : "+item1);
boolean isPresent = false;
if(item1.equals(removedItem)){
System.out.println(" Removing repeated item : "+item1);
firstList.remove(j);
j--;
continue;
}
for(int k = i+1; k < list.size(); k++) {
List<String> secondList = list.get(k);
System.out.println("Searching item "+item1+" in list : "+secondList);
for(int l = 0; l < secondList.size(); l++){
String item2 = secondList.get(l);
if( item1.compareTo(item2) < 0 )
{
break;
}
else if(item1.compareTo(item2) > 0 ){
continue;
}
else {
isPresent = true;
secondList.remove(l);
l--;
}
}
}
if(isPresent){
System.out.println("Removing item :"+item1+" from list :"+i);
firstList.remove(j);
removedItem = item1;
j--;
}
else{
System.out.println("Adding item :"+item1+" to the final list from list "+firstList);
finalList.add(item1);
}
}
}
finalList.addAll(list.get(list.size()-1));
System.out.println(finalList);
}
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SortedAndFilteredList {
private List<String> aList = null;
private List<String> bList = null;
private List<String> cList = null;
public SortedAndFilteredList(List<String> aList, List<String> bList, List<String> cList) {
this.aList = aList;
this.bList = bList;
this.cList = cList;
}
public List<String> sortAndFilter() {
List<String> aListElementsToBeRemoved = new ArrayList<>();
for (String element : aList) {
if (bList.contains(element)) {
bList.remove(element);
aListElementsToBeRemoved.add(element);
}
if (cList.contains(element)) {
cList.remove(element);
if (!aListElementsToBeRemoved.contains(element)) {
aListElementsToBeRemoved.add(element);
}
}
}
aList.removeAll(aListElementsToBeRemoved);
List<String> bListElementsToBeRemoved = new ArrayList<>();
for (String element : bList) {
if (cList.contains(element)) {
cList.remove(element);
bListElementsToBeRemoved.add(element);
}
}
bList.removeAll(bListElementsToBeRemoved);
aList.addAll(bList);
aList.addAll(cList);
Collections.sort(aList);
return aList;
}
public static void main(String[] args) {
List<String> aList = new ArrayList<>();
aList.add("aaa");
aList.add("bbb");
aList.add("ddd");
aList.add("xyxz");
List<String> bList = new ArrayList<>();
bList.add("bbb");
bList.add("ccc");
bList.add("ccc");
bList.add("hkp");
List<String> cList = new ArrayList<>();
cList.add("ddd");
cList.add("eee");
cList.add("ffff");
cList.add("lmn");
SortedAndFilteredList sortedAndFilteredList = new SortedAndFilteredList(aList, bList, cList);
List<String> filteredList = sortedAndFilteredList.sortAndFilter();
for (String str : filteredList) {
System.out.println(str);
}
}
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SortedAndFilteredList {
private List<String> aList = null;
private List<String> bList = null;
private List<String> cList = null;
public SortedAndFilteredList(List<String> aList, List<String> bList, List<String> cList) {
this.aList = aList;
this.bList = bList;
this.cList = cList;
}
public List<String> sortAndFilter() {
List<String> aListElementsToBeRemoved = new ArrayList<>();
for (String element : aList) {
if (bList.contains(element)) {
bList.remove(element);
aListElementsToBeRemoved.add(element);
}
if (cList.contains(element)) {
cList.remove(element);
if (!aListElementsToBeRemoved.contains(element)) {
aListElementsToBeRemoved.add(element);
}
}
}
aList.removeAll(aListElementsToBeRemoved);
List<String> bListElementsToBeRemoved = new ArrayList<>();
for (String element : bList) {
if (cList.contains(element)) {
cList.remove(element);
bListElementsToBeRemoved.add(element);
}
}
bList.removeAll(bListElementsToBeRemoved);
aList.addAll(bList);
aList.addAll(cList);
Collections.sort(aList);
return aList;
}
public static void main(String[] args) {
List<String> aList = new ArrayList<>();
aList.add("aaa");
aList.add("bbb");
aList.add("ddd");
aList.add("xyxz");
List<String> bList = new ArrayList<>();
bList.add("bbb");
bList.add("ccc");
bList.add("ccc");
bList.add("hkp");
List<String> cList = new ArrayList<>();
cList.add("ddd");
cList.add("eee");
cList.add("ffff");
cList.add("lmn");
SortedAndFilteredList sortedAndFilteredList = new SortedAndFilteredList(aList, bList, cList);
List<String> filteredList = sortedAndFilteredList.sortAndFilter();
for (String str : filteredList) {
System.out.println(str);
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication13
{
class Program
{
static void Main(string[] args)
{
List<string> list1 = new List<string>(){"aaa","bbb","ddd","xyxz"};
List<string> list2 = new List<string>(){"bbb","ccc","ccc","hkp"};
List<string> list3 = new List<string>() {"ddd","eee", "ffff", "lmn"};
List<string> result = new List<string>();
for (int i = list1.Count - 1; i >= 0; i--) {
if ( list2.Contains(list1[i])) {
list2.Remove(list1[i]);
list1.RemoveAt(i);
}
}
for (int i = list1.Count - 1; i >= 0; i--) {
if (list3.Contains(list1[i]))
{
list3.Remove(list1[i]);
list1.RemoveAt(i);
}
}
for (int i = list2.Count - 1; i >= 0; i--) {
if (list3.Contains(list2[i]))
{
list3.Remove(list2[i]);
list2.RemoveAt(i);
}
}
if (list1.Any())
result = list1;
if (list2.Any())
result.AddRange(list2);
if (list3.Any())
result.AddRange(list3);
result.Sort();
foreach( var entity in result)
{
Console.Write("{0} --->", entity);
}
Console.ReadLine();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication13
{
class Program
{
static void Main(string[] args)
{
List<string> list1 = new List<string>(){"aaa","bbb","ddd","xyxz"};
List<string> list2 = new List<string>(){"bbb","ccc","ccc","hkp"};
List<string> list3 = new List<string>() {"ddd","eee", "ffff", "lmn"};
List<string> result = new List<string>();
for (int i = list1.Count - 1; i >= 0; i--) {
if ( list2.Contains(list1[i])) {
list2.Remove(list1[i]);
list1.RemoveAt(i);
}
}
for (int i = list1.Count - 1; i >= 0; i--) {
if (list3.Contains(list1[i]))
{
list3.Remove(list1[i]);
list1.RemoveAt(i);
}
}
for (int i = list2.Count - 1; i >= 0; i--) {
if (list3.Contains(list2[i]))
{
list3.Remove(list2[i]);
list2.RemoveAt(i);
}
}
if (list1.Any())
result = list1;
if (list2.Any())
result.AddRange(list2);
if (list3.Any())
result.AddRange(list3);
result.Sort();
foreach( var entity in result)
{
Console.Write("{0} --->", entity);
}
Console.ReadLine();
}
}
}
import java.io.*;
import java.util.*;
public class Array1{
public static void main(String args[])
{
ArrayList<String> list1 = new ArrayList<String>();
list1.add("aaa");
list1.add("bbb");
list1.add("ddd");
list1.add("xyxy");
ArrayList<String> list2 = new ArrayList<String>();
list2.add("bbb");
list2.add("ccc");
list2.add("ccc");
list2.add("hkp");
ArrayList<String> list3 = new ArrayList<String>();
list3.add("ddd");
list3.add("eee");
list3.add("xyxy");
list3.add("hkp");
ArrayList<String> list=new ArrayList<String>();
list.addAll(list1);
list.addAll(list2);
list.addAll(list3);
Collections.sort(list);
System.out.println(list);
for(int i=0;i<list1.size();i++)
{
for (int j=0;j<list2.size();j++)
{
if((list1.get(i)).equals(list2.get(j)))
{
for(int k=0;k<list.size();k++)
{
if((list.get(k)).equals(list2.get(j)))
{
list.remove(list.get(k));
k=k-1;
System.out.println("list size is:"+list.size());
}
}
}
}
}
for(int i=0;i<list2.size();i++)
{
for (int j=0;j<list3.size();j++)
{
if((list2.get(i)).equals(list3.get(j)))
{
for(int k=0;k<list.size();k++)
{
if((list.get(k)).equals(list3.get(j)))
{
list.remove(list.get(k));
k=k-1;
System.out.println("list size is:"+list.size());
}
}
}
}
}
for(int i=0;i<list1.size();i++)
{
for (int j=0;j<list3.size();j++)
{
if((list1.get(i)).equals(list3.get(j)))
{
for(int k=0;k<list.size();k++)
{
if((list.get(k)).equals(list3.get(j)))
{
list.remove(list.get(k));
k=k-1;
System.out.println("list size is:"+list.size());
}
}
}
}
}
System.out.println(list);
}
}
import java.io.*;
import java.util.*;
public class Array1{
public static void main(String args[])
{
ArrayList<String> list1 = new ArrayList<String>();
list1.add("aaa");
list1.add("bbb");
list1.add("ddd");
list1.add("xyxy");
ArrayList<String> list2 = new ArrayList<String>();
list2.add("bbb");
list2.add("ccc");
list2.add("ccc");
list2.add("hkp");
ArrayList<String> list3 = new ArrayList<String>();
list3.add("ddd");
list3.add("eee");
list3.add("xyxy");
list3.add("hkp");
ArrayList<String> list=new ArrayList<String>();
list.addAll(list1);
list.addAll(list2);
list.addAll(list3);
Collections.sort(list);
System.out.println(list);
for(int i=0;i<list1.size();i++)
{
for (int j=0;j<list2.size();j++)
{
if((list1.get(i)).equals(list2.get(j)))
{
for(int k=0;k<list.size();k++)
{
if((list.get(k)).equals(list2.get(j)))
{
list.remove(list.get(k));
k=k-1;
System.out.println("list size is:"+list.size());
}
}
}
}
}
for(int i=0;i<list2.size();i++)
{
for (int j=0;j<list3.size();j++)
{
if((list2.get(i)).equals(list3.get(j)))
{
for(int k=0;k<list.size();k++)
{
if((list.get(k)).equals(list3.get(j)))
{
list.remove(list.get(k));
k=k-1;
System.out.println("list size is:"+list.size());
}
}
}
}
}
for(int i=0;i<list1.size();i++)
{
for (int j=0;j<list3.size();j++)
{
if((list1.get(i)).equals(list3.get(j)))
{
for(int k=0;k<list.size();k++)
{
if((list.get(k)).equals(list3.get(j)))
{
list.remove(list.get(k));
k=k-1;
System.out.println("list size is:"+list.size());
}
}
}
}
}
System.out.println(list);
}
}
import java.io.*;
import java.util.*;
public class Array1{
public static void main(String args[])
{
ArrayList<String> list1 = new ArrayList<String>();
list1.add("aaa");
list1.add("bbb");
list1.add("ddd");
list1.add("xyxy");
ArrayList<String> list2 = new ArrayList<String>();
list2.add("bbb");
list2.add("ccc");
list2.add("ccc");
list2.add("hkp");
ArrayList<String> list3 = new ArrayList<String>();
list3.add("ddd");
list3.add("eee");
list3.add("xyxy");
list3.add("hkp");
ArrayList<String> list=new ArrayList<String>();
list.addAll(list1);
list.addAll(list2);
list.addAll(list3);
Collections.sort(list);
System.out.println(list);
for(int i=0;i<list1.size();i++)
{
for (int j=0;j<list2.size();j++)
{
if((list1.get(i)).equals(list2.get(j)))
{
for(int k=0;k<list.size();k++)
{
if((list.get(k)).equals(list2.get(j)))
{
list.remove(list.get(k));
k=k-1;
System.out.println("list size is:"+list.size());
}
}
}
}
}
for(int i=0;i<list2.size();i++)
{
for (int j=0;j<list3.size();j++)
{
if((list2.get(i)).equals(list3.get(j)))
{
for(int k=0;k<list.size();k++)
{
if((list.get(k)).equals(list3.get(j)))
{
list.remove(list.get(k));
k=k-1;
System.out.println("list size is:"+list.size());
}
}
}
}
}
for(int i=0;i<list1.size();i++)
{
for (int j=0;j<list3.size();j++)
{
if((list1.get(i)).equals(list3.get(j)))
{
for(int k=0;k<list.size();k++)
{
if((list.get(k)).equals(list3.get(j)))
{
list.remove(list.get(k));
k=k-1;
System.out.println("list size is:"+list.size());
}
}
}
}
}
System.out.println(list);
}
}
I have used heap in my solution.
public class RemoveDuplicatesFromLists
{
public static void main(String args[])
{
List<String> list1 = new ArrayList<String>();
list1.addAll(Arrays.asList("aaa", "bbb", "ddd", "xyxz"));
List<String> list2 = new ArrayList<String>();
list2.addAll(Arrays.asList("bbb", "ccc", "ccc", "hkp"));
List<String> list3 = new ArrayList<String>();
list3.addAll(Arrays.asList("ddd", "eee", "ffff", "lmn"));
List<String> result = removeDuplicates(list1,
list2,
list3);
System.out.println(result);
}
public static List<String> removeDuplicates(List<String>... lists)
{
PriorityQueue<HeapEntry> priorityQueue = new PriorityQueue<>(3, new Comparator<HeapEntry>()
{
@Override
public int compare(HeapEntry o1, HeapEntry o2)
{
return o1.data.compareTo(o2.data);
}
});
for (int i = 0; i < lists.length;)
{
if (!lists[i].isEmpty())
{
HeapEntry heapEntry = new HeapEntry(lists[i].remove(0), i);
if (!priorityQueue.contains(heapEntry))
{
priorityQueue.add(heapEntry);
i++;
}
}
}
ArrayList<String> results = new ArrayList<>();
while (true)
{
HeapEntry heapEntry = getNextMax(priorityQueue, lists, null);
if (heapEntry == null)
{
break;
}
results.add(heapEntry.data);
}
return results;
}
private static HeapEntry getNextMax(PriorityQueue<HeapEntry> priorityQueue, List<String>[] lists, HeapEntry previous)
{
if (priorityQueue.isEmpty())
{
return null;
}
HeapEntry entry = priorityQueue.poll();
HeapEntry newHeapEntry = getNextEntry(lists, priorityQueue, entry.listIndex);
if (newHeapEntry != null)
{
priorityQueue.add(newHeapEntry);
}
if (previous == null)
{
previous = priorityQueue.peek();
}
if (previous != null && previous.listIndex != entry.listIndex && entry.data.equals(previous.data))
{
entry = getNextMax(priorityQueue, lists, entry);
}
return entry;
}
private static HeapEntry getNextEntry(List<String>[] lists, PriorityQueue<HeapEntry> priorityQueue, int index)
{
if (lists[index].isEmpty())
{
return null;
}
HeapEntry newHeapEntry = new HeapEntry(lists[index].remove(0), index);
return newHeapEntry;
}
private static class HeapEntry
{
String data;
private int listIndex;
public HeapEntry(String data, int listIndex)
{
this.data = data;
this.listIndex = listIndex;
}
@Override
public boolean equals(Object o)
{
HeapEntry heapEntry = (HeapEntry) o;
return this.data.equals(heapEntry.data);
}
@Override
public int hashCode()
{
return this.data.hashCode();
}
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class Challenge2 {
public static void main(String[] args) {
List<String> l1 = new ArrayList<String>();
List<String> l2 = new ArrayList<String>();
List<String> l3 = new ArrayList<String>();
// for L1 list
l1.add("aaa");
l1.add("bbb");
l1.add("ddd");
l1.add("xyxz");
// for L2 list
l2.add("bbb");
l2.add("ccc");
l2.add("ccc");
l2.add("hkp");
// for L3 list
l3.add("ddd");
l3.add("eee");
l3.add("ffff");
l3.add("lmn");
Map<String, String> map = new HashMap<String, String>();
for (int i = 0; i < l1.size(); i++) {
if (map.put(l1.get(i), "dummy") != null) {
map.remove(l1.get(i));
}
}
for (int i = 0; i < l2.size(); i++) {
if (map.put(l2.get(i), "dummy") != null) {
map.remove(l2.get(i));
}
}
for (int i = 0; i < l3.size(); i++) {
if (map.put(l3.get(i), "dummy") != null) {
map.remove(l3.get(i));
}
}
Iterator<String> iter=map.keySet().iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class Challenge2 {
public static void main(String[] args) {
List<String> l1 = new ArrayList<String>();
List<String> l2 = new ArrayList<String>();
List<String> l3 = new ArrayList<String>();
// for L1 list
l1.add("aaa");
l1.add("bbb");
l1.add("ddd");
l1.add("xyxz");
// for L2 list
l2.add("bbb");
l2.add("ccc");
l2.add("ccc");
l2.add("hkp");
// for L3 list
l3.add("ddd");
l3.add("eee");
l3.add("ffff");
l3.add("lmn");
Map<String, String> map = new HashMap<String, String>();
for (int i = 0; i < l1.size(); i++) {
if (map.put(l1.get(i), "dummy") != null) {
map.remove(l1.get(i));
}
}
for (int i = 0; i < l2.size(); i++) {
if (map.put(l2.get(i), "dummy") != null) {
map.remove(l2.get(i));
}
}
for (int i = 0; i < l3.size(); i++) {
if (map.put(l3.get(i), "dummy") != null) {
map.remove(l3.get(i));
}
}
Iterator<String> iter=map.keySet().iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class Challenge2 {
public static void main(String[] args) {
List<String> l1 = new ArrayList<String>();
List<String> l2 = new ArrayList<String>();
List<String> l3 = new ArrayList<String>();
// for L1 list
l1.add("aaa");
l1.add("bbb");
l1.add("ddd");
l1.add("xyxz");
// for L2 list
l2.add("bbb");
l2.add("ccc");
l2.add("ccc");
l2.add("hkp");
// for L3 list
l3.add("ddd");
l3.add("eee");
l3.add("ffff");
l3.add("lmn");
Map<String, String> map = new HashMap<String, String>();
for (int i = 0; i < l1.size(); i++) {
if (map.put(l1.get(i), "dummy") != null) {
map.remove(l1.get(i));
}
}
for (int i = 0; i < l2.size(); i++) {
if (map.put(l2.get(i), "dummy") != null) {
map.remove(l2.get(i));
}
}
for (int i = 0; i < l3.size(); i++) {
if (map.put(l3.get(i), "dummy") != null) {
map.remove(l3.get(i));
}
}
Iterator<String> iter=map.keySet().iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class Challenge2 {
public static void main(String[] args) {
List<String> l1 = new ArrayList<String>();
List<String> l2 = new ArrayList<String>();
List<String> l3 = new ArrayList<String>();
// for L1 list
l1.add("aaa");
l1.add("bbb");
l1.add("ddd");
l1.add("xyxz");
// for L2 list
l2.add("bbb");
l2.add("ccc");
l2.add("ccc");
l2.add("hkp");
// for L3 list
l3.add("ddd");
l3.add("eee");
l3.add("ffff");
l3.add("lmn");
l3.add("bbb");
Map<String, Integer> map = new HashMap<String, Integer>();
for (int i = 0; i < l1.size(); i++) {
if(map.containsKey(l1.get(i))){
int count=map.get(l1.get(i));
count++;
map.put(l1.get(i), count);
}else{
map.put(l1.get(i), 0);
}
}
for (int i = 0; i < l2.size(); i++) {
if(map.containsKey(l2.get(i))){
int count=map.get(l2.get(i));
count++;
map.put(l2.get(i), count);
}else{
map.put(l2.get(i), 0);
}
}
for (int i = 0; i < l3.size(); i++) {
if(map.containsKey(l3.get(i))){
int count=map.get(l3.get(i));
count++;
map.put(l3.get(i), count);
}else{
map.put(l3.get(i), 0);
}
}
Iterator<String> iter=map.keySet().iterator();
while (iter.hasNext()) {
String value=iter.next();
if(map.get(value)==0){
System.out.println(value);
}
}
}
}
TreeMap<String, Integer> tm = new TreeMap<>();
List<String> l1 = new ArrayList<>();
List<String> l2 = new ArrayList<>();
List<String> l3 = new ArrayList<>();
l1.add("aaa");
l1.add("bbb");
l1.add("ddd");
l1.add("xyxz");
l2.add("bbb");
l2.add("ccc");
l2.add("ccc");
l2.add("hkp");
l3.add("ddd");
l3.add("eee");
l3.add("fff");
l3.add("lmn");
for (String string : l1) {
tm.put(string, 1);
}
for (String string : l2) {
if (!tm.containsKey(string)) {
tm.put(string, 1);
} else {
tm.remove(string);
}
}
for (String string : l3) {
if (!tm.containsKey(string)) {
tm.put(string, 1);
} else {
tm.remove(string);
}
}
for (String string : tm.keySet()) {
System.out.println(string);
}
import java.util.ArrayList;
import java.util.List;
/**
* Created by admin on 16-02-2017.
*/
public class Amazon1 {
public static void main(String[] args){
List<String> l1 = new ArrayList<String>();
List<String> l2 = new ArrayList<String>();
List<String> l3 = new ArrayList<String>();
l1.add("aaa");
l1.add("bbb");
l1.add("ddd");
l1.add("xyxz");
l2.add("bbb");
l2.add("ccc");
l2.add("ccc");
l2.add("hkp");
l3.add("ddd");
l3.add("eee");
l3.add("fff");
l3.add("lmn");
int x=0,y=0,z=0;
while (x<l1.size() || y<l2.size() || z<l3.size()){
if(x< l1.size() && y<l2.size() && (l1.get(x) == l2.get(y)) &&
(l2.get(y)== l3.get(z))){
x++;
y++;
z++;
}
if(x<l1.size() && y < l2.size() && (l1.get(x) == l2.get(y))){
y++;
x++;
}else if(y<l2.size() && z<l3.size() && l2.get(y) == l3.get(z)){
y++;
z++;
}else if(x<l1.size() && z<l3.size() && l1.get(x) == l3.get(z)){
z++;
x++;
}else{
int r =1;
if(x<l1.size() && y<l2.size()){
r = l1.get(x).compareTo(l2.get(y));
}
if(r<1){
if(z<l3.size() && x<l1.size() && l3.get(z).compareTo(l1.get(x)) < 0){
System.out.print(l3.get(z)+" ");
z++;
}else{
System.out.print(l1.get(x)+" ");
x++;
}
}else{
if(y<l2.size() && l2.get(y).compareTo(l3.get(z)) < 0){
System.out.print(l2.get(y)+" ");
y++;
}else if(z<l3.size()){
System.out.print(l3.get(z)+" ");
z++;
}
}
}
}
}
}
import java.util.ArrayList;
import java.util.List;
/**
* Created by admin on 16-02-2017.
*/
public class Amazon1 {
public static void main(String[] args){
List<String> l1 = new ArrayList<String>();
List<String> l2 = new ArrayList<String>();
List<String> l3 = new ArrayList<String>();
l1.add("aaa");
l1.add("bbb");
l1.add("ddd");
l1.add("xyxz");
l2.add("bbb");
l2.add("ccc");
l2.add("ccc");
l2.add("hkp");
l3.add("ddd");
l3.add("eee");
l3.add("fff");
l3.add("lmn");
int x=0,y=0,z=0;
while (x<l1.size() || y<l2.size() || z<l3.size()){
if(x< l1.size() && y<l2.size() && (l1.get(x) == l2.get(y)) &&
(l2.get(y)== l3.get(z))){
x++;
y++;
z++;
}
if(x<l1.size() && y < l2.size() && (l1.get(x) == l2.get(y))){
y++;
x++;
}else if(y<l2.size() && z<l3.size() && l2.get(y) == l3.get(z)){
y++;
z++;
}else if(x<l1.size() && z<l3.size() && l1.get(x) == l3.get(z)){
z++;
x++;
}else{
int r =1;
if(x<l1.size() && y<l2.size()){
r = l1.get(x).compareTo(l2.get(y));
}
if(r<1){
if(z<l3.size() && x<l1.size() && l3.get(z).compareTo(l1.get(x)) < 0){
System.out.print(l3.get(z)+" ");
z++;
}else{
System.out.print(l1.get(x)+" ");
x++;
}
}else{
if(y<l2.size() && l2.get(y).compareTo(l3.get(z)) < 0){
System.out.print(l2.get(y)+" ");
y++;
}else if(z<l3.size()){
System.out.print(l3.get(z)+" ");
z++;
}
}
}
}
}
}
import java.util.ArrayList;
import java.util.List;
/**
* Created by admin on 16-02-2017.
*/
public class Amazon1 {
public static void main(String[] args){
List<String> l1 = new ArrayList<String>();
List<String> l2 = new ArrayList<String>();
List<String> l3 = new ArrayList<String>();
l1.add("aaa");
l1.add("bbb");
l1.add("ddd");
l1.add("xyxz");
l2.add("bbb");
l2.add("ccc");
l2.add("ccc");
l2.add("hkp");
l3.add("ddd");
l3.add("eee");
l3.add("fff");
l3.add("lmn");
int x=0,y=0,z=0;
while (x<l1.size() || y<l2.size() || z<l3.size()){
if(x< l1.size() && y<l2.size() && (l1.get(x) == l2.get(y)) &&
(l2.get(y)== l3.get(z))){
x++;
y++;
z++;
}
if(x<l1.size() && y < l2.size() && (l1.get(x) == l2.get(y))){
y++;
x++;
}else if(y<l2.size() && z<l3.size() && l2.get(y) == l3.get(z)){
y++;
z++;
}else if(x<l1.size() && z<l3.size() && l1.get(x) == l3.get(z)){
z++;
x++;
}else{
int r =1;
if(x<l1.size() && y<l2.size()){
r = l1.get(x).compareTo(l2.get(y));
}
if(r<1){
if(z<l3.size() && x<l1.size() && l3.get(z).compareTo(l1.get(x)) < 0){
System.out.print(l3.get(z)+" ");
z++;
}else{
System.out.print(l1.get(x)+" ");
x++;
}
}else{
if(y<l2.size() && l2.get(y).compareTo(l3.get(z)) < 0){
System.out.print(l2.get(y)+" ");
y++;
}else if(z<l3.size()){
System.out.print(l3.get(z)+" ");
z++;
}
}
}
}
}
}
Simple C# version of code
using System;
using System.Collections.Generic;
using System.Linq;
namespace Lists
{
public class Program
{
public static void Main(string[] args)
{
var list1 = new string[]{ "aaa", "bbb", "ddd", "xyxz" };
var list2 = new string[]{ "bbb", "ccc", "ccc", "hkp "};
var list3= new string[]{ "ddd", "eee", "ffff", "lmn"};
var lists = new List<string[]>{list1, list2, list3};
PrintResult(lists);
}
private static void PrintResult(List<string[]> lists)
{
var dictionary = new SortedDictionary<string, int>();
var removedEntries = new List<string>{ };
for (int i = 0; i < lists.Count(); i++)
{
for (int j = 0; j < lists[i].Count(); j++)
{
var key = lists[i][j];
if (dictionary.ContainsKey(key))
{
if (dictionary[key].ToString() != i.ToString())
{
dictionary.Remove(key);
removedEntries.Add(key);
}
}
else
{
if (!removedEntries.Contains(key))
{
dictionary.Add(key, i);
}
}
}
}
foreach (var key in dictionary.Keys)
{
Console.WriteLine(key);
}
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
namespace Lists
{
public class Program
{
public static void Main(string[] args)
{
var list1 = new string[]{ "aaa", "bbb", "ddd", "xyxz" };
var list2 = new string[]{ "bbb", "ccc", "ccc", "hkp "};
var list3= new string[]{ "ddd", "eee", "ffff", "lmn"};
var lists = new List<string[]>{list1, list2, list3};
PrintResult(lists);
}
private static void PrintResult(List<string[]> lists)
{
var dictionary = new SortedDictionary<string, int>();
var removedEntries = new List<string>{ };
for (int i = 0; i < lists.Count(); i++)
{
for (int j = 0; j < lists[i].Count(); j++)
{
var key = lists[i][j];
if (dictionary.ContainsKey(key))
{
if (dictionary[key].ToString() != i.ToString())
{
dictionary.Remove(key);
removedEntries.Add(key);
}
}
else
{
if (!removedEntries.Contains(key))
{
dictionary.Add(key, i);
}
}
}
}
foreach (var key in dictionary.Keys)
{
Console.WriteLine(key);
}
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
namespace Lists
{
public class Program
{
public static void Main(string[] args)
{
var list1 = new string[]{ "aaa", "bbb", "ddd", "xyxz" };
var list2 = new string[]{ "bbb", "ccc", "ccc", "hkp "};
var list3= new string[]{ "ddd", "eee", "ffff", "lmn"};
var lists = new List<string[]>{list1, list2, list3};
PrintResult(lists);
}
private static void PrintResult(List<string[]> lists)
{
var dictionary = new SortedDictionary<string, int>();
var removedEntries = new List<string>{ };
for (int i = 0; i < lists.Count(); i++)
{
for (int j = 0; j < lists[i].Count(); j++)
{
var key = lists[i][j];
if (dictionary.ContainsKey(key))
{
if (dictionary[key].ToString() != i.ToString())
{
dictionary.Remove(key);
removedEntries.Add(key);
}
}
else
{
if (!removedEntries.Contains(key))
{
dictionary.Add(key, i);
}
}
}
}
foreach (var key in dictionary.Keys)
{
Console.WriteLine(key);
}
}
}
}
(function(){
function node(data){
this.data = data;
this.next = null;
}
function list(){
this.head = null;
this.tail = null;
}
list.prototype.add = function(data){
let n = new node(data);
if(this.head === null){
this.head = n;
this.tail = n;
return
}
this.tail.next = n;
this.tail = n;
}
let l1 = new list();
l1.add('aaa');
l1.add('bbb');
l1.add('ddd');
l1.add('xyxz');
let l2 = new list();
l2.add('bbb');
l2.add('ccc');
l2.add('ccc');
l2.add('hkp');
let l3 = new list();
l3.add('ddd');
l3.add('eee');
l3.add('ffff');
l3.add('lmn');
function compare(l1,l2){
let n1 = l1.head;
let n2 = l2.head;
let out = new list();
while(n1 && n2){
if(n1.data<n2.data){
out.add(n1.data);
n1 = n1.next;
}else if(n1.data>n2.data){
out.add(n2.data);
n2 = n2.next;
}else if (n1.data === n2.data){
//out.add(n1.data);
n1 = n1.next;
n2 = n2.next;
}
}
while(n1){
out.add(n1.data);
n1 = n1.next;
}
while(n2){
out.add(n2.data);
n2 = n2.next;
}
return out
}
function combinenodes(){
let out = new list();
for(let i = 0; i<arguments.length;i++){
out = compare(out, arguments[i]);
}
// let list = compare(l1,l2);
// let list2 = compare(list,l3);
let n = out.head;
while(n){
console.log(n.data);
n = n.next;
}
}
combinenodes(l1,l2,l3);
}());
public static void MergeStringArrays(string[][] strArrays)
{
ArrayList result = new ArrayList();
int totalIndex = 0;
for(int i=0; i < strArrays.Length; i++)
{
for (int j = 0; j < strArrays[i].Length; j++)
{
int lastIndex = result.LastIndexOf(strArrays[i][j]);
if (lastIndex < 0)
result.Add(strArrays[i][j]);
else
{
if (lastIndex <= totalIndex)
{
result.RemoveAt(lastIndex);
totalIndex--;
}
else
result.Add(strArrays[i][j]);
}
}
//advance totalIndex
totalIndex = (result.Count-1);
}
result.Sort();
Console.WriteLine("Result: ");
foreach (string s in result)
Console.Write(string.Format("{0} ", s));
Console.ReadLine();
}
package com.divakar.amazon;
import java.util.List;
import java.util.ArrayList;
public class RemoveDuplicate {
public void test() {
List<String> list1 = new ArrayList<String>();
list1.add("aaa");
list1.add("bbb");
list1.add("ddd");
list1.add("xyxz");
List<String> list2 = new ArrayList<String>();
list2.add("bbb");
list2.add("ccc");
list2.add("ccc");
list2.add("hkp");
List<String> list3 = new ArrayList<String>();
list3.add("ccc");
list3.add("ddd");
list3.add("eee");
list3.add("fff");
list3.add("lmn");
int l1 = 0;
int l2 = 0;
int l3 = 0;
List<String> finalArray = new ArrayList<String>();
while (true) {
if (l1 >= list1.size() && l2 >= list2.size() && l3 >= list3.size())
break;
String value = "";
if (l1 <= list1.size() - 1) {
if (l2 <= list2.size() - 1) {
if (list1.get(l1).compareTo(list2.get(l2)) <= 0) {
value = list1.get(l1);
if (value.compareTo(list2.get(l2)) == 0) {
while (true) {
l2++;
if (list1.get(l1).compareTo(list2.get(l2)) == 0) {
continue;
} else
break;
}
} /*
* else l2++;
*/
if (l3 <= list3.size() - 1) {
if (value.compareTo(list3.get(l3)) >= 0) {
value = list3.get(l3);
if (value.compareTo(list3.get(l3)) == 0) {
while (true) {
l3++;
if (value.compareTo(list3.get(l3)) == 0) {
continue;
} else
break;
}
l1++;
} else
l3++;
} else {
l1++;
}
} else {
l1++;
}
} else {
value = list2.get(l2);
if (l3 <= list3.size() - 1) {
if (value.compareTo(list3.get(l3)) >= 0) {
value = list3.get(l3);
if (value.compareTo(list2.get(l2)) == 0) {
while (true) {
l3++;
value = list3.get(l3);
if (value.compareTo(list2.get(l2)) == 0) {
continue;
} else
break;
}
l2++;
} else {
l3++;
}
} else {
l2++;
}
} else {
l2++;
}
}
} else {
value = list1.get(l1);
if (l3 <= list3.size() - 1 && value.compareTo(list3.get(l3)) >= 0) {
value = list3.get(l3);
if (value.compareTo(list1.get(l1)) == 0) {
while (true) {
l3++;
value = list3.get(l3);
if (value.compareTo(list1.get(l1)) == 0) {
continue;
} else
break;
}
l1++;
} else
l3++;
} else {
l1++;
}
}
// l1++;
finalArray.add(value);
} else if (l2 <= list2.size() - 1) {
if (l3 <= list3.size() - 1) {
if (list2.get(l2).compareTo(list3.get(l3)) <= 0) {
value = list2.get(l2);
if (value.compareTo(list3.get(l3)) == 0) {
while (true) {
l3++;
if (value.compareTo(list3.get(l3)) == 0) {
continue;
} else
break;
}
l2++;
} else
l3++;
} else {
value = list3.get(l3);
l3++;
}
}
finalArray.add(value);
// l2++;
} else if (l3 <= list3.size() - 1) {
while (l3 < list3.size() - 1) {
finalArray.add(list3.get(l3));
}
}
if (!value.isEmpty())
System.out.println(value);
}
/*
* for(String value: finalArray){ System.out.println(value); }
*/
}
private int compare(String value1, String value2, int count1, int count2) {
int i = value1.compareTo(value2);
if (i <= 0) {
count1++;
} else {
count2++;
}
/*
* if(i==0){ System.out.println("equal"); }else if (i<0){
* System.out.println("string 1 is less"); }else{
* System.out.println("String 2 is less"); }
*/
return i;
}
public static void main(String[] args) {
RemoveDuplicate rd = new RemoveDuplicate();
/*
* int l1 = list1.size(); int l2 = list2.size(); int l3 = list3.size();
*
*
*
* if(list1.size()>=list2.size() && list1.size()>=list3.size()){
* if(list2.size() >= list3.size()){ rd.test(list1, list2, list3); }else
* { rd.test(list1, list3, list2); } }
*/
rd.test();
}
}
import java.util.List;
import java.util.ArrayList;
public class RemoveDuplicate {
public void test() {
List<String> list1 = new ArrayList<String>();
list1.add("aaa");
list1.add("bbb");
list1.add("ddd");
list1.add("xyxz");
List<String> list2 = new ArrayList<String>();
list2.add("bbb");
list2.add("ccc");
list2.add("ccc");
list2.add("hkp");
List<String> list3 = new ArrayList<String>();
list3.add("ccc");
list3.add("ddd");
list3.add("eee");
list3.add("fff");
list3.add("lmn");
int l1 = 0;
int l2 = 0;
int l3 = 0;
List<String> finalArray = new ArrayList<String>();
while (true) {
if (l1 >= list1.size() && l2 >= list2.size() && l3 >= list3.size())
break;
String value = "";
if (l1 <= list1.size() - 1) {
if (l2 <= list2.size() - 1) {
if (list1.get(l1).compareTo(list2.get(l2)) <= 0) {
value = list1.get(l1);
if (value.compareTo(list2.get(l2)) == 0) {
while (true) {
l2++;
if (list1.get(l1).compareTo(list2.get(l2)) == 0) {
continue;
} else
break;
}
} /*
* else l2++;
*/
if (l3 <= list3.size() - 1) {
if (value.compareTo(list3.get(l3)) >= 0) {
value = list3.get(l3);
if (value.compareTo(list3.get(l3)) == 0) {
while (true) {
l3++;
if (value.compareTo(list3.get(l3)) == 0) {
continue;
} else
break;
}
l1++;
} else
l3++;
} else {
l1++;
}
} else {
l1++;
}
} else {
value = list2.get(l2);
if (l3 <= list3.size() - 1) {
if (value.compareTo(list3.get(l3)) >= 0) {
value = list3.get(l3);
if (value.compareTo(list2.get(l2)) == 0) {
while (true) {
l3++;
value = list3.get(l3);
if (value.compareTo(list2.get(l2)) == 0) {
continue;
} else
break;
}
l2++;
} else {
l3++;
}
} else {
l2++;
}
} else {
l2++;
}
}
} else {
value = list1.get(l1);
if (l3 <= list3.size() - 1 && value.compareTo(list3.get(l3)) >= 0) {
value = list3.get(l3);
if (value.compareTo(list1.get(l1)) == 0) {
while (true) {
l3++;
value = list3.get(l3);
if (value.compareTo(list1.get(l1)) == 0) {
continue;
} else
break;
}
l1++;
} else
l3++;
} else {
l1++;
}
}
// l1++;
finalArray.add(value);
} else if (l2 <= list2.size() - 1) {
if (l3 <= list3.size() - 1) {
if (list2.get(l2).compareTo(list3.get(l3)) <= 0) {
value = list2.get(l2);
if (value.compareTo(list3.get(l3)) == 0) {
while (true) {
l3++;
if (value.compareTo(list3.get(l3)) == 0) {
continue;
} else
break;
}
l2++;
} else
l3++;
} else {
value = list3.get(l3);
l3++;
}
}
finalArray.add(value);
// l2++;
} else if (l3 <= list3.size() - 1) {
while (l3 < list3.size() - 1) {
finalArray.add(list3.get(l3));
}
}
if (!value.isEmpty())
System.out.println(value);
}
/*
* for(String value: finalArray){ System.out.println(value); }
*/
}
private int compare(String value1, String value2, int count1, int count2) {
int i = value1.compareTo(value2);
if (i <= 0) {
count1++;
} else {
count2++;
}
/*
* if(i==0){ System.out.println("equal"); }else if (i<0){
* System.out.println("string 1 is less"); }else{
* System.out.println("String 2 is less"); }
*/
return i;
}
public static void main(String[] args) {
RemoveDuplicate rd = new RemoveDuplicate();
/*
* int l1 = list1.size(); int l2 = list2.size(); int l3 = list3.size();
*
*
*
* if(list1.size()>=list2.size() && list1.size()>=list3.size()){
* if(list2.size() >= list3.size()){ rd.test(list1, list2, list3); }else
* { rd.test(list1, list3, list2); } }
*/
rd.test();
}
}
package com.divakar.amazon;
import java.util.List;
import java.util.ArrayList;
public class RemoveDuplicate {
public void test() {
List<String> list1 = new ArrayList<String>();
list1.add("aaa");
list1.add("bbb");
list1.add("ddd");
list1.add("xyxz");
List<String> list2 = new ArrayList<String>();
list2.add("bbb");
list2.add("ccc");
list2.add("ccc");
list2.add("hkp");
List<String> list3 = new ArrayList<String>();
list3.add("ccc");
list3.add("ddd");
list3.add("eee");
list3.add("fff");
list3.add("lmn");
int l1 = 0;
int l2 = 0;
int l3 = 0;
List<String> finalArray = new ArrayList<String>();
while (true) {
if (l1 >= list1.size() && l2 >= list2.size() && l3 >= list3.size())
break;
String value = "";
if (l1 <= list1.size() - 1) {
if (l2 <= list2.size() - 1) {
if (list1.get(l1).compareTo(list2.get(l2)) <= 0) {
value = list1.get(l1);
if (value.compareTo(list2.get(l2)) == 0) {
while (true) {
l2++;
if (list1.get(l1).compareTo(list2.get(l2)) == 0) {
continue;
} else
break;
}
} /*
* else l2++;
*/
if (l3 <= list3.size() - 1) {
if (value.compareTo(list3.get(l3)) >= 0) {
value = list3.get(l3);
if (value.compareTo(list3.get(l3)) == 0) {
while (true) {
l3++;
if (value.compareTo(list3.get(l3)) == 0) {
continue;
} else
break;
}
l1++;
} else
l3++;
} else {
l1++;
}
} else {
l1++;
}
} else {
value = list2.get(l2);
if (l3 <= list3.size() - 1) {
if (value.compareTo(list3.get(l3)) >= 0) {
value = list3.get(l3);
if (value.compareTo(list2.get(l2)) == 0) {
while (true) {
l3++;
value = list3.get(l3);
if (value.compareTo(list2.get(l2)) == 0) {
continue;
} else
break;
}
l2++;
} else {
l3++;
}
} else {
l2++;
}
} else {
l2++;
}
}
} else {
value = list1.get(l1);
if (l3 <= list3.size() - 1 && value.compareTo(list3.get(l3)) >= 0) {
value = list3.get(l3);
if (value.compareTo(list1.get(l1)) == 0) {
while (true) {
l3++;
value = list3.get(l3);
if (value.compareTo(list1.get(l1)) == 0) {
continue;
} else
break;
}
l1++;
} else
l3++;
} else {
l1++;
}
}
// l1++;
finalArray.add(value);
} else if (l2 <= list2.size() - 1) {
if (l3 <= list3.size() - 1) {
if (list2.get(l2).compareTo(list3.get(l3)) <= 0) {
value = list2.get(l2);
if (value.compareTo(list3.get(l3)) == 0) {
while (true) {
l3++;
if (value.compareTo(list3.get(l3)) == 0) {
continue;
} else
break;
}
l2++;
} else
l3++;
} else {
value = list3.get(l3);
l3++;
}
}
finalArray.add(value);
// l2++;
} else if (l3 <= list3.size() - 1) {
while (l3 < list3.size() - 1) {
finalArray.add(list3.get(l3));
}
}
if (!value.isEmpty())
System.out.println(value);
}
/*
* for(String value: finalArray){ System.out.println(value); }
*/
}
private int compare(String value1, String value2, int count1, int count2) {
int i = value1.compareTo(value2);
if (i <= 0) {
count1++;
} else {
count2++;
}
/*
* if(i==0){ System.out.println("equal"); }else if (i<0){
* System.out.println("string 1 is less"); }else{
* System.out.println("String 2 is less"); }
*/
return i;
}
public static void main(String[] args) {
RemoveDuplicate rd = new RemoveDuplicate();
/*
* int l1 = list1.size(); int l2 = list2.size(); int l3 = list3.size();
*
*
*
* if(list1.size()>=list2.size() && list1.size()>=list3.size()){
* if(list2.size() >= list3.size()){ rd.test(list1, list2, list3); }else
* { rd.test(list1, list3, list2); } }
*/
rd.test();
}
}
public LinkedList<String> mergeLists(LinkedList<LinkedList<String>> arrLists){
LinkedList<String> mergedList = new LinkedList<String>();
boolean allEmpty = false;
while(!allEmpty) {
Hashtable<String, Integer> discovered = new Hashtable<String, Integer>();
boolean match = false;
int matchIndex = -1;
int min= -1;
boolean innerAllEmpty = true;
int i;
for(i =0; i < arrLists.size(); i++){
if(min < 0 && !arrLists.get(i).isEmpty()){
min = i;
break;
}
}
discovered.put(arrLists.get(min).peekFirst(), min);
for(i = min+1; i < arrLists.size(); i++){
innerAllEmpty &= arrLists.get(i).isEmpty();
if(arrLists.get(i).isEmpty()) {
continue;
}
if(!discovered.containsKey(arrLists.get(i).peekFirst())){
discovered.put(arrLists.get(i).peekFirst(), i);
} else {
match = true;
matchIndex = discovered.get(arrLists.get(i).peekFirst());
arrLists.get(i).removeFirst();
}
if(!match && arrLists.get(i).peekFirst().compareTo(arrLists.get(min).peekFirst()) < 0){
min = i;
}
}
if(match){
arrLists.get(matchIndex).removeFirst();
} else {
if(!allEmpty)
mergedList.addLast(arrLists.get(min).removeFirst());
}
allEmpty = innerAllEmpty;
}
return mergedList;
}
private static void MergeTheseLists_FO(List<string> list1, List<string> list2, List<string> list3)
{
string minString = string.Empty;
string SomeBigString = string.Empty;
int i = 0, j = 0, k = 0;
bool firstPrint = true;
do
{
string s1 = i >= list1.Count ? string.Empty : list1[i];
string s2 = j >= list2.Count ? string.Empty : list2[j];
string s3 = k >= list3.Count ? string.Empty : list3[k];
SomeBigString = string.Empty.PadLeft(s1.Length + s2.Length + s3.Length, 'z');
if (IsNullOrEmpty(SomeBigString))
{
break;
}
minString = FindMinimum(ref i, ref j, ref k, IsNullOrEmpty(s1) ? SomeBigString : s1, IsNullOrEmpty(s2) ? SomeBigString : s2, IsNullOrEmpty(s3) ? SomeBigString : s3);
if (firstPrint)
{
Write(minString);
firstPrint = false;
}
else
Write($"-->{minString}");
} while (minString != SomeBigString);
}
private static string FindMinimum(ref int i, ref int j, ref int k, string s1, string s2, string s3)
{
string minString = string.Empty;
if (s1.CompareTo(s2) == 0) // 1 and 2 are equal
{
if (s1.CompareTo(s3) == 0) // 1 and 2 and 3 are equal
{
i++; j++; k++;
}
else // only 1 and 2 are equal
{
i++; j++; k++;
minString = s3;
}
}
else if (s1.CompareTo(s2) < 0) // 1 is less than 2
{
if (s1.CompareTo(s3) < 0) // and 1 is less than 3, so 1 is min
{
i++;
minString = s1;
}
if (s1.CompareTo(s3) == 0) // 1 and 3 are equal, so 2 is min
{
j++;
minString = s2;
}
if (s1.CompareTo(s3) > 0) // and 3 is less than 1, so 3 is min
{
k++;
minString = s3;
}
}
else // 2 is less than one
{
if (s2.CompareTo(s3) < 0) // and 2 is less than 3, so 2 is min
{
j++;
minString = s2;
}
if (s2.CompareTo(s3) == 0)
{
i++;
minString = s1;
}
if (s2.CompareTo(s3) > 0) // and 3 is less than 2, so 3 is min
{
k++;
minString = s3;
}
}
//WriteLine($"s1:{s1}, s2:{s2}, s3:{s3}, min:{minString}, i:{i}, j:{j}, k:{k}");
return minString;
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.*;
public class HelloWorld{
public static void main(String []args){
System.out.println("Hello World");
BufferedReader userInput = new BufferedReader
(new InputStreamReader(System.in));
ArrayList<String> myArr = new ArrayList<String>();
myArr.add("Italian Riviera");
myArr.add("Jersey Shore");
myArr.add("Puerto Rico");
myArr.add("Los Cabos Corridor");
myArr.add("Lubmin");
myArr.add("Coney Island");
myArr.add("Karlovy Vary");
myArr.add("Bourbon-l'Archambault");
myArr.add("Walt Disney World Resort");
myArr.add("Barbados");
System.out.println("Stupid Vacation Resort Adviser");
System.out.println("value"+myArr);
System.out.println("List Details");
List<String> listStrings = new LinkedList<String>();
listStrings.add("Five");
listStrings.add("Six");
listStrings.add("Seven");
listStrings.add("Eight");
String[] A1 = {"aaa", "bbb", "ddd", "xyxz" };
List<String> list1 =new ArrayList(Arrays.asList(A1));
String[] B1 = { "bbb", "ccc", "ccc", "hkp "};
List<String> list2 =new ArrayList(Arrays.asList(B1));
String[] C1 = { "ddd", "eee", "ffff", "lmn"};
List<String> list3 = new ArrayList(Arrays.asList(C1));
System.out.println(listStrings);
for (int i= 0 ; i< list1.size(); i++){
if (list2.contains(list1.get(i))) {
System.out.println("remove elements"+list1.get(i));
String value = list1.get(i);
list2.remove(value);
list1.remove(value);
}
if (list3.contains(list1.get(i))) {
System.out.println("remove elements"+list1.get(i));
String value = list1.get(i);
list3.remove(value);
list1.remove(value);
}
}
System.out.println(" List 2 size "+list2.size()+"value"+list2);
System.out.println(" List q size "+list2.size()+"value"+list1);
System.out.println(" List 3 size "+list3.size()+"value"+list3);
for (int i= 0 ; i< list2.size(); i++){
if (list3.contains(list2.get(i))) {
System.out.println("remove elements"+list2.get(i));
String value = list2.get(i);
list3.remove(value);
list2.remove(value);
}
}
System.out.println(" List 2 size "+list2.size()+"value"+list2);
System.out.println(" List 3 size "+list3.size()+"value"+list3);
List<String> lists = new ArrayList<String>();
lists.addAll(list1);
lists.addAll(list2);
lists.addAll(list3);
System.out.println(lists);
System.out.println("lists length :"+lists.size()+"\n List 1 size "+list1.size()+"\n List 2 size "+list2.size()+"\n List 3 size "+list3.size());
Collections.sort(lists);
System.out.println(lists);
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.*;
public class HelloWorld{
public static void main(String []args){
System.out.println("Hello World");
BufferedReader userInput = new BufferedReader
(new InputStreamReader(System.in));
ArrayList<String> myArr = new ArrayList<String>();
myArr.add("Italian Riviera");
myArr.add("Jersey Shore");
myArr.add("Puerto Rico");
myArr.add("Los Cabos Corridor");
myArr.add("Lubmin");
myArr.add("Coney Island");
myArr.add("Karlovy Vary");
myArr.add("Bourbon-l'Archambault");
myArr.add("Walt Disney World Resort");
myArr.add("Barbados");
System.out.println("Stupid Vacation Resort Adviser");
System.out.println("value"+myArr);
System.out.println("List Details");
List<String> listStrings = new LinkedList<String>();
listStrings.add("Five");
listStrings.add("Six");
listStrings.add("Seven");
listStrings.add("Eight");
String[] A1 = {"aaa", "bbb", "ddd", "xyxz" };
List<String> list1 =new ArrayList(Arrays.asList(A1));
String[] B1 = { "bbb", "ccc", "ccc", "hkp "};
List<String> list2 =new ArrayList(Arrays.asList(B1));
String[] C1 = { "ddd", "eee", "ffff", "lmn"};
List<String> list3 = new ArrayList(Arrays.asList(C1));
System.out.println(listStrings);
for (int i= 0 ; i< list1.size(); i++){
if (list2.contains(list1.get(i))) {
System.out.println("remove elements"+list1.get(i));
String value = list1.get(i);
list2.remove(value);
list1.remove(value);
}
if (list3.contains(list1.get(i))) {
System.out.println("remove elements"+list1.get(i));
String value = list1.get(i);
list3.remove(value);
list1.remove(value);
}
}
System.out.println(" List 2 size "+list2.size()+"value"+list2);
System.out.println(" List q size "+list2.size()+"value"+list1);
System.out.println(" List 3 size "+list3.size()+"value"+list3);
for (int i= 0 ; i< list2.size(); i++){
if (list3.contains(list2.get(i))) {
System.out.println("remove elements"+list2.get(i));
String value = list2.get(i);
list3.remove(value);
list2.remove(value);
}
}
System.out.println(" List 2 size "+list2.size()+"value"+list2);
System.out.println(" List 3 size "+list3.size()+"value"+list3);
List<String> lists = new ArrayList<String>();
lists.addAll(list1);
lists.addAll(list2);
lists.addAll(list3);
System.out.println(lists);
System.out.println("lists length :"+lists.size()+"\n List 1 size "+list1.size()+"\n List 2 size "+list2.size()+"\n List 3 size "+list3.size());
Collections.sort(lists);
System.out.println(lists);
}
}
Here i have converted the list type to Set to make sure,
- i don't want code to loop through elements with duplicate entries
- also set.contains complexity is O(1) where array list is O(n).
After identifying the elements which are common between the three list, i remove them and do the sorting at the end.
public static void main(String[] args) {
List<String> list1 = new ArrayList<>();
List<String> list2 = new ArrayList<>();
List<String> list3 = new ArrayList<>();
list1.add("aaa");list1.add("bbb");list1.add("ddd"); list1.add("xyxz");
list2.add("bbb");list2.add("ccc");list2.add("ccc"); list2.add("hkp");
list3.add("ddd");list3.add("eee");list3.add("ffff");list3.add("lmn");
Set<String> set1 = new HashSet<>();
Set<String> set2 = new HashSet<>();
Set<String> set3 = new HashSet<>();
set1.addAll(list1);
set2.addAll(list2);
set3.addAll(list3);
Set<String> combined = new HashSet<>();
for(String str : set2){
if(set1.contains(str)){
combined.add(str);
}
}
for(String str : set3){
if(set1.contains(str) || set2.contains(str)){
combined.add(str);
}
}
List<String> mainList = new ArrayList<>();
mainList.addAll(list1);
mainList.addAll(list2);
mainList.addAll(list3);
mainList.removeAll(combined);
Collections.sort(mainList);
System.out.println(mainList);
}
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class MergeSortedList {
public static void main(String[] args) {
List<Queue<String>> list = new ArrayList<>();
Queue<String> q1 = new LinkedList<>();
q1.add("aaa");
q1.add("bbb");
q1.add("ddd");
q1.add("xyxz");
Queue<String> q2 = new LinkedList<>();
q2.add("bbb");
q2.add("ccc");
q2.add("ccc");
q2.add("hkp");
Queue<String> q3 = new LinkedList<>();
q3.add("ddd");
q3.add("eee");
q3.add("fff");
q3.add("lmn");
list.add(q1);
list.add(q2);
list.add(q3);
printSorted(list);
}
static void printSorted(List<Queue<String>> list){
if(list == null) return;
boolean elementPresent = false;
List<String> l = new ArrayList<>();
int prevListId = -1;
do{
int listId = 0;
String min = "";
int i = 0;
elementPresent = false;
for (Queue<String> queue : list) {
if(queue.size() > 0 && min.equals("")){
min = queue.peek();
elementPresent = true;
listId = i;
}else if(queue.size() > 0){
if(min.compareTo(queue.peek()) > 0){
listId = i;
min = queue.peek();
}
elementPresent = true;
}
i++;
}
if(l.contains(min) && elementPresent){
if(prevListId == listId)
l.add(min);
else{
List<String> l2 = new ArrayList<>();
for (String s : l) {
if(!s.equals(min)){
l2.add(s);
}
}
l.clear();
l.addAll(l2);
}
}else if(elementPresent){
l.add(min);
}
if(elementPresent)
list.get(listId).poll();
prevListId = listId;
}while(elementPresent);
System.out.println(l);
}
}
Javascript solution using Binary seach
let a = ["aaa", "aaa","bbb","cccc"]
let b = ["bbb","cccc","eeee"]
let c= ["eeee", "ffff","kkkk","kkkk"]
//output ["aaa", "aaa", "ffff", "kkkk", "kkkk"]
function bs(arr, s, e, k) {
while(s <= e) {
var mid = parseInt((s+e) / 2);
if(arr[mid] === k) {
return mid;
}
if(k > arr[mid]) {
s = mid + 1;
} else{
e = mid -1;
}
}
return -1;
}
// do a binry search on b, c array based on A, value
let map = [];
function merge() {
for(let i =0 ;i < a.length; i++) {
var left = bs(b, 0, b.length, a[i]);
var right = bs(c, 0, c.length, a[i]);
// if item is not found then add it array
if(left === -1 && right === -1) {
map.push(a[i]);
} else {
// remove from array of b
if(left !== -1) {
b.splice(left, 1);
}
// remove from array of c
if(right !== -1) {
c.splice(right, 1);
}
}
}
// do a binary serch on array c based on b's value.
for(let i =0 ;i < b.length; i++) {
var left = bs(c, 0, c.length, b[i]);
// if item is not found then add it array
if(left === -1) {
map.push(b[i]);
} else {
// remove from array of c
if(left !== -1) {
c.splice(left, 1);
}
}
}
// c has the left overs
for(let i =0 ;i < c.length; i++) {
map.push(c[i]);
}
// now sort
map.sort();
}
merge();
console.log(map)
- dmitry.labutin February 09, 2017package main import "fmt" type ListNode struct { value string next *ListNode } func getMin(lists []*ListNode) int { var min *ListNode min = nil ind := -1 for i, node := range lists { if node != nil { if min == nil { min = node ind = i } else { if min.value > node.value { min = node ind = i } } } } return ind } func merge(lists []*ListNode) *ListNode { var root, end *ListNode present := map[string]map[int]bool{} for i := 0; i < len(lists); i++ { root := lists[i] for root != nil { if _, ok := present[root.value]; !ok { present[root.value] = map[int]bool{} } present[root.value][i] = true root = root.next } } for true { minNode := getMin(lists) if minNode == -1 { break } add := true if len(present[lists[minNode].value]) > 1 { add = false } if add { newNode := &ListNode{value: lists[minNode].value} if root == nil { root = newNode end = newNode } else { end.next = newNode end = newNode } } lists[minNode] = lists[minNode].next } return root } func printList(root *ListNode) { for root != nil { fmt.Print(root.value + " ") root = root.next } } func addToList(root *ListNode, add string) *ListNode { newNode := &ListNode{value: add, next: root} return newNode } func main() { lists := []*ListNode{} var root *ListNode root = addToList(root, "xyxz") root = addToList(root, "ddd") root = addToList(root, "bbb") root = addToList(root, "aaa") lists = append(lists, root) root = nil root = addToList(root, "hkp") root = addToList(root, "ccc") root = addToList(root, "ccc") root = addToList(root, "bbb") lists = append(lists, root) root = nil root = addToList(root, "lmn") root = addToList(root, "glk") root = addToList(root, "ffff") root = addToList(root, "eee") root = addToList(root, "ddd") lists = append(lists, root) root = merge(lists) printList(root) }