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]
kodeknight  merge  Single Link List  unsorted-array  linked list  two-lists  merge-sort 

Remove duplicates from unsorted array

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

**Problem ** Remove duplicates from unsorted array Example a[1,5,2,6,8,9,1,1,10,3,2,4,1,3,11,3] ```so after that operation the array should look like a[1,5,2,6,8,9,10,3,4,11] Solution **Method 1 - Brute Force - Check every element against every other element** The naive solution is to check every element against every other element. This is wasteful and yields an O(n2) solution, even if you only go "forward". **Method 2 - Sort then remove duplicates** A better solution is sort the array and then check each element to the one next to it to find duplicates. [Read More]
kodeknight  duplicate  unsorted-array  remove-duplicates 

Find Local Minimum in an unsorted array with unique elements

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

The pseudo / java code find only global minima and… Himadri Sarkar - Mar 0, 2014The pseudo / java code find only global minima and that too when no other local minima exist. I don’t think this problem can be solved in less than O(n) Hi Himadri, thanks for the comment. But I think the code is intended to give us local minima, and as we are apply binary search logic, it is possible in O(log n). [Read More]
kodeknight  local-minima  array  unsorted-array 

Find Local Minimum in an unsorted array with unique elements

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

Problem: Given an array ‘a’ of N distinct integers, design an O(log N) algorithm to find a local minimum: an index i such that a[i-1] > a[i] < a[i+1]. Examples: a = [1,2,3,4,5] (increasing, increasing) a[0] is an LM a = [5,4,3,2,1] (decreasing, decreasing) a[n] is an LM a = [1,2,2,2,1] (increasing, decreasing) a[0] and a[n] are LMs Solution: **Brute force ** Go through each element 3 tuples, and compare them. [Read More]
kodeknight  local-minima  array  unsorted-array 

Find the minimum and maximum in the array

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

Here are few question we find on finding min and max in the array, but array type changes. Unsorted 1D array Find the maximum (OR minimum) in an array Find the maximum AND minimum in an array with min number of comparisons Find the max and second maximum in an array (likewise for minimum) Find the max and nth max in an array Rotated Sorted array Find the minimum element in the rotated sorted array. [Read More]
max  kodeknight  Page  minmax  2DSortedArray  unsorted-array  min  sorted-array 

Find Maximum Value in the unsorted array

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

**Problem : **
Find Maximum Value in the unsorted array

Solution
Method 1 - Linear search

Here is the code to do that :

public int findMax(int\[\] numbers)  
{  
    int max = 0;  
  
    for (int i = 0; i < numbers.length; ++i)  
        if (numbers\[i\] > max) max = numbers\[i\];  
  
    return max;  
}

So, in worst case the number of comparisons will be (n-1).

Time complexity - O(n)

max  kodeknight  unsorted-array  min 

Find kth largest in an Array

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

**Problem : **  You have an array of numbers; you need to find the k-th largest in the arra Solution ** Method 1 - Tournament principle** We have to find the element which has competed with largest element, and is just (k-1)th level.We have discussed this principle here. Method 2 - Using max heap Consider the array of length n. Here is the algo :  Build a max heap in O(n) ;  Now remove k elements from the heap; wherein each removal costs log(n) time to maintain the heap property. [Read More]
max  kodeknight  largest  minmax  unsorted-array  kth-largest  min  smallest 

find out the largest and second largest number in an array

 Posted on February 14, 2014  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

Question: Write an efficient C program to find smallest and second smallest element in an array. Solution Method 1 - Compare each element with current max and second max Algorithm 1) Initialize both first and second smallest as a00 first = second = a00 2) Loop through all the elements. a) If the current element is greater than firstMax, then update firstMax and secondMax. b) Else if the current element is greater than second then update secondMax pseudocode [Read More]
max  kodeknight  largest  minmax  unsorted-array  min  second-largest 

How to find max. and min. in array using minimum comparisons?

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

Problem : Given an array of integers find the max. and min. using minimum comparisons. Solution Method 1 (Naive) - Iterate through the array, and update min and max pointers 1\. Iterate through the array, select element a 2\. Update min by comparing (min, a) 3\. Update max by comparing (max, a) Number of comparison here will be ~2N, if N is number of element. Time complexity will be O(n) though. [Read More]
max  kodeknight  browserstack  minmax  array  unsorted-array  min