# All posts tagged algorithms

Problem statement Given an array that contains duplicates of all the numbers except one number. Find the missing number. Solution We could of course use a HashMap that maps each number to the number of occurrences. This will have a a space complexity of . A better solution is to . . . Read more

Problem statement Borussia Dortmund are a famous football ( soccer ) club from Germany. Apart from their fast-paced style of playing, the thing that makes them unique is the hard to pronounce names of their players ( błaszczykowski , papastathopoulos , großkreutz etc. ). The team’s coach is your friend. . . . Read more

Problem statement Given an array A = [1, 2, 3, 5, 6, 7 ] and number . This means that the array consists of the numbers from . However, as you see, is missing in . Print the missing number. Solution The solution proposed here makes use of the triangular . . . Read more

Problem statement Given an array of values, design and code an algorithm that returns whether there are two duplicates within indices of each other? Do all, in running time and space. Solution The main idea is to always carry the last -visited elements with each iteration. public class FindDuplicateWithinN { . . . Read more

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 public class BuySellStockOnce { public static int solve(int[] stockPrice) { int minimumSeenSoFar = stockPrice[0]; int[] maxProfit = . . . Read more

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 a-z, A-Z and 0-9, compute the next lexicographical word , with 0-9 < A-Z < a-z. Sample Input hLPk7 Output hLPk8 Solution import sys def nextWord(w): word = list(w) cursor = len(w) – 1 carry = True while carry and cursor . . . Read more

Problem statement Given sticks of lengths , use of the sticks to construct a non-degenerate triangle with the maximum possible perimeter. Then print the lengths of its sides as space-separated integers in non-decreasing order. If there are several valid triangles having the maximum perimeter: Choose the one with the longest . . . Read more