IBM Interview Question Java Developers
Country: India
Interview Type: Written Test
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).
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;
}
}
}
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 + " ");
}
}
}
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 + " ");
}
}
}
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");
}
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;
}
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;
}
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]
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;
}
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);
}
}
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+" ");}
}
}
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+" ");}
}
}
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+" ");}
}
}
{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+" ");}
}
}}
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+" ");}
}
}
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+" ");}
}
}
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+" ");}
}
}
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+" "); }
}
}
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+" "); }
}
}
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!");
}
}
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.
function intersection(arr1, arr2){
let result = [];
arr1.forEach(function(i){
if (arr2.includes(i)){
result.push(i);
arr2.splice(arr2.indexOf(i), 1);
}
})
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]); return result;
}
intersection([2, 5, 5, 5], [2, 2, 3, 5, 5, 7]);
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.
- linteanm September 10, 2015a = [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