IBM Interview Question for Java Developers


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

- linteanm September 10, 2015 | Flag Reply
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

- codealtecdown September 19, 2015 | Flag
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).

- divm01986 September 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- codealtecdown September 19, 2015 | Flag
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;
		}
	}
}

- Espen September 09, 2015 | Flag Reply
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

- Abhinav September 09, 2015 | Flag Reply
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 + " ");
		}
		
	}
}

- Sanjay September 10, 2015 | Flag Reply
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 + " ");
		}
		
	}
}

- catsnow9 September 10, 2015 | Flag Reply
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");   
            }

- Venkat September 10, 2015 | Flag Reply
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;

}

- Alexander Opekunov September 10, 2015 | Flag Reply
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;
}

- DManchala16@students.claremontmckenna.edu September 10, 2015 | Flag Reply
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]

- Yev September 10, 2015 | Flag Reply
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;
}

- zortlord September 10, 2015 | Flag Reply
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;
}
}
}
}

- shubham.asati2626 September 12, 2015 | Flag Reply
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);
	}
	
}

- Suyash Rathi September 22, 2015 | Flag Reply
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+" ");}
}
}

- Anonymous January 07, 2016 | Flag Reply
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+" ");}
	}
}

- ANIRUDDHA SINHA January 07, 2016 | Flag Reply
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+" ");}
	}
}

- ANIRUDDHA SINHA January 07, 2016 | Flag Reply
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+" ");}
}
}}

- ANIRUDDHA SINHA January 07, 2016 | Flag Reply
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+" ");}
	}
}

- ANIRUDDHA SINHA January 07, 2016 | Flag Reply
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+" ");}
}
}

- Aniruddha Sinha January 07, 2016 | Flag Reply
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+" ");}
}
}

- Aniruddha Sinha January 07, 2016 | Flag Reply
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+" ");	}
    	}
    }

- Aniruddha Sinha January 07, 2016 | Flag Reply
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+" "); }
}
}

- Anonymous January 07, 2016 | Flag Reply
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!");
	}
	
}

- Saurabh June 16, 2016 | Flag Reply
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]);

- ion99 July 08, 2016 | Flag Reply
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]);

- ion99 July 08, 2016 | Flag Reply
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]);

- ion99 July 08, 2016 | Flag Reply
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]);

- Ion Gorincioi July 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Ion Gorincioi July 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- yo November 19, 2016 | Flag Reply
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.

- American May 07, 2018 | Flag Reply


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