7 days ago

admin 1.6k

Hyderabad

Q1

IP check

Pairtel company is given the contract to assign IP addresses to the computers of HackerEarth. The printer used to print the set malfunctioned and some of the addresses were wrongly printed.

Task

Check the validity of each address. Return "IPv4" if P is a valid IPv4 address, "IPv6" if IP is a valid IPv6 address or "Neither" if IP is not a correct IP of any type.

Notes

• A valid IPv4 address is an IP in the form x1, x2, x3, x4 where 0 <= xi <= 255 and xi cannot contain leading zeroes.
  • A valid IPv6 address is an IP in the form x1:x2:x3:x4:x5::x6:x7:x8 where 1 <= len(xi) <= 4. xi is a valid hexadecimal string (contains digits, lowercase and uppercase characters), xi can contain leading zeroes.

Example

Assumptions

• T = 3
• Input = [25.50.6.22, 120.500.0.10, "2001:0db8:85a3:0000:0000:8aw3:0370:7334"]

Output

• IPv4
• Neither
• IPv6

Approach

• The first IP matches all constraints of IPv4.
• The second IP does not match any. Its second part is 500 which makes it an invalid IPv4.
• The third IP matches all constraints of IPv6.

Function Description

Complete the solve function provided in the editor. This function takes the following parameter and returns the required answer:

• IP: Represents a string denoting the IP address.

Input Format

• The first line contains T denoting the number of IP addresses.
• Each of the next T lines contains a string, denoting the IP addresses.

Output Format

Print T lines where the ith line is the type of the ith IP address

Constraints

1 <= T <= 10^5

1 <= | ip | <= 10^5

Q2

Maximum Sum Path

================

You are given an array A of length N consisting of distinct elements.

You need to construct a Binary Search Tree(BST) by inserting each element one by one from array A, starting from the first element till last.

Task

Determine the maximum path sum from root node to leaf node of the BST after each new element is inserted.

Notes

• 1-based indexing is followed.

• A Binary Search Tree is node-based binary tree data structure that has the following properties:
• The left subtree of a node contains only nodes with keys lesser than the node's key.
  • The right subree of a node contains only nodes with keys greater than the node's key.
  • The left and right subtree each must also be a binary search tree.

• A node is a leaf node if both left and right child nodes of it are NULL.

Example

Assumptions

• N = 3
• A = [1, 2, 3]

Approach

• Inserting element A[1]. the maximum path sum of BST is 1.
• Inserting element A[2]. the maximum path sum of BST is 3.
• Inserting element A[3]. the maximum path sum of BST is 6.

Therefore the answer is 6.

Q3

Smart planning for solar powered electric vehicles

The world is rapidly changing and getting smarter day by day. To go towards the path of sustainable development, you have decided to build a future par where you have parking space for solar-powered electric vehicles that have 0 emissions and save fuel and the environment. In the future park, the solar-powered cars need to be parked in such a way that they can get just enough sunlight in 1 hour to fully charge themselves. The current state of car parking is represented by an array Current wherein the array element -1 represents the car number at that spot. You are also given an array Desired which shows the ideal parking positioning of cars so that they can charge themselves fully in 1 hour. In one move, you are allowed to move a car one place forward or backward to an empty spot.

Task

Determine the minimum number of moves required to achieve the desired state of solar-powered cars. If it is not possible, print -1.

Notes

• Assume 1-based indexing
  • You cannot move pillars. Also, no cars can fly over another car or go through the pllars.
  • Cars are numbered starting from 1 to the number of cars.

Example

Assumptions

• N = 4
• Current = [-1, 1, 0, 2]
• Desired = [-1, 0, 1, 2]

Approach

• Move car 1 from position 2 to position 3. It would take one move. After this state would be [-1, 0, 1, 2].

So, the answer is 1.

Function Description

Complete the solve function provided in the editor. This function takes the following 3 parameters and returns the minimum moves required to achieve the final state:

• N: Represents the size of the solar-powered car parking
• Current: Represents the current state of the parking for the solar cars
• Desired Represents the desired state of the parking for the solar cars

Input Format

• The first line contains T denoting the number of test cases. T also specifies the number of times you have to run the solve function on a different set of inputs.
• For each test case:
• The first line contains an integer N denoting the size of the solar-powered car parking.
  • The second line contains N space-separated numbers, denoting the current state of parking of solar cars.
  • The third line contains N space-separated numbers, representing the desired state of parking solar cars.

Output Format

For each test case in a new line print the number of moves required or -1 if not possible.

8 months ago

Shikhar Mehrotra 480

Chennai

Q3)
Assuming sum of N over all test cases is at most 10^5

Analysis

• First of all observe that you cannot take a car to a position forth and the pillar position (represented by -1).
• One more thing to note you cannot move pillars so all pillars position in current and desired should be the same.
• Now since pillars cannot be moved so the arrangement of the cars should be the same in the desired and current because if it is not same then it is not possible to swap two values which are positions of car (i.e non-zero values) because we can move cars to empty positions only.
  • • Let's take an example , suppose if between two pillars we are having following arrangement
      -1 0 1 4 0 0 5 0 0 2 -1 in current and -1 0 1 0 0 4 5 0 2 0 -1 in desired
      • Then we could see car arrangement in current is 1 4 5 2 and in desired 1 4 5 2 which is same so we can rearrange to the desired one.
  • • Let's take an example , suppose if between two pillars we are having following arrangement
      -1 0 4 1 0 0 5 0 0 2 -1 in current and -1 0 1 0 0 4 5 0 2 0 -1 in desired
      • Then we could see car arrangement in current is 4 1 5 2 and in desired 1 4 5 2 which is not same so we cannot rearrange to the desired one because we cannot swap 4 from 1 .
• Now as we see when it would be possible, now we need to find the number of moves if it is possible to make it to the desired one. It is clear that if we want to move a car from position x to y then it will take |x-y|(absolute value of (x-y)) moves. because this would be the least move required. Now if thinking that movement from x to y have some cars in between , then try to think in this way we start from the rightmost one and take it to the desired position, obviously there would be no car in between (Since we had already checked that whether it is possible or not and currently analyzing the case when it will be possible). Then allot others in the same way , in this way no car is in between and we are achieving this in minimum steps to move from x to y for all cars positions. Similarly can be done if we move from left to right. # Pseudo Code Modify current and desired a bit (i.e current --> {-1,current[0],current[1],...,current[n-1],-1} desired-->{-1,desired[0],desired[1],...,desire[n-1],-1}). This would make implementation a bit easy.

//check whether it is possible or not by checking pillars position
for(int i=0;i < n;i++)
{
//check whether if there is pillar in one of them and in other it is not.
if((desired[i] < 0) and (current[i] > =0)) 
    return -1;
if((desired[i] > =0) and (current[i] < 0))
    return -1;
}
n --- > current size of current or desired array.(Remember it had been modified a bit.) 
for(int i=0;i < n;i++)
{
if(desired[i]==-1)//This means both has pillar
{
    int j=i+1;
    list want,given; //want and given are the car arrangements in desired and current respectively.
    list want_indices,given_indices;//want_indices and given_indices represent the indices of the cars in desired and current respectively  
    while((j < n) and (desired[j]!=-1))
    {
        if(current[j] > 0){
            given_indices.push(j);
            given.push(current[j]);
        }
        if(desired[j] > 0){
            want_indices.push(j);
            want.push(desired[j]);
        }
        j++;
    }
    if(want==given)//check whether cars in same arrangement
    {
        for(int i=0;i < size of(want_indices);i++)
            ans+=abs(want_indices[i]-given_indices[i]); //number of moves
    }
    else
        return -1;
}
}  
return ans;

8 months ago

Akshay Sharma 990

Chandigarh

Question 1

Intuition/Approach

• The given problem can be solved by splitting the string with respect to ‘.’ while checking for IPv4 address and ‘:’ while checking for IPv6 address and check for the conditions for the string as IPv4 or IPv6 or Invalid.

For IPv4

• Initialize a boolean variable, ans as true to check if the string is IPv4 or not.
• Store the count of occurrence of ‘.’ in the given string, S in a variable cnt.
• If the value of cnt is not equal to 3, then update the value of ans to false. Otherwise, tokenize the string, S with respect to the character ‘.’ and store the tokenized strings in an array V
• Check if the size of V is equal to 4 or not. If not equal, update the value of ans to false
• Otherwise, traverse the array, V and for each string, str in V check it lies in the range [0-255] and does not contain leading 0s. If not, then update the value of ans to false
• If the value of ans is true, then the string is a valid IPv4 address, Otherwise, it is not a valid IPv4 address.

For IPV6

• Follow first step same
• If the value of cnt is not equal to 7, then update ans to false. Otherwise, tokenize the string, S w.r.t character ‘:’ and store the tokenized strings in an array, V.
• Check if the size of V is equal to 8 or not. If not equal, update ans to false.
• Otherwise, traverse the array, V and for each string, str in V check its length is in the range [1, 4] and it is a valid hexadecimal number. If not, then update the value of ans to false.
• If the value of ans is true, then the string is a valid IPv6 address. Otherwise, it is not a valid IPv6 address.
• Time complexity : O(N)

17 months ago

Rishabh Verma 170

Question 2 : Maximum Path sum

Overview

Find the path in the binary search tree at which sum of the value on nodes is maximum.

Approach:

• making binary search tree from the array is straight forward you just have to insert array element one by one from the beginning .
• apply any traversal and keep track of sum of that path.
• as you get a leaf node update your answer if your sum is greater then the answer till now.

Complexity

> O(nlog(n)) where n is number of nodes in the binary search tree.

C++ Code

Node* insert(Node* root, int key)
{
    Node* newnode = newNode(key);
    Node* x = root;
    Node* y = NULL;

    while (x != NULL) {
        y = x;
        if (key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    if (y == NULL)
        y = newnode;
    else if (key < y->key)
        y->left = newnode;
    else
        y->right = newnode;
    return y;
}
void Inorder(Node* root,int sum)
{
    if (root == NULL){
        val = max(val,sum);
        return;
    }
    else {
        Inorder(root->left,sum+root->key);
        Inorder(root->right,sum+root->key);
    }
}
// To make the tree insert nodes for every element of the array one by one