9 weeks ago

John 910

Hyderabad

Question 1

You are the mayor of a very old city. The city has n major tourist attractions. You are given the locations (x, y, z) for each of these tourist attractions.

To boost the tourism in your city, you can plan to create new roads that connect the tourist attractions.

To create a bidirectional road between tourist attraction A (located at (x1, y1, z1)) and B (located at (x2, y2, z2)), you need to spend min(|x1 - x2|, |y1 - y2|, |z1 - z2|) dollars. Here |x1 - x2| refers to the absolute value of x1 - x2, and min(x, y, z) refers to the minimum value out of x, y and z.

You need to create a network of roads such that it is possible to travel between any pair of tourist attractions using some sequence of roads. What is the minimum amount of dollars you need to spend in order to accomplish this task?

Sample Input

n = 3

locations = [[1, 5, 7], [2, 9, 4], [1, 3, 9]]

Expected Output

1

Explanation

We can create 2 roads -

Road connecting attraction 1 (at (1, 5, 7)) and attraction 3 (at (1, 3, 9)). The cost of creating this road is min ( | 1 - 1 | , | 5 - 3 | , | 7 - 9 |) = min ( 0 , 2 , 2 ) = 0.

Road connecting attraction 1 (at (1, 5, 7)) and attraction 2 (at (2, 9, 4)). The cost of creating this road is min ( | 1 - 2 | , | 5 - 9 | , | 7 - 4 |) = min ( 1 , 4 , 3 ) = 1.

Creating these two roads enables us to travel between any pair of tourist attractions.

The total cost of creating these roads is 1 dollar.

• [execution time limit] 3 seconds (java)

• [input] integer n

  The number of major tourist attractions in the city

  2 <= n <= 100000

• [input] array.array.integer locations

  A matrix consisting of n rows. Each row has 3 integers = Xi, Yi, Zi - which describe the location of i th attraction.

  All coordinates are integers, and -100000 <= Xi, Yi, Zi <= 100000 for all i.

• [output] integer64

Question 2

Given two non-empty strings str1 and str2, both the strings consist of only lowercase Latin letters. Your task is to calculate the number of different pairs of (a, b) such that a is a substring of str1, b is a subsequence of str2, and the content of a and b are the same.

A string s is called a substring of str, if you can form s from str by removing characters from the start and end of str. Two substrings str[x1...y1] and str[x2...y2] are considered different if x1 != x2 or y1 != y2.

For example - "uber" and "eats" are two different substrings of "ubereats" whereas "ubee" is not a substring.

A string s is called a subsequence of str, if you can form s from str by removing characters at any position of str. Two subsequences p and q are considered different if at least one character present in p has different position in the original string for the corresponding character in q. For example - "ubee" and "ubea" are two different subsequences of "ubereats" whereas "uby" is not a subsequences.

Sample Input

str1 = "aa"

str2 = "aa"

Sample Output

5

Explanation

Following are the valid (a, b) pairs - (str1[1..1] str2[1..1]) (str1[1..1] str2[2..2]) (str1[2..2] str2[1..1]) (str1[2..2] str2[2..2]) (str1[1..2] str2[1..2])

• [execution time limit] 3 seconds (java)

• [input] string str1

  The First Input string consists of lowercase Latin letters [1 <= length(str1) <= 2000]

• [input] string str1

  The Second Input string consists of lowercase Latin letters [1 <= length(str2) <= 2000]

• [output] integer

Question 3

3 months ago

Ayush Gangwani 1.2k

New Delhi

Solution to problem 2

Analysis

The problem can be solved simply by using the following dynamic programming :

Let dp[i][j] denote the number of pairs for substrings ending at index i in str1 by considering the subsequences in the prefix of length j of str2. We can have the following transitions for this dynamic programming:

• dp[i][j] = dp[i][j-1] //We first add the pairs for substrings ending at index i in str1 by considering length j-1 in str2

• if(str1[i] == str2[j]) dp[i][j] += dp[i-1][j-1] + 1 //Now, if the i-th character of str1 matches with the j-th character in str2, we add the number of pairs for substrings ending at index i-1 in str1 by considering a length of j-1 in str2, since for all such pairs we can append the i-th character from str1 and j-th character from str2, thereby making the substring end at index i in str1 and considering the prefix of length j in str2. We also add a 1 for the pair of unit length string due to str1[i] and str2[j].

Using this dynamic programming, we can solve the problem in a time complexity of O(|str1|.|str2|).

Implementation

The problem can be implemented using either memoization or tabulation. The pseudocode below uses memoization to achieve the same

PseudoCode

solve(str1, str2, i, j):
    if(i<0 or j<0):                                               //Base Case
        return 0
    if(dp[i][j] != -1):                                           //If we have already solved for (i,j) we return the dp value
        return dp[i][j]
    dp[i][j] = solve(str1,str2,i,j-1)                             //using the transitions to calculate the dp value as explained
    if(str1[i] == str2[j]):
        dp[i][j] += solve(str1,str2,i-1,j-1) + 1
    return dp[i][j]

2.2 years ago

Dolton Fernandes 30

Solution for Problem 1:

Due to the cost calculation constraint, for a particular node 'a', the edge in the optimal case can be from 'a' to the closest node to the right in sorted order of x, the closest node to the left in sorted order of x. The same idea applies to the y and z dimensions as well. The main crux of this is that if there's an edge between nodes (x1, y1, z1) & (x2, y2, z2) in the optimal answer, then we can break this edge and instead add x edges as follows:

a) (x1, y1, z1) -> (xi, yi, zi)

b) (xi, yi, zi) -> (xj, yj, zj)

.

.

.

x) (xk, yk, zk) -> (x2, y2, z2)

Where either x1, xi, xj, .., xk, x2 or y1, yi, yj, .., yk, y2 or z1, zi, zj, .., zk, z2 are in sorted order. We just add all these possible edges, and then run a minimum spanning tree algorithm to get the optimal graph with the least sum of weights (least cost).

Complexity = O(ElogV) = O(nlogn)