Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

bool CanProgramStarted(list<pair<int,int>> runningProgram, pair<int,int> Programs)
{
	list<pair<int, int>>::iterator itList;
	//if starting time falls b/w existing start and end time then No otherwise yes
	for (itList = runningProgram.begin() ; itList != runningProgram.end() ; itList++)
	{
		if (Programs.first >= itList->first && Programs.first <= (itList->first + itList->second))
			return false;
		
	}

	//Add the program to the list
	runningProgram.push_back(Programs);
	return true;
}


//_CRT_SECURE_NO_WARNINGS

int main()
{
	list<pair<int, int>> runningProgram;
	pair<int, int> progrm1(10, 5);
	pair<int, int> progrm2(25, 15);

	   
	runningProgram.push_back(progrm1);
	runningProgram.push_back(progrm2);

	pair<int, int> progrm3(18, 7);
	printf("Program start status : %d \r\n", CanProgramStarted(runningProgram, progrm3));

	pair<int, int> progrm4(12, 10);
	printf("Program start status : %d \r\n", CanProgramStarted(runningProgram, progrm4));

}

- rsullad May 10, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Are scheduled programs always sorted in ascending order of their start times?

- Sithis April 23, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I asked this question to the interview. He said that the scheduled programs can be in any order but we can arrange it in sequence order of their start time.

- Veeru April 24, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I asked this question the interviewer. He said that the scheduled programs can be in any order but we can arrange in sequence order of their start times.

- Veeru April 24, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I asked this question to the interviewer. He said that the scheduled programs can be in any order but we can arrange in sequence order of their startTimes and take as input.

- veeru April 24, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

There are two ways to solve this:
The first approach is naive: use hash to mark all busy points in time. Whenever we want to check if a program can be added, we simply loop over its range (start -> start + duration) and checking if any of the points is already marked in the hash. The complexity is O(k) where k is the duration. One problem (major one): if a program is set to work indefinitely , the performance is poor :)

A better approach:
use set (ordered set, insert is o(log n), then use binary search to find the first elements that starts *after* the program that we want to add starting point and check if this program or the one before it (if any) are conflicting

The complexity: is o(log n) - where n is the number programs we have in the set

#include <iostream>
#include <set>
#include <sstream>
#include <stdio.h>

using namespace std;

struct Program {
    int start = -1;
    int duration = -1;
    int GetDuration() const { return duration; }
    int GetStartTime() const { return start; }
    int GetEndTime() const { return start + duration; }
    bool InRange(int t, bool checkingStartTime) const
    {
        if(checkingStartTime) {
            // t is the start time
            return t >= GetStartTime() && t < GetEndTime();
        } else {
            // t is the end time
            return t > GetStartTime() && t < GetEndTime();
        }
    }
    bool Conflicts(const Program& p) const
    {
        return InRange(p.GetStartTime(),
                   true) || // The starting point of P is conflicting with the exeuction of this program
            InRange(p.GetEndTime(), false) || // The ending point of P is conflicting with the exeuction of this program
            (p.GetStartTime() <= GetStartTime() &&
                p.GetEndTime() >=
                    GetEndTime()); // P execution time starts before this program and ends after (i.e p contains this)
    }
    // Required by std::set
    bool operator<(const Program& p) const { return GetStartTime() < p.GetStartTime(); }
    std::string ToString() const
    {
        std::stringstream ss;
        ss << "[" << GetStartTime() << ", " << GetDuration() << "]";
        return ss.str();
    }
};

bool AddIfPossible(const Program& p, set<Program>& T)
{
    // empty T? just add the program
    if(T.empty()) {
        T.insert(p);
        return true;
    }

    // end should point to the first element that its starting time is greater than or p.GetStartTime()
    auto end = T.lower_bound(p);
    // No program that start after this one?
    if(end == T.end()) {
        // get the last element and check if it conflicts with p
        auto it = T.rbegin();
        if(!it->Conflicts(p)) {
            T.insert(p);
            return true;
        } else {
            cout << "Program: " << p.ToString() << " conflicts with " << it->ToString() << endl;
        }
    } else {
        // end starts after p
        auto start = T.end();
        if(end != T.begin()) { start = --end; }

        if(!end->Conflicts(p) && (start != T.end() && !start->Conflicts(p))) {
            T.insert(p);
            return true;
        } else if(end->Conflicts(p)) {
            cout << "Program: " << p.ToString() << " conflicts with " << end->ToString() << endl;
        } else if(start != T.end()) {
            cout << "Program: " << p.ToString() << " conflicts with " << start->ToString() << endl;
        }
    }
    return false;
}

int main(int argc, char** argv)
{
    Program P1{ 10, 5 };
    Program P2{ 25, 15 };
    Program P3{ 18, 7 };
    Program P4{ 12, 10 };
    Program P5{ 28, 2 };
    
    set<Program> T;
    AddIfPossible(P1, T);
    AddIfPossible(P2, T);
    AddIfPossible(P3, T);
    AddIfPossible(P4, T);
    AddIfPossible(P5, T);

    return 0;
}

- PenChief April 23, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Approach: If the new program falls into the already scheduled program duration or if the duration range of the new program is greater and falls into the already scheduled program then we cannot schedule the new program. Else we can schedule.

I wrote the below code to the interviewer and said that the time complexity is O(n) where n is the number of new programs or scheduled programs.
He asked me to check for any other occurrences of overlappings and also asked me to reduce the time complexity. I said that we can use binary search by ordering the scheduled programs based on their startTimes and the time complexity would be O(logn). The interviewer is satisfied with O(logn) time complexity.

int[][] scheduledPrograms = { {10,5}, {25, 15} };
int[][] newPrograms = { {18,7}, {12, 10} };

public void processNewPrograms(int[][] newPrograms, int[][] scheduledPrograms) {
	for(int i=0; i< newPrograms.length; i++) {
        	int startTime = newPrograms[i][0];
			int endTime = newPrograms[i][0] + newPrograms[i][1];
			System.out.println(" Whether the Program-" + (i+1) + " can be scheduled: "+canProgramSchedule(startTime, endTime, scheduledPrograms);
                
    }
}

public boolean canProgramSchedule(int startTime, int endTime, int[][] scheduledPrograms) {
	for(int i=0; i< scheduledPrograms.length; i++) {
		int scheduledStartTime = scheduledPrograms[i][0];
		int scheduledEndTime = scheduledPrograms[i][0] + scheduledPrograms[i][1];
		// To check the new Program falls into the already scheduled Program duration.
		if( (startTime >= scheduledStartTime && startTime < scheduledEndTime) || (endTime >= scheduledStartTime && endTime < scheduledEndTime) ) {
			return false;
		} 
		//I forgot to tell below if condition to the interviewer. Later I realized and adding here now. Are there any other overlappings?
		//To check any overlapping if the duration range of new program is greater than the already scheduled programs
		else if( (scheduledStartTime >= startTime && scheduledStartTime < endTime) || (scheduledEndTime >= startTime && scheduledEndTime < endTime) ) {
		    return false;
		}
	}
	return true;
}

- Veeru April 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if newPrograms overlap with each other? For example
int[][] scheduledPrograms = { {10,5}, {25, 15} };
int[][] newPrograms = { {18,7}, {20, 2} };
In this case P4 overlaps with P3. Do we need to return [true, true] or [true, false]?

- Sithis April 24, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think your program has complexity of O(mn), m=length of scheduled Programs, n=length of new programs.

- satyam May 18, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the first newProgram (for eg., P3) can be sheduled then add it to the sheduledPrograms array and then process for P4. I didn't cover this scenario in my above coding.
Then we can return true, false for {18,7}, {20,2}.

- veeru April 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In order to schedule a new process, we need to check if there is any overlap with the existing processes.
This means a new process:
Can NOT start before the previous process is finished running.
Can NOT end after the next process starts running.

I believe this algorithm runs in O(N log N).
N processes with insertion/lookup occurring in log N time.

package sandbox;

import java.util.NavigableSet;
import java.util.TreeSet;

// Needs to implement Comparable for NavigableSet.
class Process implements Comparable<Process> {
	public Process() {

	}

	public Process(int s, int r) {
		startTime = s;
		runTime = r;
		endTime = s + r;
	}

	public int getStartTime() {
		return startTime;
	}

	public int getRunTime() {
		return runTime;
	}

	public int getEndTime() {
		return endTime;
	}

	@Override
	public int compareTo(Process p) {
		return this.startTime - p.getStartTime();
	}

	private int startTime = 0;
	private int runTime = 0;
	private int endTime = 0;
}

public class Sandbox {

	public static void main(String[] args) {
		NavigableSet<Process> set = new TreeSet<>();
		addProcess(set, new Process(10, 5));
		addProcess(set, new Process(25, 15));
		addProcess(set, new Process(18, 7));
		addProcess(set, new Process(12, 10));
		printSet(set);
	}

	public static boolean addProcess(NavigableSet<Process> s, Process p) {
		if (s.isEmpty()) {
			s.add(p);
			return true;
		}
		Process prevProcess = s.floor(p);
		if (prevProcess.getEndTime() > p.getStartTime()) { // Previous process ends after new one starts
			return false;
		}
		Process nextProcess = s.ceiling(p);
		if (nextProcess != null) {
			if (nextProcess.getStartTime() < p.getEndTime()) { // Next process starts before new one ends
				return false;
			}
		}
		s.add(p);
		return true;
	}

	public static void printSet(NavigableSet<Process> s) {
		System.out.print("Set contains: ");
		for (Process p : s) {
			System.out.print("[" + p.getStartTime() + "|" + p.getRunTime() + "]");
			if (!p.equals(s.last())) {
				System.out.print(", ");
			}
		}
	}

}

- Logan April 25, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi @Logan, It requires null check on prevProcess also bcz., if we want to add the Program like (8,1) then prevProcess will be null.

- veeru April 29, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<stdbool.h>


int processArr[50] = {10,5,25,15};

void insertprocess(int startT, int executionT)
{
     int i=0 , j= 0;

    while(processArr[i])
    {
        if(startT<(processArr[i]+processArr[i+1])||(startT+executionT)>processArr[i+2])
        {
            printf("The process can't be added");
        }
        else 
        {
           while(processArr[j])
            {
                j++;
            }
            processArr[j] = startT;
            processArr[j+1] = executionT; 
        }
        i = i+2;
    }
}

int main()
{
    int i=0, j=0;

    insertprocess(16,10);

    while(processArr[i])
    {
        printf("\n%d\n",processArr[i]);
        i++;
    }
    return 0;
}

- Udit April 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<stdbool.h>


int processArr[50] = {10,5,25,15};

void insertprocess(int startT, int executionT)
{
     int i=0 , j= 0;

    while(processArr[i])
    {
        if(startT<(processArr[i]+processArr[i+1])||(startT+executionT)>processArr[i+2])
        {
            printf("The process can't be added");
        }
        else 
        {
           while(processArr[j])
            {
                j++;
            }
            processArr[j] = startT;
            processArr[j+1] = executionT; 
        }
        i = i+2;
    }
}

int main()
{
    int i=0, j=0;

    insertprocess(16,10);

    while(processArr[i])
    {
        printf("\n%d\n",processArr[i]);
        i++;
    }
    return 0;

}

- Udit Raj April 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

here you go:
c lang

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<stdbool.h>


int processArr[50] = {10,5,25,15};

void insertprocess(int startT, int executionT)
{
     int i=0 , j= 0;

    while(processArr[i])
    {
        if(startT<(processArr[i]+processArr[i+1])||(startT+executionT)>processArr[i+2])
        {
            printf("The process can't be added");
        }
        else 
        {
           while(processArr[j])
            {
                j++;
            }
            processArr[j] = startT;
            processArr[j+1] = executionT; 
        }
        i = i+2;
    }
}

int main()
{
    int i=0, j=0;

    insertprocess(16,10);

    while(processArr[i])
    {
        printf("\n%d\n",processArr[i]);
        i++;
    }
    return 0;
}

- udit raj April 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

here we go:
c lang

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<stdbool.h>


int processArr[50] = {10,5,25,15};

void insertprocess(int startT, int executionT)
{
     int i=0 , j= 0;

    while(processArr[i])
    {
        if(startT<(processArr[i]+processArr[i+1])||(startT+executionT)>processArr[i+2])
        {
            printf("The process can't be added");
        }
        else 
        {
           while(processArr[j])
            {
                j++;
            }
            processArr[j] = startT;
            processArr[j+1] = executionT; 
        }
        i = i+2;
    }
}

int main()
{
    int i=0, j=0;

    insertprocess(16,10);

    while(processArr[i])
    {
        printf("\n%d\n",processArr[i]);
        i++;
    }
    return 0;
}

- uditrajput7830 April 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.NavigableSet;
import java.util.TreeSet;

public class OverlappingProgram {

    static class Program {
        int startTime;
        int endTime;

        Program(int startTime, int duration){
            this.startTime = startTime;
            this.endTime = startTime + duration;
        }
    }

    static boolean isOverlapping(NavigableSet<Program> programs, Program program) {

        if (programs.isEmpty()) {
            return false;
        }

        //1. Test if ceiling is overlapping
        Program ceiling = programs.ceiling(program);
        if (ceiling != null) {
            // found ceiling - test if overlapping
            if (program.endTime > ceiling.startTime) {
                return true;
            }

            //2. Test if lower to ceiling is overlapping
            Program lower = programs.lower(ceiling);
            if (lower == null){
                return false;
            } else {
                return program.startTime < lower.endTime;
            }

        } else {// no ceiling means program.startTime > existing programs
            //test for overlapping with last element
            return program.startTime < programs.last().endTime;
        }
    }


    public static NavigableSet<Program> addPrograms(Program[] inputPrograms) {
        NavigableSet programs = new TreeSet<Program>((o1, o2) -> o1.startTime - o2.startTime);

        for (Program program : inputPrograms) {
            if (!isOverlapping(programs, program)){
                programs.add(program);
                System.out.println("Added program with start date " + program.startTime);
            } else {
                System.out.println("Overlapping program with start date " + program.startTime);
            }
        }
        return programs;
    }

    public static void main(String[] args) {
        Program p1 = new Program(10, 5);
        Program p2 = new Program(25, 15);
        Program p3 = new Program(18, 7);
        Program p4 = new Program(12, 10);

        Program[] inputPrograms = new Program[] {p1, p2, p3, p4};
        addPrograms(inputPrograms);
    }
}

- kziomek0000 April 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Scala:

import scala.collection.immutable.TreeSet

case class Program(startTime : Int, duration : Int) {
  def endTime():Int = startTime + duration
}

object OverlappingPrograms {
  def main(args: Array[String]): Unit = {
    val p1 = Program(10, 5)
    val p2 = Program(25, 15)
    val p3 = Program(18, 7)
    val p4 = Program(12, 10)
    val inputPrograms = Array(p1, p2, p3, p4)
    val set = addPrograms(inputPrograms)

    set.foreach(println)
  }

  def addPrograms(inputPrograms: Seq[Program]): TreeSet[Program] = {
    inputPrograms.foldLeft(TreeSet.empty[Program](Ordering.by(_.startTime)))((acc, x) => {
      if (!isOverlapping(acc, x)) acc + x else acc
    })
  }

  def isOverlapping(programs: TreeSet[Program], program: Program): Boolean = {
    if (programs.isEmpty) {
      false
    } else {
      val ceiling = programs.from(program)
      if (ceiling.nonEmpty) {
        val nextProgram = ceiling.head
        if (program.endTime > nextProgram.startTime) {
          true
        } else {
          val lower = programs.to(nextProgram)
          lower.nonEmpty && program.startTime < lower.head.endTime
        }
      } else {
        program.startTime < programs.last.endTime
      }
    }
  }

}

- guilhebl April 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#--Python:

import sets

class program:


def __init__(self,x,y):
self.set_val = set([])

for i in range(y):
# print(i)
self.set_val.add(x+i)

print("set (" + str(x) +"," +str(y) + "): " + str(sorted(self.set_val)))


def main2():

p1=program(10,5)
p2=program(25,15)
p3=program(18,7)
p4=program(12,10)


if(p1.set_val.isdisjoint(p4.set_val) and p2.set_val.isdisjoint(p4.set_val)):
print("P4 can be added")
else:
print("P4 can NOT be added")

if(p1.set_val.isdisjoint(p3.set_val) and p2.set_val.isdisjoint(p3.set_val)):
print("P3 can be added")
else:
print("P3 can NOT be added")


main2()

- cifeadi May 02, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool CanProgramStarted(list<pair<int,int>> runningProgram, pair<int,int> Programs)
{
	list<pair<int, int>>::iterator itList;
	//if starting time falls b/w existing start and end time then No otherwise yes
	for (itList = runningProgram.begin() ; itList != runningProgram.end() ; itList++)
	{
		if (Programs.first >= itList->first && Programs.first <= (itList->first + itList->second))
			return false;
		
	}

	//Add the program to the list
	runningProgram.push_back(Programs);
	return true;
}


//_CRT_SECURE_NO_WARNINGS

int main()
{
	list<pair<int, int>> runningProgram;
	pair<int, int> progrm1(10, 5);
	pair<int, int> progrm2(25, 15);

	   
	runningProgram.push_back(progrm1);
	runningProgram.push_back(progrm2);

	pair<int, int> progrm3(18, 7);
	printf("Program start status : %d \r\n", CanProgramStarted(runningProgram, progrm3));

	pair<int, int> progrm4(12, 10);
	printf("Program start status : %d \r\n", CanProgramStarted(runningProgram, progrm4));

}

- rsullad May 10, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ata Time = Time Int Int Time Time |
  Empty deriving Show

insertInterval :: (Int, Int) -> Time -> Time
insertInterval (x, y) Empty = Time x y Empty Empty
insertInterval (x, y) (Time a b tL tR)
  | y <= a = Time a b (insertInterval (x, y) tL) tR
  | b <= x = Time a b tL (insertInterval (x, y) tR)
  | otherwise = Time a b tL tR

- Keep_learning May 11, 2019 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More