Linkedin Interview Question Senior Software Development Engineers
Country: United States
Interview Type: In-Person
O(N + M) time, O(N + M) space
import java.util.ArrayList;
import java.util.List;
public class ListUtils {
public List<Integer> union(List<Integer> list1, List<Integer> list2) {
if (list1 == null || list2 == null) {
throw new IllegalArgumentException();
}
return merge(list1, list2);
}
private List<Integer> merge(List<Integer> list1, List<Integer> list2) {
List<Integer> mergedList = new ArrayList<>();
int i1 = 0;
int i2 = 0;
while (i1 + i2 != list1.size() + list2.size()) {
if (i1 == list1.size()) {
mergedList.add(list2.get(i2++));
} else if (i2 == list2.size()) {
mergedList.add(list1.get(i1++));
} else if (list1.get(i1) < list2.get(i2)) {
mergedList.add(list1.get(i1++));
} else {
mergedList.add(list2.get(i2++));
}
}
return mergedList;
}
public List<Integer> intersection(List<Integer> list1, List<Integer> list2) {
if (list1 == null || list2 == null) {
throw new IllegalArgumentException();
}
return intersect(list1, list2);
}
private List<Integer> intersect(List<Integer> list1, List<Integer> list2) {
List<Integer> mergedList = new ArrayList<>();
int i1 = 0;
int i2 = 0;
while (i1 + i2 != list1.size() + list2.size()) {
if (i1 == list1.size() || i2 == list2.size()) {
break;
} else if (list1.get(i1) == list2.get(i2)) {
mergedList.add(list1.get(i1));
++i1;
++i2;
} else if (list1.get(i1) < list2.get(i2)) {
++i1;
} else {
++i2;
}
}
return mergedList;
}
}
Complexity analysis and memory usages within the code.
public final class ListUtils{
private ListUtils(){
//do nothing
}
//O(n + m) runtime and O(n + m) memory where n and m are the lengths of the source lists
//Uses iterators to ensure that traversal of the Lists is of optimal speed. If a List were a
//LinkedList, then the .get(int) would have a runtime complexity of O(n) by itself hence the
//need for iterators
public static List<T extends Comparable> union(List<T extends Comparable> list1, List<T extends Comparable> list2){
if(list1 == null){
if(list2 == null){
return null;
}
return list2;
}
if(list2 == null){
return list1;
}
ArrayList<T> results = new ArrayList<T>(list1.size() + list2.size());
Iterator<T> list1Iter = list1.iterator();
Iterator<T> list2Iter = list2.iterator();
T list1Obj = list1Iter.next();
T list2Obj = list2Iter.next();
while(list1Obj != null && list2Obj != null){
if(list1Obj.compareTo(list2Obj) < 0){
results.add(list1Obj);
list1Obj = (list1Iter.hasNext()) ? list1Iter.next() : null;
}
else{
results.add(list2Obj);
list2Obj = (list2Iter.hasNext()) ? list2Iter.next() : null;
}
}
while(list1Obj != null){
results.add(list1Obj);
list1Obj = (list1Iter.hasNext()) ? list1Iter.next() : null;
}
while(list2Obj != null){
results.add(list2Obj);
list2Obj = (list2Iter.hasNext()) ? list2Iter.next : null;
}
return results;
}
//O(min(n, m)) runtime complexity and O(min(n, m)) memory where n and m are the length of the lists
//also uses Iterators for efficient traversal of the lists
public static List<T extends Comparable> intersection(List<T> list1, List<T> list2){
ArrayList<T> results = new ArrayList<T>();
if(list1 == null || list2 == null){
return results;
}
Iterator<T> list1Iter = list1.iterator();
Iterator<T> list2Iter = list2.Iterator();
T list1Obj = list1Iter.next();
T list2Obj = list2Iter.next();
while(list1Obj != null && list2Obj != null){
int diff = list1Obj.compareTo(list2Obj);
if(diff < 0){
list1Obj = (list1Iter.hasNext()) ? list1Iter.next() : null;
}
else if(diff > 0){
list2Obj = (list2Iter.hasNext()) ? list2Iter.next() : null;
}
else{
results.add(list1Obj);
list1Obj = (list1Iter.hasNext()) ? list1Iter.next() : null;
list2Obj = (list2Iter.hasNext()) ? list2Iter.next() : null;
}
}
return results;
}
class SetOperator:
def __init__(self, order="asc"):
self.order = order
def union(self, a1, a2):
if a1 == None or a2 == None:
return None
n1 = len(a1); n2 = len(a2)
i = 0; j = 0
result = []
while (i < n1 and j < n2):
if a1[i] < a2[j]:
result.append(a1[i])
i = i + 1
elif a1[i] > a2[j]:
result.append(a2[j])
j = j + 1
else:
result.append(a1[i])
i = i + 1
j = j + 1
if i == n1:
while j < n2:
result.append(a2[j])
j = j + 1
if j == n2:
while i < n1:
result.append(a1[i])
i = i + 1
return result
def intersection(self, a1, a2):
if a1 == None or a2 == None:
return None
n1 = len(a1); n2 = len(a2)
i = 0; j = 0
result = []
while (i < n1 and j < n2):
if a1[i] < a2[j]:
i = i + 1
elif a1[i] > a2[j]:
j = j + 1
else:
result.append(a1[i])
i = i + 1
j = j + 1
return result
//int arr1[6] = {-1, 2, 3, 6, 8, 20};
//int arr2[8] = {0, 1, 2, 5, 7, 8, 11, 21};
int* Practice::unionOfList(int* arr1, int size1, int* arr2, int size2, int *result) {
int pointer1 = 0, pointer2 = 0;
while (pointer1 < size1 && pointer2 < size2) {
if (arr1[pointer1] < arr2[pointer2]) {
result[pointer1+pointer2] = arr1[pointer1];
pointer1++;
}
else {
result[pointer1+pointer2] = arr2[pointer2];
pointer2++;
}
}
if (pointer1 == size1 && pointer2 == size2) {
return result;
}
else if (pointer1 == size1) {
while (pointer2 < size2) {
result[pointer1+pointer2] = arr2[pointer2];
pointer2++;
}
}
else if (pointer2 == size2) {
while (pointer1 < size1) {
result[pointer1+pointer2] = arr1[pointer1];
pointer1++;
}
}
return result;
}
void Practice::setOfList(int* arr1, int size1, int* arr2, int size2, int *result) {
int p1=0, p2=0, rPointer = 0;
while (p1 < size1 && p2 < size2) {
if (arr1[p1] == arr2[p2]) {
result[rPointer] = arr1[p1];
rPointer++;
p1++; p2++;
while (arr1[p1] == result[rPointer-1])
p1++;
while (arr2[p2] == result[rPointer-1])
p2++;
}
else if (arr1[p1] < arr2[p2]) {
result[rPointer] = arr1[p1];
rPointer++;
p1++;
}
else {
result[rPointer] = arr2[p2];
rPointer++;
p2++;
}
}
if (p1 == size1 && p2 == size2) {
return;
}
else if (p1 == size1) {
while (p2 < size2) {
result[rPointer] = arr2[p2];
rPointer++;
p2++;
}
}
else {
while (p1 < size1) {
result[rPointer] = arr1[p1];
rPointer++;
p1++;
}
}
}
void Practice::intersectionOfList(int* arr1, int size1, int* arr2, int size2, int *result) {
int p1=0, p2=0, rPointer = 0;
while (p1 < size1 && p2 < size2) {
if (arr1[p1] == arr2[p2]) {
result[rPointer] = arr1[p1];
rPointer++;
p1++; p2++;
while (arr1[p1] == result[rPointer-1])
p1++;
while (arr2[p2] == result[rPointer-1])
p2++;
}
else if (arr1[p1] < arr2[p2]) {
p1++;
}
else {
p2++;
}
}
}
def union(list1, list2):
if len(list1) == 0 and len(list2) == 0:
return "lists are empty"
elif len(list1)== 0:
return list2
elif len(list2) == 0:
return list1
else:
count1 = 0
count2 = 0
unionList = list()
while True:
if count1 == len(list1):
unionList.extend(list2[count2:])
break
elif count2 == len(list2):
unionList.extend(list1[count1:])
break
elif list1[count1] <= list2[count2]:
unionList.append(list1[count1])
count1 +=1
elif list1[count1] >= list2[count2]:
unionList.append(list2[count2])
count2 +=1
return list(set(unionList))
def intersection(list1, list2):
if len(list1) == 0 and len(list2) == 0:
return "lists are empty"
elif len(list1)== 0:
return list2
elif len(list2) == 0:
return list1
else:
count1 = 0
count2 = 0
intersectionList = list()
while True:
if count1 == len(list1) or count2 == len(list2):
break
elif list1[count1] == list2[count2]:
intersectionList.append(list1[count1])
count1 +=1
count2 +=1
elif list1[count1] < list2[count2]:
count1 +=1
elif list2[count2] < list1[count1]:
count2 +=1
return intersectionList
def unionIntersection(list1, list2):
if len(list1) == 0 and len(list2) == 0:
return "lists are empty"
elif len(list1)== 0:
return list2
elif len(list2) == 0:
return list1
else:
count1 = 0
count2 = 0
unionList = list()
intersectionList =list()
while True:
if count1 == len(list1):
unionList.extend(list2[count2:])
break
elif count2 == len(list2):
unionList.extend(list1[count1:])
break
elif list1[count1] == list2[count2]:
intersectionList.append(list1[count1])
unionList.append(list1[count1])
count1 +=1
count2 +=1
elif list1[count1] < list2[count2]:
unionList.append(list1[count1])
count1 +=1
elif list1[count1] > list2[count2]:
unionList.append(list2[count2])
count2 +=1
return list(set(unionList)), intersectionList
List<Integer> unionLists(List<Interger>a, List<Integer>b){
List<Integer> c = new ArrayList<Integer>();
int i =0;
int j =0;
int lena = a.size();
int leb = b.size();
while(i< lena && j< lenb) {
if(a.get(i) <= b.get(j)){
c.add(a.get(i));
i++;
}
else {
c.add(a.get(i));
j++;
}
}
// Now either a is done or b is done
if(i == lena){
for (int k=j; j< lenb; j++){
// copy all b rows to c
c.add(b.get(k));
}
}
if(j == lena){
for (int k=i; j< lena; j++){
// copy all a rows to c
c.add(a.get(k));
}
}
}
List<Integer> intersectList(List<Integer> a, List<Integer> b){
List<Integer> c = new ArrayList<String>();
int i =0;
int j =0;
int lena =a.size();
int lenb =b.size();
while (i < lena && j< lenb){
//store common elements in c
if(a.get(i) == b.get(j)){
c.add(a.get(i));
i++;
j++;
}
}
}
using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace AlgorithmsTests
{
[TestClass]
public class ListUnionAndIntersection
{
private NodeList Intersection(NodeList l1, NodeList l2)
{
NodeList list = new NodeList();
Node n = l1.Head;
while (n != null)
{
if (l2.Contains(n.Value))
{
list.Add(n.Value);
}
n = n.Next;
}
return list;
}
private NodeList Union(NodeList l1, NodeList l2)
{
NodeList list = new NodeList();
Node n = l1.Head;
Node m = l2.Head;
//Add both lists, the duplicated items will be ignored
while (n != null || m != null)
{
if (n != null)
{
list.Add(n.Value);
n = n.Next;
}
if (m != null)
{
list.Add(m.Value);
m = m.Next;
}
}
return list;
}
bool AreListsEqual(NodeList l1, NodeList l2)
{
Node p1 = l1.Head;
Node p2 = l2.Head;
while (p1 != null && p2 != null)
{
//same value: all values shold be equal
if (p1.Value != p2.Value)
{
return false;
}
p1 = p1.Next;
p2 = p2.Next;
}
//same length: both lists shoudl be at the end
return p1 == null && p2 == null;
}
class NodeList
{
public Node Head;
public static NodeList FromArray(int[] values)
{
NodeList list = new NodeList();
for (int i = 0; i < (values?.Length ?? 0); i++)
list.Add(values[i]);
return list;
}
public void Add(int v)
{
Node prev = null;
Node n = Head;
//Find the spot to place it and the previous item
while (n != null && n.Value < v)
{
prev = n;
n = n.Next;
}
//avoid duplication, don't add the item if it exists
if (n != null && n.Value == v)
{
return;
}
Node newNode = new Node()
{
Value = v,
Next = n
};
if (prev != null)
{
prev.Next = newNode;
}
else
{
Head = newNode;
}
}
public bool Contains(int v)
{
Node n = Head;
while (n != null)
{
if (n.Value == v)
{
return true;
}
n = n.Next;
}
// not found
return false;
}
public override string ToString()
{
Node p = Head;
String s = string.Empty;
while (p != null)
{
s += p.Value.ToString() + " ";
p = p.Next;
}
return s;
}
}
class Node
{
public int Value;
public Node Next;
}
[TestMethod]
public void Test_List()
{
Assert.IsTrue(
AreListsEqual(
NodeList.FromArray(new[] { 1 }),
Union(NodeList.FromArray(new[] { 1 }),
NodeList.FromArray(null))));
Assert.IsTrue(
AreListsEqual(
NodeList.FromArray(new[] { 0, 1 }),
Union(NodeList.FromArray(new[] { 1 }),
NodeList.FromArray(new[] { 0 }))));
Assert.IsTrue(
AreListsEqual(
NodeList.FromArray(new[] { 1, 3, 5, 7, 9, 14, 456, 670, 1234 }),
Union(NodeList.FromArray(new[] { 1, 3, 456, 670, 1234 }),
NodeList.FromArray(new[] { 3, 5, 7, 9, 14, 670 }))));
Assert.IsTrue(
AreListsEqual(
NodeList.FromArray(new[] { 3, 670 }),
Intersection(NodeList.FromArray(new[] { 1, 3, 456, 670, 1234 }),
NodeList.FromArray(new[] { 3, 5, 7, 9, 14, 670 }))));
Assert.IsTrue(
AreListsEqual(
NodeList.FromArray(null),
Intersection(NodeList.FromArray(new[] { 1, 3}),
NodeList.FromArray(null))));
}
}
}
/*2 3 5 6 9
4 5 6 7 10
2 3 4 5 5 6 6 7 9 10*/
public static List<Integer> sortUnion(List<Integer>a , List<Integer> b){
int aItr = 0;
int bItr = 0;
List<Integer> result = new ArrayList<Integer>();
while(aItr < a.size() && bItr < b.size() ){
if(a.get(aItr) <= b.get(bItr)){
while(aItr < a.size() && bItr < b.size() && a.get(aItr) <= b.get(bItr)){
result.add(a.get(aItr++));
}
}
else if(b.get(bItr) < a.get(aItr)){
while(aItr < a.size() && bItr < b.size() && b.get(bItr) < a.get(aItr)){
result.add(b.get(bItr++));
}
}
}
while(aItr < a.size()){
result.add(a.get(aItr++));
}
while(bItr < b.size()){
result.add(b.get(bItr++));
}
return result;
}
/*2 3 5 6 9
4 5 6 7 10
2 3 5 6 9
4 5 6 7 8 9 10
5 6
*/
public static List<Integer> sortIntersection(List<Integer>a , List<Integer> b){
int aItr = 0;
int bItr = 0;
List<Integer> result = new ArrayList<Integer>();
while(aItr < a.size() && bItr < b.size() ){
if(a.get(aItr) < b.get(bItr)){
aItr++;
}
if(aItr < a.size() && a.get(aItr) > b.get(bItr)){
bItr++;
}
if(aItr < a.size() && bItr < b.size() && a.get(aItr) == b.get(bItr)){
result.add(b.get(bItr++));
}
}
return result;
}
/*2 3 5 6 9
4 5 6 7 10
2 3 4 5 5 6 6 7 9 10*/
public static List<Integer> sortUnion(List<Integer>a , List<Integer> b){
int aItr = 0;
int bItr = 0;
List<Integer> result = new ArrayList<Integer>();
while(aItr < a.size() && bItr < b.size() ){
if(a.get(aItr) <= b.get(bItr)){
while(aItr < a.size() && bItr < b.size() && a.get(aItr) <= b.get(bItr)){
result.add(a.get(aItr++));
}
}
else if(b.get(bItr) < a.get(aItr)){
while(aItr < a.size() && bItr < b.size() && b.get(bItr) < a.get(aItr)){
result.add(b.get(bItr++));
}
}
}
while(aItr < a.size()){
result.add(a.get(aItr++));
}
while(bItr < b.size()){
result.add(b.get(bItr++));
}
return result;
}
/*2 3 5 6 9
4 5 6 7 10
2 3 5 6 9
4 5 6 7 8 9 10
5 6
*/
public static List<Integer> sortIntersection(List<Integer>a , List<Integer> b){
int aItr = 0;
int bItr = 0;
List<Integer> result = new ArrayList<Integer>();
while(aItr < a.size() && bItr < b.size() ){
if(a.get(aItr) < b.get(bItr)){
aItr++;
}
if(aItr < a.size() && a.get(aItr) > b.get(bItr)){
bItr++;
}
if(aItr < a.size() && bItr < b.size() && a.get(aItr) == b.get(bItr)){
result.add(b.get(bItr++));
}
}
return result;
}
#include <iostream>
#include <vector>
#include <cmath>
#include <list>
using namespace std;
list<int> findUnion(list<int> a, list<int> b){
list<int> ab;
while(!a.empty() && !b.empty()) {
if(a.front() <= b.front()) {
ab.push_back(a.front());
a.pop_front();
} else {
ab.push_back(b.front());
b.pop_front();
}
}
while(!a.empty()) {
ab.push_back(a.front());
a.pop_front();
}
a.swap(b);
while(!a.empty()) {
ab.push_back(a.front());
a.pop_front();
}
return ab;
}
list<int> findIntersection(list<int> a, list<int> b) {
list<int> ab;
while(!a.empty() && !b.empty()) {
if(a.front() == b.front()) {
ab.push_back(a.front());
a.pop_front();
b.pop_front();
} else if(a.front()<b.front()) {
a.pop_front();
} else {
b.pop_front();
}
}
return ab;
}
int main() {
list<int> a, b, ab;
for(int i=1; i<10; i++) {
if(i%2)
a.push_back(i);
else {
b.push_back(i);
if(i>5)
a.push_back(i);
}
}
ab = findUnion(a, b);
for(auto i: ab) {
cout<<i<<" ";
}
cout<<endl;
ab = findIntersection(a, b);
for(auto i: ab) {
cout<<i<<" ";
}
return 0;
}
stdout: Success time: 0 memory: 3472 signal:0
1 2 3 4 5 6 6 7 8 8 9
6 8
Python 2...
# Lists of integers:
a = [1,2,4,5,8,9]
b = [3, 4, 5, 9]
union = sorted(list(set(a).union(set(b)))) # ==> [1, 2, 3, 4, 5, 8, 9]
intersection = sorted(list(set(a).intersection(set(b)))) # ==> [4,5,9]
# If you want to print it out:
for i in union:
print i
# or
import sys
for i in l:
sys.stdout.write(str(i) + ' ')
O(n+m) approach which uses sorted property of lists to determine union and intersection.
- c.prashanth85 September 23, 2015using System; using System.Collections.Generic; namespace ConsoleApplication24 { class Program { static void Main( string[] args ) { List<int> l1 = new List<int>() { 1, 23, 26, 40, 45 }; List<int> l2 = new List<int>() { -1, 2, 6, 26, 40, 50, 75 }; foreach ( int val in union( l1, l2 ) ) Console.Write( val + " " ); Console.WriteLine(); foreach ( int val in intersect( l1, l2 ) ) Console.Write( val + " " ); } private static List<int> union( List<int> l1, List<int> l2 ) { if ( l1.Count == 0 ) return l2; if ( l2.Count == 0 ) return l1; List<int> op = new List<int>(); int start1 = 0; int start2 = 0; int end1 = l1.Count; int end2 = l2.Count; while ( start1 < end1 && start2 < end2 ) { if ( l1[start1] <= l2[start2] ) { op.Add( l1[start1] ); start1++; } else { op.Add( l2[start2] ); start2++; } } if ( start1 == end1 ) { while ( start2 < end2 ) { op.Add( l2[start2] ); start2++; } } if ( start2 == end2 ) { while ( start1 < end1 ) { op.Add( l1[start1] ); start1++; } } return op; } public static List<int> intersect( List<int> l1, List<int> l2 ) { if ( l1.Count == 0 ) return l2; if ( l2.Count == 0 ) return l1; List<int> op = new List<int>(); int start1 = 0; int start2 = 0; int end1 = l1.Count; int end2 = l2.Count; while ( start1 < end1 && start2 < end2 ) { if ( l1[start1] == l2[start2] ) { op.Add( l1[start1] ); start1++; start2++; } else if ( l1[start1] < l2[start2] ) { start1++; continue; } else { start2++; } } return op; } } }