## Python Interview with an Amazon engineer

#### Watch someone solve the efficient sampler problem in an interview with an Amazon engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

[Python interview with a FAANG engineer: Efficient sampler](https://www.youtube.com/watch?v=IQK3UNpSTcs)

### Interview Summary

**Problem type**

Efficient sampler

**Interview question**

1) Given a sorted integer array arr, and an integer x. Find the first and last index where x occurs in the arr.

2) Design and implement an efficient sampler that can handle the following operations in constant time:
- Adding a String
- Removing a String
- Perform a uniform random sampling over the current set of Strings

### Interview Feedback

**Feedback about Verdant Gyroscope (the interviewee)**

*Advance this person to the next round?*  
Yes

**How were their technical skills?**  
4/4

**How was their problem solving ability?**  
3/4

**What about their communication ability?**  
4/4

> Context is preparing for a software development engineer internship position at a FAANG company. I gave a phone screen with two technical questions.
>
> You meet the requirements for a phone screen at a FAANG company, I would recommend you come for an on-site. You have strong data structures and algorithms knowledge, and even better I feel like I'm talking with a peer when evaluating trade-offs and thinking through approaches. Something my company values in interns is their ability and willingness to be mentored and coached, and you give a great impression in this regard. You write working code in idiomatic Python.
>
> Some suggestions:
>  
> - Be ruthless about time, avoid long discussions or at least clarify with the interviewer if they want to have a discussion. For phone screens you don't get much time for questions. You need to propose code, propose time and space complexities, trace with one example, and cover edge cases.
> - Take a look at the Python bisect module, it's interesting. [Link](https://github.com/python/cpython/blob/3.9/Lib/bisect.py). Insert some print statements play around with edge cases for the problem.
> - Use typing hints at least for your method signature; this is a powerful and easy way to communicate what inputs and outputs are. [Link](https://docs.python.org/3.9/library/typing.html#module-typing)
> - If you're interested dive a little deeper into how lists are implemented in Python, [Link](https://docs.python.org/3/faq/design.html#how-are-lists-implemented-in-cpython) and [Link](https://github.com/python/cpython/blob/5c22476c01622f11b7745ee693f8b296a9d6a761/Objects/listobject.c#L22), but I wouldn't spend too much time on this.
> 
> Good luck!

**Feedback about Orange Malamute (the interviewer)**

*Would you want to work with this person?*  
Yes

**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

> Honestly you were the best interviewer I've had on this site -- very knowledgeable about interviewing practices at FAANG companies, lots of great advice, and you also had helpful feedback at the end of the interview. Thanks!

### Interview Transcript

**Orange Malamute:** Hi, can you hear me?

**Verdant Gyroscope:** Hi. Yeah.

**Orange Malamute:** How are things going?

**Verdant Gyroscope:** Pretty good? How about you?

... (transcript continues with detailed conversation about the interview itself) ...

**Verdant Gyroscope:** Alright. Yeah. Have a good day.

### Problem and Solution Discussion

**Efficient Sampler Problem:** 
- The solution approach involves maintaining a hash map for unique strings and an array to support constant time addition and removal while handling duplicates.

**Algorithm Overview:**
1. **Add a String:** If it doesn't exist, append to the array and update the hash map.
2. **Remove a String:** If it exists, swap with the last element, pop from the array, and update the hash map.
3. **Sample a Random String:** Generate a random index from the array to get a uniform sample.

> Utilize random sampling techniques and maintain data structures efficiently.