## IBM Interview Question for Java Developers

• 1
of 1 vote

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
3
of 3 vote

Here is a Python version with complexity O(min(n, m)), where n is the length of first list, and m is the length of second list.

``````a = [2, 5, 5, 5]
b = [2, 2, 3, 5, 5, 7]

ia = 0
ib = 0
output = []
while ia < len(a) and ib < len(b):
if a[ia] < b[ib]:
ia += 1
elif a[ia] > b[ib]:
ib += 1
else: # they are equal
output.append(a[ia])
ia += 1
ib += 1

print output``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

It might be a good idea to keep len(a) and len(b) in a variable then calculating every loop, small improvement

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````public ArrayList<Integer> merged(int[] a, int[] b) throws NullPointerException
{
if(a==null||b==null)
{
throw new NullPointerException();
}
if(a.length==0||b.length==0)
{
throw new InvalidInputException();
}
ArrayList<Integer> results=new ArrayList<Integer>();
int j=a.length-1;
int i=b.length-1;
while(j>=0 && i>=0)
{
if(a[i]==b[j])
{
results.insert(a[i]);
i--;
j--;
}
else if(a[i]>b[j])
{
i--;
}else
{
j--;
}
}
return results;
}``````

O(n+m) time complexity, O(k) space complexity (k is the number of similar elements).

Comment hidden because of low score. Click to expand.
0
of 0 votes

time complexity is O(min(n,m)) isnt it?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void printCommon(list<int> aList, list<int> bList){
node a = a.head();
node b = b.head();
while(){
int aCount = 0;
int bCount = 0;
//advance to handle duplicates
while(a.next.data == a.data){
a = a.next;
}
while(b.next.data == b.data){
b = b.next;
}

if(a.data == b.data){
for(int i = 0; i < Math.min(aCount,bCount); i++){
system.out.println(a.data);
}
if(a.next != null){
a = a.next;
}
if(b.next != null){
b=b.next;
}
}
else{
//break if either have a next of null
if(a.next == null || b.next == null) break;

//Advance the one with a smaller number
if(a.data < b.data){
a = a.next;
}
else b = b.next;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Let sorted lists be A[n] & B[m] (implemented as stacks)
Common List to store common elements

i=0
while (n>0 && m>0)
if(A[1]>B[1])
pop A[1]
--n
else if(A[1]<B[1])
pop B[1]
--m
else
CommonList[i++]=A[1] or B[1]
pop A[1]
pop B[1]
--n
--m

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package algo;

import java.util.ArrayList;
import java.util.List;

public class FindCommonSortedList {

public FindCommonSortedList() {
// TODO Auto-generated constructor stub
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr1 = { 2, 5, 5, 7, 7};
int[] arr2 = { 2, 2, 3, 5, 5, 7 };
FindCommonSortedList fc = new FindCommonSortedList();
fc.findCommon(arr1, arr2);
}

public void findCommon(int[] arr1, int[] arr2) {
List<Integer> arr1List = new ArrayList<Integer>();
for (int i : arr1) {
arr1List.add(i);
}
List<Integer> commonList = new ArrayList<Integer>();
for (int j : arr2) {
if (arr1List.contains(j)) {
commonList.add(j);
int index = arr1List.indexOf(j);
arr1List.remove(index);
}
}
print(commonList);

}

public void print(List<Integer> list){
for (int k : list) {
System.out.print(k + " ");
}

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package algo;

import java.util.ArrayList;
import java.util.List;

public class FindCommonSortedList {

public FindCommonSortedList() {
// TODO Auto-generated constructor stub
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr1 = { 2, 5, 5, 7, 7};
int[] arr2 = { 2, 2, 3, 5, 5, 7 };
FindCommonSortedList fc = new FindCommonSortedList();
fc.findCommon(arr1, arr2);
}

public void findCommon(int[] arr1, int[] arr2) {
List<Integer> arr1List = new ArrayList<Integer>();
for (int i : arr1) {
arr1List.add(i);
}
List<Integer> commonList = new ArrayList<Integer>();
for (int j : arr2) {
if (arr1List.contains(j)) {
commonList.add(j);
int index = arr1List.indexOf(j);
arr1List.remove(index);
}
}
print(commonList);

}

public void print(List<Integer> list){
for (int k : list) {
System.out.print(k + " ");
}

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int[] Arr1 = { 2, 5, 5, 5 };
int[] Arr2 = { 2, 2, 3, 5, 5, 7 };
int[] result = new int[Arr1.Length > Arr2.Length ? Arr1.Length : Arr2.Length];
int result_count = 0;
int i = 0, j = 0;
//should return 2, 5, 5 (common elements in both arrays)
// Sorted arryays
while ( i < Arr1.Length && j < Arr2.Length)
{
if (Arr1[i] == Arr2[j])
{
result[result_count] = Arr1[i];
result_count++; i++; j++;
}
else if (Arr1[i] > Arr2[j])
{
j++;
}
else if (Arr1[i] < Arr2[j])
{
i++;
}

}

for (int k = 0; k < result_count; k++)
{
Console.Write(result[k] + "\t");
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Guess if the lists are sorted, we can just compare them by 1 pass, O(N), logic already mentioned, here is just my implenetation, without any extra transformations to lists:

``````public static List getCommonElements(int[] aArr, int[] bArr)
{
List<Integer> resultList = new ArrayList<Integer>();
int i=0,j=0;

while(i<aArr.length&&j<bArr.length) {
if(aArr[i]==bArr[j]) {
resultList.add(aArr[i]);
i++; j++;
}
else if (aArr[i]>bArr[j]) j++;
else if (aArr[i]<bArr[j]) i++;
}
return resultList;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

My algorithm is identical to Alexander's, except in C++.

``````vector<int> commonElements(const vector<int>& v1, const vector<int>& v2) {

vector<int> common;
int i = 0;
int j = 0;

while (i < v1.size() && j < v2.size()) {

if (v1[i] == v2[j]) {
common.push_back(v1[i]);
++i;
++j;
}
if (v1[i] < v2[j]) {
++i;
}
if (v1[i] > v2[j]) {
++j;
}
}

return common;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Running time: O(n). Space: O(1)

``````listA=[2,5,5,5]
listB=[2,2,3,5,5,7]

def find_common(listA,listB)
common_elements=[]

iterA,iterB=0,0

while iterA < listA.length && iterB < listB.length

if listA[iterA] == listB[iterB]
common_elements << listA[iterA]
iterA+=1
iterB+=1
elsif listA[iterA] < listB[iterB]
iterA+=1
else
iterB+=1
end
end

common_elements
end

print find_common(listA,listB)``````

Output:
[2, 5, 5]

Comment hidden because of low score. Click to expand.
0
of 0 vote

Complexity O(min(n+m)), memory O(1)

``````public static Collection<Integer> getCommon(int[] arr1, int[] arr2){
if(arr1 == null || arr2 == null){
throw new NullPointerException();
}

ArrayList<Integer> results = new ArrayList<Integer>();
int arr1Index = 0;
int arr2Index = 0;
//scan the arrays
while(arr1Index < arr1.length && arr2Index < arr2.length){
int val1 = arr1[arr1Index];
int val2 = arr2[arr2Index];
//if the value in arr1 is less than arr2, move to next arr1 value
if(val1 < val2){
arr1Index++;
}
//if the value in arr2 is less than arr1, move the next arr2 value
else if(val2 < val1){
arr2Index++;
}
//otherwise add the value as a result and move to next arr1 and arr2 values
else{
results.add(val1);
arr1Index++;
arr2Index++;
}
}
return results;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

int main()
{
int a[4],b[6];
a[4]={2,5,5,5};
b[6]={2,2,3,55,7};
for(int i=0;i<4;i++)
{
for(int j=0;j<6;j++)
{
if(a[i]==b[j])
{
cout<<a[i]<<endl;
}
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.*;
public class findCommon {

public static void main(String []args)
{
findCommon obj = new findCommon();
int []a={1,2,2,3,4,5,5,6,7,8};
int []b={2,2,5,7,8,8,9};
obj.printCommon(a,b);
}

void printCommon(int []x,int []y)
{
int lx=x.length;
int ly=y.length;
int ix=0,iy=0;
List<Integer> l=new ArrayList<Integer>();
while(ix<lx && iy<ly)
{
if(x[ix]>y[iy])
iy++;
else if(x[ix]<y[iy])
ix++;
else
{
l.add(x[ix]);
ix++;
iy++;
}
}
for(int t:l)
System.out.println(t);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Sorter {
public static void main(String args[]){
List<Integer> x=new ArrayList<Integer>(){{add(30);add(12);add(13);add(46);add(6);add(8);}};
List<Integer> y=new ArrayList<Integer>(){{add(40);add(12);add(52);add(33);add(8);add(6);}};
List<Integer> common=new ArrayList<Integer>();
Collections.sort(x); Collections.sort(y);
for(Integer a:x){
for(Integer b:y){
if(a==b){
common.add(a);
}
}
}
for(Integer b:common){
System.out.println(b+" ");}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Sorter {
public static void main(String args[]){
List<Integer> x=new ArrayList<Integer>(){{add(30);add(12);add(13);add(46);add(6);add(8);}};
List<Integer> y=new ArrayList<Integer>(){{add(40);add(12);add(52);add(33);add(8);add(6);}};
List<Integer> common=new ArrayList<Integer>();
Collections.sort(x); Collections.sort(y);
for(Integer a:x){
for(Integer b:y){
if(a==b){
common.add(a);
}
}
}
for(Integer b:common){
System.out.println(b+" ");}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Sorter {
public static void main(String args[]){
List<Integer> x=new ArrayList<Integer>(){{add(30);add(12);add(13);add(46);add(6);add(8);}};
List<Integer> y=new ArrayList<Integer>(){{add(40);add(12);add(52);add(33);add(8);add(6);}};
List<Integer> common=new ArrayList<Integer>();
Collections.sort(x); Collections.sort(y);
for(Integer a:x){
for(Integer b:y){
if(a==b){
common.add(a);
}
}
}
for(Integer b:common){
System.out.println(b+" ");}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{public class Sorter {
public static void main(String args[]){
List<Integer> x=new ArrayList<Integer>(){{add(30);add(12);add(13);add(46);add(6);add(8);}};
List<Integer> y=new ArrayList<Integer>(){{add(40);add(12);add(52);add(33);add(8);add(6);}};
List<Integer> common=new ArrayList<Integer>();
Collections.sort(x); Collections.sort(y);
for(Integer a:x){
for(Integer b:y){
if(a==b){
common.add(a);
}
}
}
for(Integer b:common){
System.out.println(b+" ");}
}
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Sorter {
public static void main(String args[]){
List<Integer> x=new ArrayList<Integer>(){{add(30);add(12);add(13);add(46);add(6);add(8);}};
List<Integer> y=new ArrayList<Integer>(){{add(40);add(12);add(52);add(33);add(8);add(6);}};
List<Integer> common=new ArrayList<Integer>();
Collections.sort(x); Collections.sort(y);
for(Integer a:x){
for(Integer b:y){
if(a==b){
common.add(a);
}
}
}
for(Integer b:common){
System.out.println(b+" ");}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class Sorter {
public static void main(String args[]){
List<Integer> x=new ArrayList<Integer>(){{add(30);add(12);add(13);add(46);add(6);add(8);}};
List<Integer> y=new ArrayList<Integer>(){{add(40);add(12);add(52);add(33);add(8);add(6);}};
List<Integer> common=new ArrayList<Integer>();
Collections.sort(x); Collections.sort(y);
for(Integer a:x){
for(Integer b:y){
if(a==b){
common.add(a);
}
}
}
for(Integer b:common){
System.out.println(b+" ");}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class Sorter {
public static void main(String args[]){
List<Integer> x=new ArrayList<Integer>(){{add(30);add(12);add(13);add(46);add(6);add(8);}};
List<Integer> y=new ArrayList<Integer>(){{add(40);add(12);add(52);add(33);add(8);add(6);}};
List<Integer> common=new ArrayList<Integer>();
Collections.sort(x); Collections.sort(y);
for(Integer a:x){
for(Integer b:y){
if(a==b){
common.add(a);
}
}
}
for(Integer b:common){
System.out.println(b+" ");}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Sorter {
public static void main(String args[]){
List<Integer> x=new ArrayList<Integer>(){{add(30);add(12);add(13);add(46);add(6);add(8);}};
List<Integer> y=new ArrayList<Integer>(){{add(40);add(12);add(52);add(33);add(8);add(6);}};
List<Integer> common=new ArrayList<Integer>();
Collections.sort(x); Collections.sort(y);
for(Integer a:x){for(Integer b:y){
if(a==b){
common.add(a);
}
}
}
for(Integer b:common)	{	System.out.println(b+" ");	}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Sorter {
public static void main(String args[]){
List<Integer> x=new ArrayList<Integer>(){{add(30);add(12);add(13);add(46);add(6);add(8);}};
List<Integer> y=new ArrayList<Integer>(){{add(40);add(12);add(52);add(33);add(8);add(6);}};
List<Integer> common=new ArrayList<Integer>();
Collections.sort(x); Collections.sort(y);
for(Integer a:x){for(Integer b:y){
if(a==b){
common.add(a);
}
}
}
for(Integer b:common) { System.out.println(b+" "); }
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Working code.

``````public class IBM_CommonElem {

public static void main(String[] args) {

int[] input1={2,5,5,6,7,8,9,11,45};
int[] input2={2,5,6,11,23,25,45};

int length1 = input1.length;
int length2 = input2.length;

int counter1=0, counter2=0;
while(counter1<length1 && counter2<length2){
if(input1[counter1]==input2[counter2]){
System.out.print("\n "+input1[counter1]);
counter1++;
counter2++;
}
else if(input1[counter1]<input2[counter2]){
counter1++;
}else if(input1[counter1]>input2[counter2]){
counter2++;
}
}
System.out.println("\nThat's all folks!");
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

function intersection(arr1, arr2){
let result = [];
arr1.forEach(function(i){
if (arr2.includes(i)){
result.push(i);
arr2.splice(arr2.indexOf(i), 1);
}
})
return result;
}

intersection([2, 5, 5, 5], [2, 2, 3, 5, 5, 7]);

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````function intersection(arr1, arr2){
let result = [];
arr1.forEach(function(i){
if (arr2.includes(i)){
result.push(i);
arr2.splice(arr2.indexOf(i), 1);
}
})
return result;
}

intersection([2, 5, 5, 5], [2, 2, 3, 5, 5, 7]);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````function intersection(arr1, arr2){
let result = [];
arr1.forEach(function(i){
if (arr2.includes(i)){
result.push(i);
arr2.splice(arr2.indexOf(i), 1);
}
})
return result;
}

intersection([2, 5, 5, 5], [2, 2, 3, 5, 5, 7]);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````function intersection(arr1, arr2){
let result = [];
arr1.forEach(function(i){
if (arr2.includes(i)){
result.push(i);
arr2.splice(arr2.indexOf(i), 1);
}
})
return result;
}

intersection([2, 5, 5, 5], [2, 2, 3, 5, 5, 7]);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``intersection([2, 5, 5, 5], [2, 2, 3, 5, 5, 7]);``

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

ATTN: the time complexity of all of these solutions is O(m+n). It is NOT O(min(m,n)), as some have purported.

Here is a worst case input: [1,3,5,7] and [2,4,6,8]
You will be moving a pointer m + n times. Big-O notation describes the upper bound of an algorithm's run time, or the worst-case run time.

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More