Linkedin Interview Question for Software Engineer / Developers

• 1
of 1 vote

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
9
of 11 vote

Since both the array are sorted, traverse both the arrays from the end. If the value of the one of the array index is higher decrement that index.

``````List<int> FindIntersection(int[] A, int[] B)
{
int L = A.Length;
int K = B.Length;

List<int> intersectionArr = new List<int>();
int i = L - 1;
int j = K - 1;

while ((i >= 0) && (j >=  0))
{
if (A[i] > B[j])
{
i--;
}
else if (B[j] > A[i])
{
j--;
}
else
{
i--;
j--;

}
}
return intersectionArr;
}``````

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

does this code handle the arrays of different length? like:
{1, 3, 5, 6, 7, 8, 9}
{ 1, 4, 5, 5, 17, 81, 88, 99 }

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

Yes. It does handle the case of arrays with different lengths. By starting from the end of the array we would move the pointer of the longer array till it matches that of the shorter one.
Only condition is that the array should be sorted.

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

List<int> intersectionArr = new List<int>();??????????

List is an interface///// You cannot create an object of list this way.

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

In some languages, List is a concrete class. Don't assume everyone is using Java.

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

What if they're not sorted? In that case we'd have to use a hash map (Red Black Trees in C++)/bit vector[Need to know the range] or Sets (BST in C++) for achieving O(m+n) complexity externally?

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

``````int[] a = { 1, 2, 3, 4, 5, 6, 7 };
int[] b = {1, 2, 3, 4};
int i = 0;
while(true)
{
if (i < b.Length && (b[i]) <= a.Length)
{
int x = a[b[i] - 1];
Console.WriteLine(x);
i++;
}
else
break;``````

}

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

``````import java.util.*;
//Assuming first set is larger
public class SortedSetMatching {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Set<Integer> s = new HashSet<Integer>();
int count=0;
Set<Integer> s1=new HashSet<Integer>();
Object[] a1=(s1.toArray());
//Integer[] a2=(Integer[])a1;
Iterator<Integer> it = s1.iterator();
//System.out.println(al);
while(it.hasNext())
{
if(count==a1.length)
{
break;
}
{

count++;
}
else
{
System.out.println(a1[count++]);
}
}``````

}

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

void common_elements(int *a,int *b,int m,int n)
{
set<int> s;
set<int>::iterator it;
for(int i=0;i<m;i++)
s.insert(a[i]); /*first array elements*/
for(int j=0;j<n;j++)
{
it=s.find(b[j]);
if(*it==b[j])
cout<<b[j];
}

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

How about the following approach? Let us assume the two sets of numbers are first and second.

* Let f point to start of first and s point to start of second;
1. if first[f] == second[s] { add first[f] to common list; increment f; increment s; }
2. if first[f] < second[s] increment f;
3. if first[f] > second[s] increment s;
* Repeat 1 - 3 until f < size of first && s < size of second

Pseudo code as :

``````set_common c;
for(size_t fi(0), si(0); (fi < first.size()) && (si < second.size());)
{
if(first[fi] == second[si]) { c.push_back(first[fi]); ++fi; ++si; }
else if(first[fi] < second[si]) ++fi;
else if(first[fi] > second[si]) ++si;
}``````

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

Do a modified version of the merge part of mergesort. Advance through the two arrays the same way you would in mergesort (but don't output a merged array), and at each comparison between an element of A and an element of B, additionally check whether the two elements being compared are equal, and if so, print out one of them.

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

This seems to be the perfect solution

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

The logic of merging is same, whether you compare from the two ends or you compare from starting in parallel.

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

@YetAgain: Yes. There's nothing wrong with doing this kind of logic from the two ends instead.

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

yup. Looks good. The order will be O(min(n,m))

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

HashMap should be used

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

There is no need to use HashMap as we are not storing key -value pairs here.

ArrayList is better option

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

how do you do with ArrayList in o(n+m) ? Its not about key value pairs its about time complexity.

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

I imagine that the interviewer asks:
Yes, hash map solution works for more general problem : finding the common element in N unsorted arrays, but here we have 2 Sorted arrays. Is there a solution that does not requires the additional space?

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

The brute force is O(n+m) as at worst you need to traverse both 1st and 2nd array.

Since the arrays are sorted, you can traverse one array forward if you dont find the element or it's less.

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

I am wondering - which output is expected for the following 2 arrays:
1,1,1
1,1,1,1,1,1,1,1,1

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

those are not sets

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

complexity O(n+m);
Results are stored in the linked list with O(1)

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
};
void create(int d)
{
struct node *n1,*n2,*temp;
if(n1==NULL)
{
n2=(struct node *)malloc(sizeof(struct node));
n2->data=d;
temp=n2;
}
else
{

n2=(struct node *)malloc(sizeof(struct node));
n2->data=d;
}
printf("%d\n",d);
}
int main()
{
int i,j,n,m;
n=5;
m=4;
int A[10]={1,2,3,4,5,6};
int B[10]={5,6,7,8,9};
for(i=n,j=m;i>0;)
{
if(A[i]<B[j])
{
j--;
}
else
{
if(A[i]==B[j])
{
create(A[i]);
}
i--;
}
}

}

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

Beat way is insert first Array into HastSet. when you try to insert second array, the common elements will gets failed to insert.

Set<int> commonElements = new HashSet<int> ();
for(int i=0;i<A.length()-1;i++)
{
}
for(int i=0;i<B.length()-1;i++)
{
{ }
else
{
Sys..("common element"+B[i]);
}

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

HashSet will need a Object and int is not a object you need to convert int to Integer

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

This works

``````#include<iostream>
#include<map>
int main() {

int arr1[] = {1,2,3,4,5,6,7};
int arr2[] = {5,6,7,8,9};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2)/sizeof(arr2[0]);

std::map<int, int> numbers;

for(int i = 0; i < n1; i++) {
numbers[arr1[i]] = 1;
}
for(int i = 0; i < n2; i++) {
if(numbers.find(arr2[i]) != numbers.end()) {
std::cout << arr2[i] << "\n";
}
}
return 0;
}``````

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

Since you don't use the value you put in the map for anything, you could just use std::set.

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

Starting at the end of the longer array and moving the ptr to match the size of the samller array seems to be the wrong logic. It doesn't say in the problem that the values are consecutive numbers. What if you have
A={2,10,20,25}
B={2,4,6,8,10,12,14,20,25}
You move ptr of B to point at 8. You just missed 20 and 25.

std::set<int> findCommonElements(const std::set<int>& s1, const std::set<int>& s2)
{
std::set<int> results;

if( s1.size() < s2.size())
{
for( const auto& sItr1 : s1 )
{
const auto& sItr2 = s2.find(sItr1);
if( sItr2 != s2.end())
results.insert(sItr1);
}
}
else
{
for( const auto& sItr2 : s2 )
{
const auto& sItr1 = s1.find(sItr2);
if( sItr1 != s1.end())
results.insert(sItr2);
}
}
return results;
}

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

``````import java.util.ArrayList;

public class CommonNumbersInSortedArray {

public static ArrayList<Integer> findCommonNumbersinSortedArray(int[] array1, int[]  array2){
int count1 = 0;
int count2 = 0;
ArrayList<Integer> output = new ArrayList<Integer>();
while(count1<array1.length && count2<array2.length){
if(array1[count1] == array2[count2]){
count1++;
count2++;
}
else if(array1[count1] < array2[count2])
count1++;
else
count2++;
}
for(int i=0; i<output.size(); i++)
System.out.print(output.get(i)+" ");
return output;
}

}``````

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

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace myProgram
{
class Program
{
//        There are 2 sorted sets.Find the common elements of those sets
//e.g.
//A={1,2,3,4,5,6}
//B={5,6,7,8,9}
//o/p C={5,6}

public static List<int> commonElements(int[] a,int[]b)
{
List<int> l= new List<int>();
HashSet<int> ha = new HashSet<int>(a);
for (int i = 0; i < b.Length; i++)
{
if (ha.Contains(b[i]))
{
if (!l.Contains(b[i]))
{
}
}
}
return l;
}

static void Main(string[] args)
{
int[] a = { 1,2,3,4,5,6};
int[] b={5,6,7,5,8,9};
List<int> result = new List<int>();
result = commonElements(a, b);
foreach(int i in result)
{
Console.WriteLine(i);
}
}
}
}``````

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

``````a = Array.new
b = Array.new
a=[1,2,3]
b=[1,2,3,4,5,6]

l1=a.length
l2=b.length
if(l1 > l2)
len=l1
else
len=l2
end

c = Array.new
p=0
j=0
for i in 0...len
if a[i] != b[j]
i=i+1
else
if a[i] == b[j]
c[p]=a[i]
p=p+1
j=j+1
end
end
end
puts "#{c}"``````

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

Python version:

``````def intersect_sorted_array(arr1, arr2):
index1 = 0
index2 = 0
intersection = set()

while index1 < len(arr1) and index2 < len(arr2):
if arr1[index1] > arr2[index2]:
index2 += 1
elif arr1[index1] < arr2[index2]:
index1 += 1
else:
index1 += 1
index2 += 1

return intersection``````

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

This is a really bad python code :

``````def find_intersection(list1, list2):
return sorted(list(set(list1) | set(list2)))``````

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

Implementing Eugene's Algorithm:

``````public static void intersectionOfArrays(int []p, int[]q){

int i=0,j=0;
while(i<p.length && j <q.length){

if(p[i] == q[j]){
System.out.print( p[i] + " ");
i++;
j++;
}
else if(p[i]>q[j])
j++;
else
i++;

}

}``````

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

``````package com.problems;

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

public class FindCommonElements
{

public static void main(String[] args)
{
testFindCommon();
}

public static void testFindCommon()
{
int[] a = {1,2,4,8,9,10,13,14,16};
int[] b = {5,7,8,12,14,15};

System.out.println(findCommonElements(a, b));
}
public static List<Integer> findCommonElements(int[] a, int[] b)
{
List<Integer> commonElements = new ArrayList<Integer>();
int i = 0, j = 0;

int sizeOfA = a.length;
int sizeOfB = b.length;
while(i <  sizeOfA && j < sizeOfB)
{
if(a[i] < b[j])
{
i++;
}
else if(a[i] > b[j])
{
j++;
}
else
{
i++;
j++;
}
}
return commonElements;
}
}``````

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

O(m+n)

``````static void Main(string[] args)
{
int[] array1 = { 1, 2, 3, 4, 5, 5, 6, 7 };
int[] array2 = { 5, 5, 6, 7, 8, 9 };

var result = FindCommonSet(array1, array2);

foreach (var item in result)
{
Console.Write("{0} ", item);
}

Console.WriteLine();
}

static HashSet<int> FindCommonSet(int[] array1, int[] array2)
{
int array1Index = 0;
int array2Index = 0;

HashSet<int> result = new HashSet<int>();

while (array1Index < array1.Length && array2Index < array2.Length)
{
if (array1[array1Index] > array2[array2Index])
{
array2Index++;
}
else if (array1[array1Index] < array2[array2Index])
{
array1Index++;
}
else
{

array1Index++;
array2Index++;
}
}

return result;
}``````

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

``````public static ArrayList<Integer> intersection(int a[], int b[]) {
int n1 = a.length;
int n2 = b.length;
int i = 0, j = 0;
ArrayList<Integer> out = new ArrayList<Integer>();
while(i < n1 && j < n2) {
if(a[i] == b[j]) {
i++;
j++;
} else if(a[i] > b[j]) {
j++;
} else {
i++;
}
}
return out;
}``````

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

this is o(m+n)

``````public class Hello {

public static void main(String args[])
{

int a[]= {1,2,3,4,5};
int b[]={3,4,5,6,7};

int n=a.length;
int m =b.length;
int x=Math.min(n,m);

int c[]=new int[x];

int i=0,j=0,k=0;

while (i<n && j <m)
{
if(a[i]>b[j])
j++;
else if(a[i]<b[j])
i++;
else
{       c[k]=a[i];
k++;i++;
}

}
for(k=0;k<x;k++)
System.out.println(c[k]);
}
}``````

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

``````//
//  CommonOfSets.c

#include <stdio.h>

int main() {
int a[] = {1,2,3,4,5,6};
int b[] = {3,5,6,7};

int i, j, m, n;
m = 6; //length of array-1
n = 4; //length of array-2

i = 0;
j = 0;
while(i < m && j < n) {
if(a[i] == b[j]) {
printf("%d\t", a[i]);
i++;
j++;
}
else {
if(a[i] < b[j])
i++;
else
j++;
}
}
printf("\n");
return 0;
}``````

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

/*Inspiration came from the merge routine in merge sort; complexity of following is O(n+m)
*/

import java.util.*;
public class General {

public ArrayList<Integer> findCommonElemsForTwoSortedLists(int[] A, int[] B){
int i = 0; int j = 0;
while ((i < A.length) && (A[i] != B[j])){
i++;
}
if (i == A.length)
return null;
else{
ArrayList<Integer> commonElems = new ArrayList<Integer>();
while ((i < A.length) && (j < B.length) && (A[i] == B[j])){
i++;
j++;
}
return commonElems;
}
}

public static void main (String[] args){
General gen = new General();
int[] A = {1, 2, 3, 4, 5, 6};
int[] B = {5, 6, 7, 8, 9};
ArrayList<Integer> commonElems = gen.findCommonElemsForTwoSortedLists(A, B);
StringBuffer buffer = new StringBuffer();
boolean first = true;
for (Integer elem : commonElems){
if (first){
first = false;
}else{
buffer.append(',');
}
buffer.append(elem);
}
System.out.println(buffer.toString());

}
}

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

This is very simple in python

def intersect(a,b):
list(set(a) & set(b))

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

can be done in log(m)*log(n) time with recursion.

``````public static Set<Integer> intersect(int[] a, int[] b, int a0, int a1, int b0, int b1, Set<Integer> set) {
int la = a1-a0, lb = b1-b0;
//base case
if (la<=2 && lb<=2) {
for (int i=a0; i<a1; i++) for (int j=b0; j<b1; j++) if (a[i]==b[j]) set.add(a[i]);
return set;
}
else if (la<=lb) {
set.addAll(intersect(a, b, a0, a1, b0, (b0+b1)/2, set));
set.addAll(intersect(a, b, a0, a1, (b0+b1)/2, b1, set));
}
else {
set.addAll(intersect(a, b, a0, (a0+a1)/2, b0, b1, set));
set.addAll(intersect(a, b, (a0+a1)/2, a1, b0, b1, set));
}
return set;
}

public static void main(String[] args) {
int[] a = new int[100];
int[] b = new int[50];
for (int i=0; i<a.length; i++) a[i] = 4*i-30;
for (int i=0; i<b.length; i++) b[i] = 3*i-7;
for (int d:a) System.out.printf("%d, ", d);

System.out.println();
for (int d:b) System.out.printf("%d, ", d);
System.out.println();

Set<Integer> intersect = new TreeSet<Integer>();
intersect = intersect(a, b, 0, 100, 0, 50, intersect);
for (int d:intersect) System.out.printf("%d, ", d);

}``````

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

``````import java.util.TreeMap;

public class CommonIntegers {

static void commonInt(int[] first,int[] second){
TreeMap<Integer,Integer> map = new TreeMap<Integer,Integer>();
for(int i:first){
if(map.get(i)==null){
map.put(i, 1);
}
else{
map.put(i, map.get(i)+1);
}
}
for(int i:second){
if(map.get(i)!=null){
}
}

}

public static void main(String[] args){
int[] A={1,2,3,4,5,6,9} ;
int[] B={5,6,7,8,9} ;
commonInt(A, B);
}

}``````

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.