merge

Union and Intersection of two unsorted Linked Lists

Posted on July 30, 2014 (Last modified on August 7, 2020) | 4 minutes | Kinshuk Chandra

Problem Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Order of elments in output lists doesn’t matter. Example Input: List1: 10->15->4->20 lsit2: 8->4->2->10 Output: Intersection List: 4->10 Union List: 2->8->20->4->15->10 Solution Method 1 - Simple Following are simple algorithms to get union and intersection lists respectively. Intersection (list1, list2) Initialize result list as NULL. Traverse list1 and look for its each element in list2, if the element is present in list2, then add the element to result. [Read More]

Union and Intersection of two sorted arrays

Posted on July 30, 2014 (Last modified on August 7, 2020) | 2 minutes | Kinshuk Chandra

Problem Find Union and Intersection of two sorted arrays Example For example, if the input arrays are: arr1[] = {1, 3, 4, 5, 7} arr2[] = {2, 3, 5, 6} Then your program should print Union as {1, 2, 3, 4, 5, 6, 7} and Intersection as {3, 5}. Solution Algorithm Union(arr1[], arr2[]): For union of two arrays, follow the following merge procedure. Use two index variables i and j, initial values i = 0, j = 0 If arr1[i] is smaller than arr2[j] then print arr1[i] and increment i. [Read More]

Adobe kodeknight merge union two-sorted-arrays intersection

Merge two sorted arrays - One having big enough buffer to hold another

Posted on March 28, 2014 (Last modified on August 7, 2020) | 2 minutes | Kinshuk Chandra

Problem You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order. Another way to ask same question Given a sorted array of size n with n elements (array1) and a sorted array of size 2n with n elements (array2), merge them to get a sorted array of size 2n. [Read More]

kodeknight merge sorting two-arrays two-sorted-arrays CrackingTheCodingInterview sorted-array sorting-and-searching

Merge Overlapping Intervals

Posted on March 26, 2014 (Last modified on August 7, 2020) | 3 minutes | Kinshuk Chandra

Problem Given a collection of intervals, merge all overlapping intervals. Input - Collection of intervals Output - Collection of mutually exclusive intervals after merging Example Given

1,3

2,6

8,10

15,18

, return

1,6

8,10

15,18

. Solution Method 1 - Brute force A simple approach is to start from the first interval and compare it with all other intervals for overlapping, if it overlaps with any other interval, then remove the other interval from list and merge the other into the first interval. [Read More]

kodeknight merge sorting array interval

Sort a linked list using merge sort

Posted on January 19, 2014 (Last modified on August 7, 2020) | 3 minutes | Kinshuk Chandra

Merge sort looks like a best choice for sorting the linked list.At a first appearance, merge sort may be a good selection since the middle element is required to subdivide the given list into 2 halves, but we can easily solve this problem by moving the nodes alternatively to 2 lists. We have discussed the sorting options for linked list here. Merge sort is very special (in fact many standard sort libraries like in java internally uses a combination of merge sort and insertion sort) because it has the wonderful property of being a stable sort. [Read More]

kodeknight merge sorting linked list merge-sort

What's the fastest algorithm for sorting a linked list?

Posted on January 19, 2014 (Last modified on August 7, 2020) | 2 minutes | Kinshuk Chandra

Merge sort is the best choice. At a first appearance, merge sort may be a good selection since the middle element is required to subdivide the given list into 2 halves, but we can easily solve this problem by moving the nodes alternatively to 2 lists. It is reasonable to expect that you cannot do any better than O(N log N) in running time, whenever we use comparison based sorts. [Read More]

bubble sort kodeknight merge quicksort sorting linked list Selection Sort merge-sort insertion-sort

Merge two arrays efficiently - one sorted, another unsorted

Posted on January 19, 2014 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra

Problem Given a sorted array of n elements followed by an unsorted array of length n. Sort the 2 list into one efficiently. Solution Method 1 - Insert the elements in sorted array using binary search Since inserting a single element into array and keeping it sorted is O(n), you cannot get better then that. Thus, for both cases - sorting the smaller array and then using merge(part1,part2) will be O(n), and thus optimal in terms of asymptotic complexity. [Read More]

kodeknight merge union sorting array two-arrays two-sorted-arrays sorted-array

Bottom-up Merge Sort

Posted on January 19, 2014 (Last modified on August 7, 2020) | 3 minutes | Kinshuk Chandra

Recursive algorithm In the earlier article I’ve described a recursive version of the Merge Sort Algorithm OR Top Down Merge sort. Of course every recursive algorithm can be written in an iterative manner . Non recursive algorithm So today I am going to present the bottom-up version of the same algorithm, written in a non-recursive fashion . The main idea of the bottom-up merge sort is to sort the array in a sequence of passes . [Read More]

kodeknight merge sorting incomplete top-down merge-sort bottom-up

Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].

Posted on January 19, 2014 (Last modified on August 7, 2020) | 1 minutes | Kinshuk Chandra

Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].
e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2,1,3,3,6,8,8]

http://stackoverflow.com/questions/6153915/merging-of-two-sorted-halfs-without-extra-memory

kodeknight merge incomplete array bitonic sorted-array

k-way merge - Merging k sorted arrays of n elements

Posted on January 19, 2014 (Last modified on August 7, 2020) | 3 minutes | Kinshuk Chandra

Given k sorted arrays of size n each, merge them and print the sorted output. Example: **Input:** k = 3, n = 4 arr

= { {1, 3, 5, 7}, {2, 4, 6, 8}, {0, 9, 10, 11}} ; **Output:** 0 1 2 3 4 5 6 7 8 9 10 11 Method 1 - Merging from 1 array to other It does so by using the “merge” routine central to the merge sort algorithm to merge array 1 to array 2, and then array 3 to this merged array, and so on until all k arrays have merged. [Read More]

kodeknight merge divide and conquer sorting array two-sorted-arrays min-heap sorted-array