# All posts tagged algorithms

Problem statement Given two strings and of equal length, what’s the longest string () that can be constructed such that it is a child of both? A string is said to be a child of a string if can be formed by deleting or more characters from . For example, . . . Read more

This is a rather short post. in which I explain how to we can implement a fast pow function to raise a number to the power of . A rather naive approach would be to do the following: int pow(int x, int n){ int result = 1; while (n > . . . Read more

Problem statement You are situated in an dimensional grid at position . The dimensions of the grid are In one step, you can walk one step ahead or behind in any one of the dimensions. (So there are always possible different moves). In how many ways can you take steps . . . Read more

Problem statement The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, … 1 is read off as one 1 or 11. 11 is read off as two 1s or 21. 21 is read off as one 2, then one 1 or 1211. Given . . . Read more

The Boyer–Moore string search algorithm is an efficient string searching algorithm that is the standard benchmark for practical string search literature. For instance, GNU grep uses the Boyer-Moore algorithm. For a full explanation of the algorithm please refer to Wikipedia.

The Aho–Corasick algorithm is a string searching algorithm invented by Alfred V. Aho and Margaret J. Corasick. For a full explanation of the algorithm please refer to Wikipedia.

Problem statement Given a collection of intervals, merge all overlapping intervals. Sample Input [1,3],[2,6],[8,10],[15,18] Output [1,6],[8,10],[15,18] Solution Concept We sort the intervals by decreasing order of start times. That way we can quickly check if intervals overlap or not by comparing start time of previous interval with end time of . . . Read more

Problem statement Ema built a quantum computer! Help her test its capabilities by solving the problem below. Given a grid of size , each cell in the grid is either or . A valid plus is defined here as the crossing of two segments (horizontal and vertical) of equal lengths. . . . Read more

Problem statement You can perform the following operation on some string, : 1. Capitalize zero or more of ‘s lowercase letters at some index i (i.e., make them uppercase). 2. Delete all of the remaining lowercase letters in . Given queries in the form of two strings, and , determine . . . Read more

In the previous post I discussed an algorithm that had a running time of . Well here is an algorithm to the Goodland Electricity challenge. Greedy algorithm For each city i store its preceding tower in previousTowerFor[i]. If i has a tower then previousTowerFor[i] = i. If no tower precedes, . . . Read more