Interview practice: I solve a code challenge: Pow(x, n) on LeetCode by hand.

The following transcript was automatically generated by an algorithm.

- 00:00 : all right folks i'm going to implement
- 00:02 : the
- 00:03 : power function uh this is a
- 00:06 : challenge on the lead code website
- 00:11 : which is simply to implement the power
- 00:14 : function
- 00:15 : usually the standard library of your
- 00:17 : programming language would give this to
- 00:19 : you but
- 00:19 : in this case we're going to have to
- 00:22 : write
- 00:23 : our own it gave us a few examples
- 00:27 : such as 2 to the 10th power is
- 00:31 : the 1024
- 00:35 : some companies they don't allow you to
- 00:38 : actually execute the code so i'm going
- 00:41 : to
- 00:42 : practice doing it with only pen
- 00:45 : and paper a good damp towel here
- 00:48 : to erase off
- 00:53 : things a little faster if i need to
- 00:56 : okay and i'm going to get started so the
- 00:59 : examples are
- 01:01 : if the input is x is
- 01:05 : 2 and then n is
- 01:09 : 10 then the output
- 01:13 : then the output should be
- 01:18 : one zero two four point zero
- 01:21 : so like we're assuming floating point
- 01:23 : numbers here
- 01:26 : and then the next case is
- 01:34 : okay so i think this
- 01:38 : is just a iterative um
- 01:43 : iterative multiplication problem i
- 01:45 : believe
- 01:46 : uh because if you want to get the power
- 01:50 : of
- 01:51 : 2 so 2 to the 10th power is
- 01:54 : simply 2 multiplied by itself 10 times
- 01:58 : so you could make a loop right so for
- 02:04 : i
- 02:07 : equals i don't know 1 to 10.
- 02:11 : i'm writing in pseudo basic
- 02:15 : i guess uh i have a
- 02:18 : product i initialize it at
- 02:22 : one then i can do
- 02:26 : product equals
- 02:29 : product
- 02:33 : times two and
- 02:36 : for the uh that should give us what
- 02:39 : we're after here
- 02:40 : um however
- 02:44 : that doesn't work if the exponent
- 02:48 : is negative so in the case where the
- 02:50 : exponent is negative
- 02:53 : we should multiply it by
- 02:59 : if exponent is
- 03:02 : negative
- 03:07 : then we actually want to
- 03:11 : do product
- 03:14 : equals product
- 03:18 : times one over two
- 03:24 : of course this doesn't work just for two
- 03:26 : but uh
- 03:27 : it should work for everything uh for
- 03:30 : any base okay so
- 03:33 : let's try to write this algorithm so
- 03:37 : i'm going to write this let's write this
- 03:40 : in python
- 03:41 : because python is more terse in them
- 03:45 : and i don't have to write so much
- 03:52 : python may already have a pal function
- 03:54 : so i might have to write it
- 03:56 : with a different name so i'm gonna write
- 03:58 : it
- 03:59 : call it my pal my pal
- 04:04 : um it's gonna receive an x and an
- 04:07 : n we're gonna iterate through this sky
- 04:10 : end times basically so
- 04:14 : let's say for
- 04:20 : i in
- 04:23 : range of
- 04:26 : n and i believe that will make it
- 04:29 : iterate
- 04:30 : n times uh forgot to initialize the
- 04:34 : product
- 04:37 : so product we're gonna
- 04:41 : initialize it is one
- 04:44 : and uh now we're gonna do our for loop
- 04:48 : i in range
- 04:54 : of n which in python
- 04:58 : uh in python if you don't know that
- 05:01 : gives you a less
- 05:04 : range of n like range of let's say range
- 05:08 : of
- 05:08 : five
- 05:13 : gives you a list that is 0
- 05:16 : 1 2 3 4.
- 05:21 : i believe although in the new version of
- 05:23 : python it doesn't give you an
- 05:25 : actual list it gives you something like
- 05:27 : a lazy list
- 05:29 : so it doesn't have to allocate the
- 05:31 : memory to
- 05:32 : if if it was 1 million it will
- 05:35 : actually allocate the memory to to
- 05:39 : store all those numbers um
- 05:42 : okay so
- 05:45 : iterating through this i'm gonna say
- 05:50 : if my n
- 05:53 : is greater than zero
- 05:57 : hold up will this work if it's a
- 06:00 : negative number
- 06:04 : uh
- 06:13 : i might have to handle it initially
- 06:20 : okay so this is what i'm gonna do i'm
- 06:22 : gonna say i'm gonna
- 06:24 : say each of these
- 06:27 : each of these guys is
- 06:30 : if each of the uh parts of the product
- 06:35 : what's what's the name for this each of
- 06:37 : the the base
- 06:38 : maybe maybe it's this is called the base
- 06:42 : um i'm gonna set up a base
- 06:46 : if n is negative the base is gonna be
- 06:51 : yeah i'm just gonna write this out um
- 06:55 : i'm gonna have a base which is
- 06:58 : normally x but if
- 07:02 : n is negative then let me change the
- 07:06 : base
- 07:07 : to 1 divided by x
- 07:12 : um now i'm ready to now this space is
- 07:16 : what i'm gonna multiply by
- 07:19 : multiply into the product at every uh
- 07:22 : iteration
- 07:23 : so if i is in
- 07:28 : range of n
- 07:33 : um did i say
- 07:36 : if i meant 4 for i
- 07:40 : in range of n then product is
- 07:44 : product
- 07:47 : times base
- 07:53 : i'm going to return
- 07:56 : the product at the end
- 08:00 : okay i think that's it
- 08:04 : now i'm gonna verify this answer
- 08:07 : by um by running through this algorithm
- 08:11 : by hand okay
- 08:15 : let's use um use the
- 08:20 : input examples that we're given so
- 08:23 : the x is 2
- 08:27 : and the n is
- 08:30 : 10. i'm going to use a program counter
- 08:33 : here
- 08:33 : which is going to be
- 08:37 : this cap here so here we've initialized
- 08:41 : xq2 and n210 here
- 08:44 : i'm going to advance the program counter
- 08:48 : and execute this statement which is
- 08:50 : going to set the product
- 08:53 : two one and then we're going to advance
- 08:56 : again
- 08:57 : uh this says i'm going to create a base
- 09:00 : variable and set its value to
- 09:02 : whatever x has which is 2.
- 09:06 : i'm going to do an if statement if n is
- 09:09 : less than zero
- 09:10 : which is not true so we're skipping this
- 09:12 : next one and we're gonna go
- 09:14 : uh for i in range of n
- 09:18 : um now because this is a loop
- 09:22 : and there's actually some associated
- 09:25 : state
- 09:26 : i'm going to actually
- 09:29 : write out what the range of n would be
- 09:34 : the range of n i believe is gonna be an
- 09:37 : array
- 09:39 : that has as many items as
- 09:42 : n it's gonna start at zero
- 10:05 : okay and then i is gonna be one of these
- 10:09 : guys
- 10:09 : so i'm gonna actually put a little
- 10:14 : um maybe i need another little pointer
- 10:17 : here
- 10:18 : to remember where what i is
- 10:23 : okay so i initially
- 10:28 : is gonna be whatever this cap is
- 10:31 : pointing to
- 10:32 : is going to be zero
- 10:35 : and then we're going to advance into the
- 10:37 : loop of
- 10:38 : the body of the loop which says we're
- 10:41 : going to
- 10:41 : take the product multiply it by base and
- 10:44 : then
- 10:45 : set it back uh store it back into the
- 10:48 : variable product
- 10:50 : product is one one times
- 10:53 : base uh one times base is two so one
- 10:56 : times
- 10:57 : two is two we're going to take two and
- 10:59 : set it back
- 11:01 : into the product
- 11:09 : okay now i'm going back to the top of
- 11:10 : the loop i'm gonna move this pointer
- 11:13 : over
- 11:14 : and then that that is now gonna be the
- 11:17 : new version of
- 11:18 : i
- 11:21 : uh this is sliding down on me so i
- 11:25 : is one now i doesn't matter we're
- 11:29 : actually not
- 11:30 : using i'm not even using i
- 11:34 : so i might just not bother
- 11:38 : updating this i that's what i'm thinking
- 11:41 : because it's irrelevant um
- 11:44 : it's not getting referenced by the
- 11:46 : program
- 11:48 : um i'm just gonna have this pointer here
- 11:51 : okay so we're gonna do again product
- 11:53 : equals product times base so product is
- 11:56 : two bases two
- 11:58 : two times two is going to be four four
- 12:01 : storing four back into the product
- 12:06 : so four
- 12:09 : okay uh now moving this pointer over
- 12:13 : by another one and now we're gonna do it
- 12:16 : again
- 12:16 : four times two store it back two
- 12:19 : products four times two is
- 12:20 : eight we're gonna
- 12:24 : move this over one more time maybe i do
- 12:26 : it here
- 12:28 : so it won't drop
- 12:31 : uh okay we do this again product time
- 12:34 : space
- 12:35 : 8 times 2 is going to be 16
- 12:43 : 16 okay
- 12:46 : move this over again
- 12:50 : do the same thing 16 times 2 34.
- 13:00 : at 32 sorry
- 13:04 : uh okay
- 13:08 : i'll move this over one more um
- 13:12 : so 32 times two now is 64.
- 13:22 : move over one more 64 times two
- 13:25 : is going to be 128
- 13:35 : okay move it over one more 128 times two
- 13:39 : is going to
- 13:39 : be 256
- 13:48 : 256 okay move it over another one
- 13:52 : 256 times 2 is going to be 5 12
- 14:01 : and then move it finally
- 14:05 : this one one more time 2 times 5
- 14:08 : 12 is going to be 10 24.
- 14:14 : and then we're at the end of the range
- 14:16 : so we jump
- 14:17 : to the jump out of the for loop and
- 14:20 : we're going to return the product
- 14:22 : which is 1024. so return
- 14:25 : value
- 14:28 : is 10 24. uh that is the exact
- 14:33 : the expected output so we're good here
- 14:35 : for example number one
- 14:37 : let's go to example number two
- 14:40 : so our x again oh x is going to be 2.1
- 14:47 : n is going to be three okay
- 14:51 : all right we're initializing the product
- 14:55 : to one and then we're going to
- 14:58 : set the base to be
- 15:01 : x which is 2.1 and then if
- 15:05 : n is less than 0 which it's not
- 15:09 : so we're skipping the next statement
- 15:12 : and going to the for loop and for the
- 15:14 : for loop again
- 15:15 : we're going to generate a range range of
- 15:19 : n i'm going to write it out a range of n
- 15:22 : is a range of 3.
- 15:25 : so range of three is gonna have zero one
- 15:28 : and two in it
- 15:32 : and again let's have this little pointer
- 15:35 : here
- 15:36 : that remembers where in the iteration we
- 15:39 : are
- 15:40 : now we're going to do this statement
- 15:41 : product equals product
- 15:44 : times base so product 1
- 15:47 : times base is 2.1 gets us 2.1 we're
- 15:50 : going to store
- 15:52 : 2.1
- 15:54 : back into the product and go back to the
- 15:58 : top of
- 15:58 : four to move this pointer over by one
- 16:01 : now we're gonna do this line again
- 16:03 : product time space two point one
- 16:05 : times two point one what is 2.1 times
- 16:08 : 2.1
- 16:12 : let me see if i still remember how to do
- 16:15 : multiplication
- 16:17 : so i think it's
- 16:20 : i put a zero here
- 16:24 : oh not yet not yet let's do
- 16:28 : one times two point one
- 16:32 : one times two point one is two point one
- 16:37 : and then we're going to put a 0 here and
- 16:39 : do 2 times 2.1
- 16:41 : which is 4
- 16:44 : 2 and then we're going to add them
- 16:46 : together
- 16:47 : 1 4 four where should the decimal go
- 16:52 : i think the decimal should go here so we
- 16:55 : should have gotten
- 16:58 : 4.41
- 17:01 : i hope i'm right about that
- 17:08 : i'm going to move the pointer over one
- 17:10 : more time
- 17:12 : and then we're going to do the same
- 17:13 : thing again this time we're going to do
- 17:15 : 4.41 times
- 17:18 : 2.1
- 17:22 : um okay
- 17:25 : actually i think we line them up
- 17:31 : actually i i really don't remember how
- 17:34 : to do this
- 17:34 : but i'm going to try my best um
- 17:38 : 4.41
- 17:41 : and then 2 i'm going to put a 0 here and
- 17:44 : put 2
- 17:45 : times 4 4 1 which
- 17:48 : is going to get us 8 8
- 17:51 : 2. i'm going to add these digits
- 17:53 : together
- 17:56 : this is 12 with a carry and there's
- 17:59 : nine nine two six one and where should
- 18:01 : the decimal go
- 18:02 : i believe it should go
- 18:04 : [Music]
- 18:06 : three because you can't add the the
- 18:09 : places
- 18:09 : of both from three so enter nine
- 18:13 : two six one that's what it does the
- 18:16 : expected answer so i think i got it
- 18:19 : right
- 18:24 : nine point two six one
- 18:29 : okay so oh where were at the end
- 18:33 : of the range so that's going to drop out
- 18:36 : of the forum and return the product
- 18:38 : which is
- 18:39 : the right answer okay finally
- 18:45 : let's do the last one which has input of
- 18:49 : x is two and n is
- 18:52 : negative two this is the one that's
- 18:55 : gonna exercise
- 18:56 : this if statement see if that works
- 19:00 : um okay so we're gonna initialize the
- 19:03 : product
- 19:06 : to one initialize the base
- 19:10 : to whatever x is which is two
- 19:13 : if n is less than one which is this
- 19:16 : in this case then we're going to change
- 19:18 : the base to one
- 19:20 : divided by two so 1 divided by
- 19:24 : 2 is 0.5
- 19:30 : and then now we're gonna do this for
- 19:31 : loop
- 19:33 : um
- 19:37 : ah there's a mistake because
- 19:40 : this range of n is going to be range of
- 19:45 : range of negative 2 and i don't think
- 19:47 : that's what i want
- 19:48 : i think i need to do an absolute value
- 19:52 : of n here
- 19:55 : so i'm going to go ahead and do that
- 20:09 : okay this is called just in time
- 20:13 : coding you while the computer is
- 20:17 : executing in the code you see a mistake
- 20:20 : in the code
- 20:20 : you fix it just in time before the
- 20:23 : computer executes
- 20:25 : anyway so now that with this
- 20:29 : absolute value in in in place we're
- 20:34 : gonna end up doing a range of
- 20:35 : two which is gonna give us the array
- 20:40 : or list as we say in python that has the
- 20:44 : number
- 20:44 : zero and one and we're gonna have a
- 20:46 : pointer here
- 20:48 : okay so now we're gonna do product times
- 20:53 : the base and store it back in the
- 20:56 : product so
- 20:57 : that's gonna give us a 0.5
- 21:02 : i'm going to move this pointer over and
- 21:05 : then do the same thing again
- 21:07 : here 0.5 times 0.5
- 21:10 : pretty sure that's 0.25
- 21:14 : but i will do it out just in case
- 21:19 : so 5 times 5 is 25
- 21:22 : and we have to shift the decimal point
- 21:26 : over two places because there are two
- 21:28 : places
- 21:29 : combined so 0.25
- 21:34 : is the product
- 21:41 : and then this is the end of the range so
- 21:43 : we're going to jump out of this four
- 21:45 : loop and return the product
- 21:47 : so return value is 0.25
- 21:51 : and that is the expected answer very
- 21:54 : good so
- 21:55 : i'm gonna go ahead and type this
- 21:58 : solution
- 21:59 : product 1 base equal x
- 22:02 : if n is less than 0 base
- 22:06 : is 1 divided by x
- 22:09 : i in range of absolute value of
- 22:13 : n products
- 22:17 : times base product
- 22:22 : let's try to run this code
- 22:26 : it likes it i'm gonna do a submit
- 22:30 : time limit exceeded
- 22:41 : you