Monday, March 24, 2014

Better Programmer Contest


Completed the contest with 74% (http://www.betterprogrammer.com/certificate/BP1Q9GB5). I know its not good but i got all of the tasks correct so that's what matters to me. Following are my solutions and the JUnit tests:

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class BetterProgrammerTask {

 /**
  * Task 1
  */
 public static int getSumOfNumbers(String s) {
  int retVal = 0;
  /*
   * Please implement this method to return the sum of all integers found
   * in the parameter String. You can assume that integers are separated
   * from other parts with one or more spaces (' ' symbol). For example,
   * s="12 some text 3  7", result: 22 (12+3+7=22)
   */
  List numList = new ArrayList<>();
  String[] inStrs = s.split("\\s");
  for (String str : inStrs) {
   try {
    int num = Integer.parseInt(str);
    numList.add(num);
   } catch (Exception e) {
    // ignore and proceed to next.
   }
  }

  if (!numList.isEmpty()) {
   for (Integer n : numList) {
    retVal += n;
   }
  }
  return retVal;
 }

 /**
  * Task 2
  * 
  * @param from
  * @param to
  * @return
  */
 public static List getPerfectNumbers(int from, int to) {
  /*
   * Please implement this method to return a list of all perect numbers
   * in the given range inclusively. A perfect number is defined as a
   * positive integer which is the sum of its positive divisors not
   * including the number itself. For example: 6 is a perfect number
   * because 6 = 1 + 2 + 3 (1, 2, 3 are divisors of 6) 28 is also a
   * perfect number: 28 = 1 + 2 + 4 + 7 + 14
   */
  List perfectNumList = new ArrayList();

  for (int i = from; i <= to; i++) {
   List divisorsList = new ArrayList();
   for (int j = 1; j < i; j++) {
    if (i % j == 0) {
     divisorsList.add(j);
    }
   }
   if (!divisorsList.isEmpty()) {
    int sum = 0;
    for (Integer n : divisorsList) {
     sum += n;
    }
    if (sum == i) {
     perfectNumList.add(i);
     System.out.println(i);
    }
   }
  }
  return perfectNumList;
 }

 /**
  * Task 3
  * 
  * 
  */
 public static interface Node {
  int getValue();

  List getChildren();
 }

 public static List traverseTreeInWidth(Node root) {
  /*
   * Please implement this method to traverse the tree in width and return
   * a list of all passed nodes.
   * 
   * The list should start with the root node, next it should contain all
   * second-level nodes, then third-level nodes etc.
   * 
   * The method shall work optimally with large trees.
   */
  List visitedNodesList = new ArrayList();
  Queue queue = new PriorityQueue();

  if (root != null) {
   queue.add(root);
   while (!queue.isEmpty()) {
    Node visitedNode = queue.remove();
    visitedNodesList.add(visitedNode);
    queue.addAll(visitedNode.getChildren());
   }
  }
  return visitedNodesList;
 }

 /**
  * Task 4
  * 
  * @param cents
  * @return
  */
 public static int countWaysToProduceGivenAmountOfMoney(int cents) {
  /*
   * Please implement this method to return the number of different
   * combinations of US coins (penny: 1c, nickel: 5c, dime: 10c, quarter:
   * 25c, half-dollar: 50c) which may be used to produce a given amount of
   * money.
   * 
   * For example, 11 cents can be produced with one 10-cent coin and one
   * 1-cent coin, two 5-cent coins and one 1-cent coin, one 5-cent coin
   * and six 1-cent coins, or eleven 1-cent coins. So there are four
   * unique ways to produce 11 cents. Assume that the cents parameter is
   * always positive.
   */
  int coins[] = {1,5,10,25,50};
  
  int table[] = new int[cents+1];
  
  for (int i = 0; i < cents + 1; i++) {
   table[i] = 0;
  }
  
  table[0] = 1;
  
  for (int i = 0; i < coins.length; i++) {
   for (int j = coins[i]; j <= cents; j++) {
    table[j] += table[j - coins[i]];
   }
  }
  
  return table[cents];
 }
}
import java.util.List;

import org.junit.Assert;
import org.junit.Test;

public class BetterProgrammerTaskTest {

 @Test
 public void testGetSumOfNumbers() {
  int val = BetterProgrammerTask.getSumOfNumbers("-1 some text 3  7");
  Assert.assertEquals(9, val);
 }
 
 @Test
 public void testPerfectNumbers() {
  List list = BetterProgrammerTask.getPerfectNumbers(5, 28);
  Assert.assertEquals(2, list.size());
 }

 @Test
 public void testCountWaysToProduceGivenAmountOfMoney() {
  int count = BetterProgrammerTask.countWaysToProduceGivenAmountOfMoney(11);
  Assert.assertEquals(4, count);
 }
}

No comments:

Book notes: Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems, by Martin Kleppmann

My notes from the excellent book on how software has evolved to handle data from hierarchical databases to the NoSQL -  https://www.goodrea...