All posts tagged algorithms
Problem Statement In an array, , the elements at indices and (where ) form an inversion if . In other words, inverted elements and are considered to be “out of order”. To correct an inversion, we can swap adjacent elements. For example, consider the dataset . It has two inversions: . . . Read more
Problem Statement You are given queries. Each query is of the form two integers described below: – : Insert x in your data structure. – : Delete one occurence of y from your data structure, if present. – : Check if any integer is present whose frequency is exactly . . . . Read more
You are given an array and you need to find number of tripets of indices such that the elements at those indices are in geometric progression for a given common ratio and . For example, . If , we have and at indices and . Function Description Complete the countTriplets . . . Read more
Problem Statement Harold is a kidnapper who wrote a ransom note, but now he is worried it will be traced back to him through his handwriting. He found a magazine and wants to know if he can cut out whole words from it and use them to create an untraceable . . . Read more
Problem Statement You are given an unordered array consisting of consecutive integers without any duplicates. You are allowed to swap any two elements. You need to find the minimum number of swaps required to sort the array in ascending order. For example, given the array we perform the following steps: . . . Read more
Problem Statement Gary is an avid hiker. He tracks his hikes meticulously, paying close attention to small details like topography. During his last hike he took exactly steps. For every step he took, he noted if it was an uphill, , or a downhill, step. Gary’s hikes start and end . . . Read more
Problem Statement Create a stack data structure that supports the following operations as efficiently as possible: Push, which adds a new element atop the stack, Pop, which removes the top element of the stack, FindMin, which returns (but does not remove) the smallest element of the stack Full Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

package stacksqueues; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import datastructures.MyStack; /** * How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum * element? Push, pop and min should all operate in O(1) time. * * @author lucas */ public class E2 { protected static class MyStackWithMin extends MyStack { MyStack mins; public MyStackWithMin() { mins = new MyStack<Integer>(); } public void push(int item) { super.push(item); if (item <= min()) { mins.push(item); } } public Integer pop() { int item = (int) super.pop(); if (item == min()) { mins.pop(); } return item; } /** * Return min element on stack * * @return */ public int min() { if (mins.isEmpty()) { return Integer.MAX_VALUE; } else { return (int)mins.peek(); } } } public static void main(String[] args) { MyStackWithMin stack = new MyStackWithMin(); stack.push(3); stack.push(31); stack.push(13); stack.push(2); stack.push(5); System.out.println(stack.min()); } } 
Problem statement Given a matrix in which each row and each column is sorted, write a method to find an element in it. Solution Assumptions: 1. Rows are sorted left to right in ascending order. Columns are sorted top to bottom in ascending order. 2. Matrix is of size . . . . Read more
Problem Statement Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents Solution This is a recursive problem, so let’s figure out how to do makeChange(n) using prior solutions (i . . . Read more
Problem Statement Implement an algorithm to print all valid (e g , properly opened and closed) combinations of npairs of parentheses Example Input: 3 (e g , 3 pairs of parentheses) Output: ()()(), ()(()), (())(), ((())) Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

public class PrintAllValidParens { static void solve(int l, int r, int i, char[] str) { if (l == 0 && r == 0) { System.out.println(new String(str)); } else { if (l > 0) { str[i] = '('; solve(l  1, r, i + 1, str); } if (r > 0 && r > l) { str[i] = ')'; solve(l, r  1, i + 1, str); } } } public static void main(String[] args) { solve(3, 3, 0, new char[6]); } } 