Spasmodic Pheasant: Hello?
Intrepid Hawk: Hello.
Spasmodic Pheasant: Yeah. Can you hear me?
Intrepid Hawk: Yeah. Can you hear me?
Spasmodic Pheasant: Yeah, I can hear you, thank you.
Intrepid Hawk: Okay. This is my first time giving an interview so I'm not sure. So, is it like generally from a question bank you can take a question or how would you like to...?
Spasmodic Pheasant: Usually, I mean my previous experiences the interviewer would give me any question, and then you know we will go to discussing it.
Intrepid Hawk: Okay, okay. Let me pick one question. All right. Can you read, are you able to see the screen?
Spasmodic Pheasant: Yeah. So, yeah.
Intrepid Hawk: So, basically you are given an input string which has like your file path. So, you could have, so, typically, you could have a forward slash starting a forward slash string. So for this example, let's say you have forward slash home and then forward slash at the end. So the output should be home, because there is no... so whenever you see a dot, it means you have to stay in that directory. When you see a double dot, you have to move one level up. So in the second example, if you seea double dot, which is one directory up, so the output should be just forward slash.
Spasmodic Pheasant: Okay.
Intrepid Hawk: So another example in this input, you can see that you can also have multiple forward slashes in between. So you know, to kind of skip everything from here. So your route will be slash home slash. Then another example is, let's say you have a single dot, which means you stay on that directory. So here, what you're doing is you have a double dots or one directory up, so you skip B, you have another double dot, so you skip A, you don't do anything on the same directory. So you skip A, and your final output is forward slash C? So, you have the general idea?
Spasmodic Pheasant: Yes, I think I... let me just rephrase it so that if I'm mistaken anything, just let me know. So, can I for example, if I have foobar, then this should return foo? And can I assume that all paths will be starting with like with an absolute path from the root?
Intrepid Hawk: Yes, yes. You can assume that.
Spasmodic Pheasant: Starts with forward slash and can I also assume that, so the characters that I can expect slash dot double dot and any other characters will be part of the filename? Is that, okay. So that I can say that forward slash is going to be okay. What else? Let me check. And is it possible that, you know, I'm assuming that there's no input that's going to be null, right? It's going to be at least forward slash, right?
Intrepid Hawk: Yep. Yep. Yeah, you can assume that also. But that's. Yeah, it's kind of a corner case. You can maybe back on that input itself is empty or something.
Spasmodic Pheasant: Right. So what I am thinking is, when I look at this, I can go about, go to the string. And then as I go in as, whenever I find a forward slash, that is an indication that, you know, I have completed a file path until now. So, what I can do is I can maintain the file path in let's say something like a stack. And whenever if the most recent part is a dot, then just continue. But, hello? But if recent path is a double dot, then pop one item from the stack. And once you're done, so your stack is going to have all the character, all the file paths that contains and I can just build the final path from the stack. I think this should work. If I just read that if I had something like that, something like this, then you know, immediately going to be a routine. So I put in foo, then I pop out foo, then there's nothing to pop out. And then I would ultimately return slash foo. Do you think that's a viable solution?
Intrepid Hawk: Yeah, yeah, I think that'll work.
Spasmodic Pheasant: Okay, do you want me to start coding?
Intrepid Hawk: Yeah.
Spasmodic Pheasant: Do you want me to keep it as plaintext? Or should I change it to?
Intrepid Hawk: Yeah, maybe you can, you know, choose whatever language and check output.
Spasmodic Pheasant: Okay. Is this a good method signature, is it okay?
Intrepid Hawk: Yeah. Okay.
Spasmodic Pheasant: Okay. So I'm going to create a new tab. And then what I'm also going to do is I'm going to maintain a string builder and start off with the forward slash, right, so, because of that, you can start off with while also maintain... I think about it, if I think about the example of foo bar... so, I start off with foo. So, I append it to, now I have a forward slash. So, since I have a forward slash, I check if it's a file name. It is also no equal to the dot. And then after that I refresh the screen builder go to the next character I keep on adding even I get to here, I see that it's not a double dot, it is not equal also not a single dot. So I add it to the stack and move forward and I come I see that it's a double dot, so I just remove the item on top and then I reset the StringBuilder. Then I move on. I put a dot in here. And then when I get to this, I get to the slash, get to the slash, then what happens is that it is not equal to a dot, so that, you know, it is equal total, so I don't do any updates. And then in the end, but also, I think I need to be concerned about the cases where I could have multiple slashes, right? In that case, I will do... Okay, so this could actually be... Because I might still end up... so if it's a double dot, then, you know, this is the only action that you have to do. And if it is not a dot, then make sure that, I mean, there's no action I do. Right. So there's only double dots and single dots, they are the files that are part of that like triple dots.
Intrepid Hawk: Oh, no, I think for this case, you can assume that there are no triple dots or anything like that.
Spasmodic Pheasant: Okay, okay. So if the file path is not a double dot, and then if it's a non empty string, then you know, it should be a path, so I can put it but if it's, if it's a double dot, then you know, regardless of if something's in, then I pull it off first if not just do nothing. And yeah, so after that, what I can do is like the end if I go like this, and so there's one, so I'll have to do the same logic... I had to do the same I had to do the same logic again down here. So, because of that, I think I can use a while loop so that I can do this activity. So, what I can do here is equal to the string length is equal to the string length and I can basically say that I can just put so it is a... it is a slash, so that you know the last one whatever it is that this also will be will be handled properly. In the end, once the loop terminates... Sure, what I'll do is I will also reset this because it can't terminate right because it will always be I think it will always be interesting because I make sure the last time I can do this thing. deck is empty. Not empty. So one of the stack is going to have is foo bar. What's going to happen is it's going to create a slash. And then if I reverse it... What I can do is I can do this, but this is not the best. And then should I do a slash, and then add foo and a slash and then add bar. Finally, return stringbuilder.toString(). So, one thing that I need to think about is, if I had something like the input or something like slash dot dot dot, slash dot dot dot slash dot. In this case, the stack would not have anything. They can do it. See, it's kind of... is equal to zero. Then in our canonical thing, right so, basically, since I want it in the reverse order, I can just make it make it a deque. So, since it's a queue, what I can do is add/remove from the first and then keep on adding on the adding to the topping on treating it like a stack. But then I can do pull. I can call up okay. So in this case I'm going to take, I'll have to append this thing first. So I append the distinct for last foo, I append for last bar. I think this should work the same so that I don't do an insert on zero. Do you think this is a reasonable solution?
Intrepid Hawk: Yeah, yeah, it looks okay to me. We can just run it through a couple of examples.
Spasmodic Pheasant: Yeah. Just simply one just to check. Okay. Okay. Okay, so that works.
Intrepid Hawk: Yeah, I think it looks good.
Spasmodic Pheasant: I think the runtime complexity... So, I'm going through the entire string here. So, this whole loop would run in the order of O(n), saying that the length of the string is n. And at most at this iteration, we are just doing a single like either adding to the stack or removing from the stack. So, this should take O(1). This also should only take O(1). At the end of the day, if you have a completely proper path then you know this will run, also it will be in the order of O(n) and it will be less than O(n) because it will be the actual string sizes that will be collapsed by the characters put together. So, it could be something something less than O(n). So, in this case, overall it should be, it should take runtime complexity of O(n). And in terms of space, we can see that, you know, we are maintaining a stack, the number of items in the stack could be less than O(n) but then the whole space taken for the conductive items can be at the need to be slightly less than O(n) because of the forward slashes that's been omitted in an application only to be in the order of O(n).
Intrepid Hawk: Yeah. Yeah, I think this looks good to me.
Spasmodic Pheasant: Okay, maybe. Yeah, I mean, maybe we can optimize it a little bit to remove the stack at the end.
Intrepid Hawk: Yeah. Yeah. So basically in place, you can probably use the string itself and modify as you keep going through it. Yeah. But otherwise, I think yeah, this looks good.
Spasmodic Pheasant: Okay. Okay. Do you have any specific feedback about?
Intrepid Hawk: Yeah, I mean, overall, I think it looks good. You know, you also explained, you had good comments in between. And what you were doing, you know, thinking through that process. Also examples. You gave quite a few examples. So that was also good. Yeah, I think...
Spasmodic Pheasant: Do you think? I mean, in terms of my, you know, handling the variable, you know, commenting code, and were you able to follow it properly? Or was it a bit, you know?
Intrepid Hawk: Yeah. I mean, I was able to follow it. So that was probably, yeah. Fine, maybe just minor things, but I think it should be fine. It's good.
Spasmodic Pheasant: Okay. I actually have my on site interview with Google next week.
Intrepid Hawk: Oh, nice.
Spasmodic Pheasant: So that's why I'm taking some prep. What's your background? Are you working in the big ones?
Intrepid Hawk: No, I just started preparing. I'm working at a startup. Okay. So more into backend. Mostly using GoLang. Right now.
Spasmodic Pheasant: Where are you based out of, North America?
Intrepid Hawk: I'm in North America, California. How about you?
Spasmodic Pheasant: I'm from Montreal, originally from Sri Lanka, but I'm here in Canada for five years.
Intrepid Hawk: So you're currently working as a software engineer?
Spasmodic Pheasant: Yeah, I'm working at a company called Cloudops, in Montreal.
Intrepid Hawk: Nice. Good to see.
Spasmodic Pheasant: I mean, if you have any other feedback, please let me know if you can go to another problem if you have the time.
Intrepid Hawk: But yeah, I mean, in terms of feedback, I think I think this was a good one. I think you covered corner cases as well. You know, good examples. Yeah, I think it was good. Overall, okay. Are you okay with another example?
Spasmodic Pheasant: I'm fine, I think.
Intrepid Hawk: Okay, because you know, I don't want to... something that can be done quickly. Even if you'd have some feedback, let me know. Hello? Hello?
Spasmodic Pheasant: Yeah. Sorry, I got disconnected.
Intrepid Hawk: Oh, okay. Yeah, I was saying even if you have feedback, or you wanted me to give some hints in between, you know, was it an okay description that I gave? Yeah, I think you know, initially, just thinking, I think you kept it reasonably short and not, you did not give too much information. And also, you did not give too much out. Give me enough for me to start asking questions and build it up. And I say, as I went, I think it was good to hear that, you know, you were also nodding so that, you know, I knew that it was not complete silence. And, also, I think something that, you know, I might have missed, right, you know, in the blocks, or in some corner cases. Yeah. You waited until I catch it without pointing it out too quickly. So that allowed me to like actually, when the reversal of the stream and things like that sometimes I've seen caught too quickly, and then I don't get the time to think about that was in the right place. Other than that, I think in general, I'd say maybe, like, you know, why is coding like if I went a bit too silent and maybe like mentioned, like, can you explain what you're doing now? Just to take into the conversation. Other than that, I was supposed to go without feeling like left alone.
Spasmodic Pheasant: Okay, okay. Okay, I mean, if you are ready, I can give one more problem. It's up to you. I'm fine.
Intrepid Hawk: We'll try it. We'll see how it goes. Maybe at least discuss it if I don't even know. Okay, okay. Let me paste it in at the top. So, basically, you're given two non negative integers, number one and two. They will be presented as a string. So you have to return the sum of both the numbers. So if you can change the numbers can be you know, the numbers maximum length will be less than 100 and they also only contain digits. So characters and it does not contain any leading zeros. I mean, this could be part two if it contains zeros, but for now, you can just keep it simple.
Spasmodic Pheasant: Okay.
Intrepid Hawk: No, you cannot use any big integer library or anything like that.
Spasmodic Pheasant: Okay, okay. So, something like 295 and 3218 and the length of the number right, okay, so if I'm given something like that, I must return it as a string?
Intrepid Hawk: Yes, you must return it as a string.
Spasmodic Pheasant: Okay, so this is 3513. So, what I can do is I can do like how we would usually summation. So, I can say, initially I can have a carry that will be zero. And then I can do char to both of these, will be five and eight. So, I will sum both both of then plus then carry. So that is 13, then I get five plus eight, I will get 13 and then from here number becomes three and carry becomes one. So, I can do it, I can get that by modulo, sum modulo 10 and some divided by 10 will give me these two. And then I go one step back, and then I did nine plus one plus one. So, that is 11. So, it becomes one and carry becomes one as well. After that I have two plus two, four plus carry of one, which gives me five. And then I have five and carry is zero. And then I find that this string of bits zero so that I only take this guy, so expect to be zero plus three plus carry is also zero, that will equal to three. So, now it becomes three. So, what I can do is, I mean I could have, we need a string, right, so I could have appended it all along so I could have appended it 3153 and reversed it to 3513. And, in this case, the runtime complexity should be so the length is going to be quite 500, right. So, in that case, since it's a constant length of the strings, we are going to go through the indices in length and disease. And then it's going to be the max of the length of m and n. In terms of space complexity, I think it's going to be this is like a, b and c if there's no restriction on the length, but since there's resection, so the time complexity also typically be bounded by 100. So it'll be O(1). In terms of space complexities, it's really just using two pointers moving backwards and creating the final string, which is not included in the space complexity will be O(1) again. In the meantime, even if they are leading zeros, just keep on adding and it's not a problem at all. But once you once you've got the final string, you just need to do some cleaning to make sure that you remove them.
Intrepid Hawk: Yeah. Okay. Yeah, yeah.
Spasmodic Pheasant: Let me know if you have any comments. Leave it.
Intrepid Hawk: Yeah. Yep, I'll definitely do that.
Spasmodic Pheasant: Also connect with, I like to also connect with you. So if you're open for it, you know click yes. If not, you know, I completely understand.
Intrepid Hawk: So that will be after the end. Okay. Okay. Yeah. Okay. Okay. Cool. Sounds good. Yeah, I mean, it was nice chatting with you.
Spasmodic Pheasant: Thank you very much.
Intrepid Hawk: Thanks.
Spasmodic Pheasant: Nice to hear. Thank you very much.
Intrepid Hawk: Best of luck in your interview.
Spasmodic Pheasant: Thank you. Bye.
Intrepid Hawk: Bye.