SDE - Intern

A debugging question in which the buggy code and the question was given and we had to change at most 2 lines of code to make the code run properly. The following code runs fine for smaller inputs but not for the larger inputs. Optimize the code without changing the functionality

public int sol(int[] A){

int N = A.length(), result = 0;

for(int i=0;i<N;i++){for(int j=0;j<N;j++){if(A[i] == A[j]) 

result = Math.max(result,Math.abs(i-j));}}

return result;}

don't remember the exact question but the pattern was something like this:

A thief is robbing a store and can carry a maximum weight of ‘W’ into his knapsack. There are 'N' items available in the store and the weight and value of each item is known to the thief. Considering the constraints of the maximum weight that a knapsack can carry, you have to find the maximum profit that a thief can generate by stealing items.

Note: The thief is not allowed to break the items.

For example, N = 4, W = 10 and the weights and values of items are weights = [6, 1, 5, 3] and values = [3, 6, 1, 4]. Then the best way to fill the knapsack is to choose items with weight 6, 1 and 3. The total value of knapsack = 3 + 6 + 4 = 13.

You are given an array ‘arr’ of size ‘N’. Your task is to maximize your score by doing the following operation at most ‘K’ – times.

1. Choose an element from the start or end of the array and the value of the element to your score.
2. Remove the element from the array you have chosen in step – 1.

Note:

Initially, you have a score of zero.

You are given an integer ‘N’. Your task is to find out the ‘N’th Tribonacci Number. ‘N’th number in the Tribonacci sequence is defined as T_n = T _{n - 1} + T_{n - 2} + T_{n - 3}. Where T₀ = 0, T₁ = 1, T₂= 1. Return the answer in mod of 10⁹ + 7.

For Example :

You are given ‘N’ = 5, Here we know 0th, 1st and 2nd Tribonacci numbers are 0, 1 and 1 respectively. Therefore we can calculate the 3rd number as 0 + 1 + 1 = 2 and 4th number as 1 + 1 + 2 = 4 and 5th number as 1 + 2 + 4 = 7. Hence the answer is 7.

Follow Up :

Can you solve it in logarithmic time?

You are given ‘N’ binary tree nodes numbered from 0 to N - 1 where node ‘i’ has two children LEFT_CHILD[i] and RIGHT_CODE[i]. Return ‘True’ if and only if all the given nodes form exactly one valid binary tree. If node ‘i’ has no left child then 'LEFT_CHILD[i]' will equal -1, similarly for the right child.

Example:

Let’s say we have n=4 nodes, 'LEFT_CHILD' = {1, -1, 3, -1} and 
RIGHT_CHILD = {2, -1, -1, -1}. So the resulting tree will look like this:

It will return True as there is only one valid binary tree and each node has only one parent and there is only one root.

Ninja and his friend are playing a game of subarrays. They have an array ‘NUMS’ of length ‘N’. Ninja’s friend gives him an arbitrary integer ‘K’ and asks him to find the length of the longest subarray in which the sum of elements is equal to ‘K’.

Ninjas asks for your help to win this game. Find the length of the longest subarray in which the sum of elements is equal to ‘K’.

If there is no subarray whose sum is ‘K’ then you should return 0.

Example:

Input: ‘N’ = 5,  ‘K’ = 4, ‘NUMS’ = [ 1, 2, 1, 0, 1 ]

Output: 4

There are two subarrays with sum = 4, [1, 2, 1] and [2, 1, 0, 1]. Hence the length of the longest subarray with sum = 4 is 4.