hey everyone my name is YK and I'm a
former software developer at Google in
this video I'm going to walk you through
the process I would personally use to
get through an actual coding intimate
question from Google here I'm going to
use a question from Google as an example
but you'll be able to use the same
process to get to programming interviews
with any company and I chose a
relatively simple problem here so that I
can explain the whole process quickly
now here's the problem you're given an
array of integers for example 1 3 2 4
which represents a number this array
represents 1324 and the problem is
writing a function that takes this array
and as 1/2 this number so your function
if you're given this array should return
1 3 to 5 which represents 1325 now how
would I solve this problem let me walk
you through the whole process I would
personally use to solve this problem
step by step step 1 start with
clarifying questions and a high-level
discussion one of the clarifying
questions you could have asked here is
could this array be empty and the
interviewer might say no it cannot be
empty and you could also ask can we
always assume that each element of this
array is always an integer between 0 and
9 now let's say it is indeed the case so
each element of this array is always an
integer between 0 & 9 and you might ask
a few more questions to clarify all the
assumptions you have once you feel like
you have enough information to start
solving this problem you should start
with a high-level discussion in this
stage just explain the ideas you have in
concept first without using too much
code and it's important not to start
coding right away especially for a more
complex problem so that you don't waste
time writing code on a solution that
doesn't work in the end for example for
this problem you might say something
like what this problem would be easy
if the given array ends with a number
that's not nice
for example for this array 1 3 2 4
because in that case we can just add 1
to the last item and we get 5 and then
copy over everything else if the last
integer is 9 so if we had for example 1
3 2 9 instead of 1 3 2 4 then we need to
change this number to 0 and then carry 1
to the next number and keep repeating
this process until we have nothing to
carry at that point we can copy over
everything else and we are done the only
tricky case for this problem is when we
have something like 999 or 999 in the
given array because then the new array
will need to be 1 0 0 0 so from our
function we'll need to create a new
array with a different length a length
for here and then we turn this new array
for this problem or maybe if the problem
is more complex I'd recommend that you
list out a few potential approaches you
could use to solve this problem for
example for this particular problem you
might say well I'm thinking about using
either an iterative approach with a for
loop or with a recursive approach with
recursion especially for a more complex
problem it's really important to list
out a few potential solutions you have
in mind
because it's rare for you to get to the
optimal solution with your first idea if
you're confident enough that your first
idea is the optimal solution then go for
it but if not list out a few potential
solutions before you start coding now on
to step 2 choose your approach and start
coding here in this example you might
say something like well I think the
iterative solution is a good solution so
let me start coding with that or if
you're not 100% sure if your solution is
correct or optimal you could also say
something like well I think the EDA
resolution is good
should I start coding with that just by
asking that question should I start
coding you're communicating more with
the interviewer which is always good in
a coding interview and you're also
making sure that you're going in the
right direction just by asking that
question now I'm going to switch to a
Google Doc to explain this idea just
like a phone interview but if you're
using a whiteboard to solve this problem
in an in-person interview it's the same
idea I'm going to use pseudocode to
explain my solution here but in the real
interview usually you're supposed to use
a real language whether it's Python Java
or JavaScript the first thing I would
recommend that you do with this type of
problem is to write your function header
in this case it might look like this
define add one or a function with the
input given array and explain the input
and the output for this function you
might say something like this function
is going to take the given array as the
input and the output will be the new
array for example if you're given 1 3 4
as the given array the output from this
function will be 1 3 5 and you might say
instead of modifying the given array
directly I'm going to create a new
instance of an array and then return
that instead this is necessary in case
for example when the given array is 9 9
9 because in that case we'll need to
return an array whose length is
different from the original array after
that start writing your solution as you
explain the code and this process will
be iterative in nature so you might
write a little bit of code and then you
might go back to thinking a little bit
about your solution and then write your
code a little bit more and my
recommendation here is to always think
with specific examples in mind as you
write code so for example with this
particular problem you might say
something like well the first thing
we'll need to do is we'll need to create
a new instance of an array and then I'm
going to create it with the length being
the same as the original array for
example 1 3 4 and if we have an edge
case
like this where we have 999 or 999 then
we'll need to create a new array again
at the end of the function and then we
turn that instead so to create a new
instance of an array with the same
length as the original one in suit code
we might write something like this
result will be the new array and then
we're initializing a new array an
integer array let's say with the length
being the same as given arrays length
and another thing we'll need to take
care of is the carry so for example if
we had 1 9 9 and then if we initialize
this array for example to 0 0 0 then
when we look at this number then we'll
know that the last digit in the new
number should be 0 and they will need to
carry 1 to this number and we'll know
that the second number should be 0 and
then carry 1 again and we'll know that
this number should be 2 and to keep
track of if we need to carry anything
we'll just initialize a new variable
called carry and then we'll set it to 1
because we need to add 1 to the last
digit and with the example we saw
earlier this example we saw that we need
to iterate over each item or each digit
from right to left so we're going to do
that with a for loop with for i from
given array length minus 1 down to 0
again with this example given array dot
length will be 3 so given array dot
length minus 1 will be 2 which will
point to this item or that's the index
for this item and then I will go from 2
to 1 to 0 so that we can iterate over
each digit and we'll need to add the
carry either 1 or 0 to the current item
the current digit will do that with some
eCos given array square brackets I the
current digit plus carry and if this sum
is equal to 10
we'll set care
to one because we'll need to carry one
to the next number and if some is not
equal to ten or else we'll set carried
to zero and the current digit in the new
number or result of square brackets I
for example if we're examining this
number right here we're talking about
this digit that number or result square
brackets I should be some mod 10 and
this is just to say if the sum is ten we
should have zero end result and if the
sum is less than 10 we should have the
same number as some in the result for
example if the sum is 5 5 mod 10 will be
just 5 now this takes care of most cases
except for this case when all the digits
are 9 in that case what we would have is
we'd have 0 0 0 as the current result
and the carry at that point will be 1
because of course when we are examining
this number the carry there is 1 and 1
plus 9 is 10 and they will have carry
equals to 1 so after the for loop
if carry is still equal to 1 that means
we have a case like this where all the
digits are 9 we're going to take care of
that by creating a new array and
assigning it to result with a new
integer array given array the length
plus 1 so we're creating a new array
here with the length being one item
longer than the given array and assuming
that this initializes an array with all
the elements being 0 we'll just need to
set the first item to one and that way
we'll be able to take care of this case
when all the items are 9 after that just
return result and that's my solution now
step 3 check your solution and discuss
performance such as time and space
complexity I've copied over the code we
had earlier right here to check your
solution you should walk through your
code line by line using maybe a few
weeks
simples and make sure it works and
here's how I would do it let's think of
one example for example one two nine
nine as the input given array then we
can just look over this code line by
line carry will be 1 and then result at
the beginning will be let's say 0 0 0 0
because this is just an array of the
same length as the original array after
that we're going to run a for loop for I
from given array length minus 1 given
array dot length is 4 so I will start at
3 and it'll go to 2 to 1 to 0 when I is
equal to 3
we'd be examining these elements and the
total will be given array square
brackets 3 which is 9 plus carry which
is 1 so the total will be 10 and since
total is 10 carry will still be 1 and
the current item of result or real
result square brackets I or result
square brackets 3 in this case will be
total mod of 10 which is 0 and we go to
the next value of I which is 2 we're
going to repeat the same thing and the
current value of result will be 0 carry
will still be 1 and then I becomes 1
when I is equal to 1 total this time
will be given a race car buckets I which
is 2 plus carry which is 1 and so total
will be 3 and since total is not equal
to 10 Kerry will be 0 and then result
will be 3 mod 10 which is 3 so the
current value of result will be 3 and
since at that point Kerry will be 0
total will be just given a race car
buckets I plus carry but we can just
ignore Kerry since its darrell and total
here will be 1 and Kerry will still be 0
and the current item in the result array
or results car bracket 0 will be total
mod 10 which is 1
after that since Carrie is not equal to
one it's still zero we're going to
return results which is one three zero
zero so that's how you can go through
one example to be sure you can go
through a few other examples too
for example 999 or just zero now in this
particular example the space complexity
and the time complexity are fairly
simple let's first think about time
complexity because we go through this
entire array at most once or twice when
we create a new array in the case of 9 9
9 the time complexity is Big O of n
where n is the number of items in the
given array the space complexity will be
big-oh of n as well because the most we
create the most space we create is for
the new array which is Big O of N and
that's the framework I would personally
use for cracking a googol coding
interview or coding interviews from any
other company for that matter if you
like this video I would also recommend
my course on udemy 11 essential coding
into big questions and that's the
framework I would personally use for
cracking a Google coding interview or
coding interviews from any other company
for that matter if you like this video I
would also recommend my course on udemy
11 essential coding into big questions
in which I cover eleven of the most
essential coding interview questions to
master for your next coding interview in
case you're interested in taking a
course I put a discount code below in
the description or our thanks for
watching this video and I'll see you
soon