-1
\$\begingroup\$

Problem description: Write a method that takes in 2 parameters:

A string containing either "A" or "B" indicating the recipient of a bank transfer. An integer array containing the amount for each of those transfers. So for instance, if the String is BA and the array is [1,2], it means A transfers 1 to B, then B transfers 2 to A. This method should return what the initial balance for each bank account A and B need to be so that they never go into negative balance. In the example above, it should return [1, 1].

Initial balance [1, 1].
A transfers 1 to B [0, 2].
B transfers 2 to A [2, 0].
Final balance [2, 0].

Important points: The input String and the input Array will always have the same length. The input String will only contain "A" and/or "B". I can't remember if the numbers on the array had to be positive, though I have not tested for negative numbers, so that might be a reason for the failure.

Other test scenarios: "BAABA" - [2,4,1,1,2] - answer should be [2,4].

Initial Balance [2, 4].
A transfers 2 to B [0, 6].
B transfers 4 to A [4, 2].
B transfers 1 to A [5, 1].
A transfers 1 to B [4, 2].
B transfers 2 to A [6, 0].

"ABAB" - [10, 5, 10, 15] answer should be [0, 15].

Solution can be as follows:

public static int[] solution1(String R, int[] A) {
        int aBal = 0;
        int bBal = 0;
        int aInteraction = R.lastIndexOf('A');
        int bInteraction = R.lastIndexOf('B');
        for(int i = 0; i <= bInteraction; i++) {
            if(R.charAt(i) == 'A')
                aBal += A[i];
            else
                aBal -= A[i];                
        }
        for(int j = 0; j <= aInteraction; j++) {
            if(R.charAt(j) == 'A')
                bBal -= A[j];                
            else
                bBal += A[j];
        }
        int[] bal = {aBal > 0 ? aBal : aBal * -1, bBal > 0 ? bBal : bBal * -1};
        return bal;
    }
\$\endgroup\$
5
  • 1
    \$\begingroup\$ No, the solution1 function does not correctly answer the question. The problem statement had a pretty clear existential quantifier in it: "so that they never go into negative balance". The solution1 function only examines the final timestep, without considering interior steps. Take any "small value" BABA sequence such as [2, 2, 2, 2], with answer [2, 0]. Now insert a pair of "large" k values in the middle, such as BABABA [2, 2, k, k, 2, 2], where k is a hundred or a billion or whatever. We'll need a new answer! \$\endgroup\$
    – J_H
    Dec 21, 2023 at 23:41
  • \$\begingroup\$ Use the Java Signed Integer range, and any k value would work. \$\endgroup\$
    – Dirtygears
    Dec 22, 2023 at 13:57
  • \$\begingroup\$ To be exact, <2^31=2147483648. Cheers!! \$\endgroup\$
    – Dirtygears
    Dec 22, 2023 at 14:00
  • \$\begingroup\$ Right, so this doesn't work, and @J_H is correct. Have you tried running his proposed test case? Perhaps you should focus on correctness before profiling. Anyway, non-functional code is off-topic, so I'm voting to close. \$\endgroup\$
    – Reinderien
    Dec 30, 2023 at 3:48
  • \$\begingroup\$ @Reinderien, does your code work for range above Java int range? clearly not. So your code fails on the correctness even on this test, apart from being a non functional and costly one. So should be clearly down voted. As for J_H, is there anywhere in the question it is suggested that transactions are a subset of all natural number range? No. It clearly says integer in question though. For Java integer range it works. \$\endgroup\$
    – Dirtygears
    Dec 30, 2023 at 17:33

1 Answer 1

2
\$\begingroup\$

I don't see why you would want to do traversal of R (which should get a better name) to find indices of A and B. I think you need the entire sequence to calculate anything meaningful from the transaction ledger.

Don't * -1; just -aBal negate variables with a unary operator.

Write tests. I demonstrate poor-man's tests with assert.

Your solution isn't object-oriented, which means it isn't particularly Java-idiomatic. I would consider it to be Java-idiomatic if you parsed out the account codes to transaction records and then operated on them in a stream. Unfortunately, streams have poor support for cumulative operations, so if you go the stream route, expect to require at least two O(n) passes (or write a custom accumulator). Since you haven't provided any idea as to the input size, this might be fine.

The following approach passes all of your test cases, and uses a single cumulative sum and a built-in summary accumulation:

package com.stackexchange;

import java.util.Arrays;
import java.util.IntSummaryStatistics;
import java.util.stream.IntStream;

public class Main {
    public record Transaction(
        char dest, int amount
    ) {
        int amountTo(char relativeDest) {
            if (relativeDest == dest)
                return amount;
            return -amount;
        }
    }

    public static class Ledger {
        private final IntSummaryStatistics summary;

        public Ledger(String dests, int[] amounts) {
            int[] ledgerA = IntStream
                .range(0, amounts.length)
                .mapToObj(i -> new Transaction(dests.charAt(i), amounts[i]))
                .mapToInt(t -> t.amountTo('A'))
                .toArray();

            // Cumulative sum
            Arrays.parallelPrefix(ledgerA, Integer::sum);

            summary = Arrays.stream(ledgerA).summaryStatistics();
        }

        public int getInitA() {
            return -summary.getMin();
        }

        public int getInitB() {
            return summary.getMax();
        }
    }

    public static void main(String[] args) {
        // Pass -ea to enable assertions
        
        Ledger l = new Ledger("BA", new int[] {1, 2});
        assert l.getInitA() == 1;
        assert l.getInitB() == 1;

        l = new Ledger("BAABA", new int[] {2, 4, 1, 1, 2});
        assert l.getInitA() == 2;
        assert l.getInitB() == 4;

        l = new Ledger("ABAB", new int[] {10, 5, 10, 15});
        assert l.getInitA() == 0;
        assert l.getInitB() == 15;
    }
}
\$\endgroup\$
7
  • \$\begingroup\$ Your code is not only not java-idiomatic, but has incorrect Java syntax throughout. Second, its a competition question and not expected to be written in OO. Third, and important of all, even if we consider only the Ledger() constructor logic, the streams are way too bulky compared to simple for loops, and you have stream mapped twice. The solution was expected to have the least time complexity, and your solution (not sure whether it works) would fail royally on time complexity vs mine. \$\endgroup\$
    – Dirtygears
    Dec 29, 2023 at 15:16
  • \$\begingroup\$ Benchmarking for my solution for 1000 transactions between A and B is this:# Fork: 1 of 1 # Warmup Iteration 1: 32.476 ns/op # Warmup Iteration 2: 33.714 ns/op # Warmup Iteration 3: 26.377 ns/op # Warmup Iteration 4: 26.316 ns/op # Warmup Iteration 5: 26.409 ns/op Iteration 1: 26.243 ns/op Result "com.aquassemi.testproblem.TestproblemApplication.solution1": 26.243 ns/op \$\endgroup\$
    – Dirtygears
    Dec 29, 2023 at 15:18
  • \$\begingroup\$ Benchmark for 10000 transactions:# Fork: 1 of 1 # Warmup Iteration 1: 79.760 ns/op # Warmup Iteration 2: 59.822 ns/op # Warmup Iteration 3: 67.743 ns/op # Warmup Iteration 4: 67.843 ns/op # Warmup Iteration 5: 68.081 ns/op Iteration 1: 68.582 ns/op Result "com.aquassemi.testproblem.TestproblemApplication.solution1": 68.582 ns/op \$\endgroup\$
    – Dirtygears
    Dec 29, 2023 at 15:42
  • \$\begingroup\$ I can't tell whether you're joking. I've definitely compiled and run this. Could you give me a hint on what you think is incorrect syntax? \$\endgroup\$
    – Reinderien
    Dec 29, 2023 at 15:44
  • \$\begingroup\$ Move your benchmarks from comments on this answer to content in the question body. \$\endgroup\$
    – Reinderien
    Dec 29, 2023 at 15:45

Not the answer you're looking for? Browse other questions tagged or ask your own question.