5 weeks ago

John 910

Hyderabad

Question 1

Given an integer n, return the least number of perfect square numbers that sum to n.

Question 2

For two strings s and t, we say "t divides s" if and only if s = t + ... + t (t concatenated with itself 1 or more times)

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

Input:

str1 = 'ABCABC', str2 = 'ABC'

Output:

'ABC'

Input:

str1 = "ABABAB", str2 = "ABAB"

Output:

'AB'

Question 3

In a gold mine grid of size m x n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.

Return the maximum amount of gold you can collect under the conditions:

• Every time you are located in a cell you will collect all the gold in that cell.
• From your position, you can walk one step to the left, right, up, or down.
• You can't visit the same cell more than once.
• Never visit a cell with 0 gold.
• You can start and stop collecting gold from any position in the grid that has some gold.

Question 4

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

Question 5

Array of string is given ["abc, def, xyz, ..."]. You have to find the groups of related strings.

A String is related if the distance between each of the character of the string [at each index] is same.

Example

(d-a = 3 | e-b.= 3 | f-c=3) --> Hence abc and def are related.

Question 6

Given an array of integers, find the longest subarray in this array which is divisible by k.

Example:

arr[] = 7 8 3 -3 4 2 1 and k = 3

The longest subarray is 7 8 3 -3 4 2 which is divisible by 3 so answer is 6

Question 7

Given is an array of integers where each number exists exactly twice except one number.

It is also guaranteed that the duplicate occurrences occur consecutively.

Find the number that occurs only once

Example

1 1 2 2 4 4 6 8 8

Output:

6

11 weeks ago

Ayush Gangwani 1.2k

New Delhi

Solution to problem 4

Analysis

We can solve the problem greedily by using two pointers technique as follows. Start from the first character and find its last occurrence in the string. Note that we have to include all the characters in between the first and the last occurrence of this character in the same partition. Now if the last occurrence of some of these characters lies further beyond, we have to extend the current partition upto that position. We keep scanning the characters and extending the partition until we reach the end of the partition. Now we have successfully created the first partition and can repeat the same process on the remaining string. This can be implemented using two pointers in a time complexity of O(N).

PseudoCode

solve(s):
    last = new Hashmap<char,int>               //find the last occurrence of each character
    for i from 1 to s.length():                            
        last[s[i]] = i

    ans = new int[]
    i = 0
    while(i < s.length()):                     //i marks the beginning of a new partition
        target = last[s[i]]                    //first set the end of the partition as the last occurence of the i-th character
        j = i
        while(j < target):                     //now keep scanning the elements in between
            target = max(target, last[s[j]])   //and extend the end of the partition as explained
            j++
        ans.append(j-i+1)                      //once we reach the end of the partition, append the length in ans
        i = j+1                                //set i to the start of the remaining string 
    return ans

20 months ago

Yash Sahijwani 940

Solution to Problem 1

Analysis

We need to find the minimum number of perfect squares which sum up to the given number n. Here, we should first know Lagrange's four square theorem, which states that every natural number can be represented as the sum of 4 integer squares. So n = x^2 + y^2 + z^2 + w^2. Here, x, y, z, w can be any integer (possibly 0 as well). So our answer will always be less than or equal to 4.

Now, if the number n is a perfect square itself, then our answer will be 1. Otherwise, we check whether we can represent it as the sum of 2 perfect squares. So we need to check whether n = x^2 + y^2. We iterate overall all x from 1 to sqrt(n), and check whether n-x^2 is a perfect square or not. If we get a perfect square for some x, then the answer is 2.

Now, for numbers which neither have answer as 1 nor 2, we need to decide whether they can be represented as sum of 3 perfect squares or 4 perfect squares. For this we need to know Legendre's 3 square theorem, which states that every natural number can be represented as the sum of 3 perfect squares i.e. n = x^2 + y^2 + x^2 if and only if n is not of the form 4^a (8b+7) i.e. if n = 4^a (8b+7), it cannot be represented as the sum of 3 perfect squares.

Hence, we check this, and if n is of this form, then the answer is 4, (since 3 cannot be the answer), otherwise it is 3.

7 months ago

Akshay Sharma 990

Chandigarh

Question 3

Overview

• We have to return the maximum amount of gold that we can collect
• Assuming that the number of cells that contains Gold is less than 25
• Also we are assuming that the number of rows and columns would be less than 15.
• we can move in any of the 4 directions but can't go outside the grid and the cell that is marked with 0.
• Also we can start collecting gold from any of the cells.

prerequisite

• Graph theory / DFS

Solution

• As constraints are quite small we can simply use DFS to find the solution to this problem but how we can come up with this solution why not DP or some greedy algorithm or some precomputation?
  • If we see the above image the cell that is marked with a cross are not visitable cells if we start from one specific cell then we are not able to calculate the correct answer for this question for example in the above question the middle cell contains 99 gold which is too greater than other cells.
• If we see the grid carefully this question is more likely the sum of connected components and returns the maximum sum of the connected component.
• In the above example we have 4 connected components we can start our DFS from each connected component and calculate their sum for example the sum of the above example connected components is 99,40,9,21 So the answer to the above question is 99.
  • As the length of constraints is quite low and the maximum cell that contains gold is also 25 we can easily run a DFS function from each cell that contains gold and return the maximum result.

Pseudo Code

int dfs(vector<vector<int>>& g, int i, int j) {
if (i < 0 || j < 0 || i >= g.size() || j >= g[i].size() || g[i][j] <= 0)  return 0;
g[i][j] = -g[i][j];
auto res = max({ dfs(g, i + 1, j), dfs(g, i, j + 1), dfs(g, i - 1, j), dfs(g, i, j - 1) });
g[i][j] = -g[i][j];
return g[i][j] + res;
}

• Time Complexity:O(k * 3 ^ k), where k is the number of cells with gold. We perform the analysis for k cells, and from each cell, we can go in three directions.

7 months ago

Akshay Sharma 990

Chandigarh

Question 6

Approach

• In this problem, we have to find the length of the longest subarray whose sum is divisible by k.
• Let the sum of the first i and first j elements of the array be s1 and s2 respectively such that s1=Kn+x and s2=Km+x.
  • This way the elements between the ith and jth index would yield a sum which will be divisible by K. As, s2-s1=K(m-n)

• Let's take an Example

  

• In this example, the sum of subarray {2, 7, 6, 1} is 16 which when divided with k i.e. 3 gives 5 as quotient and 1 as remainder.

• So s1 can be written as (3*5) +1.
• Similarly, the sum of subarray {2, 7, 6, 1, 4, 5} is 25 which when divided with k i.e. 3 gives 8 as quotient and 1 as the remainder
• So s2 can be written as (3*8) +1
• And their difference i.e. s2-s1, (25-16=9) 9 is divisible by 3 which means that we have a subarray, {4, 5} whose sum is divisible by 3.
• So to start with, we need to travel to each element of the input array and find the sum till that element from the zeroth index. After that, divide the sum with the given K and capture the remainder.
• We can use a hashmap to store the index of the first occurrence.

Pseudo Code

unordered_map<int, int> um;

int max_len = 0;
int curr_sum = 0;

for (int i = 0; i < n; i++)
{
    curr_sum += arr[i];

    int mod = ((curr_sum % k) + k) % k;

    // if true then sum(0..i) is divisible by k
    if (mod == 0)
        max_len = i + 1;
    else if (um.find(mod) == um.end())
        um[mod] = i;

    else
        if (max_len < (i - um[mod]))
            max_len = i - um[mod];
}
return max_len;

• Time Complexity : O(N)

11 weeks ago

Ayush Gangwani 1.2k

New Delhi

Solution to Problem 7

Analysis

A naive solution to this problem is to check every consecutive element and determine the element that appears once in O(N). Another O(N) solution (assuming that the input values are non negative) would be to just calculate the bitwise-XOR of the given array. The elements appearing twice will cancel out and the odd element will be left out. But we can do better than O(N).

Better than O(N) would be O(logN) which implies, drumrolls 🥁 ..... Yeah you guessed it right --- Binary Search.

How to Binary search for the required index ?

Lets call the element to be found as the odd element. First note that the odd element will always be at even index if we consider 0-based indexing. This is because all the elements to the left of the odd element will be paired and hence there will be an even number of elements to its left. Hence we will binary search for only the even indexed positions.

How to determine if the odd element lies to the left or to the right of some index mid ?

Notice from the diagram that for all the even indexed positions to the left of the odd element, the value to the right is the same and for all the even indexed positions to the right (and including the odd element), the value to the right either does not exist or is different. Hence we can use this fact to determine if the odd element lies to the left or to the right of the current index mid.

Thus, using these observations, we can binary search for the odd element and find it in a time complexity of O(logN) and O(1) space complexity.

PseudoCode

solve(arr):
    low = 0, high = (arr.size()-1)/2;         //we only binary search for the even indexed positions, hence we only need n/2 search states
    while(high > low):
        mid = low + (high - low)/2;           
        index = 2*mid;                        //the real index in the array is determined by 2*mid

        if(index+1 < nums.size() and nums[index+1] == nums[index]): //if the next index exists and the value is the same
            //we are to the left of the required element and should move right, thus reduce search space to [mid+1,high]
            low = mid+1;
        else:
            //we are either on the odd element or to its right, hence reduce our search space to [low,mid]
            high = mid;

    //finally low == high and we return the value at the actual index represented by the ans. 
    return nums[2*low];

7 months ago

Shikhar Mehrotra 480

Chennai

Q2)
Analysis :
First observe that if string x is a divisor of string s then s=x+x...(concatenated some times) which means
sizeof(string s)=sizeof(string x) * (some positive integer) which means size of string x is a factor of size of string s.
Solution :
We could iterate over the common factors of string size of(s) and string size of(t) and find the common factor of both of them and then check whether a prefix of factor length is possible or not. For checking is it possible we could do it by taking a prefix of a factor length and check whether when it concatenates for length/factor times to give us a taken string and also check whether the chosen factor length prefix is common in both of them.
Pseudo Code

size_s=size of(s)
size_t=size of(t)
ans=0;
boolean possible(prefix_length)
{
x=prefix of s of prefix_length
y=prefix of t of prefix_length
x_concatenated=[x]*(size_s/prefix_length)
y_concatenated=[y]*(size_t/prefix_length)
if(x is equal to y and x_concatenated is equal to s and y_concatenated is equal to t)  
        return 1
    else
        return 0    
}
iterate over common factors(f) of size_s and size_t 
{
if(possible(f))
    ans=max(ans,f);
}
return prefix of any string(either s or t) of ans length