Longest substring with at most K unique characters

Objective: Given a string, write an algorithm to find the longest substring with at most K characters. Example: Input: aabbaacdeeeeddded, K = 3 Output: Longest substring with 3 most unique characters is: cdeeeeddded with length 11 Input: abcddefabc, K = 4 Output: Longest substring with 4 most unique characters is: abcdd with length 5 Input: … Read more Longest substring with at most K unique characters

Sort a given stack – Using Temporary Stack

Objective: Given a stack of integers, write an algorithm to sort the stack using a temporary stack.  Example: Given Stack: [14, 9, 67, 91, 101, 25] Sorted Stack: [9, 14, 25, 67, 91, 101] Approach: Use another stack, let’s call it a temporary stack. While given original is not empty Pop the element from the … Read more Sort a given stack – Using Temporary Stack

Sum of all Unique elements in a given array

Objective: Given an array of integers that contains duplicates as well. Write a program to find the sum of all unique elements in the array. This problem is also referred to as find the sum of all distinct elements in the array Example: [] arrA = {1, 6, 4, 3, 2, 2, 3, 8, 1}; … Read more Sum of all Unique elements in a given array

Selection Sort – Java Implementation

What is Selection Sort?? Selection sort is a simple sorting algorithm that builds the sorted array one item at a time. This sorting is efficient for small data sets, not efficient for large data sets. This is in-place sorting algorithm. How Selection Sort algorithm works?? This algorithm divides the given input list into two parts, … Read more Selection Sort – Java Implementation

Find Number of reverse pairs in an array

Objective: Given an array of integers A[],find no of reverse pairs means no of (i, j) pairs where i < j and A[i]>A[j]. This problem is also asked as Count Inversions in an array. Example: A[] = {10, 3, 4, 2, 5, 7, 9, 11} Output:7 Reversed pairs: (10, 3) (10, 4) (10, 2) (10, … Read more Find Number of reverse pairs in an array

Insertion Sort – Java Implementation

What is Insertion Sort?? Insertion sort is a simple sorting algorithm that builds the sorted array one item at a time. Efficient for small data sets, not efficient for large data sets. Most of the time we sort the playing cards in our hand using insertion sort without knowing about it. At any given time, … Read more Insertion Sort – Java Implementation

Heap Sort – Java Implementation

What is Heap Sort?? Heap sort is comparison based sorting algorithm. Heap sort is considered as improved selection sort, it divides the input into sorted and unsorted region. The improvement from selection sort is to use Heap Data Structure instead of using linear search algorithm to reduce of the time complexity. Pre-requisite: Binary Heap (min … Read more Heap Sort – Java Implementation

Bubble Sort and Optimized Bubble Sort- Java Implementation

In this article we will discuss about what is bubble sort, why it is considered as one of the simplest sorting algorithm, what its complexity, how we can improve the bubble sort algorithm. What is bubble sort?? Bubble sort is one of the simplest sorting algorithms. Bubble sort compares each pair of adjacent items and swaps … Read more Bubble Sort and Optimized Bubble Sort- Java Implementation

Sort Names by their Last Names.

Objective: Given a list of names ( first name and last name), sort the list by their last names. Example: List [] = {“Daenerys Targaryen”, “Jon Snow”, ” Tyrion Lannister”, ” Joffrey Baratheon”} Output: [Joffrey Baratheon, Tyrion Lannister, Jon Show, Daenerys Targaryen] Approach: We have sort() and Collections.sort() but we cannot do the normal sorting … Read more Sort Names by their Last Names.

Merge K Sorted Arrays

Objective: Given k sorted array, write an algorithm to merge Them into One sorted array.

Example :

int[][] A = new int[5][];

A[0] = new int[] { 1, 5, 8, 9 };
A[1] = new int[] { 2, 3, 7, 10 };
A[2] = new int[] { 4, 6, 11, 15 };
A[3] = new int[] { 9, 14, 16, 19 };
A[4] = new int[] { 2, 4, 6, 9 };

Output:
[1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9, 9, 10, 11, 14, 15, 16, 19]

Read moreMerge K Sorted Arrays

Counting Sort

Counting Sort is an sorting algorithm, which sorts the integers( or Objects) given in a specific range.

Algorithm: Time Complexity O(n)

  • Take two arrays, Count[] and Result[] and given array is input[].
  • Count[] will store the counts of each integer in the given array.
  • Update the Count[] so that each index will store the sum till previous step. (Count[i]=Count[i] + Count[i-1]). Now updated Count[] array will reflect the actual position of each integer in Result[].
  • Now navigate the input array taking one element at a time, Count[input[i]] will tell you the index position of input[i] in Result[]. When you do that, decrease the count in Count[input[i]] by 1. See Example

Read moreCounting Sort

Sort 3 Integers without using if condition OR use only Max() function.

Objec­tive: Given three integers, sort them without using if condition.

Appraoch:

  • Say 3 integers are, a, b, c.
  • Find the maximum of a, b, c using Max() function.
  • multiply all integers by -1. Again find Minimum of -a, -b, -c using Max() function.
  • Add the Max and Min from above steps and subtract it from (a+b+c). It will give you middle element.

Read moreSort 3 Integers without using if condition OR use only Max() function.

Merge Sort in a Linked list

Objective: Given a Linked List, Sort it using merge sort. Example: ->9->3->4->2->5->1 Sorted List: ->1->2->3->4->5->9 Approach: Reference : Merge Sort in array As it Merge sort, we apply the same logic , Divide and Conquer. Find the length of the link list, say it is L. mid will be L/2. Now we need to divide … Read more Merge Sort in a Linked list

Sort an Given Array in the order defined by another array

Objective: Given an array of integers, write an algorithm to sort it according to the order defined by another array.

Input: An Array of Integers

Example:

Input Array : 2 6 9 1 4 4 2 1 10 13 5 7 8

DefinedArray : 1 2 4 6

Output : 1 1 2 2 4 4 6 5 7 8 9 10 13

Appraoch:

Method 1: Sort and Search

Read moreSort an Given Array in the order defined by another array

Sort an Array – odd numbers appear first in ascending order followed by the even numbers in descending order.

Objective: Given an array of intergers, sort it such that the odd numbers appear first followed by the even numbers . The odd numbers in ascending order and the even numbers in descending order.

Input: An Array of Integers

Example:

Input Array : 1 2 3 4 5 6 7 8 9 10
Output : 1 3 5 7 9 10 8 6 4 2

Read moreSort an Array – odd numbers appear first in ascending order followed by the even numbers in descending order.