All posts tagged algorithms
Problem statement In a party of people, only one person is known to everyone (celebrity). That celebrity doesn’t know anyone in the party. Find the celebrity if such a person exist. Input Format The first line of the input will contain ( the number of people) and . Each of . . . Read more
Problem statement How would enumerate all the prime numbers up to a given range? Solution There way we are going to solve it is using a wellknown approach called Sieve of Eratosthenes. The approach is as follows: Assume . 1. First generate a list of integers from 2 to 30. . . . Read more
Problem statement Given two unsorted arrays, one with event start times and one with end times, find out if any two events overlap. Solution The key to the solution is to sort the appointments according to their start time in decreasing order, while keeping the correlation between the start and . . . Read more
Problem statement Write a function that takes the ordinal number of a column in a spreadsheet and returns the label of that column.

1 > A 2 > B 26 > Z 27 > AA ... 703 > AAA ... 
Full code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

public class Ordinal2SpreadsheetNumber { public static String convert(int n) { if (n>=1 && n<=26) { return ""+(char)(n + 'A'  1); } else { return convert(n/26) + (char)(n % 26 + 'A'  1); } } public static void main(String[] args) { System.out.println(convert(1)); System.out.println(convert(2)); System.out.println(convert(3)); System.out.println(convert(26)); System.out.println(convert(27)); System.out.println(convert(28)); System.out.println(convert(703)); } } 
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 fastpaced 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.
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

public class FindDuplicateWithinN { public static boolean find(int[] array, int k) { // always carry the last kvisited elements with each iteration Set<Integer> set = new HashSet<Integer>(k); for (int i = 0; i < array.length; i++) { int current = array[i]; if (set.contains(current)) { return true; } if (i < k) { // do nothing } else { set.remove(array[i  k]); } set.add(current); } return false; } public static void main(String[] args) { System.out.println(find(new int[] { 5, 5, 9, 4, 5, 20, 6, 7, 8, 10 }, 2)); } } 
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)); } } 