# How to solve Dynamic Programming(DP) problem?

Most common type of questions asked in interviews is on dynamic programming. DP is not the toughest topic to understand if your basic of programmings are strong.

Prerequisites for this topic is mentioned below

If you are not able to figure out when to use recursion…

# Max sub-array sum in a circular array

Lets first solve the problem for normal array-

Example —

Given array [4, 6, 7, -2, –3, –4, 20, -10]

Max Sum sub-array = (4+6+7–2–3–4+20) = 28

Solution —

Lets have currMaxSum & maxSum variables where currMaxSum will calculate max subarray including current element while maxSum will be sum in…

# Consistent Hashing in Simple Terms

## Problem Statement

Distribute data between servers/cache such that removal & addition server can be done efficiently & minimum data transfer should be there between servers. Also, we need to make sure data is distributed evenly b/w servers

## Solution

Single machine solution -

We will store data in hashmap which will do the below…

# Median of an array

A median of a population is any value such that at most half of the population is less than the proposed median and at most half is greater than the proposed median

It is a value which divides an array into 2 equal parts

# Basic things you should know about Java Collections

As the name suggests collection is the group of objects & java collection framework provides implementations that can hold the group of objects.

Java collection is divided into 4 main sections-

SET — It is a data structure that stores unique objects. …

# Backtracking — Rat in a Maze

Let's take the “Rat in a maze” problem, which is a common example, to understand backtracking

We have given a maze that consists of 1’s & 0’s elements. Element 1 represents the empty cell while element 0 is a wall from which the rat can not pass.

A rat starts…

# Binary Search on Matrix

Problem Statement — check whether an element is present in a matrix of size n*m in which rows & columns are sorted in increasing order.

Sample Input -

[ [1, 3, 12],

[2, 4 , 20],

[5, 10, 30]]

k=4

Output

true

Solution :

The initial thought is to apply…

# Prefix Sum Technique

Prefix sum is the technique where you precompute & store the cumulative sum of the sequence of elements that allows fast sum calculation of any range.

Let's say we have a sequence of elements A as mentioned below-

A = {a0, a1, a2, a3, a4, a5}

so Prefix Sum P…

# Data Structures

Array — prefix sum, 2 pointers, sliding window technique

Matrix — Search in the sorted matrix, find the kth smallest element in the sorted matrix