akmo75
BAN USERScala implementation:
def main(args: Array[String]) {
count(Array[Int](1, 2, 4, 1))
count(Array[Int](1, 2, 4, 1, 2))
count(Array[Int](1, 2, 4, 1, 2, 4))
count(Array[Int](1, 2, 4, 1, 2, 4, 4))
count(Array[Int](1, 2, 4, 1, 2, 4, 5))
}
def count(arr: Array[Int]) = {
val counts: Map[Int, Int] = arr
.toList
.groupBy(x => x)
.mapValues(_.size)
val evenValues = counts.map{case (x, size) => (x, size/2)}.values
val middle = counts.find(_._2 % 2 == 1).map(x => 1).getOrElse(0)
println(evenValues.sum * 2 + middle)
}
Scala solution:
def main(strings: Array[String]) = {
val s = "Salesforce is the best company to work for"
val map = mutable.Map[Char, Int]()
s.toCharArray.zipWithIndex.foreach{
case (c, i) =>
val lower = c.toLower
map.update(lower, map.getOrElse(lower, 0) + 1)
}
println(s.toCharArray.find(c => map(c.toLower) == 1))
}
Looks like a TSP, which is a O(2^n) problem.
This is why I created a greedy algorithm:
object ShortestDeliveryPath {
val officeLocation = Location(0,0)
val homeLocation = Location(100,100)
val deliveryLocations = List((20,30), (50,50), (70,70)).map(Location.tupled)
case class Location(x: Int, y: Int)
def main (args: Array[String]) {
val route = calculateRoute()
println(route)
}
def calculateRoute() = {
def go(location: Location, processedLocations: mutable.LinkedHashSet[Location]): mutable.LinkedHashSet[Location] = {
val nextLocation = closestLocation(location, processedLocations)
nextLocation.map(loc => go(loc, processedLocations + location)).getOrElse(processedLocations)
}
val route = (go(officeLocation, new mutable.LinkedHashSet()+officeLocation) + homeLocation).toList
(route, routeDistance(route))
}
def routeDistance(route: List[Location]): Int = {
route.sliding(2).map{case List(x, y) => distance(x, y)}.sum
}
def closestLocation(currentLocation: Location, processedLocations: mutable.LinkedHashSet[Location]): Option[Location] = {
deliveryLocations
.filterNot(processedLocations.contains)
.map(loc => (loc, distance(loc, currentLocation)))
.reduceOption((x, y) => if(x._2 < y._2) x else y)
.map(_._1)
}
def distance(location1: Location, location2: Location) = Math.abs(location1.x - location2.x) + Math.abs(location1.y - location2.y)
}
import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.ListMultimap;
import java.util.*;
import java.util.function.BiFunction;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class RemoveDuplicates {
private static final int MEMORY_SIZE = 4;
public static void main(String[] args) {
final List<String> values = Arrays.asList("1", "2", "4", "a", "2", "a", "9", "3", "1", "7", "3");
removeDuplicates(values.stream(), values.size(), hashFunction(), MEMORY_SIZE, 0);
}
private static final int[] primes = new int[] { 1, 2, 3, 5, 7, 11, 13, 17, 19, 23}; // Etc.
public static BiFunction<String, Integer, Integer> hashFunction() {
return (s, prime) -> s.hashCode() % prime;
}
public static <T> void removeDuplicates(final Stream<T> dataset, final int size, BiFunction<T, Integer, Integer> hashFunction, final int memorySize, int iteration) {
if(size > memorySize) { // We can also choose to do an external sort when iteration > MAX_ITERATION and then de-duplicate (but that is slower)
final ListMultimap<Integer, T> map = ArrayListMultimap.create();
dataset.forEach(el -> map.put(hashFunction.apply(el, primes[iteration]), el));
for(Integer key : map.keySet()) {
final Collection<T> value = map.get(key);
System.out.println("List (" + iteration + "): " + value);
removeDuplicates(value.stream(), value.size(), hashFunction, memorySize, iteration + 1);
}
} else {
final Set<T> set = dataset.distinct().collect(Collectors.toSet());
System.out.println(set);
}
}
}
My O(n) solution in Scala:
import scala.annotation.tailrec
object ZeroSumArray {
def findZeroSumPairs(arr: Array[Int], targetSum: Int): List[(Int, Int)] = {
val v = arr.toList.groupBy(x => x)
@tailrec
def go(in: List[Int], targetSum: Int, result: List[(Int, Int)]): List[(Int, Int)] = {
in match {
case Nil => result
case (h::t) if h <= targetSum-h => go(t, targetSum, result)
case (h::t) if h > targetSum-h =>
val pairs = v.getOrElse(targetSum-h, Nil).map(_ => (h, targetSum-h))
go(t, targetSum, pairs ++ result)
}
}
go(arr.toList, targetSum, Nil)
}
def main(args: Array[String]): Unit = {
val arr1 = Array(1, 4, 5, 7, 8, -1, -1, 1, -6, -8, -3)
println(findZeroSumPairs(arr1, 0))
println(findZeroSumPairs(arr1, 8))
println(findZeroSumPairs(arr1, 5))
println(findZeroSumPairs(arr1, 6))
/*
Result:
List((1,-1), (1,-1), (8,-8), (1,-1), (1,-1))
List((7,1), (7,1))
List((8,-3), (4,1), (4,1))
List((7,-1), (7,-1), (5,1), (5,1))
*/
}
}
Here is one that has tail recursion (optimization that avoids stack overflows):
object ZeroSumArray {
def findZeroSumPairs(arr: Array[Int]): List[(Int, Int)] = {
val v = arr.toList.groupBy(x => x)
@tailrec
def go(in: List[Int], result: List[(Int, Int)]): List[(Int, Int)] = {
in match {
case Nil => result
case (h::t) if h < 0 => go(t, result)
case (h::t) if h > 0 =>
val pairs = v.getOrElse(-h, Nil).map(_ => (h, -h))
go(t, pairs ++ result)
}
}
go(arr.toList, Nil)
}
def main(args: Array[String]): Unit = {
val arr1 = Array(1, 4, 5, 7, 8, -1, -1, 1, -6, -8, -3)
println(findZeroSumPairs(arr1))
}
}
My O(n) solution in Scala:
object ZeroSumArray {
def findZeroSumPairs(arr: Array[Int]): List[(Int, Int)] = {
val v = arr.toList.groupBy(x => x)
def go(s: List[Int]): List[(Int, Int)] = {
s match {
case Nil => Nil
case (h::t) if h < 0 => go(t)
case (h::t) if h > 0 =>
val pairs = v.getOrElse(-h, Nil).map(_ => (h, -h))
pairs ++ go(t)
}
}
go(arr.toList)
}
def main(args: Array[String]): Unit = {
val arr1 = Array(1, 4, 5, 7, 8, -1, -1, 1, -6, -8, -3)
println(findZeroSumPairs(arr1))
}
}
import java.util.List;
public DiagonalMatrix(List<List<Integer>> matrix) {
for(int i = 0; i < 2*matrix.size()-1; i++) {
printLine(matrix, i);
}
}
private void printLine(List<List<Integer>> matrix, int i) {
if(i < matrix.size()) {
printDiagonal(matrix, i, 0);
} else {
printDiagonal(matrix, matrix.size()-1, i - matrix.size()+1);
}
}
private void printDiagonal(List<List<Integer>> matrix, int x, int y) {
while(x >= 0 && y < matrix.size()) {
System.out.print(matrix.get(y).get(x) + " ");
x--;
y++;
}
System.out.println();
}
public class Island {
private int[][] fields;
public Island(int size) {
this.fields = new int[size][size];
}
public boolean isInRange(int x, int y) {
return x >= 0 && y >= 0 && x < size() && y < size();
}
public int size() {
return fields.length;
}
}
public class Walk {
private Island island;
Walk(Island island) {
this.island = island;
}
double walk(int x, int y, int numSteps) {
if(numSteps == 0) {
return 1;
}
double sum = 0;
// Go left
if(island.isInRange(x-1, y)) {
sum += walk(x-1, y, numSteps-1);
}
// Go right
if(island.isInRange(x+1, y)) {
sum += walk(x+1, y, numSteps-1);
}
// Go up
if(island.isInRange(x, y+1)) {
sum += walk(x, y+1, numSteps-1);
}
// Go right
if(island.isInRange(x, y-1)) {
sum += walk(x, y-1, numSteps-1);
}
return sum/4;
}
}
public class Walk2DArray {
private Island island;
public Walk2DArray(Island island) {
this.island = island;
}
ProbabilityContainer createArray(int numSteps) {
Walk walk = new Walk(island);
ProbabilityContainer result = new ProbabilityContainer(island.size());
for(int i = 0; i < island.size(); i++) {
for(int j = 0; j < island.size(); j++) {
result.set(i, j, walk.walk(i, j, numSteps));
}
}
return result;
}
}
-----------------------------------
Unit tests:
import static org.junit.Assert.assertEquals;
import org.junit.Test;
public class Walk2DArrayTest {
@Test
public void test1x1_0() {
Island island = new Island(1);
Walk2DArray walk2DArray = new Walk2DArray(island);
ProbabilityContainer probabilityContainer = walk2DArray.createArray(0);
ProbabilityContainer expected = new ProbabilityContainer(new double[][] {
new double[] { 1.0 }
});
assertEquals(expected, probabilityContainer);
}
@Test
public void test1x1_1() {
Island island = new Island(1);
Walk2DArray walk2DArray = new Walk2DArray(island);
ProbabilityContainer probabilityContainer = walk2DArray.createArray(1);
ProbabilityContainer expected = new ProbabilityContainer(new double[][] {
new double[] { 0.0 }
});
assertEquals(expected, probabilityContainer);
}
@Test
public void test2x2_0() {
Island island = new Island(2);
Walk2DArray walk2DArray = new Walk2DArray(island);
ProbabilityContainer probabilityContainer = walk2DArray.createArray(0);
ProbabilityContainer expected = new ProbabilityContainer(new double[][] {
new double[] { 1.0, 1.0},
new double[] { 1.0, 1.0}
});
assertEquals(expected, probabilityContainer);
}
@Test
public void test2x2_1() {
Island island = new Island(2);
Walk2DArray walk2DArray = new Walk2DArray(island);
ProbabilityContainer probabilityContainer = walk2DArray.createArray(1);
ProbabilityContainer expected = new ProbabilityContainer(new double[][] {
new double[] { 0.5, 0.5},
new double[] { 0.5, 0.5}
});
assertEquals(expected, probabilityContainer);
}
@Test
public void test3x3_1() {
Island island = new Island(3);
Walk2DArray walk2DArray = new Walk2DArray(island);
ProbabilityContainer probabilityContainer = walk2DArray.createArray(1);
ProbabilityContainer expected = new ProbabilityContainer(new double[][] {
new double[] { 0.5, 0.75, 0.5},
new double[] { 0.75, 1.0, 0.75},
new double[] { 0.5, 0.75, 0.5}
});
assertEquals(expected, probabilityContainer);
}
@Test
public void test3x3_2() {
Island island = new Island(3);
Walk2DArray walk2DArray = new Walk2DArray(island);
ProbabilityContainer probabilityContainer = walk2DArray.createArray(2);
ProbabilityContainer expected = new ProbabilityContainer(new double[][] {
new double[] { 0.375, 0.5, 0.375},
new double[] { 0.5, 0.75, 0.5},
new double[] { 0.375, 0.5, 0.375}
});
assertEquals(expected, probabilityContainer);
}
}
import static org.junit.Assert.assertEquals;
import org.junit.Test;
public class WalkTest {
private static final double EPSILON = 0.0000001;
@Test
public void test1x1_0() {
Island island = new Island(1);
Walk walk = new Walk(island);
double prob = walk.walk(0, 0, 0);
assertEquals(1.0, prob, EPSILON);
}
@Test
public void test1x1_1() {
Island island = new Island(1);
Walk walk = new Walk(island);
double prob = walk.walk(0, 0, 1);
assertEquals(0.0, prob, EPSILON);
}
@Test
public void test1x1_2() {
Island island = new Island(1);
Walk walk = new Walk(island);
double prob = walk.walk(0, 0, 2);
assertEquals(0.0, prob, EPSILON);
}
@Test
public void test2x2_1() {
Island island = new Island(2);
Walk walk = new Walk(island);
double prob = walk.walk(1, 1, 1);
assertEquals(0.5, prob, EPSILON);
}
@Test
public void test2x2_2() {
Island island = new Island(2);
Walk walk = new Walk(island);
double prob = walk.walk(0, 0, 2);
assertEquals(0.25, prob, EPSILON);
}
@Test
public void test3x3_2() {
Island island = new Island(3);
Walk walk = new Walk(island);
double prob = walk.walk(0, 0, 2);
assertEquals(0.375, prob, EPSILON);
}
@Test
public void test2x2_3() {
Island island = new Island(2);
Walk walk = new Walk(island);
double prob = walk.walk(0, 0, 3);
assertEquals(0.125, prob, EPSILON);
}
}
Or this:
- akmo75 January 28, 2016