Google Interview Question for Senior Software Development Engineers


Team: TEZ
Country: India
Interview Type: In-Person




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

import java.util.HashSet;

public class TaskNode 
{
	private char taskName;
	
	private HashSet<Character> preRequisites;
	
	private HashSet<Character> dependents;
	
	public TaskNode(char taskName)
	{
		this.taskName = taskName;
		this.preRequisites = new HashSet<Character>();
		this.dependents = new HashSet<Character>();
	}
	
	public void addDependent(char task)
	{
		this.dependents.add(task);
	}
	
	public void addPrerequisite(char task)
	{
		this.preRequisites.add(task);
	}
	
	
	
	public char getTaskName() {
		return taskName;
	}

	public HashSet<Character> getPreRequisites() {
		return preRequisites;
	}

	public HashSet<Character> getDependents() {
		return dependents;
	}

	@Override
	public boolean equals(Object node)
	{
		if((node == null) || !(node instanceof TaskNode))
			return false;
		else
		{
			TaskNode otherTask = (TaskNode)node;
			return (this.taskName == otherTask.taskName);
		}
	}
	
	@Override
	public int hashCode()
	{
		return (int)(this.taskName);
	}
}


public class TaskDependency 
{
	private HashMap<Character, TaskNode> graph;

	public TaskDependency()
	{
		this.graph = new HashMap<Character, TaskNode>();
	}

	public void addTask(char preRequisite, char dependent)
	{
		// add dependent to source
		TaskNode node = this.graph.getOrDefault(preRequisite, new TaskNode(preRequisite));
		node.addDependent(dependent);
		this.graph.put(preRequisite, node);

		// add pre-req to dependent
		TaskNode node2 = this.graph.getOrDefault(dependent, new TaskNode(dependent));
		node2.addPrerequisite(preRequisite);
		this.graph.put(dependent, node2);
	}

	public String getRunlist() throws UnsupportedOperationException
	{
		List<TaskNode> initialNodes = new ArrayList<TaskNode>();

		// get the nodes which have zero pre-requisites
		for(char key : this.graph.keySet())
		{
			if(this.graph.get(key).getPreRequisites().size() == 0)
			{
				initialNodes.add(this.graph.get(key));
			}
		}

		if(initialNodes.size() == 0)
		{
			throw new UnsupportedOperationException("Impossible sequence !");
		}

		HashSet<Character> doneTasks = new HashSet<Character>();
		HashSet<Character> queuedTasks = new HashSet<Character>();

		Queue<TaskNode> bfsQueue = new LinkedList<TaskNode>();
		StringBuilder runList = new StringBuilder();

		for(TaskNode node : initialNodes)
		{
			doneTasks.add(node.getTaskName());
			runList.append(node.getTaskName());

			for(char dependent : node.getDependents())
			{
				if(!doneTasks.contains(dependent))
				{
					if(!queuedTasks.contains(dependent))
					{
						queuedTasks.add(dependent);
						bfsQueue.add(this.graph.get(dependent));
					}
				}
			}
		}

		while(!bfsQueue.isEmpty())
		{
			TaskNode node = bfsQueue.remove();

			if(!doneTasks.contains(node.getTaskName()))
			{
				boolean areAllPreqDone = true;
				for(char preReq : node.getPreRequisites())
				{
					areAllPreqDone = areAllPreqDone & doneTasks.contains(preReq);
				}

				if(areAllPreqDone)
				{
					runList.append(node.getTaskName());
					doneTasks.add(node.getTaskName());
				}
			}

			for(char dependent : node.getDependents())
			{
				if(!doneTasks.contains(dependent))
				{
					if(!queuedTasks.contains(dependent))
					{
						queuedTasks.add(dependent);
						bfsQueue.add(this.graph.get(dependent));
					}
				}
			}
		}

		return runList.toString();
	}
}

- Interviewer February 07, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You missed the part where the graph could have a circular dependency.
In that case also Execution sequence is not possible.

- SM February 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class TaskDependency {

	HashSet<Task> noPreReqs = new HashSet<Task>();

	public void addTask(Task prerequisite, Task dependent) {
		prerequisite.dependency.add(dependent);
		dependent.prerequisite.add(prerequisite);
		noPreReqs.remove(dependent);
		if (prerequisite.prerequisite.isEmpty()) {
			noPreReqs.add(prerequisite);
		}
	}

	public List<Task> getExecutionSequence() {
		List<Task> executionSequence = new ArrayList<Task>();
		List<Task> toBeProcessed = new ArrayList<Task>(noPreReqs);

		while (!toBeProcessed.isEmpty()) {
			Task task = toBeProcessed.remove(0);
			executionSequence.add(task);
			for (Task dependent : task.dependency) {
				dependent.prerequisite.remove(task);
				if (dependent.prerequisite.isEmpty()) {
					toBeProcessed.add(dependent);
				}
			}
		}

		return executionSequence;
	}

	public static void main(String args[]) {
		TaskDependency td = new TaskDependency();
		List<Task> inputTasks = new ArrayList<Task>();
		for (int i = 0; i < 10; i++) {
			inputTasks.add(new Task("T" + i));
		}

		td.addTask(inputTasks.get(0), inputTasks.get(1));
		td.addTask(inputTasks.get(0), inputTasks.get(2));
		td.addTask(inputTasks.get(1), inputTasks.get(3));
		td.addTask(inputTasks.get(2), inputTasks.get(3));
		td.addTask(inputTasks.get(3), inputTasks.get(4));
		td.addTask(inputTasks.get(2), inputTasks.get(4));
		td.addTask(inputTasks.get(1), inputTasks.get(5));
		td.addTask(inputTasks.get(3), inputTasks.get(5));
		td.addTask(inputTasks.get(0), inputTasks.get(6));
		td.addTask(inputTasks.get(4), inputTasks.get(6));
		td.addTask(inputTasks.get(6), inputTasks.get(7));
		td.addTask(inputTasks.get(8), inputTasks.get(7));
		td.addTask(inputTasks.get(8), inputTasks.get(9));

		System.out.println(td.getExecutionSequence());
	}
}

class Task {
	String name;
	Set<Task> prerequisite;
	Set<Task> dependency;

	public Task(String name) {
		this.name = name;
		prerequisite = new HashSet<Task>();
		dependency = new HashSet<Task>();
	}

	public int hashCode() {
		return name.hashCode();
	}

	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Task other = (Task) obj;
		if (name == null) {
			if (other.name != null)
				return false;
		} else if (!name.equals(other.name))
			return false;
		return true;
	}

	public String toString() {
		return name;
	}
}

- Viv February 18, 2018 | 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