Python Interview with a Salesforce engineer

Watch someone solve the make change problem in an interview with a Salesforce engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Make change

Interview question

1) Given two strings, is one of the strings a rotated version of the other? 2) Given an array of numbers containing pairs of numbers, except for one single number, find the single number within the array. 3) Given a dollar amount and a list of denominations, find the count of the optimal way to make change.

Interview Feedback

Feedback about Mighty Lemming (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

1/4

Feedback about Epic Cheetah (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

Really good interview experience. Nice set of questions. I liked the fact that we managed to go through the 3 questions. You've been very helpful in giving me guidance and providing hints. Thank you very much for your time.

Interview Transcript

Epic Cheetah: Hello?

Mighty Lemming: Hi. How are you?

Epic Cheetah: I'm doing well. How are you?

Mighty Lemming: I'm well. Thank you.

Epic Cheetah: I'm an engineer with Salesforce.

Mighty Lemming: Okay.

Epic Cheetah: And I'm just you know, this is my second time on this platform, I'm just trying it out. By way of introductions, you can contribute as much as you're comfortable with.

Mighty Lemming: Okay, well, I'm a self-taught programmer. I'm still looking for my first gig, so I'm using this platform to improve my coding skills and to my interview skills, as well as communication skills and I've been using it for a couple of months.

Epic Cheetah: Nice.

Mighty Lemming: And I'm really excited about it.

Epic Cheetah: Cool. Cool. So did you say you are already working somewhere or are you trying to get into programming?

Mighty Lemming: No, I'm still trying to get my foot in the door. I'm on the way hopefully.

Epic Cheetah: I'm just trying to gauge, you know, the the complexity of the questions I should start with. So do you understand the concepts of big O? Like time complexity and space complexity?

Mighty Lemming: Yes. I mean, I might be confused once in a while like everybody else, but I understand the general picture and I can do the goal of space and time complexity analysis.

Epic Cheetah: Okay, cool. Let's start then. You can choose whatever programming language.

Mighty Lemming: Okay, I would go with Python. Python 3.

Epic Cheetah: Nice. So, let me go ahead and clear this and get you your first question. So I'm gonna give you two strings. So what I want you to do is write a function that would output true if the string two, the second string, is something that can be rotated, that can be found by rotating string one. So let's say C D E A B. If you can get string two, just by rotating string one, then I want it to be true. If it is totally something else, like you have something that's missing let's say, you can't rotate a to get it in that case. I want the function to return false.

Mighty Lemming: Okay. The question seems clear. I can rephrase it a little bit so it's easier for me to to proceed with it. I can say that I'm given two arrays of integers and I need to determine whether the secondary is the rotation of the first array. And if I find the solution to this question, then I will find the solution to the original question I believe.

Epic Cheetah: Yeah, that makes sense. Yeah.

Mighty Lemming: It's just easier for me to think in this category. What we can do here? How do I deal with it? Okay, I have a few solutions in mind. I will start with the most obvious and I think the most inefficient solution, but I will talk it out anyway. What we can do is, we can try all the possible rotation combinations of string 1 in string 2. So what we can do is we can take string 1 as it is, so don't make any rotation, and check if that's equal to string two, then we're going to rotate it to the right once on one character and check it again, rotate on two characters and so on until we exhaust all n rotations and we make a check and well it's going to take obviously O(n^2) time, proportional to the lengths of the string and I'm going to assume the length of the strings are the same because if they're different, then I'm going to return false from the start.

Epic Cheetah: Okay.

Mighty Lemming: But that's going to be rather inefficient solution since I'm going to make lots of comparisons.

Epic Cheetah: So, how do you say it's O(n^2)?

Mighty Lemming: Okay, so suppose I start with the initial string. And I'm going to compare it with the second string, so I'm going to compare A with C, D with B. I mean if I'm going to compare A with C and it's not equal, I'm going to break from the loop of course, but suppose they are equivalent in some kind of the worst case. So this is going to take O(n) time, n is the length of the string and I'm going to do this n times, because then I'm going to have string this one, and then the next string A B and so on. So I'm gonna do it n times. But that's a rather inefficient solution. I think there must be something better in this. Just let me think for a minute.

Epic Cheetah: I was just thinking, suppose I do like that, so I merge two strings together, I join two strings. And then I can check, I can just find the substring, I can try to find a string two in the new merge string and in this case, if I have an efficient substring search algorithm, it might take... I think it might take O(n) time here in the worst case, but it all depends on the substring search in this case.

Mighty Lemming: It is O(n) yeah, so yeah, this is exactly right, yeah this is linear time. Can you go ahead and write the function?

Epic Cheetah: Yes, sure. Okay, I'm just gonna comment this. So I'm gonna write function check strings. I have string one and string two as input. First thing what I need to do... I'm gonna check the length of the strings just in case, so if the lengths are different it means the string two cannot be the rotation of string one, so I'm gonna return false. In the second case what I'm gonna do, I can create a new string. I'm gonna go with union_string. So yeah, I'm gonna just double the first string and then...

Mighty Lemming: So which string are you searching for? Are you searching for string two or string one?What is the input string that is standard. So in my question, string one is standard and I want to check if you can rotate string two to see if it matches string one.

Epic Cheetah: Here I merged my string. I have this double string right now. And I'm gonna search this substring and this substring. So I'm gonna check if string two is in string one.

Mighty Lemming: Okay, okay, that makes sense okay.

Epic Cheetah: Okay. And well at this point, what I can do I can use just the built-in Python algorithm. I can call it like that. I'm gonna call method find. String two. And it should return index of the substring if there is one and it's gonna return minus one, if I'm not mistaken, if there is no such substring. So I can say, if you union substring find is not equal to minus one, then I can return true and if it's equal to minus one then I'm gonna return false.

Mighty Lemming: Yep, that looks good to me.

Epic Cheetah: And this part, of course, it can be implemented in different ways, but I think in most of the cases the built-in find function is gonna be the fastest one anyway.

Mighty Lemming: Can you test it?

Epic Cheetah: Oh yes sure. I'm gonna start with our example, so I'm just gonna change this to strings. I'll start with a true case, one of the duplicates. So I'm gonna copy it, so we're gonna see the results of check strings. I'm going to run it. Returns true, okay. Then suppose I'm gonna change the last character, so right now it's not the rotation, it should return false. Yes, it returned false. Well I can try different lengths, but obviously should return false. I can just try a different rotation, just to make sure everything is correct. I'm gonna take this rotation of a string. Returns true. What I... yeah what I could also have done is just make some kind of automated testing with rotating the string one, but I'm sure it's gonna work anyway.

Mighty Lemming: Yeah, this looks good to me. I think you did a good job. You were able to very clearly articulate the problem and go through the the brute force solution and you explain the time complexity correctly by making sure that you get to go over every string of entire length and you do that for every category. And so I think you went over the time complex for this and what's this space complexity for this one?

Epic Cheetah: Thank you. For the second solution you mean?

Mighty Lemming: Yeah, the one that you have written here.

Epic Cheetah: It's gonna be O(n), since this part of my code when I'm concatenating the strings is gonna take O(n) space and O(n) time also, but this is creating a new string, so it's gonna depend on the length of the input string.

Mighty Lemming: That's right, yeah. That sounds good to me, okay. I think yeah, you're able to write clear code and just almost all the cases, so this is nicely done. Shall we move onto the second question?

Epic Cheetah: Sure, okay.

Mighty Lemming: I'm going to go ahead and clear this board, is that okay with you?

Epic Cheetah: Yeah, that's fine. I'm sure it's going to be in memory later anyway, so I can check it out.

Mighty Lemming: Okay, so. The second question is, you have an array and there are... Maybe I can let you write the cases. So the array has an odd number of elements where every element repeats except for one element. I need you to return just that one element.

Epic Cheetah: Can you repeat one more time? I didn't get the first part. Array has n number of elements?

Mighty Lemming: It has an odd number of elements.

Epic Cheetah: Odd number of elements.

Mighty Lemming: Not even. Yeah odd number of elements okay. And it is basically, every element repeats except for one element. So the simplest case would be something like this. So here, it has an odd number of elements, you have an element that repeats, but there is one element that does not repeat okay. I want you to take in the array and return the element that's not repeating.

Epic Cheetah: Okay, okay. I'm just going to repeat the question out loud one more time. We have an array with odd number of elements. And every element in the array is repeated once except for one and I need to find and return that element. Okay. So yes, obviously it's gonna have odd number of elements since every element is gonna be two plus two plus two times and then we're gonna have one element. That's why it's gonna be odd. Okay. Okay, I have two solutions in mind. But I also think there might be the third solution that's gonna be even more efficient, but I'm gonna go over these two solutions and you'll let me know what you think. The first one is gonna be, we can just loop over the array and for each element in the array, we're gonna search the array. If it has this element. And so if it doesn't have this element then, well then I found my element. And this solution is inefficient because I'm gonna loop over array, say the length of the array is gonna be n, then the solution is gonna be n squared, since I'm gonna check every element against all other element except for this element. And yes in the worst case, it's gonna take a lot of time. If my desired element is in somewhere in the end. The second solution might be, I can use a hash map, so I can loop over the array and I can count occurrences of every element in the array and then once I have this hash map, I'm gonna dictionary in python for that. Once I have this dictionary, I'm just gonna go over the keys in the dictionary and if for any of the keys I find that it occurred only once, then it means I found my element. And this solution is gonna be O(n) time, since I'm gonna loop over array a few times, but it's also gonna take O(n) space because I need to construct a dictionary. I believe there also might be a solution without using the extra space, but I don't see it right away. Maybe I will just think a couple of minutes and I'll come up with something.

Mighty Lemming: Yeah, so there is. So, I think we got the time complex right here. So you can do this in linear time. And, so you are using an axillary space here. So you are using a dictionary here. So a dictionary with a key value pair, right? You can have a set. So, I'm not saying this is the optimal solution, but instead of key value where you have a store for every element, you also have the count right next to it. You can add a set. And if the element is not in the set, so you first add an element, then let's say for this example you add one and then you move on to the next element and you see if the element is in the set. If it's already in the set, then you basically remove the element from the set. At this point the set is empty. Now you go take a look at this set you add two and then you are done iterating.

Epic Cheetah: Right.

Mighty Lemming: So, this is a better space complexity solution than the one you had in mind, okay, but this is still not the most optimal.

Epic Cheetah: What can be the most optimal solution, how can I do that. Obviously I cannot sort the array because it's gonna take O(n log n) time, so what I can do here to improve my space complexity...

Mighty Lemming: If you sort the array, it'll still be linear... you can still take O(n log n) time and then if the element is at the array, it will take linear time. I'll give you a hint, it involves bit manipulation.

Epic Cheetah: I think yeah, I'm sorry for interrupting you, I'm just been thinking about that too, about bit manipulations, or maybe doing some arithmetic with array, so I can somehow subtract or add elements and then I'm gonna arrive at my solution. What I'm thinking here is... The bit manipulation, so I have a few operations. I have and operation, I have or, I have xor, I have not, but not is not gonna be useful here. So, if I add two elements well, it's not gonna do much here. No, I don't think so. Or it's... I don't know, yeah, I don't think so. Xor though... If I'm gonna xor the same numbers, say I have something like that in binary and if I'm xoring these numbers, then I'm gonna have one for every bit that's different. But since the numbers are equal, all the bits are the same, it means I'm gonna have all zeros. So... What I can do is I can just go over the array. I can start with a zero, with a number zero and I can xor to this number, all other numbers. And the number that's gonna be left from that is gonna be my number because every other number should be cancelled out by xor operation.

Mighty Lemming: That's right. I think you got it right, yeah. Can you go ahead and implement that.

Epic Cheetah: Yes yes sure, and I'm sorry once again for interrupting you. I just wanted to let you know that I had something in mind, so I wanted to tell you that. Okay. I'm gonna call find number. Okay. I'm gonna have my number X, it's gonna be initialized to zero. Then, I'm gonna loop over numbers in array. Okay. And then I'm gonna xor each number to my current number X, so then the X is gonna be equal to X xor this number. And at the end of the day, I'm gonna return X and my X should be the number that's unique, that's not repeated. I'm gonna test it on our example here, on this one first. For a number, I'll have array initialize already. Okay, I'm gonna call it. Two, okay. I'm just gonna add a bunch of other numbers. Something like that, well in this case it should return eight as my number. Okay and assume if I don't have a unique number, then it should return zero. And in this case, well the time complexity is still gonna be O(n), but I'm gonna loop over array once, which is an improvement comparing to previous solution with a dictionary. And space complexity is gonna be constant, since I'm gonna need only space for this X, so this integer.

Mighty Lemming: Yeah. I think that's a good one, nicely done, yeah. I think you did well here, this one here too yeah. Nice, so this one's a little more complicated. I don't think that the number of lines of code you will have to write is that much, but the intuition is a little tricky, at least in my opinion, if you have not seen that before. So is it okay if I clear this?

Epic Cheetah: Oh, yes yes, definitely sure.

Mighty Lemming: Okay, so what I want is to give you the dollar denominations, like the US dollar denominations, okay dollar bills. So the dollar bills that we have are one, five, ten, fifty, hundred. These are the dollar bills. I want you to write a function where if I give you a value, like 173, okay? What is the minimum number of dollar bills that you will have to use to come up with that number, to make that number? Okay, so for example, if I said 105, right? It's basically going to be hundred and plus five.

Epic Cheetah: The minimum number, yeah. Okay, well the question is clear. I have some dollar bills denominations and I need to return the minimum number of bills needed to return some some kind of sum of money. Okay. Well, the first solution that comes to mind, what I can do is that, let's start with the toy example of 173. I can try to give the change in the largest bills possible, so I can give the change in hundred, I have 73 left at this point. Then I'm gonna give another fifty. Another... I don't have 20 here, okay. So it's gonna be hundred, then it's gonna be fifty. Then I have 23 left, so I'm gonna take 10. I have 13 left, 10. And then just 1, 1, and 1. That's one of the ways I can change 173. But I could have also changed it maybe in a different way. Could it have been done differently? Maybe. I'm just thinking, is that the most optimal number of bills I can use.

Mighty Lemming: I will say that, so this is... so what you have here, that's called a greedy approach. You basically take the simplest approach and in most cases, the simplest approach is the right approach. So yeah, so this falls into the greedy algorithm category, and I think you have it right here, do you want to go ahead and code it?

Epic Cheetah: Oh yes, sure sure. Okay, I'll just keep this as a reference, as my example. I'm gonna define function count builds. I'm gonna have my bills as an input. I'm gonna initialize variable result, it's gonna be a number of bills I'm gonna need. And what I'm gonna do here is.... Okay, just just give me a minute to think through the logic of the code. I didn't think it's through when I started to write in the function. So what I need to do at each step is choose the maximum bill possible. And well, I can assume that my bills are in sorted order? Or I can sort them of course and since I have only five bills, it's not gonna take a lot of time. I mean, if I have a really, really long list of bills yeah, it's gonna influence my time complexity. Okay if I have them sorted in ascending order, I can resort them in descending order, so I have my largest bill first, so what I'm gonna do here is say dollar bills sort, okay? I'm gonna need to reverse.Oh, but if they're already sorted, what I can do is just call reverse function. Now I have the largest bill in the first place. Now what I need to do is... Oh I'm sorry. I missed the argument in the function. I have the argument amount, that's my current amount that I need to change. I have a while loop here and while my amount is greater than zero, it means I still have some some amount that I need to change using the bills. At this point, I need to select the largest bill possible and the largest bill is gonna be the one that doesn't exceed the amount. So I need to check the bills right now. So what I can do is I can look over the bills for bill in bills. If current bill is less than or equal to current amount and that's going to be the first largest bill. What I'm going to do here is subtract it from my amount. I'm going to increase the number of used bills by one. And it means I'm going to be done at this point with this amount and I'm going to break out of this for loop here. So I'm breaking and then I'm going to start my while loop again, if the amount is still greater than zero, of course. And I'm going to make some other changes. And at the end of the day, I'm going to return my results which contain number of used bills. Let me just go through the code one more time. I'm going to assume I have my bills sorted in ascending order. Initialize my results. I reverse this array. So now the largest bill is at index zero. Then I'm gonna run the while loop while amount is greater than zero, while I still have something to change. I'm gonna loop over the bills each time and if bill is less than or equal to amount that should be okay. I'm gonna subtract it from amount, I'm gonna increase my count result, break, and repeat the while loop. And it should do the trick. The time is gonna take me to do that is... Complexity is a bit tricky here since I don't know how many bills I'm gonna use in advance. Well this part of my goal is... Sorry?

Mighty Lemming: Yeah, so when it comes to computing complexity, you always use the the worst case. So let's say like nine dollars is the input here. Yeah.

Epic Cheetah: Not nine dollars. I'm sorry, I didn't quite get you. So you were, you know, thinking about computing time complexity, and you said something like I don't know how many dollar bills I'm going to use. So usually in time complexity we assume the worst. So let's say, you know, since you have the the highest denomination on top, which is hundred dollars, okay, which means you're going to use the the one dollar bill, which is the least of the denomination at the very end, and the maximum that you can use, that you can make using one dollar bills is nine dollars, right? So I'm saying like if you wanted to compute the worst case time complexity and it's not just, it's not even that, I mean, you can still have you know, like I can give you like 17 billion dollars and you have to go through the hundred dollars again and again. So I would give you... I mean, I didn't mean to take this much time. Why don't you go ahead and test it first.

Mighty Lemming: Okay, sure. I have my dollar bills initialized already. I have the amount, well let's go with 173 and I'm gonna print out the result. Returns seven bills, which is... yeah what I've got when I did it on the paper.

Epic Cheetah: Can you try something like nine? So you're doing something a bit odd here. So on line seven right? So you take bills as an argument and then on line nine you use a different variable, dollar underscore bills, which is defined in line one. So, I don't think you need to take in the first argument, you can just use that as a constant. So you don't need the first argument bills. So you see what I'm saying? So yeah, you use bills as an argument passed in and you use that in line 11, on line nine, you're using a totally different argument, dollar bills, which is defined actually here. Yeah, you can change that to dollar bills.

Mighty Lemming: Yes, yes, right. Yeah, sorry for the confusion.

Epic Cheetah: Let me take care of this.

Mighty Lemming: Oh, I meant to put it in the function instead of using the constant, okay.

Epic Cheetah: That's it. So if I give you something like this, it is still going to work I think. But it will take a while. So it's running, you're still looping through here, you go through hundred dollars, and then you reduce the amount by $100 and then you add one. And then the next time you come here, you reduce it. So, can you think of... so I'm going to stop it. So, can you think of... so instead of... so what you're doing here, I think you've got the logic outline correct. But is there a better way to do this? Can you optimize the time for it?

Mighty Lemming: That's a good question.

Epic Cheetah: I can give you a hint, okay?

Mighty Lemming: Yeah, okay.

Epic Cheetah: So instead of, you know, just reducing the total amount that's passive by just one bill at a time, is there something you can do to see if the incoming dollar bill that you're checking, if that's a multiple and then you can actually reduce the multiple of it.

Mighty Lemming: Right, yes. What I can do is I can just divide my amount by that bill and if it divides and I'm going to divide it, and then if there is a remainder left, I'm going to work with that remainder and if it divides without the remainder, it means that, well I got lucky with that change using only that bill.

Epic Cheetah: Yeah, okay. Can you try implementing that?

Mighty Lemming: Sure. So, I checked the bill here. I checked that it's less than or equal to amount. Now what I'm gonna do is, when I'm gonna divide my amount by that bill, it's gonna tell me how many times I can use that bill. So instead of adding one to result here, what I can do is divide my amount by that bill, it's gonna be a number of these bills I've used on adding it to my result. And I also need to update my amount. And the amount that's left is gonna be the remainder of this operation. So remainder is modulo and then amount is gonna be equal to amount module bill, and that's gonna be my new amount. Right? Shall I run the coat and give it a try?

Epic Cheetah: Yeah tru, try to run it.

Mighty Lemming: Oh, that was fast. That was really fast.

Epic Cheetah: Yeah, it was fast. So, I don't think we need this while, right? So let's remove that. Okay.

Mighty Lemming: Makes sense.

Epic Cheetah: So and do we really even need the bill is less than or equal to?

Mighty Lemming: Oh, no. No, no we don't, we don't.

Epic Cheetah: Yeah we take a single bill, and then, that's pretty much it, right?

Mighty Lemming: Right.

Epic Cheetah: So this is like coming from the world of Java, we take an operator precedence in those things into consideration. But in Python, I think they take care of that, so I think this is all we need, right?

Mighty Lemming: Yes, yes, it's definitely looks cleaner. Yeah, the same result. Yeah, because the first bill, the first largest bill, then we'll move on to the next bill, and so on. Yeah.

Epic Cheetah: So, what is the time complexity of this one?

Mighty Lemming: It's gonna be the length of my dollar bills array, since I'm looping over it and I'm doing constant time in both of these lines, so yeah.

Epic Cheetah: Okay nice. So yeah, that's all the questions I had. I think you did very well there. For someone trying to get into the software industry, I think you did fantastic, so yeah. You have very good communication skills, you can think out loud clearly, you know, go through base case, there's a brute force, explain the time and space complexity, and then build on top of that while trying to work on your optimal solutions, yeah I think I'm very happy with the way you have proceeded in solving these problems, nice.

Mighty Lemming: Thank you, thank you very much. It's very kind words and it's very good to hear. I mean, I know I'm on the right track, thank you.

Epic Cheetah: Do you have any feedback for me?

Mighty Lemming: I appreciate your time taking for this interview. I like the questions and I also like the fact that we manage to do three questions, because sometimes someone needs to do only one question, and I'm really happy about the interview. Thank you, thank you once again.

Epic Cheetah: Okay, cool, take care.

Mighty Lemming: Okay, you too. Have a good evening. Bye.