In-feeds

Total views

Codenation CodeAgon 2021

 CodeAgon 2021 Codenation



About CodeAgon

Trilogy Innovations ( formerly known as CodeNation Innovation Labs)  is conducting a nationwide Coding Challenge, CodeAgon! You'll be solving about 6 challenges focused around Algorithms and Data Structures with the contest duration spanning 4 hours. 

You get a chance to win prizes worth over 2 lakhs and a chance to interview with TI for the position of Software Development Engineer for 2022 graduating students and Summer Internship for 2023 graduating students.

Eligibility for CodeAgon

This CodeSprint is open to all for participation. To be eligible for prizes and job opportunities at TI, users must reside in India and be a fresher (Graduating in 2022/2023) pursuing BTech, BE, MTech, ME, MCA, MS, Dual Degree- MTech+BTech, PHD.

Earning these prizes isn't going to be easy. You'll first have to take up the CodeAgon challenge and face off against thousands of other developers who are taking up this challenge!

Date of Event

Duration: 4 hours
Starts on: 03 Oct 2021 7:00 PM IST 

Job Profile : SDE/ SDE Intern
Location : Remote/ Bangalore
CTC: INR 36.5 Lakh per annum

Test Instructions


Questions

1) Golden String

Problem Description

You are given a string A containing english lowercase alphabets. You need to find if A contains a Golden string as a substring of itself.
A string S of length N is Golden if:
1. N is atleast 3
2. S is only composed of 2 letters. Let's call them p and q.
3. Count of p in the string must be greater than N/3 and the other letters must all be q.
If the string A has a golden substring, return 1, else return 0.

Problem Constraints

  • 1<= |A| <= 10^5

Input Format

        The first argument is the string A.

Output Format

        Return a single integer as state above.

Example Input

    Input 1:
        A  =  'abbad

    Input 2:
        A =  'abcd'

Example Output

    Output 1:
        1

    Output 2:
        0

Example Explanation

Explanation 1:
The substring 'abba' has two a's and two b's with total length 4. Since, 2 is greater than 4/3 - 1.33, it is a valid golden string. Note that there are more possible golden substrings in this string.

Explanation 2:
No golden string is present.

2) DP Integers

Problem Description

You are given two non negative integers A and B, you have to make both of them equal to 0. You can perform the following types of operations:
  • Replace both A and B with the floor (greatest integer function) of the square root of their product

    The cost of this operation is 2.
  • Divide either A or B by 2. 

    The cost of this operation is 1.
You can do any operation any number of times.
Output the minimum cost to make both A and B equal to 0.

Problem Constraints

  • 0 <=A, B = 10^9

Input Format

  •     First argument is the integer A.
  •     Second argument is the integer B.
Output Format
  • Return a single integer which denotes the minimum integer cost.

Example Input

Input 1:
    A 2
    B 2

Input 2:
    1

Example Output

Output 1:
    4

Output 2:    
    1

Example Explanation

Explanation 1:
    You have to apply 4 operations to make them 0:
    Apply 2nd operation on each integer 2 times.

Explanation 2:
    Apply 2nd operation on 2nd integer to become

3) Swap It Harder

Problem Description

You are given an array of integers A of size N with elements ranging from 0 to9. All elements were distributed to different groups and then array was reformed from these groups with the following rules:

    1. Elements don't repeat in a group.
    2. The number of groups is minimal, that is, no other way of distribution exists that can reduce the             number of groups even further.

After the formation of these groups, they were merged in such a way that forms the lexicographically largest array.
Find the minimum number of neighbouring swaps needed to form this final array
from the initial array A
Since the answer can be large, output it modulo 10+7.
Please note that the groups need not be contiguous.

Once the groups are formed, you are free to arrange the elements of the group as
per your wish to achieve the lexicographically largest array.

Problem Constraints

  • 1= N <= 10^5
  • 0<= A[i] <= 9

Input Format

    The first argument is the integer array A.

Output Format

    Return a single integer as per the given problem.


Example Input

Input 1:    
    A  = [9, 1, 9]

Input 2:
    A =  [4, 0, 6, 0, 1, 9, 8, 0, 4]

Example Output

Output 1:    
    1

Output 2:    
    16

Example Explanation

Explanation 1:
Groups that can be formed are: [9, 1] and [9]. To get the lexicographical1 y largest array from these two groups, merge them like [9] [9, 1] to get [9, 9, 1]. Thus, we need only 1 Swap(1 with 9) to get the final array. Please note that after forming the groups, the numbers inside can be be re arranged as needed. So, the first group has exactly two forms [1, 9] and [9, 1].

Explanation 2:

It can be shown that the minimum swaps needed are equal to 16.

4) TWO Summations

Problem Description

You are given two integer arrays A and B of length N.

You have to find the value of two summation:





Problem Constraints

  • 1 <= N <= 10^5
  • 1 <= A[i] , B[i] <= 10^5

Input Format

  • First argument is the integer array A.
  • Second argument is the integer array B.

Output Format

        Return the value of Z modulo 10+7.

Example Input

Input 1:
    A  = [1, 2]
    B  = [2, 3]

Input 2:    
    A  = [1]
    B  = [1]

Example Output

Output 1:
    16

Output 2:
    2

Example Explanation

Explanation 1:
    Z  = max(3, 3) + max(4, 4)+ max(4, 4) + max (5, 5) = 16

Explanation 2:

    Z = max(2, 2) = 2

Space Race 2025

Problem Description

The year is 2025. The space race is in full motion. Elon Musk and Jeff Bezos have already launched their rockets into space. Bill Gates on the other hand, is struggling to even get started. However, his good friend Elon, offers him his secret rocket fuel formula if Gates is able to solve a particular problem. There are A planets. Jeff's space company is not very good so he can only jump from the ith planet to the (i+1)th planet and (i+2)th planet. Let XJ be the array of integers representing the number of ways to get to the ith planet if Jeff starts from the 1st planet. XJ[0] would be 1. Since the values can be very large, consider them all modulo 1e9+7. 
Elon's space company is quite advanced compared to Jeff's. So from the ith planet, Elon's rocket can jump to all planets such that:
  • For every set bit in XJ[i]'s binary representation, Elon's rocket when at the ith planet can jump ahead by values in the range [2^bit, 2^(bit+1)].

  • Let XJ[i] be 5. It's binary representation would be 101. Thus, from the ith planet, Elon's rocket will be able to jump ahead by [2^0, 2^1] U [2^2,2^3 ] where U is  union. If i was, let's say, equal to 23 and XJ[i] was equal to 5 then from there, the rocket can jump to all values in these ranges [24, 25] u [27, 31].
Let XE be the array of integers that denote the number of ways to get to the ith planet using Elon's rocket, starting from the 1st planet. Elon asks you the calculate this array. Since the values can be very large, consider them all modulo 1e9+7. XE[O] = 1

Problem Constraints

  • 1 <= A <= 1e5

Input Format

  • The first and only argument is the integer A, denoting the number of planets.

Output Format

  • Return an array of integers as per the given problem.

Example Input

Input 1 : 
    A = 3 
Input 2:
    A=1

Example Output

Output 1:
    1 1 2
Output 2:
    1

Example Explanation

Explanation 1:
XJ[0] = 1, and  XJ[1] = 1 too. So from both the 0th and 1st index, we can jump ahead by [1, 2].
Therefore, XE[1] = 1, and XE[2] = 2.  XE[0] = 1, as given in the problem statement.

Explanation 2:
XE[O] = 1, as given in the problem statement.

Shipment

Problem Description

Little Pony owns a shipment company. There is a priority value and a weight associated with each package. To ship in a single batch with priorities P1, P2, P3,...,Pk they charge-







Now, they have a queue of N packages to be shipped. The weight of ith package is A[i][0] and its priority is A[i][1]. They can not ship the ith package until (i - 1)th package is shipped. Also, they can ship at most B total weight of package at a time.

They can use multiple batches to ship the packages.
Help Little Pony find the maximum amount they can charge.

Problem Constraints

  • 1 <= N <= 2 x 10^5
  • 1 <= A[i[0] <= 5000
  • -5000 <= A[i][1] <= 5000
  • 1 <=B <= 10^9
B >= max(A[i][0]), so it is always possible to ship all items, as B is greater than
maximum weight package.

Input Format

  • The first argument contains a 2D array A of size N x 2.
  • The next argument contains an integer B.

Output Format

Return the maximum charge to ship all packages. Return the answer modulo 10
+7.
Note that you do not need to maximize your answer modulo 10+7. Find the
answer and return it modulo 10"+ 7.

Example lnput

Input 1:
A:
    [
        [4, -3]
        [1, 1]
        [3,-1]
    ]
B: 8
Input 2:
A:
    [
        [2, 4]
        [1, 3]
        [3, -3]
        [4, 1]
    ]
B: 6

Example Output

Output 1:
    1000000005
Output 2:
    16

Example Explanation

Explanation 1:
Optimal way is to ship first package and then second and third packages to
For shipping first package, they will charge -3.
For shipping first and second package, they will charge 1 * 2 - 1 = 1.
Total charge = -2.
which is 1000000005 modulo 10^9+7.

Explanation 2:
optimal way is to ship first 3 packages and then last package. We can not

Comments

Post a Comment

We need people who give us feedback and this is how we grow. Please do comment if you find something faulty, wrong , helpful, valuable in anyway. You can comment anonymously. Thanks for your contribution.

Popular posts from this blog

Solutions LTI Infinity Coding Challenge 2021

LTI Infinity Coding Challenge 2021