Algorithms

What is Backtracking? For any given problem — be it a decision-making problem like whether to stop the vehicle at any instance — in autonomous driving, an optimization problem like choosing the best path from my home to the office, or an enumeration problem like generating all possible permutations and combinations of teams play-outs in […]

How insertion sort works? Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It works best on a nearly sorted list. It has the following characteristics Stable; i.e., does not change the relative order of elements with equal keys In-place; i.e., only requires a […]

Problem statement: A binary array sorted in decreasing order is given. We need to count the number of 1’s in it. Examples: Input: arr[] = {1, 1, 0, 0, 0, 0, 0} Output: 2 Input: arr[] = {1, 1, 1, 1, 1, 1, 1} Output: 7 Input: arr[] = {0, 0, 0, 0, 0, 0, […]

Given problem: A list of n strings each of length n is sorted into lexicographic order using the merge sort algorithm. Solution: Comparing two strings require O(n) comparisons, hence each merge will take O(n2) time. So, the recurrence equation will be: T(n) = 2 T(n/2) + O(n2) The n in the equation represents no.of elements […]

Let us start with the heapsort algorithm: The build_maxheap() funnction has a standard implementation of O(n). The important part of the sorting is the for loop, which executes for n times. Inside that we have a swap method call and heapify method call. The heapify method is a standard walk through of complete binary tree. […]

Problem statment Given two queues with their standard operations (enqueue, dequeue, isempty, size), implement a stack with its standard operations (pop, push, isempty, size). Solution There can be two ways you can solve the above problem. Option A: The stack – efficient when pushing an item Option B: The stack – efficient when popping an item In this post lets us discuss the an implementation […]

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It works best on a nearly sorted list. It has the following characteristics Stable; i.e., does not change the relative order of elements with equal keys In-place; i.e., only requires a constant amount O(1) of […]

What is multiple-column index? MySQL or many RDBMS supports multiple-column indexes. i.e. The index key will be more than 1 column in the table. For example, consider a table consolidated CREATE TABLE `consolidated` ( `consolidated_id` int(11) NOT NULL AUTO_INCREMENT, `pub_id` int(11) DEFAULT NULL, `cp_id` int(11) DEFAULT NULL, `ro_id` int(11) DEFAULT NULL, `country_id` int(11) DEFAULT NULL, […]

Coin Exchange Problem: Coin exchange problem is nothing but finding the minimum number of coins (of certain denominations) that add up to a given amount of money. It is a knapsack type problem. The interesting fact is that it has 2 variations: 1. Greedy Algorithm: For some type of coin system (canonical coin systems — […]

What is a Data Structure? We will not be talking about data structures implementation in this post, but about their usage or choice during programming. As usual lets start from the basic definition. Data Structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. They […]