Morgan Stanley Interview Question
Senior Software Development EngineersCountry: United States
Sorry missed out 2.
Eg: After print: 1 , 2, 3 , 4 , 6 , 10, 33, 34, 44,, 66, 89, 100, 123
To deal with duplicates you can just skip ahead either iterator if the next value is the same as the current value, until it's not and then use the not-same value.
I followed the above approach and come to this solution..
#include <stdio.h>
int main()
{
int arr2[]={1,3,4,6,8,10,17,34};
int arr1[]={2,8,17,33,44,66,89,100};
int len1 = sizeof(arr1)/sizeof(arr1[0]);
int len2 = sizeof(arr2)/sizeof(arr2[0]);
int i=0,j=0;
while ( (i <len1) && (j <len2))
{
if( i <len1 && j < len2 && arr1[i] < arr2[j] )
{
printf("%d ", arr1[i]);
i++;
}
else if( arr1[i] > arr2[j])
{
printf("%d ",arr2[j]);
j++;
}
else
i++,j++;
}
while(i < len1){
printf("%d ",arr1[i]);
i++;
}
while(j <len2 ){
printf("%d ",arr2[j]);
j++;
}
return 0;
}
Let me know if i am missing anything.
def merge_remove_dup(l1, l2):
p1=0
p2=0
last_match=None
while p1<len(l1) and p2<len(l2):
if l1[p1]<l2[p2]:
if l1[p1]!=last_match:
yield l1[p1]
p1+=1
elif l2[p2]<l1[p1]:
if l2[p2]!=last_match:
yield l2[p2]
p2+=1
else:
last_match=l1[p1]
#print "skipping ", l1[p1]
p1+=1
p2+=1
while p1<len(l1):
if l1[p1]!=last_match:
yield l1[p1]
p1+=1
while p2<len(l2):
if l2[p2]!=last_match:
yield l2[p2]
p2+=1
def main():
l1=[1,3,4,6,8,10,17,34]
l2=[2,8,17,17,33,44,66,89,100,123]
print l1
print l2
print [x for x in merge_remove_dup(l1,l2)]
@constant I think in your code, when arr1[i] == arr2[j], j should also be incremented, but only i gets incremented.
@Joe Flip, Please run the code using pen and paper then you will find that there is no need of increament of j when arr1[i] == arr2[j].
what I did ?? I just take the one element of "arr2" and iterate the first array up to less then equal to the value of element of "arr1" and compare if less and unequal then print the value of first array and increase the index and so on.
@constant have you run your code on computer? Your code will print out the duplicate element. Because when arr1[i] == arr2[j], your code will look at arr1[i+1], and if arr1[i+1] > arr2[j], it will print out arr2[j], which is a duplicate
Who said that the duplicates should be skipped? If the number is not present in the second list its duplicates should be also included in the result.
@Aalok
You missed this in ur C program(check for duplicates) :
else
{
temp=arr1[i];
i++,j++;
if(arr1[i]==temp)
i++;
if(arr2[j]==temp)
j++;
}
You can use two sets and the removeAll method.
import java.util.HashSet;
import java.util.Set;
public class RetainAllUnique {
public static void main(String[] args) {
int [] arr1 = {1, 3, 5, 7, 9};
int [] arr2 = {1, 2, 5, 6, 9};
Set <Integer> a1 = new HashSet();
for(int i : arr1) a1.add(i);
Set <Integer> a2 = new HashSet();
for(int i : arr2) a2.add(i);
Set <Integer> a1C = new HashSet(a1);
Set <Integer> a2C = new HashSet(a2);
a1C.removeAll(a2);
a2C.removeAll(a1);
Set <Integer> a3 = new HashSet();
a3.addAll(a1C);
a3.addAll(a2C);
for(int i : a3)
System.out.print(i + ", ");
System.out.println();
}
}
As Gayle would mention in her book, here's a solution that works (but I'm sure its not optimal :-))
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class CTest {
public static void main(String args[]) {
List<Integer> aList = new ArrayList<Integer>(Arrays.asList(1, 3, 4, 6,8,10, 17, 34));
List<Integer> bList = new ArrayList<Integer>(Arrays.asList(2, 8, 17, 33, 44, 66, 89, 100, 123));
List<Integer> finalList = new ArrayList<Integer>();
int i=0;
//In A; but not in B
for (Integer value : aList){
if (!bList.contains(aList.get(i))) {
finalList.add(aList.get(i));
}
i++;
}
//In B; but not in A
i=0;
for (Integer value : bList){
if (!aList.contains(bList.get(i))) {
finalList.add(bList.get(i));
}
i++;
}
//Final List
Collections.sort(finalList);
System.out.println(finalList);
}
}
1. If it is sorted then just check highest element in both arrays.If one is less than other than all elements greater than that element is not present in the second array.
2. Hash all the elements in the first array and check if the elements of the second array is present in the the hash but this will work only if the range is not high enough :)
Any better approaches?
HashSet<Integer> hs=new HashSet<Integer>(listA);
for(Integer i:listB){
if(!hs.add(i))
listA.remove(i);
else
listA.add(i);
}
collections.sort(listA);
System.out.println(listA);
int A[]={1, 3, 4, 6,8,10, 17, 34};
int B[]={2, 8, 17, 33, 44, 66, 89, 100, 123};
int lenA=8;
int lenB=9;
int notinA[16];
int i=0,j=0;
int a=0;
while(j<lenB && i<lenA)
{
if(B[j]< A[i] )
{
notinA[a]=B[j];
++a;
j++;
}
if(A[i]<B[j])
{
notinA[a]=A[i];
a++;
i++;
}
if(A[i]==B[j])
{
i++;
j++;
}
}
while(i<lenA)
{
notinA[a]=A[i];
a++;
i++;
}
while(j<lenB)
{
notinA[a]=B[j];
++a;
j++;
}
for(int i=0;i<a;i++)
{
std::cout<<notinA[i]<<" ";
}
this solution will give you the exclusive list as u have mentioned in 1 and 2
after that you can just add them using a Hashtable(in case you want to remove the duplicates eg: if((table.containsKey(element)) go next else table.put(element))
package com.april.eighth;
import java.util.Arrays;
import java.util.List;
public class Exclusion {
public static void main(String[] args) {
List<Integer> A = Arrays.asList(1, 3, 4, 6,8,10, 17, 34);
List<Integer> B = Arrays.asList(2, 8, 17, 33, 44, 66, 89, 100, 123);
for(int element:A)
{
int temp=B.indexOf(element);
if(temp==-1)
{
//element which are in A but not in B
//store it where you want list or aarray
}
}
for(int element:B)
{
int temp=A.indexOf(element);
if(temp==-1)
{
//element which are in B but not in A
// store it where you want list or aarray
}
}
}
}
private static void uniqueElements() {
List<Integer> lstA1 = Arrays.asList(1, 3, 4, 6 , 8, 10, 17, 34);
List<Integer> lstA2 = Arrays.asList(2, 8, 17, 33, 44, 66, 89, 100, 123);
Set<Integer> stResult = new TreeSet<Integer>();
for (int i : lstA1) {
if(!lstA2.contains(i)) stResult.add(i);
}
for (int i : lstA2) {
if(!lstA1.contains(i)) stResult.add(i);
}
System.out.println(stResult);
}
public class FindUnique {
public static void find(ArrayList<Integer> A, ArrayList<Integer> B){
int posA = 0;
int posB = 0;
ArrayList<Integer> result = new ArrayList<Integer>();
while(posA < A.size() || posB < B.size()){
//if we've been thru one of the lists
if(posA >= A.size()){
result.add(B.get(posB));
posB++;
continue;
}
else if(posB >= B.size()){
result.add(A.get(posA));
posA++;
continue;
}
//put the smaller one into result list
if(A.get(posA) < B.get(posB)){
result.add(A.get(posA));
posA++;
}
else if(A.get(posA) > B.get(posB)){
result.add(B.get(posB));
posB++;
}
else { //when equal, skip to next in both lists
posA++;
posB++;
}
}
//output result
for(int i=0;i<result.size();i++){
System.out.print(result.get(i)+" ");
}
}
}
/*
You have two sorted list A and B.
A = [1, 3, 4, 6,8,10, 17, 34]
B = [2, 8, 17, 33, 44, 66, 89, 100, 123]
Write a program to print those numbers which are
1) in A and not in B
2) in B and not in A
Eg: After print: 1 , 3 , 4 , 6 , 10, 33, 34, 44,, 66, 89, 100, 123
*/
#include<iostream>
#include<vector>
using namespace std;
void printArray(int *a, int *b, int _a,int _b )
{
int i=0,j=0;
vector<int> onlyA;
vector<int> onlyB;
vector<int>::iterator it;
for(;i<_a && j<_b;)
{
if(a[i]==b[j])
{
i++;
j++;
}
else
if(a[i]<b[j])
{
if(a[i]!=a[i-1])
onlyA.push_back(a[i]);
i++;
}
else if(a[i]>b[j])
{
if(b[j]!=b[j-1])
onlyB.push_back(b[j]);
j++;
}
}
while(i<_a)
{
onlyA.push_back(a[i++]);
}
while(j<_b)
{
onlyB.push_back(b[j++]);
}
cout<<"Present in a only"<<endl;
for(it=onlyA.begin();it!=onlyA.end();++it)
cout<<*it<<endl;
cout<<"Present in b only"<<endl;
for(it=onlyB.begin();it!=onlyB.end();++it)
cout<<*it<<endl;
}
int main()
{
int a[]={1,2, 3, 4, 6,8,10, 17, 34} ;
int b[]={2,2,2,2, 8, 17, 33, 44, 66, 89, 100, 123};
printArray(a,b,sizeof(a)/sizeof(a[0]),sizeof(b)/sizeof(b[0]));
return 0;
}
class Test
{
public static void main(String g[])
{
int i,j,k=0;
int A[] = {1, 3, 4, 6, 8, 10, 17, 34};
int B[] = {2, 8, 17, 33, 44, 66, 89, 100, 123};
int s1 = A.length;
int s2 = B.length;
int c[] = new int[s1+s2];
for(i=0,j=0;;)
{
if((i==s1) && (j==s2))
{break;}
else if((i == s1) && (B[j]>A[i-1]))
{c[k]=B[j];
j++;
k++;}
else if(A[i]==B[j])
{i++;
j++;}
else if(A[i]<B[j])
{c[k]=A[i];
i++;
k++;}
else if(B[j]<A[i])
{c[k]=B[j];
j++;
k++;}
}
for(i=0;i<k;i++)
{
System.out.print(c[i]+" ");
}
}
}
public static void main(String ars[]){
ArrayList<Integer> B=new ArrayList<Integer>();
ArrayList<Integer> A=new ArrayList<Integer>();
ArrayList<Integer> res=new ArrayList<Integer>();
boolean found=false;
B.add(2);B.add(8);B.add(17);B.add(33);B.add(44);B.add(66);B.add(89);B.add(100);B.add(123);
A.add(1);A.add(3);A.add(4);A.add(6);A.add(8);A.add(10);A.add(17);A.add(34);
for(int i=0;i<B.size();i++){
for(int j=0;j<A.size();j++){
found=false;
if(A.get(j)==B.get(i)){
found=true;
break;
}
}
if(!found){
res.add(B.get(i));
}
}
//System.out.print(res);
for(int i=0;i<A.size();i++){
for(int j=0;j<B.size();j++){
found=false;
if(A.get(i)==B.get(j)){
found=true;
break;
}
}
if(!found){
res.add(A.get(i));
}
}
System.out.print(res);
}
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package mar31;
/**
*
* @author Harika
*/
public class ArrayEx {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
int[] arr={1,3,4,6,8,10,17,34};
int[] arr1={2,8,17,33,44,66,89,100,123};
System.out.print("A elements which are not in B:");
for (int i = 0; i < arr.length; i++) {
int s=0;
for (int j = 0; j < arr1.length; j++) {
if (arr[i]==arr1[j]) {
s=2;
break;
}else{
s=0;
}
}
if (s==0) {
System.out.print(arr[i]+",");
}else{
s=0;
}
}
System.out.println();
System.out.print("B elements which are not in A:");
for (int i = 0; i < arr1.length; i++) {
int s=0;
for (int j = 0; j < arr.length; j++) {
if (arr1[i]==arr[j]) {
s=2;
break;
}else{
s=0;
}
}
if (s==0) {
System.out.print(arr1[i]+",");
}else{
s=0;
}
}
System.out.println();
}
}
#include<stdio.h>
#include<iostream>
using namespace std;
struct list
{
int data;
struct list *next;
}*head=NULL,*head1=NULL;
struct list *ins_list(struct list *head,int n)
{
struct list *temp=head,*t;
if(!head)
{
head=new list;
head->data=n;
head->next=NULL;
}
else
{
while(temp->next!=NULL)temp=temp->next;
t=new list;
t->data=n;
t->next=NULL;
temp->next=t;
}
return head;
}
int remove_dupilicates(struct list *head,struct list *head1)
{
int flag=1;
struct list *temp=head,*temp1=head1;
while(temp||temp1)
{
if(!temp)
while(temp1)
{
printf("\n%d",temp1->data);
temp1=temp1->next;
}
else if(!temp1)
while(temp!=NULL)
{
printf("\n%d",temp->data);
temp=temp->next;
}
else
{
while(temp1&&temp1->data<temp->data)
{
printf("\n%d",temp1->data);
temp1=temp1->next;
}
if(temp&&temp1&&temp->data==temp1->data)flag=0;
else if(temp1&&(temp1->data!=temp->data)&&temp->next&&(temp1->data<temp->next->data))
{
printf("\n%d\n%d",temp->data,temp1->data);
temp1=temp1->next;
}
else if(temp1&&!temp->next&&temp1->data!=temp->data){
printf("\n%d\n%d",temp->data,temp1->data);
temp1=temp1->next;}
else if(!temp1)
printf("\n%d",temp->data);
else
printf("\n%d",temp->data);
if(!flag){
temp=temp->next;
temp1=temp1->next;}
else
temp=temp->next;
flag=1;
}
}
return 0;
}
int main()
{
int i,n,d;
printf("enter the number of elements in list1:\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&d);
head=ins_list(head,d);
}
printf("enter the number of elements in the list2:\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&d);
head1=ins_list(head1,d);
}
remove_dupilicates(head,head1);
return 0;
}
public class PrintTwoListExclusiveData {
public static void printExclusiveDataByList(List<Integer> aList, List<Integer> bList) {
List<Integer> exclusiveDataList = new ArrayList<Integer>();
if(aList != null) {
for(Integer aListItem : aList) {
Integer find = Collections.binarySearch(bList, aListItem);
if(find < 0) {
exclusiveDataList.add(aListItem);
}
}
}
if(bList != null) {
for(Integer bListItem : bList) {
Integer find = Collections.binarySearch(aList, bListItem);
if(find < 0) {
exclusiveDataList.add(bListItem);
}
}
}
Collections.sort(exclusiveDataList);
System.out.println(exclusiveDataList);
}
//thanx Anonymous
public static void printExclusiveDataByHashSet(List<Integer> aList, List<Integer> bList) {
Set<Integer> aSet = new HashSet<Integer>(aList);
Set<Integer> bSet = new HashSet<Integer>(bList);
aSet.removeAll(bList);
bSet.removeAll(aList);
aSet.addAll(bSet);
Integer[] resultArray = new Integer[aSet.size()];
resultArray = aSet.toArray(resultArray);
List<Integer> resultList = Arrays.asList(resultArray);
Collections.sort(resultList);
System.out.println(resultList);
}
public static void main(String[] args) {
List<Integer> A = Arrays.asList(1, 3, 4, 6, 8, 10, 17, 34);
List<Integer> B = Arrays.asList(2, 8, 17, 33, 44, 66, 89, 100, 123);
printExclusiveDataByList(A, B);
printExclusiveDataByHashSet(A, B);
}
}
list : binary search or using set
public static void main(String[] args) {
int[] A = {1, 3, 4, 6,8,10, 17, 34};
int[] B = {2, 8, 17, 33, 44, 66, 89, 100, 123};
int l1=A.length, l2=B.length, i=0, j=0;
while(i+j<l1+l2 && i<l1 && j<l2){
if(A[i] < B[j]){
System.out.println(A[i]);
i++;
}
else if(A[i] > B[j]){
System.out.println(B[j]);
j++;
}
else{
i++;
j++;
}
}
if(i<l1){
for(;i<l1;i++){
System.out.println(A[i]);
}
}
if(j<l2){
for(;j<l2;j++){
System.out.println(B[j]);
}
}
}
static void printUniqueList(int list1[],int list2[]){
int i=0,j=0;
while(i<list1.length || j<list2.length )
{
if(i<list1.length){
if(list1[i]<list2[j]){
System.out.println( list1[i++]);
}else if(list1[i]!=list2[j]){
System.out.println( list2[j++]);
}else{
i++;
j++;
}
}else{
System.out.println( list2[j++]);
}
}
}
}
}
Time= O(N)
Space= O(1)
public class AandBArray {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = {1, 3, 4, 6, 10, 17, 24, 33, 100,101};
int b[] = {2, 8, 17, 33, 44, 66, 89,100,101,102,103};
int i=0,j=0;
for(;;)
{
if(a[i]==b[j])
{
common++;
i++;
j++;
}
else if(a[i]>b[j])
{
System.out.println(b[j]);
j++;
}
else
{
System.out.println(a[i]);
i++;
}
if(i==a.length || j==b.length)
{
System.out.println(i+" "+j);
break;
}
}
while(i!=a.length)
{
System.out.println(a[i]);
i++;
}
while(j!=b.length)
{
System.out.println(b[j]);
j++;
}
package Morgan_Stanley;
public class Print_Not_Comman_Elems_In_SortdArry {
int [] A = {1, 3, 4, 6,8,10, 17, 34} ;
int [] B = {2, 8, 17, 33, 44, 66, 89, 100, 123};
int len1 = A.length;
int len2 = B.length;
int maxlen = len1+len2-1;
int i=0;int j=0;
public void print(){
while(i<maxlen){
if((i<len1)&&(j<len2)){
if(A[i]==B[j]){
j++;
i++;
continue;
}else if(A[i]>B[j]){
System.out.println(B[j]);
System.out.println(A[i]);
j++;
}else
System.out.println(A[i]);
}else if(i<len1)
System.out.println(A[i]);
else{
if(j<len2)
System.out.println(B[j]);
j++;
}
i++;
}
}
public static void main(String args[]){
Print_Not_Comman_Elems_In_SortdArry obj = new Print_Not_Comman_Elems_In_SortdArry();
obj.print();
}
}
package com.shweta.demo;
import java.util.ArrayList;
import java.util.List;
public class FindElementsPresentInoneArray {
/*
* You have two sorted list A and B.
A = [1, 3, 4, 6,8,10, 17, 34]
B = [2, 8, 17, 33, 44, 66, 89, 100, 123]
Write a program to print those numbers which are
1) in A and not in B
2) in B and not in A
Eg: After print: 1 , 3 , 4 , 6 , 10, 33, 34, 44,, 66, 89, 100, 123
*/
public static void main(String[] args) {
int A[] = {1, 3, 4, 6,8,10, 17, 34} ;
int B[] = {2, 8, 17, 33, 44, 66, 89, 100, 123};
List result = new ArrayList<Integer>();
int j=0;
int i=0;
while(i<A.length && j<B.length)
{
if(A[i] < B[j])
{
result.add(A[i]);
i++;
continue;
}
if(A[i] == B[j])
{
i++;
j++;
continue;
}
if(A[i] > B[j])
{
result.add(B[j]);
j++;
continue;
}
}
while(i==A.length && j<B.length)
{
result.add(B[j]);
j++;
}
for(int k=0;k<result.toArray().length;k++)
{
System.out.println(result.toArray()[k] +",");
}
}
}
import java.util.ArrayList;
public class sample1
{
public static void main(String args[])
{
int ar[]={2,3,4,5,6,7,8};
int ar1[]={3,6,8,10,12,14,16};
//int com[]=null;//
int count=0;
ArrayList<Integer> com=new ArrayList<Integer>();
for(int i=0;i<ar.length;i++)
{
for(int j=0;j<ar1.length;j++)
{
if(ar[i]==ar1[j])
{
com.add(ar[i]);
count++;
}
}
}
for(int i=0;i<com.size();i++)
{
System.out.print(com.get(i));
}
System.out.println("int A NOt in B");
for(int i=0;i<ar.length;i++)
{
int count1=0;
for(int j=0;j<com.size();j++)
{
if((com.get(j).equals(ar[i])))
{
count1++;
}
}
if(count1!=1)
{
System.out.println(ar[i]);
}
}
System.out.println("int B NOt in A");
for(int i=0;i<ar1.length;i++)
{ int count2=0;
for(int j=0;j<com.size();j++)
{
if((com.get(j).equals(ar1[i])))
{
count2++;
}
}
if(count2!=1)
{
System.out.print(ar1[i]);
}
}
}
}
package com.cv;
import java.util.Set;
import java.util.TreeSet;
public class CollectionTest {
public static void main(String[] args) {
int[] arr = {1, 3, 4, 6,8,10, 17, 34};
int[] arr1 = {2, 8, 17, 33, 44, 66, 89, 100, 123};
Set set1=returnList(arr);
Set set2=returnList(arr1);
set2.addAll(set1);
System.out.print("Final Elements"+set2);
}
public static Set returnList(int[] arr)
{
Set set=new TreeSet();
for(int i=0;i<arr.length;i++)
{
set.add(arr[i]);
}
return set;
}
}
#include<iostream.h>
#include<conio.h>
int main(){
int A[] = {1, 3, 4, 6, 8, 10, 17, 17, 34};
int B[] = {2, 8, 8, 17, 33, 44, 66, 89, 100, 123};
int i=0, j=0;
int Al = sizeof(A)/sizeof(A[0]);
int Bl = sizeof(B)/sizeof(B[0]);
char x='a';
cout<<"NotInA or NotInB (A/B): ";
cin>>x;
if(x=='a' || x=='A'){
while(i<Al && j<Bl){
if(A[i]<B[j]){
i++;
}
else if(A[i]>B[j]){
cout<<B[j]<<endl;
j++;
}
else{
j++;
}
}
while(j<Bl){
cout<<B[j]<<endl;
j++;
}
}
else{
while(i<Al && j<Bl){
if(B[j]<A[i]){
j++;
}
else if(B[j]>A[i]){
cout<<A[i]<<endl;
i++;
}
else{
i++;
}
}
while(i<Al){
cout<<A[i]<<endl;
i++;
}
}
getch();
return 0;
}
public void printUnique(int[] arrA, int[] arrB) {
int aLength = arrA.length;
int bLength = arrB.length;
int a = 0;
int b = 0;
while (true) {
if (a == aLength){
for (;b < bLength; b++)
System.out.println(arrB[b]);
break;
}
if (b == bLength) {
for (;a < aLength; a++)
System.out.println(arrA[a]);
break;
}
if (arrA[a] < arrB[b]) {System.out.println(arrA[a]); a++; }
else if (arrA[a] > arrB[b]) {System.out.println(arrB[b]); b++;}
else {a++; b++;}
}
}
public static void main(String[] args) {
int A[] = new int[]{1, 3, 4, 6,8,10, 17, 34, 89,125};
int B[] = new int[]{2, 8, 17, 33, 44, 66, 89, 100, 123};
int j = 0;
for (int i = 0; i < A.length ; i++){
if (A[i] > B[j]){
while (j < B.length){
if (A[i] > B[j]){
j++;
}else{
break;
}
}
}
if (j < B.length && A[i] == B[j]){
System.out.println("A[i] == B[j]" + B[j]);
j++;
}
}
}
public static void main(String[] args) {
int[] A = { 1, 3, 4, 6, 8, 10, 17, 34 };
int[] B = { 2, 8, 17, 33, 44, 66, 89, 100, 123 };
int a = 0, b = 0;
while (b < B.length) {
if (A[a] == A.length) {
System.out.println(B[b++]);
continue;
}
if (A[a] < B[b]) {
System.out.println(A[a++]);
} else if (A[a] > B[b]) {
System.out.println(B[b++]);
} else {
a++;
b++;
}
}
}
public class inAnotinB {
public static void main(String[] args) {
int[] A = {1, 3, 4, 6,8,10, 17, 34} ;
int[] B = {2, 8, 17, 33, 44, 66, 89, 100, 123};
int largest = A[A.length-1] > B[B.length-1]? A[A.length-1] : B[B.length-1];
int smallest = A[A.length-1] < B[B.length-1]? A[A.length-1] : B[B.length-1];
int i=0,j=0;
while(smallest != largest) {
if(A[i] == B[j]) {
smallest = A[i];
i++;
j++;
} else if(A[i] < B[j]) {
System.out.print(A[i]+" ");
smallest = A[i];
i++;
} else {
smallest = B[j];
System.out.print(B[j]+" ");
j++;
}
if(i>=A.length) {
for (; j < B.length; j++) {
System.out.print(B[j] + " ");
smallest = B[j];
}
}
if(j>=B.length) {
for (; i < A.length; i++) {
System.out.print(A[i] + " ");
smallest = A[i];
}
}
}
}
}
public class PrintNotCommonInBothArrays {
List<Integer> list=new ArrayList<Integer>();
public void print(int A[],int B[])
{
int i=0,j=0;
boolean flag=false;
for( i=0;i<A.length;i++)
{
flag=false;
for( j=0;j<B.length;j++)
{
if(A[i]==B[j])
{
flag=true;
break;
}
}
if(j==B.length && flag==false)
{
//System.out.println(A[i]);
list.add(A[i]);
}
}
}
public static void main(String[] args) {
PrintNotCommonInBothArrays pib=new PrintNotCommonInBothArrays();
int A[] = {1, 3, 4, 6,8,10, 17, 34};
int B[] = {2, 8, 17, 33, 44, 66, 89, 100, 123};
pib.print(A,B);
pib.print(B, A);
Collections.sort(pib.list);
System.out.println(pib.list);
}
}
private static void getUnion(){
List<Integer> list1 = (List<Integer>)Arrays.asList(1, 3, 4, 6,8,10, 17, 34);
List<Integer> list2 =(List<Integer>) Arrays.asList(2, 8, 17, 33, 44, 66, 89, 100, 123);
for(Integer i : list1){
if(list2.contains(i)){
continue;
}else{
System.out.println(i);
}
}
for(Integer i : list2){
if(list1.contains(i)){
continue;
}else{
System.out.println(i);
}
}
}
Here is my solution in java.There is one advantage with this data is both the array are already sorted,so we are taking advantage of that by comparing.
This can be considered as one step of merge sort also.
int a[] = {1, 3, 4, 6,8,10, 17, 34};
int b[] = {2, 8, 17, 33, 44, 66, 89, 100, 123};
StringBuilder result = new StringBuilder();
int aCntr = 0,bCntr = 0;
while(aCntr<a.length && bCntr<b.length) {
if(a[aCntr]==b[bCntr]){
aCntr++;bCntr++;
}
else
result.append(a[aCntr]<b[bCntr] ?a[aCntr++]:b[bCntr++]).append(",");
}
while(aCntr<a.length) result.append(a[aCntr++]).append(",");
while(bCntr<b.length) result.append(b[bCntr++]).append(",");
System.out.println(result.toString());
Integer[] int1Ary = { 1, 3, 4, 6, 8, 10, 17, 34 };
Integer[] int2Ary = { 2, 8, 17, 33, 44, 66, 89, 100, 123 };
ArrayList<Integer> ar1 = new ArrayList<Integer>(Arrays.asList(int1Ary));
ArrayList<Integer> ar2 = new ArrayList<Integer>(Arrays.asList(int2Ary));
ArrayList<Integer> ar3 = new ArrayList<Integer>(Arrays.asList(int2Ary));
ar2.retainAll(ar1);
System.out.println(ar2);
ar1.removeAll(ar2);
System.out.println(ar1);
ar3.removeAll(ar2);
System.out.println(ar3);
ArrayList<Integer> ar4 = new ArrayList<Integer>();
ar4.addAll(ar1);
ar4.addAll(ar3);
System.out.println("Output :" + ar4);
Integer[] int1Ary = { 1, 3, 4, 6, 8, 10, 17, 34 };
Integer[] int2Ary = { 2, 8, 17, 33, 44, 66, 89, 100, 123 };
ArrayList<Integer> ar1 = new ArrayList<Integer>(Arrays.asList(int1Ary));
ArrayList<Integer> ar2 = new ArrayList<Integer>(Arrays.asList(int2Ary));
ArrayList<Integer> ar3 = new ArrayList<Integer>(Arrays.asList(int2Ary));
ar2.retainAll(ar1);
System.out.println(ar2);
ar1.removeAll(ar2);
System.out.println(ar1);
ar3.removeAll(ar2);
System.out.println(ar3);
ArrayList<Integer> ar4 = new ArrayList<Integer>();
ar4.addAll(ar1);
ar4.addAll(ar3);
System.out.println("Output :" + ar4);
Integer[] int1Ary = { 1, 3, 4, 6, 8, 10, 17, 34 };
Integer[] int2Ary = { 2, 8, 17, 33, 44, 66, 89, 100, 123 };
ArrayList<Integer> ar1 = new ArrayList<Integer>(Arrays.asList(int1Ary));
ArrayList<Integer> ar2 = new ArrayList<Integer>(Arrays.asList(int2Ary));
ArrayList<Integer> ar3 = new ArrayList<Integer>(Arrays.asList(int2Ary));
ar2.retainAll(ar1);
System.out.println(ar2);
ar1.removeAll(ar2);
System.out.println(ar1);
ar3.removeAll(ar2);
System.out.println(ar3);
ArrayList<Integer> ar4 = new ArrayList<Integer>();
ar4.addAll(ar1);
ar4.addAll(ar3);
System.out.println("Output :" + ar4);
public class FindUniqueIntegers {
public static void main(String[] args) {
List<Integer> list1 = new ArrayList<>(Arrays.asList(1, 3, 4, 6,8,10, 17, 34));
List<Integer> list2 = new ArrayList<>(Arrays.asList(2, 8, 17, 33, 44, 66, 89, 100, 123));
List<Integer> list3 = new ArrayList<>();
//Elements in list1 and not in list2
for(Integer l1: list1){
if(!list2.contains(l1)){
list3.add(l1);
}
}
//Elements in list2 and not in list1
for(Integer l2: list2){
if(!list1.contains(l2)){
list3.add(l2);
}
}
Collections.sort(list3);
System.out.println(list3);
}
}
need more clarification, as per the question, out put should contain 2 as well.
- Vin April 07, 2013if that is the case, below will work.
take 2 pointers which points to the first elements of A and B respectively.
while both pointers are in list range compare the values pointer by the pointers
if both values are equal, increment both pointers till the next value not equal to current value.
if one less than the other, print the smaller value and increment the pointer which points to smaller one.
print the remaining values in the non completed list.
time O(n) and constant space.