Amazon Phone | SDE II | Toronto, Canada | Oct 2020 | REJECTED
Anonymous User
981

Update: Rejected - LP not satisfying the recruiter. Consider to reapply in 3-6 months
Have a phone interview on Amazon Chime. My interviewer was nice, and a pretty girl was shadowing him, but he does not seems to be LP-oriented like all the posts have described. Thought I gave some OK-ish answer, but he didn't fancy with how I embedded LP into that like I expected.
2 LP: Tell me about a time you have to
- Compromise code quality due to time constraint
- Fixed your serious mistake
We chatted for about 15 minutes, and he quite rushing into the code (I still want to talk more because I feel I didn't satisfy him with my LP answer - he also admitted that he'd prefer the coding part from the start of the interview).

Coding question:
Give a list of word, return a list of lists of all isomorphic string together.
Example: ['leet', 'boot', 'baby', 'xaxy', 'leek', 'abcd'] => [['leet', 'boot', 'leek'], ['baby','xaxy'], [abcd]]

Firstly I didnt understand the term isomorphic - I thought it was some kind of Ceasar encode because he said something related to map character. So I asked him some clarify question: string should be the same length and consist of only alphabet, what return of null to null, etc - He mentioned map here, therefore I tried to come up with a solution about two character at the same place should have constant distance. He said nope, and give me another example: 'ABAC' -> 'DCDZ'.
Figured out I need to map the string to some kind of universal form - but my head just went blank after that (He said I came very close - which I have came up with is the canonical form, and ask if I need a function to actually do the mapping). Thanks God, after his hint, my brain suddenly came online and I completed with the right mapping function (using a defaultdict).
Then for the meaty part of looking through the list, I gave an exhaustive searching in O(n^2). He asked if I can do better, I reply yes if I can use some more spaces, and code up a dictionary solution with the key is the canonical form.
He told me there was one bug in my code, and I figured out that I need a separator due to the nature of int number - they will not distinguish between '1,1' and '11'.
He asked me what I am going to do to let this code go to production. I said about commenting, documenting, testing. I also mention that due to time constrain, I have used vague variable name, and will change that if I have time. He asked me to do that while asking for time complexity of my solution. It was O(ab), with a is list length and b is maximum length of a word.
He kinda satisfy with my technical solution, and tell me what I want to know about his job. I was really curious about how Amazon handling its enormous requests everyday in a timely manner and asked some questions around that. I also asked for personally connect with him on LinkedIn because I researched him earlier. He answered me politely, and I feel that I find some nice and interesting answers. I sent him a thank you note and a connection request after that.
Overall, I thought I still need to work hard on my LP if I can passed this round. If I'm going to rate myself I can give 70-80% grade.
Here is my whiteboard solution:

from collections import defaultdict


def convert_to_canonical_form(st):
	# I used variable name st because str is conflicted with Python string type
    i = 1
    res = ''
    char_canonical_map = defaultdict(int)
    for char in st:
        if char not in char_canonical_map:
            char_canonical_map[char] = i
            i += 1
    for char in st:
        res += (str(char_canonical_map[char]) + '-') # gotcha here, it needs separator
		# also told that I could optimize using ''.join() but he told me it's ok
    return res


def find_set_isomorphic(lst):
    word_canonical_map = defaultdict(list)
    res = []
    for word in lst:
        canonical_form = convert_to_canonical_form(word)
        word_canonical_map[canonical_form].append(word)
    for canonical_form in word_canonical_map:
        res.append(word_canonical_map[canonical_form])
    return res
Comments (1)