timotheehub

TransferWise Coding Challenge #1

Editorial of the first question: TransferWise Invite Program Winner

The questions are still open and you can try them here.

The question was about finding the person who invited the largest number of users through TransferWise's invite program. This question can be generalized to finding the largest tree in an acyclic unidirectional disconnected graph. If you don't remember it, you can also find it below.

There are multiple ways to solve the first question including:

1. Finding the root nodes of the trees by finding the nodes without parents

timotheehub

TransferWise Coding Challenge #1

Editorial of the second question: TransferWise Worldwide Relay

The questions are still open and you can try them here.

The second question was harder and was about finding the fastest way to do a relay with cyclists having different abilities and starting from different locations. This can be generalized to finding the fastest way to go from one node to another in an acyclic unidirectional graph described with distances and speeds. In each node, there is a cyclist with a speed and a maximum distance. Each edge is associated with a distance. At each node, we have the choice between keeping the current cyclist (current speed and remaining distance) or switching to the one available at this node (new speed and distance). What makes this problem harder is having two dimensions: distance and time. If you don’t remember the question, you can also find it below.

There are multiple ways of solving the second question including:

1. Using a modified

timotheehub

TransferWise Coding Contest #2

Editorial of the second question: TransferWise Transfer Single Linking

The questions are still open and you can try them here.

The question was about linking one transfer request with a list of payments. This question can be generalized to the Subset Sum Problem with strictly positive integers and the guarantee that there is at most one solution. If you don't remember the question, you can also find it below.

There are multiple ways to solve the second question including:

1. Recursive way. The idea is that for each payment, there are two possibilities: either the payment is part of the solution or it’s not. We can then solve the problem in a recursive way by trying both possibilities. This solution is less efficient but depending on how you optimize it, you can pass all the test cases.

timotheehub

TransferWise Coding Contest #3

Editorial of the second question: TransferWise Fika

The questions are still open and you can try them here.

The question was about dividing an array into K + 1 segments such that the minimum segment is maximized. The minimum segment is the segment that has the smallest sum of elements. If you don't remember the question, you can find it below.

There was also a restriction on where the array can be cut because of the caramels. To make the algorithm easier to write, we can first rewrite the array so that chunks of chocolates with caramels are grouped together. The solution will be equivalent.

Once we got rid of the caramels, there are multiple ways to solve this problem: