The Coding Shala

Home >> Algorithms >> Selection Sort  In this post, we will learn what is Selection Sort Algorithm and how to implement Selection Sort in Java. Selection Sort Algorithm The selection sort algorithm is a sorting algorithm that sorts an array by repeatedly finding minimum element(ascending order)/maximum element(descending order) from the unsorted part and put it at the beginning of the unsorted array. This algorithm maintains two subarrays in a given array, one is sorted and the second is the remaining unsorted subarray. Working of Selection Sort Algorithm We follow the below steps to implement the Selection Sort Algorithm: Step 1. We pick the minimum element from the unsorted subarray. Step 2. Swap it with the first element of the unsorted subarray. Step 3. Now the first element of unsorted subarray becomes a part of the sorted subarray. Here is an example that explains the selection sort algorithm: Array:  64 25 12 22 11     ...

Last Updated: 27-Jan-2021 Home >> Algorithms >> Radix Sort Algorithm  In this post, we will learn what is Radix Sort Algorithm and how to implement Radix Sort in Java. Radix Sort Algorithm As we know sorting algorithms like Merge sort, Quicksort, etc is works in O(N log N) time. They can not do better than NlogN. We have another option as Counting sort that works in a linear time O(n+k) but the limitation in the range is there. We use the Radix sort algorithm when we have elements in the range from 1 to n^2. In the Radix sort algorithm, we do digit by digit sort starting from least significant digit(leftmost) to most significant digit(rightmost). We use counting sort to sort the digits because the range of these digits is less in the range of 0 to 9. Working of Radix Sort Algorithm Radix sort works by sorting the input numbers one digit at a time. let's take an example: input array->  { 127,  324, 173,  4,  38,  217,  134...

Last Updated: 27-Jan-2021 Home >> Algorithms >> Quick Sort Algorithm  In this post, we will learn what is Quick Sort Algorithm and will write a Java program for Quick Sort. Quick Sort Algorithm Quick Sort is one of the most efficient sorting algorithms. If effectively implemented quick sort algorithm is significantly faster than any of the common sorting algorithms. Like Merge Sort, Quicksort is also a classic example of the divide-and-conquer approach. Working of Quick Sort Algorithm In a quick sort algorithm, we follow the divide and conquer approach. The following are the steps used in quicksort: step 1. First, we select a value from the list, called pivot value and it divides the list into two sublists. One sublist contains all the values that are less than the pivot value, another sublist contains the values that are greater than or equal to the pivot value. This process is also called partitioning. we can choose the first/last element in the list as the ...

Last Updated: 27-Jan-2021 Home >> Algorithms >> Sliding Window Algorithm  In this post, we will learn what is Sliding Window Algorithm and how to implement it in Java. Sliding Window Algorithm What do you mean by Sliding Window? A window of fixed length can be slide over the input. The sliding window algorithm is used to reduce the time complexity by converting the nested for loops into a single for loop. Let's take an example and understand the sliding window problem. we have given an array of integers of size n and need to find the maximum sum of k consecutive elements in the array. Input array:  { 100, 200, 300, 400} k = 2 Output: 700 So how we solve this problem we start outer loop from index 0 and inner loop runs till i+k size every time and compare the maximum sum. The following is the code for this brute force approach. Java Program:  static int maxSum ( int arr [], int n , int k ) { // Initialize result ...

Last Updated: 27-Jan-2021 Home >> Interview Questions >> Validate Binary Search Tree  In this post, we will learn how to Validate Binary Search Tree and will implement its solution in Java. Validate Binary Search Tree Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees. Example 1:     2    / \   1   3 Input: [2,1,3] Output: true Example 2:     5    / \   1   4       / \     3   6 Input: [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4. Validate Binary Search Tree Java Program Approach 1 Using recursion and inor...

Last Updated: 27-Jan-2021 Home >> Interview Questions >> Unique Binary Search Trees  In this post, we will learn how to Generate all Possible Unique Binary Search Trees and will implement its solution in Java. Generate all Possible Unique Binary Search Trees Given N, generate all structurally unique BST’s (binary search trees) that store values 1…N. Example: Input:     A = 3 Output:    1          3        3        2         1      \        /        /         /   \         \       3    2       1         1    3         2      /     /           \          ...

Last Updated: 26-Jan-2021 Home >> Data Structures >> Introduction to Trie Data Structure  In this post, we will learn what is Trie Data Structure and how to implement Trie in Java. Introduction to Trie Data Structure Trie is a special form of an N-ary tree, also called prefix tree. Tries are an extremely special and useful data-structure are based on the prefix of a string. They are used to represent the Retrieval of data and thus the name Trie. A Trie is a special data structure used to store strings that can be visualized like a graph. It consists of nodes and edges. Each node consists of at max 26 children and edges connect each parent to its children. These 26 pointers are nothing but pointers for each of the 26 letters of the English alphabet.  Note: Root node is null in Trie. Strings are stored in a top to bottom manner on the basis of their prefix in a trie. All prefixes of length 1 are stored until level 1, all prefixes of length 2 are sorted until...