Maven Securities OA

[ttd]

Subarray Sum Equals Zero

Write a function solution that, given an array A consisting of N integers, returns the number of fragments of A whose sum equals 0 (that is, pairs (P, Q) such that P ≤ Q and the sum A[P] + A[P+1] + ... + A[Q] is 0 ). The function should return -1 if this number exceeds 1,000,000,000 .

Examples:

1. Given A = [2, -2, 3, 0, 4, -7] , the function should return 4 , as explained on this picture:
   
2. Given A = [0, 0, ..., 0] of length 100,000 , the function should return -1 .

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000] ;
• each element of array A is an integer within the range [-10,000..10,000] .

Use either Java or Python, time given 1 hour 5 min. Sample code stub:

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
    }
}

Min Time to Merge Lists

Merging a sorted list consisting of K elements with a sorted list consisting of L elements takes ( K+L ) milliseconds (ms). The time required to merge more than two lists into one final list depends on the order in which the merges are performed.

For example, consider the following three lists:

• list P consisting of 100 elements,
• list Q consisting of 250 elements,
• list R consisting of 1000 elements.

They can be merged into one final sorted list in three different ways:

1. first merge P with Q , then merge the result with R ; or
2. first merge P with R , then merge the result with Q ; or
3. first merge R with Q , then merge the result with P .

The times needed to perform the above merges are respectively:

• merge P with Q : 350ms; result with R : 1350ms; total: 1700ms;
• merge P with R : 1100ms; result with Q : 1350ms; total: 2450ms;
• merge Q with R : 1250ms; result with P : 1350ms; total: 2600ms.

The first schema is the fastest (1700ms).

If there are more than three lists to merge, there are even more merge strategies to consider. When the number of lists to merge is fewer than two, no merges are performed and the total merge time is assumed to be 0.

Write a function:

def solution(A)

that, given an array A of length N describing the lengths of N lists, returns the shortest time (measured in milliseconds) required to merge these lists into one.

For example, given array A consisting of three elements such that:

• A[0] = 100
• A[1] = 250
• A[2] = 1000
  the function should return 1700, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..10,000] ;
• each element of array A is an integer within the range [1..1,000] .

Use either Java or Python, time given 1 hour 5 min.

Game of Battleships

John plays a game of battleships with his friend Sonia. The game is played on a square map of N rows, numbered from 1 to N . Each row contains N cells, labeled with consecutive English upper-case letters (A, B, C, etc.). Each cell is identified by a string composed of its row number followed by its column number: for example, 9C denotes the third cell in the 9th row, and 15D denotes the fourth cell in the 15th row.

John marks the positions of all his ships on the map (which is not shown to Sonia). Ships are defined by rectangles with a maximum area of 4 cells. Sonia picks map cells to hit some ships. A ship is considered to be hit if at least one of its constituent cells is hit. If all of a ship’s cells are hit, the ship is sunk.

The goal is to count the number of sunk ships and the number of ships that have been hit but not sunk.

For example, the picture below shows a map of size N = 4 with two blue ships and five hits marked with the letter X :

In this example, one ship has been sunk and the other has been hit but not sunk. In the next picture, the sunken ship is shown in grey and the ship that has been hit but not yet sunk appears in red:

The positions of ships are given as a string S , containing pairs of positions describing respectively the top-left and bottom-right corner cells of each ship. Ships’ descriptions are separated with commas. The positions of hits are given as a string T , containing positions describing the map cells that were hit: for the map in the example shown above, S = "1B 2C,2D 4D" and T= "2B 2D 3D 4D 4A" . Ships in S and hits in T may appear in any order.

Write a function:

def solution(N, S, T)

that, given the size of the map N and two strings S , T that describe the positions of ships and hits respectively, returns a string with two numbers: the count of sunken ships and the count of ships that have been hit but not sunk, separated with a comma.

For instance, given N = 4 , S = "1B 2C,2D 4D" and T = "2B 2D 3D 4D 4A" , your function should return "1,1" , as explained above.

Given N = 3 , S = "1A 1B,2C 2C" and T = "1B" , your function should return "0,1" , because one ship was hit but not sunk.

Given N = 12 , S = "1A 2A,12A 12A" and T = "12A" , your function should return "1,0" , because one ship was hit and sunk.

Assume that:

• N is an integer within the range [1..26] ;
• string S contains the descriptions of rectangular ships of area not greater than 4 cells;
• there can be at most one ship located on any map cell (ships do not overlap);
• each map cell can appear in string T at most once;
• string S and string T contain only valid positions given in specified format.

In your solution, focus on correctness . The performance of your solution will not be the focus of the assessment.

Use either Java or Python, time given 1 hour 5 min.