Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close

Attend Meetings Problem

Given a list of meeting time intervals consisting of start and end times [[s1, e1], [s2, e2], ...] (si < ei). You need to complete canAttendAllMeetings function and return 1 if a person can attend all given meetings else 0.

Input Format:

There is only one argument in input, list of intervals (Each interval is a list containing two elements where the first element is the start time of that interval and the second element is the end time of that interval).

Output Format:

Return either a 1 or a 0.

Solutions

We have provided a solution which contains necessary comments to understand the approach used: solution.java

Description:

We are asked to determine whether a person can attend all meetings represented by a list of given intervals or not.

In brute force method, we can iterate over each interval and try to find another overlapping interval with the current interval. As this process will take two loops and hence will lead to O(n^2) time complexity.

Hence to optimise, we sort the given array by start time of intervals and if start time are same then we sort by end time of intervals.

As intervals are sorted, we can easily observe a relation between end time of previous interval to start time of current interval to determine overlap. If previous_end time > current start time that means previous and current are overlapping intervals. Hence we will return 0 else else continue to iterate. Here if current means ith interval then previous means i-1th interval.

For better understanding, please have a look at the solution.

Time Complexity:

O(n log n) where n denotes the number of intervals.

As we are sorting list of n intervals hence it will take O(n log n) time. After sorting we are iterating over n intervals it will take O(n) time. Hence the total time complexity will be O(n log n) + O(n) → O(n log n).

Auxiliary Space Used:

O(1).

We are not storing anything extra. We are assuming that sorting of n intervals will be in place hence O(1).

Space Complexity:

O(n) where n denotes the number of intervals.

To read input it will take O(n) as we are reading n intervals, auxiliary space used is O(1) and to store output it will take O(1) hence total space complexity will be O(n).


// -------- START --------
    public static int canAttendAllMeetings(List> intervals){
        // Sorting in ascending order of start value of an interval
        // if start value is same for two intervals then sort in ascending order of end value of intervals
        Collections.sort(intervals, new Comparator>() {
            @Override
            public int compare(List l1, List l2) {
                if (l1.get(0) - l2.get(0)!= 0) {
                    return (int)(l1.get(0) - l2.get(0));
                }
                return (int)(l1.get(1) - l2.get(1));
            }
        });
        // As intervals have at least one element
        int previous_end = intervals.get(0).get(1);
        for (int i=1; i intervals.get(i).get(0)) {
                return 0;
            }
            // Updated previous' end.
            previous_end = intervals.get(i).get(1);
        }
        return 1;
    }
    // -------- END --------


Try yourself in the Editor

Note: Input and Output will already be taken care of.

Attend Meetings Problem

Given a list of meeting time intervals consisting of start and end times [[s1, e1], [s2, e2], ...] (si < ei). You need to complete canAttendAllMeetings function and return 1 if a person can attend all given meetings else 0.

Input Format:

There is only one argument in input, list of intervals (Each interval is a list containing two elements where the first element is the start time of that interval and the second element is the end time of that interval).

Output Format:

Return either a 1 or a 0.

Solutions

We have provided a solution which contains necessary comments to understand the approach used: solution.java

Description:

We are asked to determine whether a person can attend all meetings represented by a list of given intervals or not.

In brute force method, we can iterate over each interval and try to find another overlapping interval with the current interval. As this process will take two loops and hence will lead to O(n^2) time complexity.

Hence to optimise, we sort the given array by start time of intervals and if start time are same then we sort by end time of intervals.

As intervals are sorted, we can easily observe a relation between end time of previous interval to start time of current interval to determine overlap. If previous_end time > current start time that means previous and current are overlapping intervals. Hence we will return 0 else else continue to iterate. Here if current means ith interval then previous means i-1th interval.

For better understanding, please have a look at the solution.

Time Complexity:

O(n log n) where n denotes the number of intervals.

As we are sorting list of n intervals hence it will take O(n log n) time. After sorting we are iterating over n intervals it will take O(n) time. Hence the total time complexity will be O(n log n) + O(n) → O(n log n).

Auxiliary Space Used:

O(1).

We are not storing anything extra. We are assuming that sorting of n intervals will be in place hence O(1).

Space Complexity:

O(n) where n denotes the number of intervals.

To read input it will take O(n) as we are reading n intervals, auxiliary space used is O(1) and to store output it will take O(1) hence total space complexity will be O(n).


// -------- START --------
    public static int canAttendAllMeetings(List> intervals){
        // Sorting in ascending order of start value of an interval
        // if start value is same for two intervals then sort in ascending order of end value of intervals
        Collections.sort(intervals, new Comparator>() {
            @Override
            public int compare(List l1, List l2) {
                if (l1.get(0) - l2.get(0)!= 0) {
                    return (int)(l1.get(0) - l2.get(0));
                }
                return (int)(l1.get(1) - l2.get(1));
            }
        });
        // As intervals have at least one element
        int previous_end = intervals.get(0).get(1);
        for (int i=1; i intervals.get(i).get(0)) {
                return 0;
            }
            // Updated previous' end.
            previous_end = intervals.get(i).get(1);
        }
        return 1;
    }
    // -------- END --------


Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve.

Ryan-image
Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Accelerate your Interview prep with Tier-1 tech instructors
blue tick
360° courses that have helped 14,000+ tech professionals
blue tick
100% money-back guarantee*
Register for Webinar

Recommended Posts

All Posts