All posts in Algorithms
Problem statement Logan is cleaning his apartment. In particular, he must sort his old favorite sequence, , of positive integers in nondecreasing order. He’s tired from a long day, so he invented an easy way (in his opinion) to do this job. His algorithm can be described by the following . . . Read more
Problem statement Write a program that takes an array denoting the daily stock price, and returns the maximum profit that could be made by buying and then selling one share of stock. Solution
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

public class BuySellStockOnce { public static int solve(int[] stockPrice) { int minimumSeenSoFar = stockPrice[0]; int[] maxProfit = new int[stockPrice.length]; for (int i=0; i < stockPrice.length; i++) { maxProfit[i] = stockPrice[i]  minimumSeenSoFar; if (stockPrice[i] < minimumSeenSoFar) { minimumSeenSoFar = stockPrice[i]; } } int max = maxProfit[0]; for (int i=0; i < maxProfit.length; i++) { if (max < maxProfit[i]) { max = maxProfit[i]; } } return max; } public static void main(String[] args) { int[] stocks = { 310, 315, 275, 295, 260, 270, 290, 230, 255, 250 }; System.out.println(solve(stocks)); } } 
Problem statement You are given a square map of size . Each cell of the map has a value denoting its depth. We will call a cell of the map a cavity if and only if this cell is not on the border of the map and each cell adjacent . . . Read more
Problem statement Two people are playing game of Misère Nim. The basic rules for this game are as follows: The game starts with piles of stones indexed from to . Each pile (where ) has stones. The players move in alternating turns. During each move, the current player must remove . . . Read more
Problem statement Given a word , consisting of characters az, AZ and 09, compute the next lexicographical word , with 09 < AZ < az. Sample Input
Output
Solution
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

import sys def nextWord(w): word = list(w) cursor = len(w)  1 carry = True while carry and cursor >= 0: carry = False word[cursor] = chr(ord(word[cursor]) + 1) if ord(word[cursor]) == 58: # '9' > 'A' word[cursor] = "A" elif ord(word[cursor]) == 91: # 'Z' > 'a' word[cursor] = "a" elif ord(word[cursor]) == 123: # 'z' > '0' if cursor > 0: word[cursor] = "0" cursor = 1 carry = True else: return None return "".join(word) word = "k7" print(nextWord(word)) 
Notebook file https://github.com/lucaslouca/codingproblems/tree/master/python/NextWord
Problem statement Given sticks of lengths , use of the sticks to construct a nondegenerate triangle with the maximum possible perimeter. Then print the lengths of its sides as spaceseparated integers in nondecreasing order. If there are several valid triangles having the maximum perimeter: Choose the one with the longest . . . Read more
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 > 0){ result *= x; n; } return result; } 
This is ok, but the algorithm has a running time of . . . 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 countandsay 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