Python Interview with a Microsoft engineer
Watch someone solve the currency conversion problem in an interview with a Microsoft engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.
Interview Summary
Problem type
Currency Conversion
Interview question
Given the above parameters, find the conversion rate that maps to the 'from' currency to the 'to' currency for every single query
Interview Feedback
Feedback about Crimson Almond (the interviewee)
Advance this person to the next round?
How were their technical skills?
4/4
How was their problem solving ability?
4/4
What about their communication ability?
4/4
🎉 Summary: Interviewee is very solid, if I interviewed him at Microsoft for an Intern position, whether it's a technical phone screen or a virtual onsite, It would be a pass for me. I broke down his performance in 4 categories, and he did very well in all of them. ⚫ -----Communication-----⚫ Candidate was very clear in explaining his thought process, especially his style of drawing his thought process and showcasing his data structure design, I suggested he to continue these good traits moving forward. An example of his data structure breakdown, this is very clear: adj_list = { USD : [(JPY, 100)] JPY : [(USD, 1 / 100), (CHN, 20), (USD, 1 / 100)] CHN : [(JPY, 1 / 20), (THAI, 200)] THAI : [(CHN, 1 / 200)] } Some suggestions: [~] Candidate could clarify a bit more on the input and size to avoid some friction at the end where you re-clarify some of the input type. Friction in interview can add in stress especially under a strict timeline. [~] Try to talk to the interviewer for more permission questions, like "do you want me to run through an example?" or "I think BFS and DFS both make sense here. I am thinking about implementing a BFS. What do you think?". The reason for these is to see what your interviewer is trying to prioritize, thus, you can skip some procedures, and again, this will save you tons of time, and you can use them to impress the interviewer on the part they care about. For example, I did have follow-up questions at the end, but due to time sake, I wasn't able to ask you. After you finish coding, one thing you can say is, "For time sake, do you have another problem for me or any follow-up questions? If not, I will take my time and walk you through some examples in detail." ⚫ -----Problem Solving-----⚫ This is a strong candidate area for all three questions that I mentioned. He was able to break down / digest the problem and provide the optimal solution for all in the end. He was able to detect the graph problem at ease, and came up with BFS/DFS as solution, he also paid close attention to do trade-off analysis which I enjoyed. Some suggestions: [~]When seen the currency problem, you immediately mention "this looks like a graph problem." I like how responsive you are when it comes down to digesting a problem. One recommendation that I will say is to explain a bit further on the reason you start thinking toward Graph. For instance, you can say something along the line of "The problem reminds me of graph, the reason is that the relationship mentioned in the example, I can view them as connected component, and this is a problem where we can potentially model it as a search problem within a weighted graph...." I suggested this because sometimes candidates forget to explain the "WHY," and some interviewers may think they are memorizing a solution instead of solving it on the spot. [~] One thing to point out is, in a weighted graph, if trying to search for shortest path, the normal way is using a dijkstra. I think clarify a bit on why BFS in this case work is critical. BFS usually work with a unweighted graph. Something I would probably add is, "Even though we are modeling this as a weighted graph, we are still traversing neighbors on a first-come, first-serve basis. The weight is for us to keep track of the final result instead of using it to determine which shorter path to take. So, in this case, we can use a Queue and perform BFS." [~] I would mention using a visited set in the problem-solving stage before the implementation to handle the cycle. You did say it during coding, so it was more of a personal preference on clarity of problem-solving before coding. ⚫ -----Coding-----⚫ You did well in coding, your coding speed was on point, good variable names, and you worried a lot about refactoring the code. All of these are good traits Some suggestions: [~] In a time-sensitive interview (Facebook or Amazon), you want to code out quickly because there could be follow-up questions. I suggest you do as much talking as possible during the problem-solving stage. When you start coding, you can ask permission questions such as "Let me go ahead and make the graph quickly, and I can come back and explain the code, does that sound ok with you?" In this case, you permitted yourself to go silent for 2-3 minutes, where you could concentrate on coding without interruption. This is the key to speeding up the coding even further. [~] consider using a defaultdict to represent the graph. it's edge-case friendly and a bit more clean [!] list.pop(0) takes linear time. If you want to use a list to represent a queue, make sure you talk to the interviewer and mention: I can potentially use deque here, but I will come back to this one later for time's sake. [~] small thing on type, result should be list of float. ⚫ -----Testing-----⚫ This step is important, however you may want to ask the interviewer whether they have another followup question for you before you start debugging. [~] for the sake of time, try to reduce the sample I gave to you, the interviewer could give you a long input, and testing through everything may be time-consuming [+] it would be even better if you could draw out the adjacent list before implementation. In the end, you can spend more time debugging the code instead of going through the code.
Feedback about Winter Pumpkin (the interviewer)
Would you want to work with this person?
How excited would you be to work with them?
4/4
How good were the questions?
4/4
How helpful was your interviewer in guiding you to the solution(s)?
4/4
Thank you for doing a great practice session. You forced me to think profoundly and test my problem-solving skills. You also allowed me to discover some shortcomings I have when asking clarifying questions. Thank you for the detailed post-interview feedback and for being nit-picky with it as I asked. Thank you very much!
Interview Transcript
Crimson Almond: Hello! Can you hear me?
Winter Pumpkin: Yeah I can hear you.
Crimson Almond: Just is my voice audible.
Winter Pumpkin: Yes, I can hear your voice pretty well.
Crimson Almond: Alright all good. Yo how's your day been?
Winter Pumpkin: Yeah, I'm doing pretty good. How was yours?
Crimson Almond: Fantastic. Thanks for asking again.
Winter Pumpkin: Okay, sounds good. You can hear me correct, right? I just want to this is the first time using this platform. So I want to make sure that my audio is very, you know, very clear to you.
Crimson Almond: Yes, yes, I can I can hear you all good.
Winter Pumpkin: Okay, sounds good. So why don't we do this, let me quickly go ahead and do an introduction. And we will leave about 45 to 60 minutes to to actually do the coding part. So in the meantime, I will just kind of to talk a little bit about, you know, the position that I work at Microsoft, and also to get a little bit of your context, why you're focused on this, specifically for Microsoft and what you want to get out of it. How does that sound?
Crimson Almond: Yep, all good.
Winter Pumpkin: Cool. So yeah, my name is Derek and I are working the operation analytics team. So we do a lot of dashboard, dashboarding telemetric type of work regarding the Microsoft Azure platform. And typically, you know, stuff that we do is more infrastructure heavy. But yeah, like I've been in this position for the past few months actually recently gone for a job search myself. So I think it's a really good time to kind of, you know, talk to you about what you're looking for, I guess, anything that I can support on the side, we can probably leave some time at the end of this interview to kind of go over that. But yeah, if you don't mind, just kind of let me know like, you know, what you're looking for currently? How can I support you?
Crimson Almond: Yeah, thank you. So thank you for the introduction. So right now, I am a third. I'm a college student. I am a third year, computer science major. I go to a public school in California. And tomorrow, actually, I have an intern interview coming up for amazon. So I've practised most of the lists on leetcode. Done. I mean, I, I've been i, you said that this was your first time on the platform, correct?
Winter Pumpkin: Yes. But I've been doing, like mock interviews for a very long time. Just this particular platform. Yeah.
Crimson Almond: Okay. So but yeah, I've been I've been long term user of this platform. So whenever I have an interview coming up, just to calm the nerves and just, you know, work on skills again, that's what I do. So I guess, like, just, you know, just tried to, I guess, I guess, if there's anything, I just want you to, you know, make it as realistic as possible that that's what I would would love to expect from you. And just
Winter Pumpkin: Of course, of course.
Crimson Almond: And if you could let me know, like some of the quote unquote, red flags or even basically I'm just trying to refine my skill as an interviewee. So even if they're like tiny nit-picks, you know, just just at the end, just, you know, let me know, so you know, I can work on, you know, even the tiniest of the details, but yeah, that's, that's basically it from me.
Winter Pumpkin: And if I'm assuming this correctly for this intern interview, is there going to be a first round phone interview, or this is the onsite interview? Because for different, different rounds? The expectation is also a little bit different, depending on the question, difficulty and all of that.
Crimson Almond: Um, quite honestly, I mean, I had one Amazon interview. I mean, this is for a fall intern position. I did one for a summer intern position. This was like, like, a year ago. I didn't get the job but the question was literally a leetcode easy. It was just a HashMap question. But usually, these intern rounds are just one or two coding questions, and they just did some behavioural questions. So just one round, one 45 minute round.
Winter Pumpkin: I see. I see. Okay, okay. Yeah, so I'm pretty familiar with the Amazon to process the behaviour question could be like about 15, 20 ish minutes, right. And then, in the next 30 ish minutes, we need to give you a time that you're able to manage to finish within that timeframe. So let's get into it. I'll provide you with the problems. And also I want to make sure that if I give you this question, and you have seen it before or have done it, I don't want to waste your time so that we can I can have a lot of questions I can take from, so just let me know. Okay?
Crimson Almond: Alright all good. Yep. Yep.
Winter Pumpkin: Okay, so what programming language do you want to use?
Crimson Almond: I'll take Python three.
Winter Pumpkin: Okay, Python three no problems. Cool. So for the intern i Let's go with this one. And then again, right if you've done it, please let me know I'll select like a different question.
Crimson Almond: Yeah, group anagrams. Yep. I've done this. You sort them in a dictionary. Yeah I've done this.
Winter Pumpkin: So can you walk me through just the the high level time complexity how you want to do it.
Crimson Almond: Okay, yeah, no, I'll explain just the approach of this. So okay, so given an array of string scripts the anagrams together, you can return the answer in any order and anagrams a word or phrase by rearranging. So what we can now do is since since each anagram a word is an anagram where the the, what we can do is put so let me let me give you an example. We have Nat and tan. So what we can do is, if I take nat and I sort its characters, right, it becomes ant. And similarly, if I take tan, and I in a sort its character, it also becomes ant. And so since all these anagrams have the same letters with the same frequencies after them, they all give us the same exact thing. So we can use this sorted string. And we can have a HashMap where this sorted string then becomes the key. And then within the key refers to some bunch of values. So if you're not in tan, and let's say for eat, eat ate and tea, it would probably be aet. And aet would refer to eat, ate, eat and tea. And so for this, our overall time complexity would be so so if our input list is of size, so input list size N and
Winter Pumpkin: Let's just say the maximun let's say the stream with a longest lens will be represented as K.
Crimson Almond: Okay, okay, cool. So input size of N, and let's see, yeah, worst case, you know, longest string of size k. So what we're doing here is, first of all, we're going to be iterating. So it would probably be you know, for, you know, word in strs, something like that. And then we would probably have our word map, you know, just a dictionary right here. And then we would probably do, we would do our key would be something like this, we would just join sorted word. And so this operation right here would probably take us k logK. And so and so that operation, and we would probably do like word map, you know, key, and the word map, dot get and you know, just just do an operation so we can insert into the map. And this thing right here is O of n. So we're doing o of k log K work O of n times. So our resulting time complexity should be NK log of K, in our space complexity should just see us and because we're using a HashMap.
Winter Pumpkin: Right, right, exactly. So typically, for this problems there, this is a good solution. I will go ahead and give you another question, since you probably done this before. But I want to just give you maybe five minutes to think about, Is there anything you can do to go a little bit faster than the the current time complexity?
Crimson Almond: Yeah, yeah. And so so where we can, where we can save time is here, here where we're sorting it. So I think what we can do is, and here's here's my thought, instead of sorting it, right, because sorting, is taking we're doing this additional work. I think where we can cut time is because an anagram, so yeah, so what we can do is we can have we can sort of we instead of putting them right with these with this sorted key, we can we can bucket them, let's see some some some other key, let's say 101 right, and I'll explain how I came up with that. That just could be, you know, the sum of and I think what I can then do is I can iterate over, let's say nat, right, and I'll do that here. If I have nat, I can just do score that just can be you know, the ASCII value of n, you know, plus the ASCII value of a plus the ASCII value of t, and you know, have that score and assign that here. And we could do that work outside here outside of this for loop, and pass it for each word, and that word would probably take us O of N time.
Winter Pumpkin: I like the direction you're going, this is great. Let me interrupt you a second. Is there going to be possibility that when you're adding characters that will give you the same score? For example, let's just say that on line 31, right, creating another list, I mean another line. Now, let's say I have a different character here. Maybe this is ASCII A, or lets just say opqrc? Let me do something like r. And then I have it adding another ordinary of a, again, this is just a hypothetical, right? Is it possible that these two line will have exactly the same score and how are you going to address those issues yeah?
Crimson Almond: You're right, that's a possibility. Ord of t could be also equal to ord of r plus order of a. So that's a good edge case. In that case, I guess?
Winter Pumpkin: Basically, I think the your approach is that I like the idea because what you're doing here, right, is trying to serialise in a way that we don't have to necessarily store the every single string one at a time, right? Because you want to serialise in a way that you can quickly getting the result. Right. I think that that direction is very well, but I just think that the approach you came up with may have been you know,
Crimson Almond: I think yeah, you said the word serialised, that does ring a bell, in my mind, I think what we can do is just going off of this, what I would suggest that we do. And what I can do is, since there are and so my question is, would all these strings just contain like, like English alphabet characters, or can I also have like, something like that?
Winter Pumpkin: Yeah, this is a good question to clarify. So one of the things you can add to the beginning, which is I like to slip a question, right? It could be just contain small case A to Z. Or it could contain like A to Z uppercase, and zero to nine. Right? So I'll just say you can do all of this. Yeah. That's a good, that's a good clarification question.
Crimson Almond: Mmm hmm. So we can do that. So what I'm not trying to think is so so my thought and the reason why I asked you that was, you know, if it, let's say, assuming that it was just a to z, just a to z, then we can just use some extra memory. And like, you know, had like, something like, you know, a sense of 26 characters, how someone did this sort of thing. And, you know, this like frequency list. And then within what I can do with this frequency list is that I can, I can just combine it together. So I can just do you know, after, so let's just say, let's just say right now, you know, I have something like this, and you know, this would probably be a for B, and this would be C, so this would tell me that, you know, at this position is telling me the frequency of C, then what
Winter Pumpkin: I like that, okay, I like that. Yeah.
Crimson Almond: And then what I can then do is I can you know after that and so now this is in a list, what I have to do is do something like this or convert that into let's say a string, or something like that. So that would probably give me some some sort of string key that I can then use to index. So
Winter Pumpkin: Can I ask you a question. So what is the problems of having the array just being the key?
Crimson Almond: The array being a key? Well, this is, well, yes. Because arrays are mutable. The keys,
Winter Pumpkin: Okay, I like that answer, okay, good answer.
Crimson Almond: A workaround is that in Python, this is specific to Python, we can use tuples, we can tupple. So we can convert that into a string, and then we can do that. And so doing that using so performing this beforehand, before we jump to this, before we do some work on our HashMap doing this entire work for all of our words would take us O(N) time and plus, plus O(N) space, O(N) time and O(N) space. And so we do that for this and then we jump into and for HashMap we do the same thing. Again, here's O(N) time and O(N) space so at the end I guess at the, I think the final answer, and I'm doing this down below here, on line 71 so we would have O(N) plus n time, which would then just boil down to O(N) time and then we would have o, n plus n space. But at the end of the final stage complexity would just also be linear.
Winter Pumpkin: Okay, I like this solution. So I will, based on what I've seen, from what you typed, I will assume that you will know how to run the code. So why don't we jump into the new question? I got enough note taking down so we can move on. Good job. So let me paste the new question. Again. If you'd have done this, let's walk through the thought process. And then I'll give you another question. If so,
Crimson Almond: Alright.
Winter Pumpkin: So if you could go to Line 80.
Crimson Almond: Alright. Yes. So...
Winter Pumpkin: You've seen this question before, right?
Crimson Almond: Given the return the vertical order traversal up it's notes. And so output here should be9,3,15. This is a BFS problem. Yes, I've done this.
Winter Pumpkin: Okay. Okay, so let's move on. Yeah, I'll give you a new problem. So let me copy that and paste it at one ten.
Crimson Almond: Okay, an array of currency conversions, which means one USD is equal to point. I don't know why this everything is in red. That's an indent not. This is just I think it's just bugging me, but I guess I'll still read through it.
Winter Pumpkin: Yeah, let me let me just get rid of maybe the rest of the chat. And you could actually,
Crimson Almond: Let's, let's just combine it together. Like everything being in a single comment block.
Winter Pumpkin: Yeah, let me yeah, I'll just Okay.
Crimson Almond: Yep that's fine. Yeah now it's fine, that's fine. An array of, which means $1 is equal to .77 GBP. A list of trays containing from two, given the above parameters, find the conversion rate that map's, that maps to the from currency to the to currency for every single query. So we have USD and yen and we have 100. So does that so this means that one, so one, USD is equal to 100 of JPY? And then, and then, one JPY equals to 20 CHN, correct?
Winter Pumpkin: Correct.
Crimson Almond: Okay. And then similarly, one, CHN would be 200 THAI and then we would do USD to CHN? And so I'm assuming that would. And what would happen is, since we don't have a and then we should return 1000. And similarly, for JPY to THAI we should we should do that conversion. And then similarly
Winter Pumpkin: I think the answer should be 2000.
Crimson Almond: 2000 Okay, and let's just check. So for JPY, we only have one link to the CHN. So and but yet, and then has a link to THAI. So you multiply these values. And that's how you come to 4000. And similarly, if there doesn't exist, okay, so I think I think I'm trying to think of any clarifying questions about the data, but it seems seems kind of obvious how these conversions are taking place. The first thought this definitely looks like a graph problem to me. And this looks like a weighted graph problem. Where so in and I'll draw the graph for you. So we have the USD right. And right now it is it has an edge to JPY. So I'll just draw an edge here. JPY, and the weight of that edge is 100. Similarly, JPY has an edge to ch n and the weight of that edge is the weight of that edge should be well, it's 20. And then similarly, CHN has a edge to THAI and that edge is the weight 200. And let me make sure I have this down. Correct. And this seems like a a I also also also need to make sure that it's, it's 100 when I go from USD to JPY, but if I go from JPY, to USD, it's one over 100,000. So that could be a very tricky, that could be one edge case. So I
Winter Pumpkin: Float both ways, right? And, yeah.
Crimson Almond: So I guess I guess we can I can have this, it could be like a by, so what I can do is, you know, I can have two, so we can have two sort of edges. So one edge that goes this way, and one edge that goes the, in the other direction, and both of those edges will have different weights. So one, one, we can, you know, in our, when we model our data, we can have, you know, one edge that goes from USD to Japan has a weight of 100. But then, then similarly, we would have one edge that goes the other way. And that edge would have some sort of this valley and then after this. So once we have this sort of a graph constructed once we do these clarity, so we know we need to go to from from us to to China, for example, then we can just do now it's a question of, should we do a BFS or a DFS? I'm thinking is there an advantage of using bfs here? Hmm, I guess my other question, also is? It could be well, yeah, I guess another question. Now, I think of this, let's say that, you know, Japan also has an, I'll draw this other edge. Other edge, let's say it has Indian rupees, for example, and that has some arbitrary x value.
Winter Pumpkin: Correct.
Crimson Almond: And then that that, but there's an in that also leads to China. That could be also that could also be a case, we have multiple links, we have multiple ways to get to China. We can either go from Japan to China or Japan to India, then to China. So in that case, BFS would be a better alternative. Because if we go from USD, to Japan, to India, to China, well, we're wasting compute power, and it's not efficient. But if we were to do it with BFS, we would just go to USD Japan and directly to China. Because as we know the way BFS works, if we reach a node, we've probably taken the shortest path. So we can we can do this we could. So basically, we construct so the problem can be broken down into two sub problems, we construct a graph, construct a bi-directional weighted graph and then perform BFS. And in that, and so so so we do that. And that's how we can. And so here, if you look at our queries that will be the source and other would be the destination and just like do the do the math as we keep on doing our BFS and see where we reach. So So that's and I think the time complexity, since we're doing BFS. And I would probably use an adjacency list of some sort probably would just be O of V plus e. V plus e where V is vertices in the in the graph, and E are the the edges in the graph and then the space complexity to just be want to say, just V I think I think at maximum, or BFS queue the worst case just has all the all the vertices in it. I think yeah. So So for first space. So that would be time. And that would be that space. So yeah, so that's my, my thoughts on this problem.
Winter Pumpkin: Perfect. So just to make sure that this V plus E is the time complexity where you can perform one single BFS right, or is this the case? I think the the question is asking you to find multiple queries, right? Not just like, you know, once starting and yeah, so I think I think what you said was correct. I like the analysis. But if you have to done I guess there should be another time complexity on top of this.
Crimson Almond: So we could just say that that would probably oh wait oh think yeah so I missed that. So that would just be, you know, that'll just be another factor. So you know if q is the length, so we just multiply that by two, now i'm gunna leet question, is this a space change? I would say no.
Winter Pumpkin: Let's just say, Yeah, I just say space could be the way it is for now.
Crimson Almond: Yeah.
Winter Pumpkin: Because you need to write an adjacency list. Right. And everything that you created in an adjacency list will remain the same. So I think we do it yeah.
Crimson Almond: Okay. Yep.
Winter Pumpkin: Okay, yeah, this is perfect. So I can, yeah, so I took enough notes. So let's, why don't you go ahead. And start on this, let's try to write a function. I will say to for clearness of qualification, the input will be a list of list. And then for the rates and for the query will be lists of lists of strings. And output expected to be a list of floats.
Crimson Almond: Okay, so yep. Let's just do get get conversions. Get conversions, and we take in a rates array. Let's just do from typing import list. So we have those type annotations. So we will have a list of list of str. Yep. And then our queries that would oh wait it? Well, it could be I'll just say it's just a list. It's just a nested list for now. And then queries would also be a list of list. And then we take, and that's all we take. And then we return a list of integers. Good. So we have this and now let's build a an adjacency. list. So the first thing, so let's make it our adjacency, adjacency list, I would keep this a dictionary or hash map. And so now now what I would want to do is I would want to do for rate in rates, for raising rates. And I guess another question. So you know, similar to how we have here, USD two to Japan and 100. Could there also be a case where, you know, we have, let's say, and we have the other way around? Like, is there is there a possibility? And, you know, that would probably be 0.01. Is there a case of something like that?
Winter Pumpkin: Right. There could be a case like that, right? But I think to what you proposed earlier, right? Because this is an undirected bi directional relationship. Either way, even with or without that, you still have to create it. Yeah. Yeah. But yeah, there is a possibility like that. Yeah.
Crimson Almond: Okay, I think, okay, because I want to take that into account or keep that on the back of my mind. So we have the rate. So we have to would probably be rate of the first value, the from the from will be rate at one. And then I think, let me just to currency, and then from currency, and then lets have a rate. And so now what we want to do is oh wait. Currency rate, okay, we have that. Now, what we want to do is, we want to do adjacency list. And I want to do, I want to add an edge and from my to currency, what I would want to do is I would do adjacency list dot get and now I'm getting all the things and if there doesn't exist, anything, I return an empty list. And to that, I would want to add an edge from so in this, just, I will hold two informations. I would hold what's my current currency, and what's the currency rate. And similarly, and conversely, I would want to do the other way around. I would want to do adjacency list dot get from currency return an empty list. And to this I add an edge to my fro currency to my to currency. And this should be one over my currency rate. So I think this seems okay to me. Now what we want to do so now we have that adjacency list built out. Let's do. So here, we probably wanted to, for, you know, queries for query in queries, and we would, in here let's have let's just have, you know, to, to currency, which would be query up zero. And from currency would be query at index position one, but also have answer arrays. So output, our name this output queries. And let's do that. And now I want to start my BFS que, my BFS que would now begin. So I would start it off from to, or what I want to do is now now here's Yeah, okay. obviously want to kick it off from to currency. So so that, so So that's the, that is the i've added a node.
Winter Pumpkin: Right? Because that's the starting point, right?
Crimson Almond: Yes. So that's the starting point. So now I jump into my BFS traversal. And so while my length of my queue while the length of my queue, I would just do something like queue dot so my, I'm still I still need to edit, I think I should probably put more information, what I'm putting in the queue. But basically, what I'm, what I would try to do is, I would do my current node, something my current node, current node, I would probably get my current current rate. And I also need to keep track of that, like the multiplier, because this is a weighted graph. And so I need to keep that in mind. So for now, I'll just do like current multiplier or something. And so I have my current node, my current rate, current multiplied, this can change. So this is just rough idea of what I want to do. So I would just do queue dot pop 0. So now I need to change that here. So my two currency is that. And right now my multiplier should be one. And then and then that should be my multiplier. So I don't think that I need to. Yeah, I don't think I need so all I need is this. So if I start from USD, right, so if it was USD to USD, the answer should just be one, right?
Winter Pumpkin: That's correct.
Crimson Almond: Yeah. So okay, this Yeah, this makes sense. Because if it's, let's, let's say if now if my current node is if my current node is equal to my foreign currency, so I've reached my node, I can just do output queries dot append, I can just do my current multiplier. And also let me just do visited nodes. Let's, let's keep that a set. And the first one that I want to put on there is my to currency. So I've done that. So, now I want to do for neighbour or for neighbours in for neighbours in my adjacency list for my current node and I think I want to break out so so if I've not so, here is the case if I reached where I want to reach I append it and I exited my BFS and you know, we go on to the next query, but if not, then we traverse the other neighbours. So we go for neighbours and for neighbours in adjacency list of our current node we first of all, what we want to do is we want to do we want to do so the first thing the first thing that we Get is because we're storing our edges in a form of a tupple. So we would first of all, so our so I think this should be for neighbour and multiplier. So, and so we would probably unpack, because we're traversing. So I think I think Python will automatically unpack them, what we would want to do is first of all, visited nodes dot add our neighbours, and then to our queue, we added so queue dot append. And so we now want to do is, first of all we want to add the neighbour and then we want to grab our current multiplier and then multiply by our multi the neighbours multiplier. And then we keep on traversing. And now in the case from USD to Australia, who so I guess this is, in this case, we all have a we have an edge that just just doesn't exist, correct?
Winter Pumpkin: Yeah, yeah. Because like, you know, the kind of queries that you're getting could be like, you know, could be null as well, right? It could be a Yeah, it could be an edge doesn't exist.
Crimson Almond: Um, so in that case, so So I need to, I need to check that I can probably just, I mean, a naive way is just, I can just have a flag, honestly. And you know, I can just said, found equals true. And if not, you just have if not found, I can just do output queries dot append, we just append a negative one. So I think that takes care of it. And so that picture of that. Now, the things that have I. So another question. So let's say I just have INR to, XYZ. Is there a possibility? We could get this and not have anything about them in our rates array?
Winter Pumpkin: Correct. So yeah, there's a kind of queries that you're getting from what you said the user could be very arbitrary. They sometimes type things that is out of the search capacity within your rights. So yeah, like the the most of the start, and the end input could be arbitrary, right? Yeah, it could be something that doesn't exist in the graph.
Crimson Almond: All right. So I guess one way, I could check that if, you know, to currency, not in my adjacency list, or from currency, not in, not in adjacency list. There is no point in doing this. So we can just do output queries dot append a negative one. And then because there's no point in going to BFS and I think we can
Winter Pumpkin: Exactly, exactly. I liked that, because you'll you'll save a lot of search space. You could probably argue that the sorry. Because the type of like the queries coming from user is unpredictable. So they could possibly have a lot of backward coming in. And if you just do the STS get rid of that this can save you a lot of calculations space.
Crimson Almond: Yes, yes, I do. The only thing is, if we can, if we cannot now this block of code looks really untidy. But I'm old first. But we'll we can definitely refactor this, but I in the interest of time, let's not do that. Let's just complete this algorithm. And if we get time, we can address that. So once we're done, we do our here we do our output queries, and then we jump in I think, I think here we can return our output queries. And let's just do a quick dry run of the code. Let's let's do it on top of the function here. Let's just want to see if I can have another okay, it's gonna throw that error it's fine so Okay, so now we have and let's copy let's just copy this example that you provided us. So and let's just also insert this additional thing in here and I also want to see, I didn't address this edge case. This is fine, we'll, we'll see. We'll just fix as we go. So right now we have our adjacency lists. So this would be our adjacency list. And so, okay, and so we jump in, so we hop into our array. So we jumped into our first rate, our first rate would be from, so it would be our to. So let's also keep track of our variables here are to currencies is USD our from currency is JPY, and our current currency rate, right now is 100. And here we do. So here we would do USD, which then become when we add a node, so we would add. So we would add JPY, and 100. And then, and then we would do the converse. And we would also to JPY would add USD and, and we would then add point or I'll just do it, keep it this way. That and then we move on to our next rate, that would be JPY to CHN. So are to becomes JPY, this becomes a CHN, and this becomes 20. So now we come here to our JPY, we just append it, we append CHN, and then we add to 20. And then likewise, we do the same, we add JPY. And then we do one over 20. Then we go on to the next. So we have CHN. And then we have THAI and we have that to 200. And so we come to CHN, we add THAI, we add 200. And then we go on to THAI and then we add CHN and one over 200. And then we had Yeah, I just wanted to look at this, how we would want to deal with that. So we had JPY. And then we have our USD and then we have one over, let's just keep it that. And so we come here the way that would right now work is we would come here, right? And then then we would just insert a duplicate node. Just the that now, I think the shouldn't be a problem. And the reason we can still so so the first thing we can do, we can just, we can just, you know, make this a set basically, the entire list is set. And since we're already adding tuples we know that we know that they're immutable. So even, if this is a set set and we add this exact tupple. Given that, you know USD to Japan 100 And Japan to USD would you know, be I think it just depends on the assumption that this will be correct. This would be the inverse of that. So we can do that. So that's a quick fix. But I but that would but I don't think we need to do that. Because if you come down to let's see here for neighbour in Oh yes. We can just add if neighbour and so line 192 If neighbour not in visited notes, then we can just add that because now what will happen is, you know, let's say if we were going to Japan, we discover USD while we add USD, right, we're gonna go to China, we add China. But then we again come to USD. Well USD is right now already in our visited nodes. And so we would and then we don't need to so so basically this is just boils down to the fact that on line nine 192. Or this statement would just never, this statement would be false. So we would never go into that block. So think our algorithm just takes care of this edge case. But that's, that's our adjacency list the way it looks. And so we have that and now let's jump into our queries. So we now have USD so Uh, so queries. So our to currency right now is a USD our from currency is now a, CHN. And so we come here, we make this our queue, our queue right now is USD to, one. And our visited is just a set that contains USD. And right now our found is false. And so we jump in here, we check that we check for either of these cases, well, both of them exist in our maps so not a problem. Now we jump in here, we grab our current node. And so our current node in our current multiplayer should be equal to two. So we pop from our queue, so this becomes zero and one and our queue is now empty. And then we check if we have reached our end goal here. Current node, we want to go to China, our current node is USD. So Nope, we have not we continue that then then we then we hop into the neighbours of USD. So the first neighbour is Japan and Japan is not so. And we check that Japan is not in our list of notes, so we have not visited it. So first thing we do, we add it and then to our queue, then we add JPY. So this should be neighbour JPY. And card multiplier, which is one times the multiplier of Japan, the cost it takes to go from Yossi to Japan, which is 20. So one times 20 is just 20. And we do this, and then we go back up, again. Now we're here, we pop our current node 20. And so we do that. And we realise we still haven't reached our end goal yet. So then we jump to our for loop, we we go we go check our Japan node. Well, we have already visited the US we visited USD, it's already in our visited nodes. So we don't you know, add that to the graph or to the queue. We see that hey, we have not listed China yet. So let's add that here. Well, before we add that, we add that to our seen. And here we would add CHN and current multiplier, which is right, current which is 20. And the cost it takes for him to go from JPY. To China, that should be um, wait. Let me let me make sure I have this right. I think I think I got this wrong in the first place. So what did I do? I think there should have been 100, I think I looked at the wrong value. So USD, we added Japan. And in that case, the current multiplier was one. And so we did one times 100. Yeah, so that's bad on my part, I think
Winter Pumpkin: So you should get a hundred.
Crimson Almond: Yeah, yeah. So this should have been 100. My bad. So when we add this, so right now our current multiplier is 100, multiplier to get to China from Japan is a 20. So 100 times 20 is 2000. We go through that. And now we come on to our next iteration, we pop China, and then we get 200 or 2000. Sorry. And then we pop this from our queue we jump into our while loop, we do check that hey, our current node is where we want to reach and we have our current multiplier
Winter Pumpkin: so we added it
Crimson Almond: here, you know we just append to that 2000 here and then we break then we don't need to check and then and then we move on to the to the to the next query. And similarly, Japan and THAI we have a relationship from Japan to THAI. So similarly, as I've demonstrated, we will just do a similar logic. It will start from Japan. Or actually wait a second, we'll start from Japan. Probably go to China and from China we'll go we'll go to THAI in so that we will get the first multiplier 20 times a second multiplier 200 multiply both of them get 4000 That's what we want. And then the other case would be USD to show Australian Dollar but our if statement on one line 185 would run so
Winter Pumpkin: Right so I think I think on the high level, this makes total sense. One question is, do you still need to have the flag, given that you have the edge case on 185, line 185?
Crimson Almond: Well, right now. So the reason why I say yes, and I could be wrong, there could be a possibility we could have a, we could have two separate graphs. So two unjoined graphs, right. And so if we have two graphs that are separate, well, we would still have to have their nodes in here, would still have their nodes in here. Let's say we also have, you know, let's say, x, y, z, right, another graph and ABC, another graph, and you know, XYZ only has an edge to ABC, and, you know, same in this case, you know, we have x, y, z, and same, it's something like that, well, these would still be in or adjacency list, but there's no way for me to see to XYZ. So if we start at USD, we traverse everything. And I think line 185 doesn't catch that case. So so that's one reason why I had this condition here. A guy I'm trying to see, well, the only thing Yeah, I. I mean, since you mentioned this is probably a better way we could do this, but but that's my thought process as to why I had the flag.
Winter Pumpkin: Yeah, that makes sense. That's fine. Okay. Cool. So I think in terms of time, we started around 4:16 for this particular problem. So roughly, this is the end time for now. So why don't we take a step back? And, by the way, do you have any last minute thoughts you want to finish or otherwise we can kind of start talking?
Crimson Almond: Oh, no, no, I mean, if this was, if we had the time I would definitely refactor this, and these indented blocks, just kind of like
Winter Pumpkin: So why don't you walk through that? I mean, in a real interview, this is probably a lot, but since like, you know this is a mock interview go ahead, please. I kinda want to see like how you would refactor this.
Crimson Almond: So I think my only well, the only thing is, how would I like un indent? Like, the first would be to bring just one level out. One level out. So this is I think this this logic would just stay as it is we're not, I don't think there's much that I can do to change this logic. What I can, I mean, the only way I think I think this would this would, we this would probably waste computation power, but just for the sake of like, making the code look good. Or not found. And then I can just, you know, cut this and paste it outside here. I think I think here and we get rid of that indent. So kind of makes it cleaner to look at. But wait, no, no, wait a second. Let me see if current node for neighbour in current. No, this will actually could you
Winter Pumpkin: Should you do this check like online 201. Before or after you you execute the BFS?
Crimson Almond: I think I think I think we should not yeah, you're right. This this check should be here. But then we should get rid of this. And do it here if not found because because then then we could potentially get a key error. So the there's a possibility, if not found we can just do not append negative one only thing guess what, both of these blocks are achieving the same purpose. Right? But it's like in so so you know, what I'm trying to do is like how can I combine these together but it just so happens that way, but then if we have append we don't we shouldn't be running this. So I think I think there's a
Winter Pumpkin: I think I think the way it makes sense because these two are checking on different things. 188 is more checking whether the starting point and the end point is in the graph. And then the if not on at the end is more about like you know, can even if you those things exist in the graph, but can I actually have an edge to connecting the two nodes? Right? So I think having that there is okay. Yeah.
Crimson Almond: But then but then we just come back, right? Even if we check it, we would still jump into this while loop so. And it just, this just brings me back to where we started where I had this under an else. So we're back to where we started?
Winter Pumpkin: Yeah, you can, you can probably, yeah, that's, you can you can probably break it there. You know, just to say you don't have to execute on the, the while loop. Yeah. Because if not, if one of the things is not in the graph, so they shouldn't, you shouldn't execute that. Yeah.
Crimson Almond: I think I think I think just to make it I can just make this its own function. I mean, that's, that's something that I can do. Just to use the get conversion function. So that's, that's a stylistic at that point. Doesn't really have much impact on the performance of the code. But yeah,
Winter Pumpkin: okay, cool. So I think it's fair for us to take a step back. And yeah, so good job, first of all, and that was pretty, pretty, pretty good. I want to first talk about your personal skill, like you say, this is your Amazon interview, you got this question, this is your performance. Why don't you do a self evaluation? And then I could give you some of my perspective at the end.
Crimson Almond: Okay so I think I think from if I were to judge myself on cleanup, problem solving, technical skills, and communication and verification, on those four skills, I think I did the problem solving part really good. I think I explained the problem. I told you, I told you how we could get that data, how we could modify, build a graph and then perform BFS and why BFS and not DFS specifically, and like on a higher level. So I think I think we did that in this in like, just column. And so I think I did good on problem solving technical skills, just the coding part. While I coded the question out, in I think, I think I think I could have been faster. It's just that, you know, as I'm trying to explain, you know, I'm trying to like, going slow. So it's just, it's just like a very like, then balance that, you know, I must be writing fast. But at the same time, I should be explaining to you the things that I'm doing so, but overall, I think I think that on that communication, I think I think I was just I was I was making sure that every single line I write, I just let you know what's going through my mind. So I think I'm good, good on that. And I think I also did a dry run of the code so I verified to you that hey, look, my algorithm does run. So I think keeping those things in mind, I would I mean, given that I've done interviews and mock interviews, I think that I passed the interview. So so that's my conclusion.
Winter Pumpkin: Yes, I think that's a very, very accurate assessment. So let me go ahead and copy my, my notes that I've taken over the interview. So the whole point of this reflection here is to see you know, if there's anything that we can do better, I think for depending on you said, this is just for an internship, right. And if this is the level for internship, this is definitely a either a higher to strong higher performances. So let me break it down to you. On line 213 I'm going to put all the notes down here. So yeah, like, so the four axis Yeah, like I'm going through a very similar to you mentioned communication, I also care about problem solving. I do care about trade off analysis, and then also like coding and testing, so different company using different metrics, but they on a high level, they're much the same. So let's start with the communication, I see you're very experienced in terms of how you communicate, like you're drawing things out, and you're, you know, going through is very much step by step. I like that very thorough, like, you know, communication, I really like that. So I think one of the things I want to add into is that some clarification on the input and output is important. You don't think you're practically did that, but then doing when you're starting going into the problems, and they realise, oh, right here, am I expecting this to be you know for the edge cases, what is exactly the input type, right? Because at the time when you tried to do lists of lists of strings, but then you realise, oh, there's a list of lists of string and integer there, right. So you know, in Python, the type could be different in the array. So those are things that I will personally probably clarify a little bit more, right. So there's another thing if you look at line 206, right, you know, this is negative one, but it should be negative 1.0. Right? Just if you want to keep that consistency, having a float type right. So again, right clarify on the input output type, cool, help you to resolve some of the issue like that. And when you go to 218. So here are some of the things I want to kind of ask you is that in order to save you time during an interview, right? This may be a case for a company like Amazon or like Facebook. So Amazon is known for getting a behaviour question at the beginning, right? And then leave you about like 30 to 20 to 30 minutes at the end, right? So sometimes you may or may not have the luxury to talk a lot, right? So a lot of times that you probably want to ask yourself, like, can we cut down sound like talking? So this way, you have more time to actually finish the problems more time to, to demonstrate your coding ability. So you can probably situation only asking the interviewer be like, hey, you know, do you want me to run through an example? Or do you think and I think BFS DFS both make sense here. During this, like, what do you think? Right? So basically picking at their mind to see where they want to direct the interview. That way, you can use that to your advantage by saving times, right? So you could integrate the wanting to explain too much. They already understand everything. Yeah, you can save that time. And you can use that time, maybe they can give you another problem. Does that make sense? But yeah, I think I think what you did was perfect, like, you know, just adding that situation things, letting your interview decide. So that way they can get the most out of you. So that you have more time to shine, and show showcase more things that you have. So when it comes to problem solving, this is I think he's the strongest suit you really fast and you're really to the point. So basically, you say when I give you the problems, the first problem I gave it to you, you know, you can do sorting here. And then when I give you a little bit hints on this realisation, you're able to come up with the type of solution right or the the serialisation solution and you are very strong on data structure, you know, that HashMap the key needs to be immutable, right, the value could be anything, but but I was trying to get tricky a little bit there, but you did perfectly fine. So your data structure is really good in terms of thinking about an algorithm you also come up with this graph problems algorithm very quickly, right. So you break it down into two steps. First is make the graph second was to traversal. And within the traversal, I really really like your trade off analysis. You mentioned like you know, I should use DFS or BFS right. So you started asking yourself that question. So I will give you I will say that one thing I will add on to that is that when you are talking about BFS and DFS, right, BFS will be a shortest path. In this case, you give me an example. But they also could be cases with BFS, we know we have a very, a lot of value on a horizontal level. So one thing you probably should mention is that either BFS or DFS worst case scenario, right? You know, if you don't know the structure of the graph, who ended up becomes the policy, right? Like in that case, you would just basically iterate through all of this, right? And then there's also another factor in this specific question is that because you potentially have a lot of division going here? So if you think about this way, right, like you have USD to, let's say, Chinese, right, right here, it's like, you know, 100, right. And if you do the other way around, so then you're going to get a reciprocal value of one divided by 100. Right? You mentioned that as well. If you imagine that if you started out this path and started doing division one divided by 100, then you divide that by another 100, then you divide it by another 200. You see, I'm going here, right? You potentially going to lose a lot of flows accuracy, the more the more node you traverse, right, the more accuracy, you may lose in that process. So in that case, you should probably go with the one that had the shorter path. Does that make sense to you? So that's why BFS is more preferred could be another patient just just right there. Right? Yeah. Am I make sense. Yeah.
Crimson Almond: Yeah, no, I think, yeah. So BFS could be explained to you up? I think I did. What was your point? If you can just reclarify on that part?
Winter Pumpkin: Right. So for example, you have two paths, right? One is to just say you have two ways to access these USD right? You gave the example here, by something like this. Right? You have another path here. It could be a THAI. Right? And then what if you have 10 Different neighbours right here, right? And then eventually you move back to USD. And then the question is, like, you know, should I use the BFS or DFS? In this case, the shorter passage is, the more accurate your float in your float will be avoiding a lot of those deviations. Does that make sense? So that's why having having a shortest path to avoid you from doing all of us division, right. So I think just snuck up on to just for this problem specifically, right. But I think I liked your analysis at BFS. A DFS is quite a you can do either way. Right? They'll both get you the answer. So I like that. Let's see. adjacency list. Oh, by the way, this one thing I think that I want to mention is when you are using a queue, I believe in Python. The queue you're using currently sees a list. What is the time complexity on line?
Crimson Almond: Yeah, you're right. There is a there is a Dequeue so there is a data structures would like just do, we can just do a pop left?
Winter Pumpkin: I think, okay,
Crimson Almond: we can do that. You're right. You're right. Yeah, this is we can use the dequeue
Winter Pumpkin: I think I think the just just have the array if you constantly deleting things from the front, the actually might cost you linear time complexity, I think I think I'm not really familiar with Python. But that's something I heard. Right. So yeah, if you have a different data structure, like a Dequeue, which implemented using, I guess, a linked list that might be a little bit better.
Crimson Almond: Could we just, I actually have an interview. So if you could just kind of go through like really fast? That'd be really good.
Winter Pumpkin: Okay, yeah. So I think basically, the rest of the hour, go ahead and write in notes. And then I'll post it on the the platform but yeah, those are the things that I think on top of my head right now, this is a few more, I'll running the comments, in the notes later, so you can go through them. I also suggest you something when I went and do that, okay.
Crimson Almond: All right. So but yeah, the thank you so much. I'm also I just so you said this was your first time on the platform
Winter Pumpkin: Using this platform at all.
Crimson Almond: This is funny. Well, because I'm also I'm actually an intern at interviewing.io so I actually work for the company.
Winter Pumpkin: That's great. That's great. Amazing products. Yeah,
Crimson Almond: Yes, I thank you so much. I actually, actually they have their interposition for their jobs board I applied and they gave me a job. I'm like, Cool. Yeah, but thank you so much for your time. I unfortunately got to run but but thank you.
Winter Pumpkin: Yeah. Hey, you did very good. You're worth everything about this process. You did really good. If this is an intern for Amazon, I think you can you can get this job in a heartbeat. So good job on that. Continue what you do and good luck. Best of luck on that.
Crimson Almond: Alright, thank you so much. Alright, see you later.
Winter Pumpkin: Alright, talk to you later.
We know exactly what to do and say to get the company, title, and salary you want.
Interview prep and job hunting are chaos and pain. We can help. Really.
