Question: Uber | 15th October, 2022 | Recent Interview Questions | Jobs and Profits | Pattern Printing

Entering edit mode

Avg CTC: 20lpa

Job roles: Software Engineer, Backend Developers, Program Analyst and more

Job List: Positions open for Uber, India

Question 1

Jobs and Profits

There are some job opportunities in one company. And there are some candidates for these jobs. Candidate can be hired for the ith job if he has all skills that are needed for this job. There are some distinct skills which can be needed for jobs. Company needs only one person for each job. Moreover each candidate can be hired only for one job and the profit of hiring somebody for the ith job is profits[i]. Profit of hiring for the set of jobs equals to sum of profits of each job in set. For the empty set it's 0.

Your task is to calculate a maximum profit after hiring a subset of candidates for a subset of jobs.

Example

For profits = [4, 10], skillsForJobs = [[true, false], [false, true]], and skillsOfCandidates = [[true, true], [true, false]], the output should be

solution(profits, skillsForJobs, skillsOfCandidates) = 14;

For profits = [5], skillsForJobs = [[true]], andskillsOfCandidates = [[true]], the output should besolution(profits, skillsForJobs, skillsOfCandidates) = 5.

Input/Output

[execution time limit] 0.5 seconds (cpp)

[input] array.integer profits

Guaranteed constraints:

1 <= profits.length <= 50

0 <= profits[i] <= 106.

[input] array.array.boolean skillsForJobs

If skillsForJobs[i][j] = true then candidate for ith job must have skill with number j.

Guaranteed constraints:

skillsForJobs.length = profits.length

skillsForJobs[i].length = skillsForJobs[0].length

1 <= skillsForJobs[i].length <= 50

[input] array.array.boolean skillsOfCandidates

If skillsOfCandidates[i][j] = true then ith candidate has skill with number j.

Guaranteed constraints:

1 <= skillsOfCandidates.length <= 50

skillsOfCandidates[i].length = skillsForJobs[0].length

[output] integer

Question 2

Given 3 positive integers K, L, N where K <= L <= N

A integer set T of size L is called good if all integers in T are distinct and in range [1,N].

Let S be the set of all such possible sets T of given length L.

Let A be the uniformly and randomly chosen set from S, JA be the smallest integer in set A. Find sum of JA modulo 998244353 over all such good sets A.

Since the problem is too easy for you, you will have to solve this for Q such query.

Input is given in form of 3 arrays Ks, Ls, Ns each of size Q.

ith query consists of K = ks[i], L = ls[i], N = ns[i]

Constraints:

1 <= Q <= 10^3
1 <= K <= L <= N <= 10^6

Sample Input

ks: [2, 1, 2, 3]
ls:  [2, 1, 2, 3]
ns: [3, 1, 2, 3]

Sample Output:

[8, 1, 2, 3]

Here one has to solve for four different queries-

K = L = 2, N = 3
K = L = N = 1
K = L = N = 2
K = L = N = 3

Question 3

Click here to Practice

Pattern Printing

So Mr.George recently joined college and he is too much fascinated by patterns. He was able to implement the following star pattern-

*
** 
****
****** 
********

in which the no. of asterisk at a level N is N.

Now instead of just Asterisk, Mr.George also decided to use small alphabet o

So Patterns may look like these -

** 
oooo 
****** 
******** 
oooooooooo

But he won't mix a row with both 'o' and '*'

Now given He has A no. of 'o' and BB no. of '*'

Tell the total ways he can implement a star pattern.

Since this no. can be very large, return it modulo 998244353998244353.

Explanation

Sample Case 1

Asterisk - 2

Alphabet o - 2

Possible patterns -

**


oo 


** 
oooo 



oo 
****

[execution time limit] 4 seconds (cpp)

[input] integer a

denotes the max no. of asterisk we can use.

1 <= a <= 1e51 <= a <= 1e5

[input] integer b

denotes the max no. of alphabet o's we can use.

1 <= b <= 1e51 <= b <= 1e5

[output] integer

find the total no. of ways of creating star patterns with given Asterisk and Alphabet o's

ADD COMMENT • link

Entering edit mode

Solution to Question 3

Analysis

Lets first find the maximum height of such a pattern. We can note that the maximum height of the pattern by using atmost a asteriks and b o's will be the same as of that obtained by using atmost a+b characters of the either type. This can be proved as follows:

First assume that you have created a pattern of the maximal height and now you have to decide the characters to be put on the rows.
Lets greedily start putting the asteriks on the rows with the largest width possible until we either run out of the asteriks or we dont have sufficient asteriks to be put on the largest row remaining. We can now use the remaining asteriks (if any) to fill the floor with the width equal to the remaining asteriks (we can always do this as we rows with consecutive widths).
It can be seen that you can easily fill the rest of the floors with the o's.

Now to obtain the maximal height, we need to find the largest h such that h*(h+1)/2 <= a+b. We can do the same using either binary search or even simple math.

Now to solve the original problem , we will use dynamic programming. Let dp[height][cnt_*][cnt_o] denote the number of ways to create the patterns of height height and we are currently left with cnt_* asteriks and cnt_o o's. We can do the following transitions for this dp:

We can place asteriks on the next row (if possible) and update dp[height+1][cnt_* - height+1][cnt_o].
We can place o's on the next row (if possible) and update dp[height+1][cnt_*][cnt_o - height+1].

The final ans to the problem can be obtained by summing up the dp values for patterns of heights from 1 to h. Thus we solve the problem in a time complexity of O(h*a*b). Since h is atmost sqrt(a+b), the total complexity is O(sqrt(a+b)*a*b). This however TLEs for the constraints.

How to optimize the dp ?

We can optimize the dp simply by reducing the state of dp. We only need to keep either of cnt_* or cnt_o in the dp state as the other can be simply obtained by subtracting the first one from the total characters placed. Thus the problem is now solved in a time complexity of O(sqrt(a+b)*min(a,b)).

PseudoCode

For an interview setup, you may be asked to code the dp with the minimal space. The following Code(C++) does the same and solves the problem in a space complexity of O(min(a,b)) and time complexity of O(sqrt(a+b)*min(a,b)).

int solve(int a, int b)
{
    int lo = 1, hi = 1000, h = -1;               //h is the maximum height of such a tower
    while(hi &gt;= lo)
    {
        int mid = mid(lo,hi);
        if((mid*(mid+1))/2 &lt;= a+b)
        {
            h = mid;
            lo = mid+1;
        }
        else hi = mid-1;
    }

    if(!a) swap(a,b);

    vector&lt;int&gt; dp(a+1,0);                      //dp[x] denotes the number of ways to create patterns and having x asteriks left

    //place o in the first row
    if(a) dp[a] = 1;
    //paint asterisk in the first row.
    if(b) dp[a-1] = 1;

    int ans = 0;
    for(int height=1; height&lt;h; height++)
    {
        for(int asteriks_left = 0; asteriks_left&lt;=a; asteriks_left++)
        {
            ans = (ans + dp[asteriks_left])%mod;
            int o_left = b - ((height*(height+1))/2 - (a-asteriks_left));         //calculate the no of o left using math
            if(asteriks_left &gt;= height+1) dp[asteriks_left - (height+1)] = (dp[asteriks_left - (height+1)] + dp[asteriks_left])%mod;                                                                 //place asteriks in the next row.
            if(o_left &lt; height+1) dp[asteriks_left] = 0; 
        }
    }
    for(int asteriks_left = 0; asteriks_left&lt;=a; asteriks_left++) ans = (ans + dp[asteriks_left])%mod;
    return ans;
}

ADD COMMENT • link 2.1 years ago Ayush Gangwani 1.2k

Entering edit mode

Solution to Problem 1

Analysis

Let's first make a graph where the nodes are the jobs and the candidates, and if candidate i is a fit of job j add an edge of weight profit[j] between candidate i and job j. Note that this graph is bipartite as the only edges are from jobs to candidates. So now our problem reduces to finding a set of independent edges (i.e. edges that do not share a node) that has maximum weight as there exists only a single candidate for a single job and vice versa. Hence what we are looking for is the maximum weighted matching of a bipartite graph as the set of independent edges forms a matching. This is a very well-known problem and many algorithms like the Hungarian algorithm and Linear Programming algorithms exist to solve exactly the same problem. Note that the constraints are so low that it even allows the general weighted matching using Blossom's algorithm to pass.

PseudoCode

int solve(vector<vector<bool>> jobs,vector<vector<bool>> candidates,vector<<ll>profits){
 graph.initialize();
   for(vector<bool> job:jobs){
      for(vector<bool> candidate:candidates){
           if(match(candidate,job)){
             add_edge(candidate,job,price_of_job);
             }
      }
   }
   return blossom(graph);
}

ADD COMMENT • link