Space Dragon, a LinkedIn engineer, interviewed Ice Gyro in Java
Reverse Word in String
Given a string with multiple words and spaces represented as a character array. Write an in-place algorithm to reverse the order of words in the string. Example: convert ['p', 'e', 'r', 'f', 'e', 'c', 't', ' ', 'm', 'a', 'k', 'e', 's', ' ', 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e'] to ['p', 'r', 'a', 'c', 't', 'i', 'c', 'e', ' ', 'm', 'a', 'k', 'e', 's', ' ', 'p', 'e', 'r', 'f', 'e', 'c', 't']
Feedback about Ice Gyro (the interviewee)
Advance this person to the next round?
How were their technical skills?
How was their problem solving ability?
What about their communication ability?
In interviews, problem solving ability is considered very important. Failing to come up with the answer is a no deal. But you had written the code so beautifully that how could I say no :) PS: You have nice personality :)
Feedback about Space Dragon (the interviewer)
Would you want to work with this person?
How excited would you be to work with them?
How good were the questions?
How helpful was your interviewer in guiding you to the solution(s)?
Please keep doing what you're doing! You did a great job explaining the problem and helping me think about it. You guided my thinking with examples until I saw the solution. It's really good to talk and talk about the solution before the coding starts. If the probing questions (are you looking now? Are you in the bay area?) are normal that's fine; I didn't answer any question I did not want too. e.g. I declined to say where I live & work. My understanding from reading the introductory materials that Interview.io is anoymous. I'm looking forward to having my interviews (this was my first). I hope all of the interviewers are as good as you are! GREAT WORK! Many thanks!!!
Ice Gyro: Yeah can you hear me? Space Dragon: Yeah I can hear you now, thank you. Ice Gyro: Yeah I can hear you. Thanks for the skype invitation. Space Dragon: Let's jump in the question right away. Just one quick question: are you actively interviewing right now? How much are you prepared? Ice Gyro: I'm not very prepared. I'm not actively interviewing right now. I work as a programer. I'd like to get better. This is my first every time doing interviewing.io Space Dragon: Okay cool. What programming language are you most comfortable with? Ice Gyro: Java. Space Dragon: Okay cool, I'll just write the question on top here. So you basically have an array and it has something like this….So here is the array:
[ 'p', 'e', 'r', 'f', 'e', 'c', 't', ' ', 'm', 'a', 'k', 'e', 's', ' ', 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e' ]If you notice there is a
spacecharacter and another
spacecharacter later on as well. We want to convert this array into “
practice makes perfect.” Ice Gyro: So it's moving the letters around is what you want to do. Space Dragon: Yeah, but what's important is that we have an array of characters and spaces in between. This whole list basically has words in reverse order, you know? So this array is basically: “
perfect makes practice” and you convert it to “
practice makes perfect.” Ice Gyro: Yeah I think I understand. Space Dragon: And the only thing that is given is that there can be one or more
spacecharacters between two words. So you have to make such a string into this, but it has to be in-place, you cannot use any extra anything. Ice Gyro: Oh, in-place. I was thinking to make a brand new array. Space Dragon: Do it in-place. Maybe before even writing the code we can discuss how you plan to do it? Ice Gyro: Yeah so. If it was not in-place. I would allocate a brand new array, find where the spaces are and read them with
indexOf()and copy the words into the spot. But since I don't have an extra array to work with that makes it a bit more tricky especially because I'm assuming the length of the words are not going to be the same. I'm not counting but the last word of the list might be shorter or longer than the first word in the list. Space Dragon: Exactly. That is true. Ice Gyro: And when you say swap it in place I'm thinking that I can't use any kind of temporary array. The most I could use is a single character array. So I need to basically move the first letter of the first word and swap it with the first letter of the last word and then the second letter of the first word with the second letter of the last word and so on. And when I do that one of the problems I think might happen is: suppose the first word is quite a bit longer than the last word, then I'm going to have all these blanks and in order to make everything fit, I wonder if I'm going end up sliding over the letters and stuff. So the requirement that it be done in-place seems to make the problem more difficult. Space Dragon: Yeah exactly. Ice Gyro: Yeah I don't mind, I'm here to get better. And if this first word is very very short. Like if this first word is just “g o,” then I would have to move things over quite a bit before I was able to put in this eight letter word. I would have to swap the first two letters, then go “golly I'm out of space,” and move things over a little bit. One of the things I'm not good at yet is recursive solutions and I kind of think this is perhaps is a thing that a recursive solution would be really good for, but even though I can kind of smell the recursion, I don't think I could do that in the half an hour we have. Space Dragon: Maybe think about this. This is a relatively easier question once you know how to do it. There's something over there if you could think about that. Just think what strategies are there to make the last word in the beginning. Ice Gyro: So just start with the last word in the beginning, is that it? Space Dragon: So basically you can do some interplay of words here. I mean you can just look at the list and….There's one small thing that will make the whole question solved in that aspect, so a hint would be giving you an answer, but if you just look at the structure of the array, then you can think about how you could iteratively think about how you can get the last word in the beginning and the second last word in the second place and so one. Ice Gyro: By pasting it down here and reformatting it a little bit I'm hoping I'll see the thing that will help. Not very familiar with the editor but in eclipse this is the trick for telling it not to format. So I wonder if I can take advantage of the letter being the same like: the first letters are both “
p”s I don't have to move it, then I swap the
rthen I swap the
rand then swap the
e. And then there actually I don't want to swap a
spacewith anything. If I get a
spacethen I just put a
spacehere so we can have multiple spaces around things. So I could try that, but I still don't think that's the answer because if this were a very short word up front…. Space Dragon: Let me put it like this: what if the input array was something like this:
['a', ' ', 'b', ' ', 'c']. How would we approach this sort of input? Ice Gyro: Right so, here I would want to swap
c. I wonder if what I should do is have something like
frontis where the
a.... Space Dragon: Try to build the algorithm first. If you know this sort of input the output would have been like:
['c', ' ', 'b', ' ', 'a']. Ice Gyro: Right, that's correct. Space Dragon: So for this input we have the reverse of output. This is the reverse of input. Ice Gyro: So you don't have to be aware of where the words are at, you can just swap things sometimes. Space Dragon: Yeah, if word is just one character, you could simply reverse the whole array. What if word is more than a character? What would happen then? Ice Gyro: Then instead of reversing the whole thing you would want to treat the sequence of characters as one unit. Space Dragon: Exactly, exactly. One is to do that even if you don't do that, what will happen is something like this: if you had a and say, b together and then we had space c and space d together
['a', 'b', ' ', 'c', ' ', 'd']this would return something like
['d', ' ', 'c', ' ', 'b', 'a']right? Ice Gyro: Yeah, yes yes. Space Dragon: But this is not something you're looking for.
cis fine, but this word is reversed right? Ice Gyro: Yeah that should be “
'a', 'b'” Space Dragon: Yeah, so how can you fix that then. Ice Gyro: I could go through and find the individual words and then just reverse them in place. I think I see it now: you reverse the entire string, then you reverse each word in place. Space Dragon: Or: you reverse each word in place, and then reverse the entire string. That is also fine. Ice Gyro: Very nice, thank you! That's an absolutely delightful problem, I like it very much. Space Dragon: Yeah that's the problem with this: if you start helping the person it's very easy that you just tell the whole solution. Anyways let's start the coding. [14:04] Ice Gyro: Sure sure sure. So, code it up? Space Dragon: Yeah. Let's do it. Ice Gyro: Alright, good. [15:22] Ice Gyro: Alright, so it seems to me that there might be two cases: one where it's an odd number and one where it's an even number but I'm not sure about that. So I'm just going to have
tailand… Space Dragon: Can you use the function
reverseWholeString()? Oh sorry my bad my bad. Ice Gyro: Oh no worries, I appreciate your suggestions. You're a very good teaching interviewer, it's very nice. Space Dragon: Okay so that looks okay to me and if I were at my desk in my old friend Eclipse I'd do this inside of some unit tests and have some asserts, but that's not the style of interviews just yet. So that's okay.
currentis going to just start there, and we're going to say while
currentspot in the array, word
frontis equal to the
tailis equal to....So if it was a string it would have an
indexOf()but since it's a character array it doesn't have an
indexOf(). And we're going to look for
space, so we find the first
spaceand now we know where the word is, so it's time to reverse the string there. I think I can reuse this reverse the string business by passing in the
tail. This version's going to take a
stopand this one's just going to call the version with
stopbeing set to
length. Ice Gyro: Yeah. Space Dragon: And then here this
tailare really the badly named variables, but in the interest of time I'm not going to change their names. Alright so,
reverseWholeString(), and once that's done then we need to move current up to the tail plus one and that looks reasonable to me. Then we're going to have this
indexOf()guy, and it's going to go and look for a particular character. Ice Gyro: Maybe one more thing you want to put in
indexOf(): from where to start looking for. Space Dragon: Oh that's a great idea, thanks. Ice Gyro: Okay so, makes lots of sense. Off the top of my head, it looks pretty good. What I would do if I was just doing this for fun to learn is I'd do it as J in it, but since I don't think I have that, I'm just going to output the input array. Is it okay if I run it? [22:14] Space Dragon: Okay yeah we have some errors that you can address. One more thing that you did is while reversing the string….Here is main, from here we go to
reverseTheWords(). Your small string is basically just
reverseWholeString()with this input and
reverseTheWords()I would create from
currentis less than this thing.
w startis correct your
tis the end….So basically on line sixty when you pass
reverseWholeString(), maybe you're looking to pass
wtminus one. Ice Gyro: On line 60? Yes yes, you're absolutely correct. Space Dragon: And then the current word increment by plus one and next you enter the loop, here are just
fis less than
t, we get the
felement out, you're not implementing
fhere, in this while loop. While loop at 47. Ice Gyro: Yes, that is a big problem. Space Dragon: And I like the thing you did at line 60 where you wrote
wt. Oh so this is a problem: so if
lengththen it breaks right? Here you just need
t--? No no, you set
tempas the element at
f, you put
tempnow. So at 51,
fshould go up and
tshould come down right? Ice Gyro: Okay, yeah that makes sense. Space Dragon: Yeah exactly. It's fine to me now. Ice Gyro: Let's just try it. Space Dragon: On line 43,
reverseWholeString()….Yeah you also need to pass in the initial word. You have to pass in the array as well. Ice Gyro: Okay let's try that. Space Dragon: At line 61 there's another error. It cannot find
inputArrayis misspelled here. Ice Gyro: Okay, I'll fix that. Space Dragon: Yeah I guess it's fine can you run it again? Ice Gyro: Yeah let's try it. Okay one more: on line 61. And do you think twenty two is the value? Oh I don't think that
IndexOutOfBoundsExceptiongive you the value. Space Dragon: Probably we are looping something wrong. We are sending
fin? Ice Gyro: Yeah. Space Dragon: So what is
f? Ice Gyro: So little off, way to high. So line 43 is calling it. Ah here we go: like that. Space Dragon: Yeah so the last one is wrong here: “perfect.” So we never entered the loop for the last one right? So we can address that very easily. Ice Gyro: So here's where we're reversing the individual words in place. Space Dragon: The last word didn't. Ice Gyro: Oh right here, what if we just say...and instead of
wtwe're just going to do the
inputArray. Space Dragon: Yeah. Ice Gyro: That was really fun, what a good time. Space Dragon: Yeah someone asked me and never gave me any clue and took me like thirty minutes to think how to do it. Yeah you did good, you created a function and used those functions and that's very nice because that isn't something that comes to mind intuitively. So yeah, it was great work here. [29:27] Space Dragon: And can you tell me the asymptotic bounds on it? What would be the runtime of this? Ice Gyro: So we loop through the entire array and we do that a couple of times so I think if the size of the input is the length of the character array I think this is a linear time complexity:
O(n). And in space complexity I think it's
O(1), actually it's really fuzzy in space complexity because you're going to need that input array. So space complexity is either constant
O(n). Space Dragon: It isn't
O(n). It's always constant right because we're not building any extra space anywhere so it will always remain constant, apart from the array that was given to us. That's why it's in-place right. And as the runtime is concerned you inverted a string once,
O(n)and plus you invert each word again and that at most is
O(n). Ice Gyro: Yeah yeah I agree and you're saying in space complexity it's constant