Solving My Google Phone Interview Question

Summary

In this video, the creator walks through the Google phone interview process, specifically focusing on a coding problem involving trees and depth-first search. The video explains how candidates are required to write code in a Google Doc without IDE support, encouraging proficiency in the coding language. The example problem involves printing a tree structure from a list of parent-child relationships. The solution utilizes a HashMap for depth-first traversal and discusses the time and space complexity of the approach. The video also provides tips for tackling coding interviews, and encourages viewers to practice in similar environments.

Takeaways

• 📱 The video discusses the Google phone interview process and coding challenges.
• 🔗 A link to the full Google interview experience and Amazon phone interview is provided in the description.
• 📝 During the Google phone interview, candidates code in a Google Doc without code completion or syntax error checking.
• 💡 It is recommended to practice writing code in Google Docs before the interview to get familiar with coding without an IDE.
• 🌳 The coding prompt provided involves writing a Java function to print a tree based on a list of parent-child relationships.
• 🔍 The solution involves using a depth-first search (DFS) approach to navigate the tree structure.
• 📄 An adjacency list (represented using a HashMap) is used to store the tree relationships, where each parent points to its children.
• 🧠 To find the root of the tree, the candidate can create a set of all children and loop through the keys to identify the root node.
• 🧮 The time complexity of the solution is O(n), where n is the number of nodes in the tree, and the space complexity is also O(n).
• ✅ The provided solution passed the interview, allowing the candidate to advance to the on-site interview round.

Q & A

What is the primary topic discussed in the video?

The primary topic discussed is the Google phone interview, including how to prepare for it and solve a specific coding problem given during the interview.

What is the first tip provided for preparing for the Google phone interview?

The first tip is to practice writing code in a Google Doc without code completion or syntax error checking, as the interview environment does not provide these features.

What is the coding problem presented in the Google interview example?

The coding problem involves writing a Java function called `printTree` that prints a given tree to standard output based on a list of parent-child relationships.

What data structure is recommended for solving the problem in the video?

The video suggests using an adjacency list, which is represented by a HashMap, where each parent node is a key and the corresponding value is a list of its children.

What approach is used to traverse the tree in the given solution?

The video uses a Depth-First Search (DFS) approach to traverse the tree, printing each node along the path and keeping track of the level to format the output correctly.

How is the root of the tree determined in the solution?

The root of the tree is determined by looping through all the parent nodes and checking which one is not a child in the relations. This node is the root since it has no parent.

What challenge did the presenter face when implementing the solution?

The presenter mentions that the biggest challenge was determining the root of the tree, as an extra set was required to store all the child nodes.

What is the time complexity of the solution provided?

The time complexity is O(n), where n is the number of nodes in the tree. The algorithm loops through the nodes multiple times, but constants are dropped in Big-O notation.

What is the space complexity of the solution provided?

The space complexity is also O(n) since the algorithm uses extra space for the adjacency list and the set of child nodes, which both can store up to n elements.

What advice is given for candidates who don’t understand the problem during the interview?

The video advises candidates to ask questions during the interview to ensure they fully understand the problem before trying to solve it.

Outlines

00:00

📱 Google Phone Interview Overview and Coding Tips

The video begins with the host thanking the audience for watching and introduces the topic: the Google phone interview process. It references other videos about interview experiences at Google and Amazon. The Google phone interview requires coding in a Google Doc, without code completion or syntax error checking, making it challenging for those accustomed to IDEs. The video suggests practicing in a Google Doc beforehand to ensure familiarity with a language. The plan for the video is explained, which includes discussing the interview prompt, outlining an algorithm, writing code, and analyzing the solution.

05:00

🧠 Understanding the Google Interview Problem Prompt

The speaker introduces the coding problem from the Google interview: to write a Java function `printTree` that prints a tree structure based on a stream of parent-child relationships. An example set of relations is provided where animals like 'mammal' and 'bird' are siblings under the 'animal' node, and 'animal' is a child of 'life-form'. The function must print the tree in a specific format using a depth-first search. The problem is analyzed as a tree traversal challenge, where nodes like 'bird' and 'fish' are printed in a structured manner as children of 'animal'.

10:02

📝 Steps to Solve the Tree Printing Problem

The speaker explains the process of solving the tree-printing problem. The first step is to convert the list of relations into a data structure, such as a HashMap, to allow depth-first search (DFS) traversal. The relations are treated like an adjacency list representing a graph. Next, the depth is tracked to ensure proper indentation (tabs) when printing child nodes. Since the root node is not explicitly provided, a method to find it is described by identifying a node that is not a child of any other node. The algorithm's high-level structure is explained with each step outlined.

🔍 Implementing the Tree Structure and Depth-First Search

The speaker walks through the code implementation. First, a HashMap is created to represent the adjacency list of the tree, and a set is used to track child nodes. The speaker explains how to loop through relations to fill the map with parent-child relationships. Then, by looping through the map keys and checking if they are in the child set, the root node is identified. A depth-first search (DFS) is performed, recursively visiting each child and printing the appropriate number of tabs based on the depth level. The DFS ensures the tree is printed in the correct format.

🐾 Testing and Analyzing the Code

After implementing the solution, the code is tested, and some adjustments are made to ensure the output matches the expected format. A minor issue with printing is corrected by changing a newline statement. The correct tree structure is printed, displaying 'life-form', 'animal', 'mammal', and their respective children. The time and space complexity of the solution is analyzed, both of which are O(n), where n is the number of nodes in the tree. The speaker reflects on the solution, acknowledging that the extra data structure for finding the root might be unnecessary but was sufficient to pass the interview.

Keywords

💡Google phone interview

A Google phone interview is a remote interview process conducted by Google to assess potential candidates' technical skills and problem-solving abilities. In the video, the speaker discusses their experience with the Google phone interview, emphasizing the importance of being able to write code without the aid of an IDE, which is a common feature in such interviews.

💡Google Doc

Google Docs is a free web-based office suite that allows for collaborative editing of documents in real-time. In the context of the video, the speaker mentions that candidates are expected to write code in a Google Doc during the interview, simulating the experience of coding without the benefits of an integrated development environment (IDE).

💡Proficiency

Proficiency refers to the state of being highly skilled or competent in a particular area. The video emphasizes that candidates should be proficient in the programming language they claim to know, as they will be expected to write code without code completion or syntax error checking.

💡Depth-first search

Depth-first search (DFS) is a traversal algorithm used in graph theory and computer science. It starts at a given node and explores as far as possible along each branch before backtracking. In the video, the speaker explains that the problem they were given during the interview required a depth-first search approach to print out a tree structure.

💡Adjacency list

An adjacency list is a collection of lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph. The video script describes using an adjacency list to represent the tree structure for the interview problem, where each parent node points to a list of its children.

💡IDE

An Integrated Development Environment (IDE) is a software application that provides comprehensive facilities to computer programmers for software development. The video discusses the challenge of coding without the assistance of an IDE during phone interviews, which is a skill that candidates are expected to have.

💡Siblings

In the context of the video, siblings refer to nodes in a tree that share the same parent. The speaker mentions that the order of the pairs in the input list determines the nodes' order with respect to its siblings, which is an important detail in how the tree is printed out.

💡Time complexity

Time complexity in computer science is the computational complexity that describes the amount of computer time taken by an algorithm. The video script includes an analysis of the time complexity of the solution provided, which is O(n), where n represents the number of nodes in the tree.

💡Space complexity

Space complexity is the amount of memory space required by an algorithm. The video script discusses the space complexity of the solution, which is also O(n), accounting for the storage of the adjacency list and the children set used in the algorithm.

💡Recursion

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem. The depth-first search algorithm described in the video uses recursion to traverse the tree, printing out nodes and then recursively printing their children.

💡Root

The root of a tree is the topmost node in a tree data structure from which all other nodes are descendants. The video script describes how to find the root of the tree, which is essential for starting the depth-first search. The root is identified as a node that is not a child of any other node.

Highlights

The Google phone interview requires coding in a Google Doc, without the support of code completion or error checking, making it important for candidates to be proficient in their chosen language.

The interviewer expects candidates to be able to write code in a plain text environment, showcasing their mastery of coding syntax and structure without an IDE.

Candidates should practice coding in a Google Doc to prepare for the interview environment, as this format is designed to test deep familiarity with the programming language.

The core problem presented in the interview is to build a tree structure from a series of parent-child relationships and print it in a hierarchical format using a depth-first search algorithm.

The interviewer provides a list of unordered parent-child relationships, and the candidate must organize them into a tree structure.

The key challenge of the problem is identifying the root of the tree, which requires determining which node does not appear as a child in any of the relationships.

Depth-first search (DFS) is employed to traverse the tree and print the nodes in the required hierarchical order.

Using a HashMap (adjacency list) to store the parent-child relationships is suggested as an efficient approach for building the tree structure.

The algorithm needs to keep track of the current depth in the tree to ensure proper indentation when printing the hierarchy.

A set is used to store all children nodes, which helps identify the root of the tree by finding a node that does not appear in this set.

The time complexity of the solution is O(n), where n is the number of nodes, as each node is visited once during the depth-first search and while building the map.

The space complexity is also O(n) due to the storage of the adjacency list and the children set.

DFS ensures that the tree is printed in the correct order, with each child printed beneath its parent node and proper indentation to represent depth.

The presenter emphasizes the importance of asking clarifying questions during the interview if the problem statement is not fully understood.

This solution was successful and led to the presenter advancing to the on-site interview stage at Google.

Transcripts

good day subscribers thank you guys so

much for watching in this video we're

going to be talking about the Google

phone interview now if you haven't

checked it out already I do have a video

talking about the entire Google

interview experience so I will leave a

link to that in the description also I

have a video talking about the Amazon

phone interview so you guys should

definitely check that out after you

watch this now in the Google find review

they will give you the prompt and that

will give you a Google Doc to write your

coding I mean you can't build and run

your code you don't have any code

completion you don't have any syntax

error checking so it definitely makes

things harder if you are used to coding

in an IDE that's why I recommend if you

are prepping for this interview you

should definitely practice writing code

in a Google Doc and they do this to

ensure that the candidate has a lot of

experience in the language that they are

coding in if you really are proficient

in a language you should be able to code

in it without needing any type of code

completion you should know the correct

spacing and where the brackets should go

etc so I think it's a good thing so how

the format of this video is going to go

is I'm going to let you guys know what

the prompt was we're gonna talk about a

high level algorithm and then we're

actually gonna write the code and then

we're gonna do some analysis on it

afterwards if you guys are enjoying the

content please go ahead and hit that

like button and please subscribe to the

channel if you haven't and with that

being said let's go ahead and take a

look at what the given problem was all

right so this is the actual prompt that

was given during the interview so the

objective is to write a Java function

print tree which prints a given tree to

STD out details the argument of print

tree is a stream of relations pairs of

parent-child relationships each string

found anywhere in the input represents a

unique node each parent can have many

children the input list may contain

relations in any order although the

order in which the pairs appear in the

input list determines the nodes order

with respect to its siblings so if we

come down here and look at an example

input we see that we're given a list of

relations and then down here we add six

relations

the first one is animal is a parent of

mammal animal is a parent of bird so

mammal and bird are siblings life form

is a parent of animal so now we have

life form points to animal points to

mammal and bird cat as a parent of Lion

mammal is a parent of

an animal is a parent of fish and down

here we call this print tree which is a

static method of the tree printer class

and it takes in our input as it's

argument if we look at our output we see

that life-form is printed first so this

is going to be the root of our tree then

down here notice we have this extra

space here and then we have animal which

is a child of life-form and its child is

mammal its child is cat and cats child

is lion also down here we have bird and

fish notice that they're on the same

level as mammal meaning that these three

mammal bird and fish are children of

animal and finally if we go down to the

code that was provided we see that we

have that class tree printer we have

that method print tree which takes in

the list of relations and this right

here is where we have to write our code

and down here we have that relation

class which is a parent a child and a

constructor now if we go back and look

at the expected output notice how it's

printed out so we have the route here

first and then we have the child here

and then we have the child of animal

here so if you are familiar with graphs

and trees you recognize a pattern here

that this is actually going to be a

depth-first search basically we're going

down a certain path here down till we

get to a node that doesn't have any

children and then we go back up to the

next highest sibling so once we're done

with this path we see that we go back to

animal and we print out its next child

which is bird bird doesn't have any

children so then you would go to the

next child and you print out fish now if

this problem didn't make any sense

please make sure you go back and

re-watch it if you are in a real

interview and you don't understand the

problem make sure you ask questions and

make sure you completely understand the

problem before trying to solve it all

right so let's go ahead and move over to

the editor and see if we can come up

with a high level solution all right so

here we have our tree printer class with

the method print tree I went ahead and

moved the relation class to its own file

so it's called relation Java and has

that same parent-child relationship so

the first thing we want to do is we want

to figure out the steps that we're gonna

take to solve this problem so the first

step we want to do is we want to convert

our relations into some kind of data

structure where we can do a depth first

search on it so one thing we can use is

we can use a hash map or every pair

is the key and we can have its value be

the list of children so for example in

the example that was given we had

something like life-form and that's

going to point to a list of its children

which would be in our case just animal

an animal would be its own key pointing

to its children so in our case we would

have mammal bird and fish then down here

we had mammal which pointed to cat so

just given these three here what we

could do is we could say okay look at

light form give me give me all its

children okay we have animal now let's

do a search on animal okay we go to

animal get all its children now we'll go

to mammal look at its children and then

now we have cat once we're done we'll go

back and look at the next child of

animal okay bird well bird doesn't have

any children because it's not is it's

not a key in our map next we look at

fish fish also doesn't have any children

because it's not a key in our map now

some of you guys might recognize this

but this is actually called an adjacency

list an adjacency list is just one way

of representing a graph or a tree

because every tree is a graph right all

right so that's gonna be the first step

and when you're interviewing you want to

actually like explicitly write this up

so we could say something like loop

through relations and put all parents as

keys pointing to their children the next

step we want to do is perform a

depth-first search so we can simply say

perform depth-first search with starting

at root now one thing we want to notice

is if we go and we look at the expected

output again we do have a tab between

every parent and its child so we need to

keep track of which depth we're on and

based on the depth that's how many tabs

we're gonna have so if we go down here

perform def first search starting at

root we can also add perform depth first

search starting at root keep track of

depth to know how many tabs we need to

write and this doesn't have to be super

example or anything this is kind of more

like just just this the like a

high-level steps of what you're gonna do

now one thing that we're forgetting is

we need a way to actually get the root

right because we were given this list

here and I mean it's just the it's just

a list of pairs and it doesn't

explicitly tell us what

route is so the easiest way to get the

route is to in our first step we could

put each child in in a set we could put

each child in a set then we could have

this as our second step and make this

our third so what we can do is we can

loop through the keys of our map once we

find a key that's not in the children

set we know that that's gonna be our

route since it's not a child of anything

and this will make more sense when we

actually look at the code so let's go

ahead and do that next all right so the

first thing we need is gonna be our map

here which is going to be our adjacency

list that represents our graph we have

this pointer here which is whenever

we're going to put a new list of

children into our map as a value and

then we have our children set here which

is going to show anything that's a child

in this tree so the first thing we're

going to do is we're going to loop

through all the relations and we're

gonna put him inside our map okay so

here we're looping through each relation

if the map already has this parent we

want to go ahead and grab its list of

children and we want to add whatever our

current relation is and we're gonna

specifically add the child otherwise if

we haven't seen the key yet in her map

we're gonna go ahead and create a new

list we're gonna put the child in that

list and we're gonna put a new entry in

our map with the parent as the key and

the list as the value finally the last

thing we need to do is we need to add to

our children set and we're just going to

add the child of the current relation

we're on and since it's a set it won't

add any duplicates the next thing we

need to do is we need to find our route

so we're gonna go ahead and loop through

all the keys in our map and we're gonna

check if it's in the children set so

down here we have this for loop here and

we're just gonna basically check in this

if statement if the children set

contains the current key that we're on

in the map rather if it doesn't contain

it then we know that this is our route

and we're just gonna set root equal to

entry get key and we're gonna break out

of this for loop and at this point we

know what our route is and we have our

map so now we just need to perform the

depth-first search so down here we can

simply just call DFS which we haven't

created yet we're gonna pass in our

route

you know passing the depth right because

we need to know how many tabs to print

and then we also need to pass it in our

map all right so this is what our

depth-first search is going to look like

it's going to take in the string which

is the root the level that we're on and

the map the first thing we're gonna do

is we're going to print out as many tabs

as the level that we're on

once we do that we're going to print out

the route

we need to get all the children of that

room

you

so the first thing we're going to do is

we need to check if the map actually

contains that key if we're ever on a

leaf of the graph it won't have anything

as a key in the map so we need to check

against that finally once we do get the

children we need to just loop through it

and recurse

and as we are rehearsing we need to

increase the level by one so when we

print it out we're printing out an

additional tab at each level all right

so let's go ahead and hop back over to

Maine and what we can actually do is we

can go ahead and run this and down here

we see that it doesn't look right and

that's because if we go back to the tree

printer this right here is actually

going to be print instead of printing a

new line so if we go back and we go

ahead and run that we see that we do

actually get what is expected so we have

life-form animal mammal cat fly and

burden fish and up here we see that that

is the expected output so what is the

time and space complexity of this

algorithm well if we want to say that

the number of nodes in our tree is n we

are doing a four loop through all the

relations which could potentially be n

elements so that's gonna be n we do

another for loop through our map which

is also n and finally we do this

depth-first search which could

potentially be n as well so so our time

complexity here is going to be Big O of

technically we are looping three times

through the elements so it's going to be

three n but since we drop constants it's

just going to be Big O of n for the

space complexity we are creating this

map and storing all the relations in

that map so that's gonna be N we also

have this children set which is also

going to store n up to n elements we

also have this depth-first search here

which could potentially be called for

every element so again the space

complexity would be Big O of 3n which if

we drop the constant will just be n so

this is the solution that I came up with

during the interview the thing that I

was caught up with was them with the

most was the finding the root because we

are creating this extra child set this

children set here in fact and it seems

like this is extra data that could be

used but I haven't been able to think of

a better solution for this

if you

I can think of something please leave it

down in the comments but other than that

that's gonna wrap it up for this

question this solution that I wrote up

ended up passing me through to the

on-site interview so obviously in their

eyes it was an acceptable solution so I

just wanted to share that with you guys

but yeah other than that that's gonna

wrap it up for this video if you guys

have any questions or comments please

leave them down below in the comment

section for anyone who is in your being

at Google good luck I hope this video

was helpful and yeah until next time I

will see you guys in the next video

[Music]