---`

layout: post

title: "Day progress 9961"

date: "2019-09-26 17:44:46 +0530"

tags:

- amazon

- interview

- hyderabad

I slept around 2:00 AM Yesterday. I was preparing for non-technical questions

and it took little late for me to go to bed. Despite sleeping late I had to wake

up at 7:30 AM anyhow. If I do any delay than this, then I might had difficulty

in reaching for the Amazon office.

First round was Data structure and Algorithm round. This round was taken by an

Amazon employee who was working from Amazon Hyderabad centre before and then

he transferred to Amazon Seattle centre.

You have given two strings and a set of words. You can replace any string from

given set of words if they are only differ by one character. You have to give

minimum number of replaces required to match both strings.

For example given two strings are "hot" and "cog" and "lit", "lot", "cit", "cot", "hit", "cog" are part of words.

Now below is a graph of all possibilities if we start replacing one string with

another from a given list of words. Our goal is to return the minimum number of

replaces.

1. "hot" -> "hit" -> "lit" -> "lot" -> "cot" -> "cog"

2. "hot" -> "hit" -> "lit" -> "cit" -> "cot" -> "cog"

3. "hot" -> "hit" -> "lit" -> "cit" -> "cot" -> "cog"

4. "hot" -> "hit" -> "lit" -> "cit" -> "cot" -> "lot" -> None

5. "hot" -> "lot" -> "cot" -> "cog"

Here minimum solution is number 5 because it only takes 4 swaps of string.

It took some time to understand this question. After discussing for a bit, I

mentioned that we can compare if two strings are similar by one different

characters using hash table approach. He instructed me to first write that

function. So I wrote a function which returns a boolean value that weather given

strings are not different than two characters.

Then he instructed me to compose my final code. I mentioned him aurally that I

can compute this by using backtracking approach in which I remove one string and

then increase a count.

We can break when two strings are equal or there are no more words left. When we

break we also check weather given number of swaps is minimum then our string.

He then instructed me to wrote a code for it. I wrote a backtrack code in which

I wrote code as per our discussion. Then he tried to check the flow of my code

and said that it looks like it will work.

Then he said he has already more minutes than decided so he want to end. He

asked me that if I have any questions for him. He said that rather going for

each and every branch given problem can be improved in which it doesn't go for

each branch and it will return a value.

I thought for bit and then told that rather than going with Depth first approach

I could have gone with Breadth first approach. He smiled and told me that I

should think later about this problem. He also mentioned that I should not worry

and be relaxed.

When I look this problem now I feel it can be improved using Dynamic programming

because minimum sequence from given string is always limited. If we store it, we

can reduce our computations based on it. But I didn't got his hint during my

interview.

This round was taken by an engineering manager. He first discussed about my

existing experiences and asked few non technical questions.

One question from these was which is my favourite programming language and

requested me to mention disadvantages of it.

TODO: Write your answers

I have to write a method which takes long DNA string as an input. DNA string is

only sequence of 4 characters LGTA. Given list of sub strings, I have to match

given characters of DNA with list of strings.

I took some time to understand the problem. During this process he mentioned

that because given DNA string is too long, I have to come up with an approach in

which I iterate on given DNA string and I can also match which sub strings are

matched.

His this hint clicked me that this is a problem of Trie. After thinking a bit I

told him that this can be solved better using Trie data structure. He told me to

first define class for Node of Trie. I created and and mentioned that Node will

point to next node. If it is null then we can say that this reached to end. We

can also put one more variable called "end" to indicate that given key ends

here.

Then he mentioned me to describe Trie aurally. I describe how comparision of

keys we can do and he agreed to my approach.

Then he said that I should implement code for method and assume Trie is present.

I just have to call API functions of Trie.

We add pointer to head of a string. Responsibility of pointer is to track how

many character from given DNA string we can match from our group.

We iterate on each character from DNA string and iterate throw each pointers. If

current DNA character is equal next of pointer then we increase pointer to its

next node. At the end we start

We first manage collection of pointers. If a pointer is at end then we can tell

that a string is matched.

I mention that we can manage pointer to a node and while iterating on DNA

sequence we can

I coded a function in which I create a pointer for matching existing string. If

nothing is found, we start matching for string from the beginning of Trie.

My code was confusing I told that there is huge chance to improve it. He said it

is okay. He tried to went with the flow and said it looks it will work.

Then he said how will I get sequence of DNA characters?

I said I will just call that function. He said okay this looks good.

At the time of writing this post, I think I was missing one important point he

mentioned earlier. He mentioned that sequence of DNA is too huge I can't load it

into memory. I think I have to came up with any better solution in which I

iterate given DNA sequence not in one rather divide it in batches, but I didn't

showed any of these improvements in my interview. I could have improved this.

Interviewer started by asking couple of non technical questions.

This was a system design round. I was asked to define a resturent reservation

system. In this system a user can reserve a table from on-line app or by walking

to the restaurent. He told me to explain the flow of the system first.

I started by mentioning various entities of the system. I then explained a flow

of online and walking customer. He was having a few questions based on it. Then

I draw schema diagrams of reservations.

Then he asked couple of questions based on it. He mentioned that how will I

handle a case in which one user is booking a table and another user is also

booking the same table at the same time.

I mentioned then there will be a different state of the system. In this case, we

can manage a global cache service which takes table id, restaurent id for making

it into block stage for a while. We can update blocked or un blocked states to

User may be when they first loads a system or improved will be to send server

sent events to client.

As a followup questions he said that there is possibility that this cache become

too much huge and it will be stayed in memory. It is possible that we can go

overload by memory. I said that then we can use shrading for distributing our

caches to other work stations to achieve horizontal scaling. And I also added

that we can manage replicas for each shred we can use that as a fallback

mechanism in which if given shard fails we have working worsion if it available.

He agreed with my approach and said that he want to conclude this interview.

While he was winding, I request him to provide any feedback on my solutions. He

said he liked my approach, he also said that I went for schema diagram based

approach and that is also a good thing to do. He mentioned some improvements

that I forgot somehow.

At the time of writing this blog post, I realized that I have done one big

mistake in my system design diagram. I haven't mentioned webserver in my system.

This mistake I keep do while ploting my system design solution. It is a big

mistake. After this, I will always mention webserver as one of my component in

system.

This round was object oriented design round. First she asked me couple of

questions related to my experience and requested me to define a situation where

I think I could have done better. This was tough one. I thought for various

examples and then I tried to look to it.

She was confused on one of my solution and then we keep discussion things on Git

couple of minutes. It was around 15 minutes. I think I was not able to explain

her clearly or may be she thought she had understood and I am the one who is

making mistake.

In my past experience, I had lost my tempre. This time I was controlling my

self. It was hard for me to control and don't be ancious. Finally, she got my

point and then she also mentioned that I didn't did something interesting. She

mentioned that I have done something very basic stuff. This was a reaction of

all interviwers. Because it is a role for seniour position, a recruiter has

already mentioned that I should have some good experience of ledership and

training people. So far they are right here. I don't think I have a strong

experience of working at some large system and more client centric.

Then she mentioned that she has very less time to go with System design

question.

I have to design a system for managing inventory management for scale of Amazon.

There can be various ware houses which are located at different locations.

Inventory is responsible for managing various items and their quantities.

I started writing an interface for Item and then wrote concrite factory method

and the time for given slot was up. I defined a class for each item category.

She said I have 5 minutes in which I have to explain here how will I manage

items in given inventory. I said I will store items by their category into a

hash map. And store items as sub hash map by their id.

She said that she is interested in identifying how will I manage my inventory

when there are many var houses.

Her ultimate goal was to provide an search for items by its name and my approach

in which how I provide a search operation to it.

She explained a solution quickly by saying that one more hash map which stores

location of items by its type and have reference to each ware houses which again

has our previous implementation of items. I am not sure this was the exact

solution but it was something similar to this.

When she was wrapping up, I asked her to get a review on my approach. She said

she was expecting me to have managers for each items and inventories. And she

was interested in knowing my iteractions of item, inventory and warehouse.

She didn't mentioned that my approach was good, okay or anything else. I asked

her how my approach felt to her. She said my factory and item type implemtation

works.

Her this remarks felt me sad. I don't think she was happy with my appraoch.