(Interviu angajare) Problema Java la despre un Array ce contine un sir de numere si returneaza un sir cu suma a n elemente alese

Limbaje de Programare Java
, , , ,
1

Salut
Am si eu o problema de rezolvat si nu reusesc sa ajung ii dau de cap. Problema am primit-o in cadrul unui interviu de angajare ca proba tehnica. Nu am reusit sa o rezolv atunci pe loc, dar totusi as vrea sa aflu rezolvarea.

Cerinta:

Ți se dă un Array ce contine un șir de numere întregi, nu conteaza ordinea numerelor, deci pot fi random. Trebuie creezi o metoda ce returneza un Array cu suma a N elemente cate N. imi pare rau daca explicatia este vaga.

Date de intrare:
int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8};

Date iesire:
int[] result = {3, 5, 7, 9, 11, 13, 15}; // pentru suma a 2 cate 2 numere

int[] result = {6, 9, 12, 15, 18, 21}; // pentru suma a 3 cate 3 numere

int[] result = {10, 14, 18, 22, 26}; // pentru suma a 4 cate 4 numere

Iar aici este incercarea de rezolvare a mea:

public static void main(String[] args)  {
    int[] input = {1, 2, 3, 4, 5, 6, 7, 8};         // size = 8   

    int[] output1 = sumOfNumbers_v1(input, 2);
    int[] output2 = sumOfNumbers_v2(input, 3);

    Arrays.stream(output1).forEach(x -> System.out.println(x));
    Arrays.stream(output2).forEach(x -> System.out.println(x));
}
   
public static int[] sumOfNumbers_v1(int[] initial, int count) {
    int[] finalArray = new int[(initial.length + 1) - count];
    for(int i = 0; i < initialArray.length; i++) {
        int sum = 0;
        int k = i;

        for(int j = 0; j < count; j++){
            sum += initialArray[k];
            k++;
        }
        System.out.println(sum);
        finalArray[i] = sum;
    }
    return finalArray;
}

public static int[] sumOfNumbers_v2(int[] initial, int count) {
    int[] finalArray = new int[(initial.length + 1) - count];
    for(int i = 0; i < initial.length; i++) {
        int sum = 0;

        for(int j = i; j < count + i; j++){
            sum += initial[j];
        }
        System.out.println(sum);
        finalArray[i] = sum;
    }
    return finalArray;
}

Ambele metode au un flaw, si anume ca arunca o exceptia: java.lang.ArrayIndexOutOfBoundsException: Index 8 out of bounds for length 8

Daca ma puteti ajuta cu cateva sfaturi, as aprecia maxim.

2

Calculezi exact pana unde sa iterezi i, nu pana la finalul sirului.

Apoi, daca as vrea sa arat ca stiu folosi streams, as implementa solutia pe baza lor, nu acel forEach ce face codul mai complicat decat o bucla for fara nici un beneficiu.

3

Am reusit sa returnez corect. Am incercat sa urmez sfatul tau, dar o solutie mai eleganta fata de asta, nu am gasit.

public static int[] sumOfNumbers(int[] initial, int count) {
        int[] finalArray = new int[(initial.length + 1) - count];

        for(int i = 0; i < initial.length; i++) {
            int sum = 0;

            for(int j = i; j < count + i; j++){
                if(j >= initial.length) {
                    break;
                }
                sum += initial[j];
            }
            if(i < (initial.length + 1) - count) {
                finalArray[i] = sum;
            }
        }
        return finalArray;
    }
4

Vezi ce metode iti ofera stream pentru a lua primele 5 elemente. Dar 5 elemente incepand cu pozitia 3?

5

Nu cred ca ai inteles cerinta, eu la metoda sumOfNumbers() ii furnizez array-ul, si count ce reprezintacate numere consecutive sa adune din sir. Pot sa ii dau, 2 cate 2, 3 cate 3, 6 cate 6, nu conteaza, doar sa fie count-ul ca valoare mai mic decat marimea array-ului primit.

Deci daca ii dau count = 5, o sa returneze un array ce contine:
{15, 20, 25, 30}

1+2+3+4+5 = 15
2+3+4+5+6 = 20
3+4+5+6+7 = 25
4+5+6+7+8 = 30

1 Like
6

Da. Poti calcula acel array cum ai facut-o, in modul traditional sau poti sa-l calculezi folosind streams intr-un singur rand.

1 Like
7

Idea mea :slight_smile:

	public void devforumProblem() {
		var input = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8);
		int windowSize = 3;
		IntStream.range(0, input.size() - windowSize + 1)
				.mapToObj(start -> input.subList(start, start + windowSize))
				.map(elem -> elem.stream().reduce(0, Integer::sum))
				.forEach(System.out::println);
	}

Am facut un sliding window peste elemente (pana la mapToObj) si cu al doilea map am adunat elementele din ceea ce a rezultat in urma aplicarii ferestrei.

4 Likes
8

Sliding window e solutia, dar cu inner loopu ala ai dat o palma la cacat:) Adica tot ai complexitate quadratica in loc de lineara.

  1. Calculeaza sum pentru window
  2. Initializeaza doua pointere pentru left-right
  3. while right < len(nums):
    left += 1
    right += 1
    sum -= nums[left-1]
    sum += nums[right]
    append new res.
3 Likes
9

image
image1042×1217 27.4 KB

1 Like
10

:cough: Scala :cough:

Spoiler

println(Array(1, 2, 3, 4, 5, 6, 7, 8).sliding(4).map(_.sum).mkString(", "))
10, 14, 18, 22, 26

1 Like
11

Multumesc tuturor pentru solutii. Uitati si adaptarea la Java pentru viitori cititori.

public static int[] sumOfSubSet(int[] initial, int subSetSize) {
        int[] finalArray = new int[(initial.length + 1) - subSetSize];

        int sum = 0;
        int counter = 0;
        for(int i = 0; i < initial.length; i++) {
            sum += initial[i];
            counter++;

            if(counter == subSetSize ) {
                finalArray[i+1-counter] = sum;
                sum = 0;
                counter = 0;
                i = i - (subSetSize - 1);
            }
        }

        return finalArray;
}
1 Like
12

Poti oferii un code snippet in Java cu indicatiile mentionate? Nu imi e clar conceptul de sliding window

13

Daca ai deja suma elementelor 0 + 1 + 2 + 3 + 4 e usor sa calculezi suma 1 + 2 + 3 + 4 + 5 fara sa aduni toate 5 valorile

14

manevra e sa sugerezi aia ca improvement si o faci ca varianta finala