1. Student prep for test
Un student se pregateste de un examen, are de studiat o carte impartita in capitole: pages[i] reprezinta nr. de pagini per capitole. El are la dispozitie un numar maxim de zile de pregatire pana la examen si ar vrea sa citeasca cat mai putin pe zi, daca se poate. De fiecare data cand se termina capitolul, studentul incheie ziua si incepe cu urmatorul capitol in urmatoarea zi. Sa se afle numarul minim de pagini/zi pe care trebuie sa le citeasca pentru a fi gata la timp.
Ex.: pages = [2,3,4,5] si days=5 . Daca citeste 4 pagini/zi, in primele 3 zile citeste 3 capitole, iar al patrulea il face in 2 zile (4+1 pagini). Daca ar citi mai putin, nu s-ar incadra in timp.
package amazon;
import java.util.*;
class StudentExam {
public static int minimumNumberOfPages(List<Integer> pages, int days) {
if (pages.isEmpty()) {
return 0;
}
if (pages.size() > days) {
return -1;
}
int max = 0;
for (int page : pages) {
if (page > max) {
max = page;
}
}
if (pages.size() == days) {
return max;
}
return solve_kiss_approach(pages, days);
}
public static int solve_kiss_approach(List<Integer> pages, int days) {
int totalPages = pages.stream().reduce((a,b) -> a+b).get();
int pagesPerDay = totalPages % days == 0 ? totalPages/days : totalPages/days+1;
while (true) {
int neededDays = 0;
for (int i=0; i<pages.size(); i++) {
neededDays += pages.get(i) % pagesPerDay == 0 ?
pages.get(i) / pagesPerDay :
pages.get(i)/pagesPerDay+1;
}
if (neededDays <= days) {
return pagesPerDay;
}
pagesPerDay++;
}
}
public static void main(String args[]) {
new StudentExam().test();
}
public void test() {
List<TestCase> testCases = new ArrayList<>();
testCases.add(new TestCase (Arrays.asList(2,3,4,5), 5, 4));
testCases.add(new TestCase (Arrays.asList(3,1,5,3,2), 2, -1));
testCases.add(new TestCase (Arrays.asList(3,1,5,3,2), 6, 3));
testCases.add(new TestCase (Arrays.asList(3,1,5,3,2), 8, 3));
testCases.add(new TestCase (Arrays.asList(3,1,5,3,2), 9, 2));
testCases.add(new TestCase (Arrays.asList(7), 2, 4));
testCases.add(new TestCase (Arrays.asList(20,1,30,25,1), 9, 13));
testCases.add(new TestCase (Arrays.asList(30,25,20,1,1), 12, 9));
testCases.add(new TestCase (Arrays.asList(70,4,1,1,1), 12, 9));
testCases.add(new TestCase (Arrays.asList(15,15,16,20,11), 12, 8));
testCases.add(new TestCase (Arrays.asList(2,3,4,5), 100, 1));
for (TestCase testCase : testCases) {
int result = StudentExam.minimumNumberOfPages(testCase.pages, testCase.days);
System.out.println("Test case #" + testCases.indexOf(testCase) + " " +
(result == testCase.expectedResult ?
"PASSED" :
"FAILED with output=" + result + " " +
"[expected=" + testCase.expectedResult + "] \t\t<------"));
}
}
public class TestCase {
public final List<Integer> pages;
public final int days;
public final int expectedResult;
public TestCase(List<Integer> pages, int days, int pagesPerDay) {
this.pages = pages;
this.days = days;
this.expectedResult = pagesPerDay;
}
}
}
2. Market trends of Amazon stocks
Se da un array reprezentand profiturile pe un numar de luni consecutive, initial toate valorile sunt pozitive (castig). Sa se afle numarul maxim de luni ale caror valori pot fi transformate in pierdere (inmultindu-le cu -1), astfel incat profitul cumulat de la luna la luna sa reprezinte totusi castig.
Ex.: PnL = [5,3,1,2], daca il transformam in [5,-3,-1,2] => profitul cumulat este [5, 2, 1, 3] cu toate valorile pozitive => 2 elemente s-au putut negativiza si nu exista o solutie cu 3 elemente negativizate.
package amazon;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class AmazonStocks {
public static int getMaxNegativePnL(List<Integer> PnL) {
int maxCumul = 0;
for (int i=0; i<PnL.size(); i++) {
maxCumul += PnL.get(i);
}
int num = 0;
for (int i=PnL.size()-1; i>=1; i--) {
if (maxCumul - PnL.get(i)*2 > 0) {
maxCumul -= PnL.get(i)*2;
num++;
}
}
return num;
}
public static void main(String args[]) {
new AmazonStocks().test();
}
public void test() {
List<TestCase> testCases = new ArrayList<>();
testCases.add(new TestCase(Arrays.asList(5,3,1,2), 2));
testCases.add(new TestCase(Arrays.asList(1,1,1,1,1), 2));
testCases.add(new TestCase(Arrays.asList(5,2,3,5,2,3), 3));
testCases.add(new TestCase(Arrays.asList(5,10,1,9,5,4), 3));
testCases.add(new TestCase(Arrays.asList(2,3,4,1,1,2), 3));
testCases.add(new TestCase(Arrays.asList(3,2,4,1,1,2), 4));
for (TestCase testCase : testCases) {
int res = AmazonStocks.getMaxNegativePnL(testCase.pnl);
System.out.println("Test case #" + testCases.indexOf(testCase) + " " +
(res == testCase.result ? "PASSED" : "FAILED with output=" + res +
" [expected=" + testCase.result + "] <------"));
}
}
public class TestCase {
public final List<Integer> pnl;
public final int result;
public TestCase(List<Integer> pnl, int result) {
this.pnl = pnl;
this.result = result;
}
}
}
Bonus Demo #1: Optimizing Box Weights
Se da un array de greutati ale unor cutii, se cere impartirea acestor valori in 2 multimi A si B cu urmatoarele conditii:
- A intersectat cu B = vid
- A reunit cu B = arr
- A are numar minim de elemente
- sum(A) > sum(B)
- A trebuie returnat in ordine crescatoare
- daca exista mai multe multimi A, se returneaza cea cu greutate totala maxima
Ex.: arr = [1, 12, 5, 5, 7] => A = [7, 12]
package amazon.demo;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;
class SetProblem {
public static List<Integer> minimalHeaviestSetA(List<Integer> arr) {
arr.sort(Comparator.reverseOrder());
AtomicInteger totalSum = new AtomicInteger(0);
arr.forEach(elem -> totalSum.set(totalSum.get() + elem));
List<Integer> A = new ArrayList<>();
int aSum = 0;
for (int elem : arr) {
A.add(elem);
aSum += elem;
if (aSum > totalSum.get() - aSum) {
A.sort(Comparator.naturalOrder());
return A;
}
}
return new ArrayList<>();
}
public static void main(String[] args) {
new SetProblem().test();
}
public void test() {
List<TestCase> testCases = new ArrayList<>();
testCases.add(new TestCase(Arrays.asList(1,12,5,5,7), Arrays.asList(7, 12)));
testCases.add(new TestCase(Arrays.asList(70,4,1,1,1), Arrays.asList(70)));
testCases.add(new TestCase(Arrays.asList(15,15,16,20,11), Arrays.asList(15,16,20)));
testCases.add(new TestCase(Arrays.asList(2), Arrays.asList(2)));
testCases.add(new TestCase(Arrays.asList(1,10,9), Arrays.asList(9,10)));
testCases.add(new TestCase(Arrays.asList(1,10,12), Arrays.asList(12)));
testCases.add(new TestCase(Arrays.asList(), Arrays.asList()));
testCases.add(new TestCase(Arrays.asList(6,7,3,10,1), Arrays.asList(7,10)));
for (TestCase testCase : testCases) {
List<Integer> result = SetProblem.minimalHeaviestSetA(testCase.arr);
System.out.println("Test case #" + testCases.indexOf(testCase) + " " +
(result.equals(testCase.result) ? "PASSED" : "FAILED with output=" + result +
" [expected=" + testCase.result + "] <------"));
}
}
public class TestCase {
public final List<Integer> arr;
public final List<Integer> result;
public TestCase(List<Integer> arr, List<Integer> result) {
this.arr = arr;
this.result = result;
}
}
}
Bonus Demo #2: Items in containers
Se da un string compus din caracterele '*' pentru un obiect si '|' pentru delimitarea unui compartiment. Se cere sa se afle toate obiectele aflate intre pozitiile start si stop din acel string, cu conditia ca obiectul sa apartina unui compartiment inchis (intre doua caractere '|').
Ex.: "|*|**|*|" , start = 1, stop = 5 => se afla 2 obiecte (numerotarea incepe de la 0, start/stop sunt inclusive)
package amazon.demo;
import java.util.*;
public class Containers {
private Map<Integer, Integer> buildMap(String input) {
Map<Integer, Integer> countMap = new TreeMap<>(); // the keys are sorted asc
int count = 0;
int indexStart = -1;
for (int i=0; i<input.length(); i++) {
if (input.charAt(i) == '|') {
if (indexStart >= 0) {
countMap.put(indexStart, count);
}
indexStart = i;
count = 0;
} else if (input.charAt(i) == '*') {
count++;
}
}
return countMap;
// key: indexFrom, value: number of items
}
private int find(int from, int to, Map<Integer, Integer> map) {
if (to - from < 2) {
return 0;
}
int count = 0;
boolean started = false;
for (int key : map.keySet()) {
if (!started && key >= from && to >= key + map.get(key) + 1) {
count += map.get(key);
started = true;
} else if (started && to >= key + map.get(key) + 1) {
count += map.get(key);
}
}
return count;
}
public static void main(String[] args) {
new Containers().test();
}
public void test() {
List<TestCase> testCases = new ArrayList<>();
testCases.add(new TestCase("|*|**|*|", new int[]{0, 0, 1, 2, 5, 7, 15},
new int[]{2, 1, 4, 7, 7, 7, 17}, new int[]{1, 0, 0, 3, 1, 0, 0}));
testCases.add(new TestCase("|**|*|*", new int[]{0, 0, 1},
new int[]{4,5,6}, new int[]{2,3,1}));
testCases.add(new TestCase("*|*|*|||**|", new int[]{0,0,0,1,5,5, 0},
new int[]{1,2,3,5,9,10,10}, new int[]{0, 0, 1, 2, 0, 2, 4}));
Containers containers = new Containers();
for (TestCase testCase : testCases) {
Map<Integer, Integer> occurrenceMap = containers.buildMap(testCase.input);
for (int i=0; i<testCase.start.length; i++) {
int res = containers.find(testCase.start[i], testCase.stop[i], occurrenceMap);
System.out.println("Test case #" + testCases.indexOf(testCase) + " " +
(res == testCase.result[i] ? "PASSED" : "FAILED with output=" + res +
" [expected=" + testCase.result[i] + "] <------"));
}
}
}
public class TestCase {
public final String input;
public final int[] start;
public final int[] stop;
public final int[] result;
public TestCase(String input, int[] start, int[] stop, int[] expectedResult) {
this.input = input;
this.start = start;
this.stop = stop;
this.result = expectedResult;
}
}
}
Niciun comentariu:
Trimiteți un comentariu