5 weeks ago

John 910

Hyderabad

Question 1

Job

You just got a new job, but your new office has a weird rule. They allow you to take interval breaks in between tasks if there is no task available. But the problem is that the tasks come randomly and sometimes it may be required to do them simultaneously.

On your first day, you are given a list of tasks with their starting and ending time. Find out the total time will get for breaks. Assume ending time to be greater than starting time.

Note: The minimum start time and the maximum end time in the array is the total time duration he spent in the office.

Input Specification:

input1: Number of tasks
input2: 2-d array in form [t1,t2] representing starting and ending time period of the task

Output Specification:

Your function must return an integer representing the total break time.

Example 1

input1:4 
input2: { {6,8},{1,9},{2,4}, {4,7} }

Output: 0

Explanation: You will be working from1 to 9, so there is no break time.

Example 2

input1: 4
input2: { {4,5},{2,3},{1,2},{7,9} }

Output: 3

Explanation: You will be working from1 to 3, 4 to 5 and 7 to 9. You will have break time of 1+2=3.

Question 2

Money confusion

In a laundry, it happens often that people forget to take their money out of their pockets and the money is washed with the clothes. The laundry man simply takes these wet notes out and puts them sequentially under the sunlight to dry them. He does not mix them up, for example, if he gets 3 notes from one cloth, he places them sequentially and then places the notes received from other clothes and so on.

Shane forgot some money in his trousers and gave his clothes to the laundry man, afterward, when he realized his mistake, he got back to the laundry and asked for his money. You have to tell the number of notes he forgot in his trousers if he knows the exact amount he forgot in his trouser.

Input Specification:

input1: Total money Shane has.
input2: Total notes the laundry man has.
input3: An array of the order in which the notes are placed.

Output Specification:

Return the number of notes Shane has. Return 0 if his money is not there.

Example 1:

input1: 15 
input2: 6 
input3: {1,4,20,3,10,5}

Output: 2

Explanation:

Note in the fifth position(10) and Note in the sixth position(5) add up to 15, which is the amount that Shane forgot.

17 months ago

Ayush Kumar Shaw 110

Solution to Q2 - Money Confusion

Since, the notes received from a single pocket is placed in a contiguous sequence, the amount of money Shane forgot in his pockets must form a subarray in the given array. Hence, we look for the minimum length subarray that has a sum equal to the money that Shane has forgot in his pockets. This can be solved by keeping a map of the different prefix sums encountered, mapping to their indices.

Pseudo Code

int solve(vector<int> a,int n,int k){
    map<int,int> ps;
    ps[0]=-1;
    int ans=INT_MAX,sum=0;
    for(int i=0,1,2,...,n-1){
        sum+=a[i];
        if(ps.find(sum-k)!=ps.end()){
            ans=min(ans,i-ps[sum-k]);
        }
        ps[sum]=i;
    }
    return ans==INT_MAX?-1:ans;
}