Data Structures, Algorithms and Coding Round For Data Scientist at Agoda (26 Sep 2023)

Note: problems are ordered in increasing order of complexity.

Problem 1
Problem Description:

You are standing on a unique diamond-shaped platform composed of 5 tiles. These tiles are positioned at coordinates: (-1,0), (0,-1), (0,0), (0,1), and (1,0).

From a starting position (xs,ys), you make random moves in one of four directions: left (decrease x by 1), right (increase x by 1), up (increase y by 1), or down (decrease y by 1). Each direction has the same probability and the direction of each move is entirely independent of previous moves.

Determine the probability that you can reach a given destination (xe,ye) without stepping off the diamond platform.

Constraints:

(xs, ys) must be one of: (-1,0), (0,-1), (0,0), (0,1), (1,0)
(xe, ye) must also be one of the above coordinates.
Starting and ending coordinates are distinct: xs != xe or ys != ye

Input:

A single line containing four integers, denoting xs, ys, xe, ye respectively.

Output:

A single line showing the probability that you'll reach the destination before stepping off the platform.

Sample input:

-1 0 0 0

Sample Output:

0.25

Explanation:

From the starting position, you have a 25% chance of moving right (and thus reaching the destination). Any other move would result in falling off the platform.

    [execution time limit] 4 seconds (py3)

    [memory limit] 1 GB

    [input] integer xs

    The x-coordinate of the starting position.

    [input] integer ys

    The y-coordinate of the starting position.

    [input] integer xe

    The x-coordinate of the end position.

    [input] integer ye

    The y-coordinate of the end position.

    [output] float

    Probability to reach end position before falling of platform.


Problem 2

There are two operators:

    operator1: adds x to current number
    operator2: multiplies current number by y

where the values of x an y are given and fixed. The starting number is 1 and the goal is to get to number t by sequentially applying operator1 and operator2. You have to maximize the number of times you use operator2. For maximum usage of operator 2, you have to minimize the number of times you use operator 1.

Constraints:
2 <= x <= 1000
2 <= y <= 1000
1 <= t <= 10^20

Input: t, x, y

Output in case there is a solution:
List of strings where:

    Element 1: "operator_add" or "operator_multiply" followed by how many times you want to apply it.
    Element 2: "operator_add" or "operator_multiply" followed by how many times you want to apply it to result of previous line.
    ...

The solution should be returned in a compact format in the sense that if element i corresponds to operator_add, then element i+1 corresponds to operator_multiply and vice versa.

Output in case there is no solution:
List with one element: "no_solution".

Sample input:
t = 54
x = 1
y = 3

Sample output:
["operator_add 1", "operator_multiply 3"]

Explanation: ((1 + 1) times 3^3) = 54
Operator2 can be used maximally 3 times because 3^4 > 54. For operator2 being used three times, operator1 needs to be used at least once because 3^3 is not equal to 54.

Sample input:
t = 3
x = 4
y = 4

Sample output:
["no_solution"]

Explanation: every operator increase the number and applying any operator once already results in a number that is too big.

    [execution time limit] 4 seconds (py3)

    [memory limit] 1 GB

    [input] integer64 t

    Target number: the number you want to reach by sequentially applying the operators.

    [input] integer64 x

    By how much you increase the current result if you apply operator1.

    [input] integer64 y

    By how much you multiply the current result if you apply operator2.

    [output] array.string

    List of strings where element i equals "operator_add" or "operator_multiply" followed by how many times you want to apply it. In case there is no solution, output is ["no_solution"].


Problem 3

You want to buy a billboard featuring the name of your company. The price of the billboard is the sum of the price of the letters in your company name. For example, the price of company name "aga" is two times the price of letter "a" plus the price of letter "g". You don't know the price per letter, but you do know the prices of other company names. Can you derive the price of your company name? A company name only contains letters from the alphabet. There are 26 different letters and they are all lower case.

You are given:

    your_company_name: a string representing the name of your company
    other_company_names: a list of strings where each element is the name of another company
    other_company_prices: a list of real numbers where other_company_prices[i] is the price of other_company_names[i]

Return the price of your company name if it can be derived, otherwise return -1

Constraints:
The length of a company name is maximally 100
len(other_company_names) = len(other_company_prices) <= 100
For each price in other_company_prices: -10^6 <= price <= 10^6

Sample Input:
your_company_name = "aabc"
other_company_names = ["ab", "ac", "bd"]
other_company_prices = [99.5, 1000.2, 2000.8]

Sample Output:
1099.7

Explanation: The letters in "aabc" is the union of the letters in "ab" and "ac", hence the price is the sum.

Sample Input:
your_company_name = "d"
other_company_names = ["aab", "acc"]
other_company_prices = [500, 6000]

Sample Output:
-1

Explanation: The letter d doesn't appear in any other company name and therefore we cannot derive its price.

    [execution time limit] 4 seconds (py3)

    [memory limit] 1 GB

    [input] string your_company_name

    String representing the name of your company

    [input] array.string other_company_names

    List containing the names of other companies.

    [input] array.float other_company_prices

    List where element i contains the prices of other_company_names[i]

    [output] float

    Price of your company

Tags: Technology,Algorithms,Interview Preparation,