## 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

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

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){
while(){
int aCount = 0;
int bCount = 0;
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) {
}
List<Integer> commonList = new ArrayList<Integer>();
for (int j : arr2) {
if (arr1List.contains(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) {
}
List<Integer> commonList = new ArrayList<Integer>();
for (int j : arr2) {
if (arr1List.contains(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]) {
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{
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
{
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> common=new ArrayList<Integer>();
Collections.sort(x); Collections.sort(y);
for(Integer a:x){
for(Integer b:y){
if(a==b){
}
}
}
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> common=new ArrayList<Integer>();
Collections.sort(x); Collections.sort(y);
for(Integer a:x){
for(Integer b:y){
if(a==b){
}
}
}
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> common=new ArrayList<Integer>();
Collections.sort(x); Collections.sort(y);
for(Integer a:x){
for(Integer b:y){
if(a==b){
}
}
}
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> common=new ArrayList<Integer>();
Collections.sort(x); Collections.sort(y);
for(Integer a:x){
for(Integer b:y){
if(a==b){
}
}
}
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> common=new ArrayList<Integer>();
Collections.sort(x); Collections.sort(y);
for(Integer a:x){
for(Integer b:y){
if(a==b){
}
}
}
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> common=new ArrayList<Integer>();
Collections.sort(x); Collections.sort(y);
for(Integer a:x){
for(Integer b:y){
if(a==b){
}
}
}
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> common=new ArrayList<Integer>();
Collections.sort(x); Collections.sort(y);
for(Integer a:x){
for(Integer b:y){
if(a==b){
}
}
}
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> common=new ArrayList<Integer>();
Collections.sort(x); Collections.sort(y);
for(Integer a:x){for(Integer b:y){
if(a==b){
}
}
}
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> common=new ArrayList<Integer>();
Collections.sort(x); Collections.sort(y);
for(Integer a:x){for(Integer b:y){
if(a==b){
}
}
}
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.

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.

### 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.