Coupon Dunia Interview Question SDE1s
Country: India
Logic goes like this:
Sample imput :
ar1[] = {1, 5, 10, 20, 40, 80}
ar2[] = {6, 7, 20, 80, 100}
ar3[] = {3, 4, 15, 20, 30, 70, 80, 120}
1: Take the first element from all arrays and pick the greatest among them (6 as per this imput)
2: Remove all elements from the arrays which are smaller than this selected element, as the arrays are sorted so smaller number would not be present in all arrays(1,5 and 3,4 will be deleted from arr1[] and arr2[] respectively)
Sample input would reduce to:
ar1[] = {10, 20, 40, 80}
ar2[] = {6, 7, 20, 80, 100}
ar3[] = {15, 20, 30, 70, 80, 120}
3: Keep on repeating step 1 and 2 until don't find same element at first position in all arrays.
4: return the element if same element occurs at first index in all arrays.
int ar1[] = {1, 5, 10, 20, 40, 80};
int ar2[] = {6, 7, 20, 80, 80};
int ar3[] = {3, 4, 15, 20, 30, 70, 80, 80};
int i_A, i_B, i_C;
int max = 0;
int res_len = 0;
int res[8]; // the size of the biggest one - simple to calculate
i_A = i_B = i_C = 0;
bool stop = false;
bool terminated = false;
while(!terminated){
if(ar1[i_A] > ar2[i_B] && ar1[i_A] > ar3[i_C])
max = ar1[i_A];
else if(ar2[i_B] > ar1[i_A] && ar2[i_B] > ar3[i_C])
max = ar2[i_B];
else
max = ar3[i_C];
// AR1
stop = false;
while(i_A < ar1.size() && !stop){
if(ar1[i_A] >= max)
stop = true;
else
i_A++;
}
// AR2
stop = false;
while(i_B < ar2.size() && !stop){
if(ar2[i_B] >= max)
stop = true;
else
i_B++;
}
// AR3
stop = false;
while(i_C < ar3.size() && !stop){
if(ar3[i_C] >= max)
stop = true;
else
i_C++;
}
if(i_A < ar1.size() && i_B < ar2.size() && i_C < ar3.size()){
if(ar1[i_A]==ar2[i_B] && ar2[i_B]==ar3[i_C]){
res[res_len] = ar1[i_A];
res_len++;
}
i_A++;
i_B++;
i_C++;
}
else{
cout<<"Result"<< endl;
for(int i = 0; i < res_len; i++){
cout<<res[i]<<endl;
}
terminated = true;
}
}
If there is no space constraint, then go over all the arrays and find the min and max values.
Then, create an array of size max + min only if the min is negative. If the min is positive, then just create an array of size max.
When going over the arrays, then the value of the array is the index in the newly array which you created, and add 1 to the value of the index.
After going over all the arrays, scan once again the created array and check who has value which is more than 1.
Of course, if the min value is negative, then there will be an offset to consider.
import java.util.*;
import java.lang.*;
import java.io.*;
class CommonElement
{
private static int arrayOfArrays[][] = {
{1, 5, 4, 3},
{3, 4, 5, 10, 6, 8},
{5, 10, 20, 4, 3},
{5, 4, 10, 20, 12},
{2, 4, 10, 5}
};
public static ArrayList<Integer> presentElements = new ArrayList<Integer>();
public static int[] getSmallestSizedArray() {
int smallestSize = getSmallestArraySize();
int[] smallestArray = null;
for(int i = 0; i< arrayOfArrays.length; i++) {
if(arrayOfArrays[i].length == smallestSize) {
smallestArray = arrayOfArrays[i];
}
}
return smallestArray;
}
private static int getSmallestArraySize() {
ArrayList<Integer> arrays = new ArrayList<Integer>();
for(int i = 0; i< arrayOfArrays.length; i++) {
arrays.add(arrayOfArrays[i].length);
}
Collections.sort(arrays);
int smallest = arrays.get(0);
return smallest;
}
public static void checkInArray(int index, int element) {
for(int i = 0; i< arrayOfArrays[index].length; i++) {
if(arrayOfArrays[index][i] == element) {
if(index == arrayOfArrays.length-1) {
presentElements.add(element);
} else {
checkInArray(index+1, arrayOfArrays[index][i]);
}
}
}
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int[] smallestArray = getSmallestSizedArray();
for(int i = 0; i< smallestArray.length; i++) {
checkInArray(0, smallestArray[i]);
}
System.out.println(presentElements.toString());
}
}
int[] array1 = {1, 5, 10, 20, 40, 80};
int[] array2 = {6, 7, 20, 80, 100};
int[] array3 = {3, 4, 15, 20, 30, 70, 80, 120};
int length1 = array1.length;
for (int i = 0; i < length1; i++)
{
if(Arrays.binarySearch(array2, array1[i]) < 0)
{
continue;
} else if(Arrays.binarySearch(array3, array1[i]) < 0)
{
continue;
} else
{
System.out.println(array1[i]);
}
}
import java.util.Arrays;
public class FindCommonElementInArrays {
public static void main(String[] args) {
int[] array1 = {1, 5, 10, 20, 40, 80};
int[] array2 = {6, 7, 20, 80, 100};
int[] array3 = {3, 4, 15, 20, 30, 70, 80, 120};
int length1 = array1.length;
int count = 0;
long startTime = System.nanoTime();
while (count < 100000000)
{
for (int i = 0; i < length1; i++)
{
if(Arrays.binarySearch(array2, array1[i]) < 0)
{
continue;
} else if(Arrays.binarySearch(array3, array1[i]) < 0)
{
continue;
} else
{
//System.out.println(array1[i]);
}
}
count++;
}
long stopTime = System.nanoTime();
System.out.println((stopTime - startTime) / 1000000000.0);
}
}
import java.util.Arrays;
public class FindCommonElementInArrays {
public static void main(String[] args) {
int[] array1 = {1, 5, 10, 20, 40, 80};
int[] array2 = {6, 7, 20, 80, 100};
int[] array3 = {3, 4, 15, 20, 30, 70, 80, 120};
int length1 = array1.length;
int count = 0;
long startTime = System.nanoTime();
while (count < 100000000)
{
for (int i = 0; i < length1; i++)
{
if(Arrays.binarySearch(array2, array1[i]) < 0)
{
continue;
} else if(Arrays.binarySearch(array3, array1[i]) < 0)
{
continue;
} else
{
//System.out.println(array1[i]);
}
}
count++;
}
long stopTime = System.nanoTime();
System.out.println((stopTime - startTime) / 1000000000.0);
}
}
As @gowtham's answer works for the above sample. The below code is not restricted just the 3 arrays provided in the sample. It will work for n number of arrays added to a ArrayList in Java.
/*
* Compare one array to another, for the first time compary first two arrays
* and find the common elements. Next time onwards use this common array to compare
* the next array, repeat this till the last array.
*/
public static void printCommonElements(List<Integer[]> intArrays){
if(null != intArrays){
Integer commonArray[] = null;
for(int i=0;i<intArrays.size();i++){
if(null == commonArray){
commonArray = intArrays.get(i);
}
if(i+1 != intArrays.size()){//Compare only against last element
commonArray = getCommonElements(commonArray, intArrays.get(i+1));
}
}
//Print the result.
for(Integer val:commonArray){
System.out.print(" "+val);
}
}
}
/*
*Compare the two arrays and return the common elements amongst them.
*/
public static Integer[] getCommonElements(Integer ar1[],Integer ar2[]){
List<Integer> intArry = new ArrayList<Integer>();
for(int i=0;i<ar1.length;i++){
for(int j=0;j<ar2.length;j++){
if(ar1[i] == ar2[j]){
intArry.add(ar1[i]);
}
}
}
return intArry.toArray(new Integer[intArry.size()]);
}
public static void main(String... args){
List<Integer[]> list = new ArrayList<>();
list.add(new Integer[] {1, 5, 10, 20, 40, 80});
list.add(new Integer[] {6, 7, 20, 80, 100,10});
list.add(new Integer[] {3, 4, 15, 20, 30, 70, 80,10, 120} );
list.add(new Integer[] {10,30,40,50,80,20} );
printCommonElements(list);
}
}
#include<iostream>
using namespace std;
int main()
{
int a[]={1,2,3,5,6};
int b[]={2,5};
int c[]={2};
int s=sizeof(a)/sizeof(int);
int s1=sizeof(b)/sizeof(int);
int s2=sizeof(c)/sizeof(int);
int i=0;
int j=0;
int k=0;
int dum1=100;
int dum2=1000;
while(s--)
{
while(s1--)
{
// cout<<"yo"<<s1<<endl;
if(a[i]==b[j])
{
// cout<<"hey"<<endl;
dum1=b[j];
break;
}
else
j++;
}
while(s2--)
{
if(a[i]==c[k])
{
dum2=c[k];
break;
}
else
k++;
}
//cout<<s<<dum1<<dum2<<endl;
if(dum1==dum2)
cout<<dum1<<endl;
dum1=100;
dum2=1000;
i++;
j=0;
k=0;
s1=sizeof(b)/sizeof(int);
//cout<<"size of s1"<<s1<<endl;
s2=sizeof(c)/sizeof(int);
}
// cout<<s<<endl;
return 0;
}
#include<iostream>
using namespace std;
int main()
{
int a[]={1,2,3,5,6};
int b[]={2,5};
int c[]={2};
int s=sizeof(a)/sizeof(int);
int s1=sizeof(b)/sizeof(int);
int s2=sizeof(c)/sizeof(int);
int i=0;
int j=0;
int k=0;
int dum1=100;
int dum2=1000;
while(s--)
{
while(s1--)
{
// cout<<"yo"<<s1<<endl;
if(a[i]==b[j])
{
// cout<<"hey"<<endl;
dum1=b[j];
break;
}
else
j++;
}
while(s2--)
{
if(a[i]==c[k])
{
dum2=c[k];
break;
}
else
k++;
}
//cout<<s<<dum1<<dum2<<endl;
if(dum1==dum2)
cout<<dum1<<endl;
dum1=100;
dum2=1000;
i++;
j=0;
k=0;
s1=sizeof(b)/sizeof(int);
//cout<<"size of s1"<<s1<<endl;
s2=sizeof(c)/sizeof(int);
}
// cout<<s<<endl;
return 0;
}
class SameElementsInArray
{
public static void main(String[] args)
{
int a1[]={2,3,5,7,9,11};
int a2[]={1,2,3,4};
int a3[]={1,2,3};
int i=0;
while(i<a3.length)
{
for(int j=0;j<a2.length;j++)
{
if(a3[i]==a2[j])
{
for(int k=0;k<a1.length;k++)
{
if(a3[i]==a1[k])
System.out.println("The Common Elements are:"+a3[i]);
}
}
}
i++;
}
}
}
The below code is written in java
- gowtham kesa March 15, 2015int ar1[] = {1, 5, 5} , ar2[] = {3, 4, 5, 5, 10}, ar3[] = {5, 5, 10, 20} ; int s1=ar1.length,s2=ar2.length,s3=ar3.length; int i=0,j=0,k=0; while(i<s1 && j<s2 && k<s3) { if((ar1[i]==ar2[j])&&(ar2[j]==ar3[k])) {System.out.println(ar1[i]);i++;j++;k++;} else{ if(ar1[i]<ar2[j]) {i++;continue;} else if(ar1[i]>ar2[j]) {j++;continue;} if(ar2[j]<ar3[k]) {j++;continue;} else if(ar2[j]>ar3[k]) {k++;continue;} } }