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 space character and another space character 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 space characters 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 e and the r then I swap the r and then swap the f and the c the e and the t the c and the i the c and the t and the space and the e. And then there actually I don't want to swap a space with anything. If I get a space then I just put a space here 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 a and c. I wonder if what I should do is have something like front is 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. d is fine, c is 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.
Ice Gyro: Sure sure sure. So, code it up?
Space Dragon: Yeah. Let's do it.
Ice Gyro: Alright, good.
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 front and tail and…
Space Dragon: Can you use the function reverseTheWords() in the 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. current is going to just start there, and we're going to say while current spot in the array, word front is equal to the current and word tail is 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 space and 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 front and the tail. This version's going to take a start and stop and this one's just going to call the version with start and stop being set to 0 and the length.
Ice Gyro: Yeah.
Space Dragon: And then here this front and tail are 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?
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(), reverseTheWords() calls reverseWholeString() then reverseTheWords(). Your small string is basically just reverseWholeString() with this input and reverseTheWords() I would create from current is less than this thing. w start is correct your t is the end….So basically on line sixty when you pass reverseWholeString(), maybe you're looking to pass wt minus 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 wf and wt and in reverseWholeString() while f is less than t, we get the f element out, you're not implementing f here, 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 -1 before wt. Oh so this is a problem: so if current is length then it breaks right? Here you just need t--? No no, you set temp as the element at f, you put inputArray[f] as inputArray[t], and inputArray[t] is temp now. So at 51, f should go up and t should 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 inputArray? inputArray is 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 IndexOutOfBoundsException give you the value.
Space Dragon: Probably we are looping something wrong. We are sending f in?
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 wt we're just going to do the length of 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.
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(1), or 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). So O(n) plus O(n) is O(n).
Ice Gyro: Yeah yeah I agree and you're saying in space complexity it's constant O(1).
Space Dragon: Yeah because we aren't creating any extra anything at all. Yeah that question you solve in 35 minutes yeah, less than that maybe.
Ice Gyro: Well thanks, thank you very much. This was really fun I'd like to do this again. It was really nice practice.
Space Dragon: Which languages do you general program in?
Space Dragon: And how many years have you been programming?
Ice Gyro: I've been programming for….I think I got my first programming job in 1988.
Space Dragon: Oh okay, okay. Your experience is my age.
Ice Gyro: That's alright. I'm used to that kind of thing. I have a lot of co-workers in their twenties and thirties.
Space Dragon: So where are you based. Are you based in Bay Area or are you based somewhere else?
Ice Gyro: Well, I kind of like the anonymity so I'll just say I'm based somewhere else is that alright?
Space Dragon: Yeah that's fine. I'm just asking because in Bay Area usually don't see people with this much experience, mostly younger people. Yeah I'm surprised. Yeah it was nice working with you.
Ice Gyro: Yeah you too, you too. So my understanding of how this works is we each fill out some feedback and since this is my very first interview I probably won't see your feedback until I interview several more times….
Space Dragon: No no, so you will see my feedback when you give me feedback and I give you feedback, then we can see each other's feedback.
Ice Gyro: Oh good. Well I plan to do that and I'd really like to do an interview once a week or something, cause I really do want to get better, and I think gone are the days of just talking to someone for forty minutes and getting a job. I think you have to do the interviews like this.
Space Dragon: Yeah yeah.
Ice Gyro: I really like your interviewing style I think you did a great job, and I'll write up the feedback in the next few minutes and maybe we'll talk to each other again sometime.
Space Dragon: Great, thank you. See you man, see you. Good luck.
Ice Gyro: Thanks, bye bye.
Space Dragon: Yeah, definitely
Ice Gyro: Have a great day! Bye!
Space Dragon: Bye!