10 weeks ago

Rohit • 610

Hyderabad

Question 1

Wildcard Matching

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

• '?' Matches any single character.
• '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Constraints:

• 0 <= s.length, p.length <= 2000
• s contains only lowercase English letters.
• p contains only lowercase English letters, '?' or '*'.

Examples:

Input 1:

s = "aa", p = "a"

Output 1:

false

Explanation:

"a" does not match the entire string "aa".

Example 2:

Input 2:

s = "aa", p = "*"

Output 2:

true

Explanation:

'*' matches any sequence.

Input 3:

s = "cb", p = "?a"

Output 3:

false

Explanation:

'?' matches 'c', but the second letter is 'a', which does not match 'b'.

Question 2

Maximum Subset Sum

Given an integer array nums, find the subarray which has the largest sum and return its sum.

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

Examples:

Input 1:

nums = [-2,1,-3,4,-1,2,1,-5,4]

Output:

6

Explanation:

[4,-1,2,1] has the largest sum = 6.

Input 2:

nums = [1]

Output 2:

1

Input 3:

nums = [5,4,-1,7,8]

Output 3:

23

Question 3

Overlapping Trees

Given two binary trees, you have to overlap Tree 2 over Tree 1.

Example

Tree 1: 4, 5, 6, 1, Null, 4, Null

Tree 2: 7, -2, -6, Null, 5, 4, 3

Output:

7, -2, -6, 1, -5, 4 ,3

Question 4

Shifting Homes

Homes are aligned in a row. In any given row, maximum half of the homes are occupied. In a season, people got infected and all must vacate homes to move to unoccupied homes. Movements are sequential and not parallel (i.e one home completes the movement, then only the second home starts). To reduce the overall time taken, it's better to move to a nearby empty room than a farther one. i'th home to j'th home movement results in abs(j-i) distance. Minimize the overall distance covered by the time all infected home completes the movement to unoccupied homes.

Input : n = no of homes String s denoting occupied and unoccupied homes(1 = occupied, 0 = unoccupied)

Example:

Input

n = 4

"1001"

Output:

2

Question 5

A string S of length N has to be reconstructed from 2(start, end)+k substrings(random length). Start substring is a prefix of S and end substring is a suffix of S. These substrings can be overlapping each other from right, left or both sides with minimum of 4 characters.

Example:

Input

abcde123, de123xyz, 3xyzpqr

Output :

abcde123xyzpqr

Question 6

Burst Balloon

There are n balloons and n bullets and each balloon is assigned with a particular number (point).

Whenever a particular balloon is shot the no of points increases by

1. The multiplication of point assigned to balloon on left and that of right side.
2. Point assigned to left if no right exists
3. Point assigned to right if no left exists.
4. The point assigned to itself if no other balloon exists.

You have to output the maximum no of points possible.

Input

1 2 3 4

Output

20

19 months ago

Gigaliths 570

IIT Ropar

Solution - Q1

This is a well known dynamic programming problem which uses the idea of string matching DP.

Approach

• Let dp(i,j) = true if sub-string s[ i...n-1] matches with sub-pattern p[ j...m-1] , else false.
• We can define a recursive relation to find solution for this state using other precomputed states.
• dp(i,j) is true if any of the following below cases satisfies.
• Case 1 : if s[i] == p[j] , then dp(i,j) will be surely true if dp(i+1,j+1) is true.
• Case 2 : if p[j] == '?' , then dp(i,j) will be surely true if dp(i+1,j+1) is true.
• Case 3 : if p[j] == '*' , we have the following possibilities.
• Case 3.1 : Match current character and extend , check if dp(i+1,j) is true
• Case 3.2 : Match current character with '*' and end , check if dp(i+1,j+1) is true.
• Case 3.3 : Match zero characters , check if dp(i , j+1) is true
• Base cases:
• BC1 : If both pointers have reached the end. ( string has successfully matched with pattern)
• BC2 : if string pointer has reached the end , and pattern hasnt ended . (if remaining pattern contains only '*' , return true. Else false.)
• BC3 : pattern has ended , but string hasnt ended ( return false as this is an incomplete match )

Code

string str , pat;
int dp[2001][2001];
int dfs(int i , int j){
        //BASE CASE
        if(i == str.size() && j == pat.size())return 1;
        if(i == str.size() && j != pat.size()){
            if(pat[j]=='*')return dp[i][j] = dfs(i , j+1);
            else return dp[i][j] = 0;
        }
        if(i != str.size() && j == pat.size())return 0;
        if(dp[i][j] != -1)return dp[i][j];

        int val = 0;
        // Case 1 : string matches with pattern , move both pointers ahead.
        if(str[i] == pat[j])val |= dfs(i+1 , j+1);
        // Case 2 : Match '?' with the string pointer , move both pointers ahead.
        if(pat[j] == '?')val |= dfs(i+1 , j+1);
        // Case 3 : Match '*' with zero or more string pointers.
        if(pat[j] == '*'){
            val |= dfs(i+1,j); 
            val |= dfs(i+1,j+1);
            val |= dfs(i , j+1);
        }
        return dp[i][j] = val;
}

21 months ago

hardik kapoor 130

Solution - 2

Approach

This is a standard problem, usually done by Kadane's algorithm.

Following are the steps for Kadane's algorithm:

• Initialise a maxSoFar to -infinity and currentMax to 0
• maxSoFar contains answer till now, and currentMax is the sum for the current subarray
• Iterate over the array, add ai to currentMax
• If currentMax > maxSoFar, maxSoFar=currentMax
• If currentMax < 0 , we don't need to take the previous subarray, hence set currentMax = 0.

C++ Code

int maxSubarraySum(vector<int> a)
{
    int n=a.size();

    int maxSoFar=-1e9,maxEndingHere=0;

    for(int i = 0;i < n;i++)
    {
        maxEndingHere=maxEndingHere+a[i];

        maxSoFar=max(maxSoFar,maxEndingHere);

        maxEndingHere=max(maxEndingHere,0ll);
    }

    return maxSoFar;
}

2.0 years ago

Nikunj Nawal 10

Solution-Q3

Approach

Step 1: Generate the binary trees from the input.

Step 2: Merge the binary trees.

• Traverse recursively.
• If subtree of Tree 2 is null, then node will be the subtree of Tree 1 as it is.
• If both the values exist, then value will be the value of Tree 2. Then traverse recursively in both the subtrees and repeat the procedure.

Step 3: Decompose the binary tree back into array format.

Here are the required function codes:

node* overlapTrees(node* r1, node* r2) {

    if(r2 == nullptr)
        return r1;

    if(r1 == nullptr) {
        return r2;
    }

    r2 -> left = overlapTrees(r1 -> left, r2 -> left);
    r2 -> right = overlapTrees(r1 -> right, r2 -> right);

    return r2; 
}

vector <int> flattenTree(node* root) {
    node* cur = root;
    vector <int> tree;
    queue <node*> q;
    q.push(root); 
    if(cur != nullptr) {
        tree.push_back(root -> val);
    } else {
        tree.push_back(0);
    }
    while(!q.empty()) {

        if(cur -> left == nullptr && cur -> right == nullptr) {
            q.pop();
            continue;
        }

        if(cur -> left != nullptr) {
            tree.push_back(cur -> left -> val);
            q.push(cur -> left);
        } else {
            tree.push_back(0);
        }

        if(cur -> right != nullptr) {
            tree.push_back(cur -> right -> val);
            q.push(cur -> right);
        } else {
            tree.push_back(0);
        }

        q.pop();
        if(!q.empty()) {
            cur = q.front();
        }
    }

    return tree;
}

node* tree_create(int* arr, int n){
    queue <node*> q;
    int i = 1;
    bool l = true;
    node* root = new node(arr[0]);
    node* cur = root;
    q.push(cur);

    while(!q.empty() && i < n){
        if(l) {
            l ^= 1;

            if(arr[i] != 0) {
                cur -> left = new node(arr[i]);
                q.push(cur -> left);
            } else {
                cur -> left = nullptr;
            }

        } else {
            l ^= 1;

            if(arr[i] != 0) {
                cur -> right = new node(arr[i]);
                q.push(cur -> right);
            } else {
                cur -> right = nullptr;
            }

            q.pop();
            if(!q.empty()) {
                cur = q.front();
            }
        }

        i++;
    }

    return root;
}

21 days ago

Lokesh 310

Hyderabad

Question 4

overview:

• N Houses are there in a line, of which m<=N/2 are occupied (denoted by 1) by a family
• All Families have to move to a house which was not occupied initially.
• Movements are sequential, only one family can move at a time.
• The time taken to move house number i to house number j is equal to abs(i-j)

Solution (O(N^2)):

• Basic greedy idea: if family i1 moves to j1 and family at family at i2 moves to j2, and i1 < i2 , then j1 < j2
  • There are only two possibilities j1 is in between i1 and i2 , or j1 is after i2
  • As the diagram below shows, in both cases j1 < j2 gives a lower time'
• All arrays below are 1 indexed
• Now find the indices of houses with and without families and store them in array occupied[] and empty[] respectively
  • Size of occupied[] = K
    • occupied[i] = index of 'i^th' occupied house
  • Size of empty[] = L
    • empty[ij = index of 'j^th' empty house
• Find distance between every empty and occupied house , store it in dist[][]
  • Dist[i][j] = Distance between i^th occupied house and j^th empty house .
  • Size of Dist[][] = K*L
• Define dp[i][j] = minimum time taken for movement of all families residing till i^th occupied house to a empty house such that family on the i^th occupied house moves to a empty house on or before j^th empty house
  • Initialization:
    • all dp[i][j] = INF
    • dp[1][1] = dist[1][1]
    • dp[1][j] = min(dp[1][j-1],dist[1][j])
  • Updation:
    • dp[i][j] = min(dp[i][j-1],dp[i-1][j-1]+dist[i][j])
  • final answer:
    • ANS = min of all dp[K][i] , 1 <= i <= L