CareerCup

I'm not really sure where people got the assumption that you had to remove duplicates. That doesn't appear specified in the question. I can think of many cases where you'd want to keep duplicates. Think about two list of events, for example, you wouldn't want to remove all events of the same type when merging, you'd want to keep them. If that is the case, then the solution is simply using two linked lists and doing l1->last->next = l2->head.

If, in fact, "merge" does imply that duplicates should be removed. Then I'd have to agree with Arpan and Vikram on the solution using bit representation.

>>Lists data structure design depends on you.
As design choice is ours,we can use doubly linked lists data structure.

How about this?
use hash table to represent the list. h[key]=1 means key is inside the list. so, lookup is O(1), traverse is O(n).
when do the union, just keep them as they are. So, when lookup, when just do OR of h1[key], h2[key]. it's still O(1). when traverse, traverse in h1 and h2, O(2n)=O(n). meanwhile, eliminating h2.
a bit tricky. donot whether it is acceptable.

A single linked list is OK and we need two structures: one for list another for each element.

struct Elem{
int val;
Elem* next;
};
struct list{
Elem* head;
Elem* tail;
};

When we merge two lists with O(1):

l1.tail = l2.head;
l1.tail = l2.tail;

I believe that I solved. My cornerstone was in keeping updated a non-public reference to the last element of the list at all times.


Unit tests first:

//
//  CSPQuickListMergeTests.m
//

#import <XCTest/XCTest.h>
#import "CSPQuickMergeList.h"

@interface CSPQuickListMergeTests : XCTestCase

@end

@implementation CSPQuickListMergeTests {
    CSPQuickMergeList *_list1, *_list2;
}

- (void)setUp
{
    [super setUp];

    _list1 = [CSPQuickMergeList listWithArray:@[ @0, @1, @2, @3, @4 ]];
    _list2 = [CSPQuickMergeList listWithArray:@[ @5, @6, @7, @8, @9 ]];
}

- (void)tearDown
{
    _list1 = _list2 = nil;

    [super tearDown];
}

- (void)testSingleMerge
{
    CSPQuickMergeList *expected =
    [CSPQuickMergeList listWithArray:@[ @0, @1, @2, @3, @4, @5, @6, @7, @8, @9 ]];

    XCTAssertEqualObjects(expected, [_list1 merge:_list2]);
}

- (void)testDoubleMergeTakeOne
{
    CSPQuickMergeList *expected =
    [CSPQuickMergeList listWithArray:@[ @0, @1, @2, @3, @4, @5, @6, @7, @8, @9,
                                        @10, @11, @12, @13, @14 ]];

    CSPQuickMergeList *list3 =
    [CSPQuickMergeList listWithArray:@[ @10, @11, @12, @13, @14 ]];

    XCTAssertEqualObjects(expected, [_list1 merge:[_list2 merge:list3]]);
}

- (void)testDoubleMergeTakeTwo
{
    CSPQuickMergeList *expected =
    [CSPQuickMergeList listWithArray:@[ @0, @1, @2, @3, @4, @5, @6, @7, @8, @9,
                                        @10, @11, @12, @13, @14 ]];

    CSPQuickMergeList *list3 =
    [CSPQuickMergeList listWithArray:@[ @10, @11, @12, @13, @14 ]];

    XCTAssertEqualObjects(expected, [[_list1 merge:_list2] merge:list3]);
}

- (void)testNullInput
{
    XCTAssertEqualObjects(_list1, [_list1 merge:nil]);
}

- (void)testMergeSame
{
    XCTAssertEqualObjects(_list1, [_list1 merge:_list1]);
}

- (void)testOneElementListMerge
{
    CSPQuickMergeList *list3 = [CSPQuickMergeList listWithObject:@100];
    CSPQuickMergeList *expected =
    [CSPQuickMergeList listWithArray:@[ @100, @0, @1, @2, @3, @4 ]];
    XCTAssertEqualObjects(expected, [list3 merge:_list1]);

    list3 = [CSPQuickMergeList listWithObject:@100];
    expected =
    [CSPQuickMergeList listWithArray:@[ @0, @1, @2, @3, @4, @100 ]];
    XCTAssertEqualObjects(expected, [_list1 merge:list3]);

    CSPQuickMergeList *listA = [CSPQuickMergeList listWithObject:@('a')];
    CSPQuickMergeList *listB = [CSPQuickMergeList listWithObject:@('b')];
    expected = [CSPQuickMergeList listWithArray:@[ @('b'), @('a') ]];
    XCTAssertEqualObjects(expected, [listB merge:listA]);
}

@end

The list interface:

//
//  CSPQuickListMerge.h
//

#import <Foundation/Foundation.h>

/**
 * Single-linked list implementation that features O(1) merge.
 */
@interface CSPQuickMergeList : NSObject

@property (nonatomic, readonly) id data;

/**
 * Constructor that creates a 1-element list.
 * @param object
 * @return nil if object is nil, a new list otherwise
 */
+ (instancetype)listWithObject:(id)object;

/**
 * Constructor that creates a list whose elements come from the array passed as
 * parameter.
 * @param array
 * @return nil if the array is nil or has no elements, a new list otherwise
 */
+ (instancetype)listWithArray:(NSArray*)array;

- (instancetype)initWithObject:(id)object;

/**
 * Default initializer.
 */
- (instancetype)initWithArray:(NSArray*)array;

/**
 * Appends the received list at the end of this list. This method is optimized
 * for constant complexity.
 * @param list
 * @return the original list with the parameter appended. If the input is the
 * same list that this list, just returns this list without changes (i.e., 
 * doesn't append the list to itself).
 */
- (instancetype)merge:(CSPQuickMergeList*)list;

/**
 * Returns the next element (eventually nil).
 */
- (instancetype)next;

@end

The list implementation:

//
//  CSPQuickListMerge.m
//

#import "CSPQuickMergeList.h"

@implementation CSPQuickMergeList {
    CSPQuickMergeList *_next;
    CSPQuickMergeList *_last; // at all times, a reference to the last element
                              // of the list is kept. This will help merge lists
                              // with O(1).
}

@synthesize data = _data;

+ (instancetype)listWithObject:(id)object
{
    return [[CSPQuickMergeList alloc] initWithObject:object];
}

+ (instancetype)listWithArray:(NSArray*)array
{
    return [[CSPQuickMergeList alloc] initWithArray:array];
}

- (instancetype)initWithObject:(id)object
{
    if (!object) return nil; // fail-fast

    if ((self = [super init])) {
        _data = object;
        _next = nil;
        _last = self;
    }

    return self;
}

- (instancetype)initWithArray:(NSArray*)array
{
    if ((!array) || (![array count])) return nil; // fail-fast

    if ((self = [self initWithObject:[array objectAtIndex:0]])) {
        for (NSUInteger i = 1; i < [array count]; ++i) {

            [self merge:[CSPQuickMergeList
                         listWithObject:[array objectAtIndex:i]]];
        }
    }

    return self;
}

- (instancetype)next
{
    // here's the trick: the last element is propagated is the list is
    // traversed
    if (_next) [_next setLast:_last];

    return _next;
}

- (instancetype)merge:(CSPQuickMergeList*)list
{
    // skips empty lists or self-concatenation
    if ((list) && (list != self)) {
        // the original last element becomes predecessor of the new list
        [_last setNext:list];
        // And the last element of the resulting merged list is the last element
        // of the appended list
        _last = [list last];
    }

    return self;
}

// Notice that this method don't belong to the public interface
- (void)setNext:(CSPQuickMergeList*)next
{
    _next = next;
}

// Notice that this method don't belong to the public interface
- (instancetype)last
{
    return _last;
}

// Notice that this method don't belong to the public interface
- (void)setLast:(CSPQuickMergeList*)last
{
    _last = last;
}

- (BOOL)isEqual:(id)object
{
    if (self == object) return YES;

    if (![object isKindOfClass:[CSPQuickMergeList class]]) return NO;

    return [self isEqualToList:(CSPQuickMergeList*)object];
}

- (BOOL)isEqualToList:(CSPQuickMergeList*)list
{
    if (!list) return NO;

    CSPQuickMergeList *thisOne = self, *theOtherOne = list;
    while (thisOne) {
        if ((!theOtherOne) || (![[thisOne data] isEqual:[theOtherOne data]])) return NO;

        thisOne = [thisOne next];
        theOtherOne = [theOtherOne next];
    }

    return !theOtherOne;
}

- (NSUInteger)hash
{
    return (_last == self) ? [_data hash] : ([_data hash] ^ [[_last data] hash]);
}

- (NSString*)description
{
    NSMutableString *ret = [NSMutableString stringWithFormat:@"[ %@", [_data description]];

    CSPQuickMergeList *thisList = _next;
    while (thisList) {
        [ret appendFormat:@", %@", [thisList data]];
        thisList = [thisList next];
    }

    [ret appendFormat:@" ]"];

    return ret;
}

@end

what do you mean "merge them" are the lists sorted? Or simply appended to the end?

Merging is akin to taking union of the two lists in this case.I mean two say that we have to take the union of the two sets,removing duplicate entries,if any.
(Remember how do we take the union of two sets)
Given {1,2,3} and {2,5,3}
O/p of theri union is {1,2,3,5}

>>Lists data structure design depends on you.
As design choice is ours,we can use doubly linked lists data structure.

.......But,how do we take care of possible duplicates....we can't simply append them.You need to design some other list data structure

hmmm
Well it seems to me that if we separating random entries in a list in constant time, then we need O(1) lookup, which is not provided by a list. So we will have to use a random access data structure somewhere, if this is still a "list" then it is possible.

We can use a hash table and hash all the elements into it. We will be left with the Union of the elements which are the keys of the hash table. But this is still O(2n) and not O(1). O(1) does it mean just append one list to another...???

ya man n u think traversing of list is O(1) lol

Lol you obviously need a random access data structure. The only thing I can think of is to have a "pool" of list elements, store in an array. I.e. node* pool[n];

Then each "list" has a bitmap bool bitmap[n], where the ith value in the bitmap is true if the list contains that element.

Then to merge 2 lists we simply OR the two bitmaps. However this only works if we can know ahead of time how many elements there will be, or growing each bitmap as new elements are added to the pool.

Be warned.. This solution sucks.

Prabhav: O(1) is not possible.

Because we have choise to design data structure for the lists, so I use three containers to store data, one std:map (or hash table) to store real data(the data may be the key), and useing two lists (link table or vector or what ever) to store the key for the data which belongs to the list. The Add operation is OK because for map add is automatically unique but in two lists maybe dublicate, for delete operation, only the data don't belong to both list, then delete it from map. now it is easy for merge two list, do nothing just access map.

If we use a bit vector representation (a bit vector is a an long integer or a group of integers, such that if a number n is present in our data, we set the n'th bit in the integer or range of integers to 1), we can do a bitwise OR which is O(1) and we get the union! The space complexity will be high because this depends on the range of the data.

Bit representation is one of the possible solutions I gave once the same and solution was accepted .Because we have a very realistic limit of O(1) time we have to compensate on the space

Bit representation is one of the possible solutions I gave once the same and solution was accepted .Because we have a very realistic limit of O(1) time we have to compensate on the space

What if we use doubly circular..we can merge in o(1). hence we need to change 3 pointers only

typedef struct node
{
struct node* next;
int data;
}node;

//we maintain the head and tail of the list
//e.g. add will be:
// void add_node(node** head, node** tail, int info);

void merge(node* tail1, node* head2)
{
tail->next=head2; //this is O(1)
return;
}

The case is not about O(1) but about how we design the list to have O(1)...
To design the list, we should try to remove duplicates when putting entries into the list. So, for example, if an element is going into list 1, we have to lookup the both lists to check if there is a duplicates. If there are duplicates, then, dont insert, else insert into one.

Maybe I'm missing something here, but if we can choose how to design the lists then we have some information regarding their contents. Looking at the contents we can come up with a condition that would neatly separate them into two groups, L1 would contain group1 and L2 would contain group 2, merging would then simply be appending one to the other.

A more concrete example:
Suppose our lists are to contain ints, in that case we can pick something like 16384 and put everything under that number in L1 and the rest in L2 in sorted order. Can use doubly-linked lists for this.

Of course efficiency and and the rest will depend upon what we are storing... but the idea was to get O(1) merge.

Comments?

Implement L1 and L2 as doubly linked lists. Merge them like this :

temp = L2 -> left;
(L1 -> left) -> right = L2;
L2 -> left = L1 -> left;
L1 -> left = temp;
(L1 ->left) -> right = L1;

Correct me if I'm wrong.

Skip list is the key...

What if we design the two lists to be circular lists. The tails point to the heads. Then we only have to break the two circles and combine them. What do you think about this?

I believe that should be double circular linked list

Just a circular linked list would do..

Data structure choice is ours hey? So what say we just add a bit "needsmerge" with an array of lists that would potentially need to be merge into one on next traversal/other operation. That is a typical tradeoff. If you want merge in O(1) then you expect it to be a common operation. So we just do it via lazy evaluation...

I think, if we need to remove duplicates then answer should be : not possible

Minimum O(N) not O(1) , question itself is wrong or it's not asking coding problem
O(N) java code for your reference

public static void main(String[] args){
		int[] a1={1,2,3,4,5,6,7,8};
		int[] a2={2,9,0,1,34,7,8};
		
		merge(a1,a2);
	}
	
	static void merge(int[] a1,int[] a2){
		ArrayList<Integer> arr=new ArrayList<>();
		for(int i=0;i<a1.length;i++){
			arr.add(a1[i]);
		}
		
		for(int i=0;i<a2.length;i++){
			if(arr.contains(a2[i]))
				continue;
			else
				arr.add(a2[i]);
		}
		
		for(int i:arr){
			System.out.println(i);
		}
	}

Isnt it a merging of two sorted list. (Merge sort), The time complexity is O(m+n). However,

struct node {
  int v;
  node *next;
    
};

node *merge(node *l, node *r) {
    node *root = NULL;
    node **np = &root;
    while(l && r) {
        if (l->v <= r->v) {
            // select l
            *np = l;`
            l = l->next;
            np = &l->next;
        } else {
            *np = r;
            r = r->next;
            np = &r->next;
        }
    }
    if (!l) {
        *np = r; 
    } else if (!r) {
        *np = l;
    }
    return root;
}

I assume we have two sorted list, which needs merging to get a combined merged list, in the same way we get for merge sort The time complexity is O(m+n) though,For O(1) merge, I assume that is just linking the list, (in case we have doubly linked list)

struct node {
  int v;
  node *next;
    
};

node *merge(node *l, node *r) {
    node *root = NULL;
    node **np = &root;
    while(l && r) {
        if (l->v <= r->v) {
            // select l
            *np = l;`
            l = l->next;
            np = &l->next;
        } else {
            *np = r;
            r = r->next;
            np = &r->next;
        }
    }
    if (!l) {
        *np = r; 
    } else if (!r) {
        *np = l;
    }
    return root;
}

Define the structure as-
struct node
{
int info;
int listFlag;
struct node *next;
};
/*
Flag can be
0 - 1st List,
1 - 2nd List,
2 - both
*/
So the insertion operation will either modify the flag of a node or add a new node with.
We do not need to perform any special operation.
And I suppose using this structure we can perform Union, Intersection, Set Difference in O(1) time.
The only thing that we need to change is the testing of listFlag while traversing the list.

How about this. since we can define our data structure, let us define the data structure as "always sorted linked list with a tail pointer." Now whether the data structure requires extra time for insertion is not a headache. so at this point just take the tail pointer of one list and make it point to the head of the second.

Does it sound logical?

assuming we are talking about stl lists, then we can do this using one of the splice functions.

if not using stl lists then since lists are data structs with a pointer to the next element, we just have to do one instruction i.e lst1.end->next = lst2.head. voila both lists are merged !!!