# Category: Software Development Engineer (SDE)

## Stock Single Sell Problem – O(n) Solution

Objec­tive:  Given an array represents cost of a stock on each day. You are allowed to buy and sell the stock only once. Write an algorithm to maximize the profit in single buy and sell....

## Maximum Subarray OR Largest Sum Contiguous Subarray Problem – Divide and Conquer

Objec­tive:  The max­i­mum sub­ar­ray prob­lem is the task of find­ing the con­tigu­ous sub­ar­ray within a one-dimensional array of num­bers which has the largest sum. Exam­ple: int [] A = {−2, 1, −3, 4, −1, 2, 1, −5, 4}; Output:...

## Maximum difference between two elements where larger element appears after the smaller element

Objective: Given an array A[], write an algorithm to find Maximum difference between two elements where larger element appears after the smaller element or in other words find A[i] and A[j] such that A[j]-A[i]...

## Find the two repeating elements in a given array | 6 Approaches

Objective: Given an array of n+2 elements. All elements of the array are in range 1 to n and all elements occur once except two numbers which occur twice. Write an algorithm to find...

## Find the element which appears maximum number of times in the array.

Objective: Given an array of integers, write a algorithm to find the element which appears maximum number of times in the array. Example: int [] arrA = {4, 1, 5, 2, 1, 5, 9,...

## Find duplicates in an given array in O(n) time and O(1) extra space.

Objective: Given an array of integers, find out duplicates in it. Example: int [] a = {4, 6, 2, 1, 2, 5}; Output: Array has duplicates : 2 int a [] = {1, 6,...

## Find the last repeating character in a given string.

Objective: Given a string, write an algorithm to find the last repeating character in it. Example: String input = “horizon tutorials” Output: ‘i’ String input = “algorithms” Output: No repeating character found. Approach: Naive...

## Find longest Snake sequence in a given matrix

Objective: Given two dimensional matrix, write an algorithm to find out the snake sequence which has the maximum length. There could be many snake sequence in the matrix, you need to return the one...

## Dynamic Programming – Count all paths in 2D Matrix with Obstructions in it

Objective: Given two dimensional matrix, write an algorithm to count all possible paths from top left corner to bottom-right corner. You are allowed to move only in two directions, move right OR move down....

## Dynamic Programming – Count all paths from top left to bottom right of a mXn matrix

Objective: Given two dimensional matrix, write an algorithm to count all possible paths from top left corner to bottom-right corner. You are allowed to move only in two directions, move right OR move down....

## Dynamic Programming – Edit Distance Problem

Objective: Given two strings, s1 and s2 and edit operations (given below). Write an algorithm to find minimum number operations required to convert string s1 into s2. Allowed Operations: Insertion – Insert a new...

## Dynamic Programming – Coin In a Line Game Problem

Objective: In this game, which we will call the coins-in-a-line game, an even number, n, of coins, of various denominations from various countries, are placed in a line. Two players, who we will call...

## Dynamic Programming – Box Stacking Problem

Objective: You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack...

## Dynamic Programming – Split the String into Minimum number of Palindromes.

Objective: You are given a large string. You need to cut the string into chunks such that each substring that you get is a palindrome. Remember that each 1 length string is always a...

## Dynamic Programming – Highway Billboard Problem

Objective:  Suppose you’re managing construction of billboards on the Rocky & Bullwinkle Memorial Highway, a heavily traveled stretch of road that runs west-east for M miles. The possible sites for billboards are given by...