0 like 0 dislike
1,914 views
| 1,914 views

0 like 0 dislike

Applied on career portal without referral. Had to finish OA within 7 days of receiving OA link.

Platform : HackerRank

OA was divided in 2 parts : DSA and Behavioral

Part-1 : Consists of two DSA questions which we need to complete within 105 mins with code explanation

`Question 1 (Difficulty : Easy , Topic : Math)`

Given an integer denoting a total number of wheels, help Amazon Logistics find the number of different ways to choose a fleet of vehicles from an infinite supply of two wheeled and four-wheeled vehicles such that the group of chosen vehicles has that exact total number of wheels. Two ways of choosing vehicles are considered to be different if and only if they contain different numbers of two-wheeled or four-wheeled vehicles.

For example, if our array wheels = [4,5,6] our return array would be res = [2, 0,2]. Case by case, we can have 1 four-wheel or 2 two wheel to have 4 wheels. We cannot have 5 wheels. We can have 1 four-wheel and 1 two wheel or 3 two-wheel vehicles in the final case.

`Question 2 (Difficulty : Medium , Topic : Math+Prefix-Sufix Sum)`

The Amazon Kindle Store is an online e-book store where readers can choose a book from
a wide range of categories. It also provides the ability to bookmark pages the user wishes to return to later. A book is represented as a binary string having two types of pages:

• '0': an ordinary page
• '1': a bookmarked page

Find the number of ways to select 3 pages in ascending index order such that no two adjacent selected pages are of the same type.

Example
book = '10111'
Output : 3

This was a good question compared to question 1 as one might think to solve this using DP as it consists of making choice(take/not-take) at every point but DP will give TLE. I had done this question befor thanks to OA experience shared by someone on LC and this question does not exist on any platform as far as I know , so I didn't had hard time solving this one and question 1 was just a beginer level so I completed both questions and passed all TC's in around 12 mins and in next 15 mins explained in detail both approaches with example and why approach I had taken is better than any other approach and of course time and space complexity for both of them. Over all it took me around 30 mins to complete this part.

After part 1 we can take a break without any time restrictions

Part - 2 : No time constrain

It took me around 10 mins in this part, also an advise to briefly go throuh Amazon's LP for this part. This part consists of selecting an option for given questions so no need to worry much about this part

Verdict : Got Interview call on very next day(Around 18 hrs to be precise) of completing OA.

by Expert (111,530 points)
0 like 0 dislike

`Question 1`

``````class Solution :

def chooseFleet(self,wheels) :

res = []

for wheel in wheels :

# If odd
if wheel&1 :
res.append(0)

else :
''' If wheel = 10 => ans = 2 => insert 3 in res(as our distribution of wheels can have 0 4's(all 2's) or 1 4's or 2 4's) '''
ans = wheel//4
res.append(ans+1)

return res
``````

`Question 2`

``````class Solution :

def findLeft(self, s, size) :

self.cnt0 , self.cnt1 = 0 , 0  # Total 0's and Total 1's in string
self.cntLeft0 = [0 for _ in range(size)] # 0's on left of given index
self.cntLeft1 = [0 for _ in range(size)] # 1's on left of given index

for ind in range(size) :

self.cntLeft0[ind] = self.cnt0
self.cntLeft1[ind] = self.cnt1

if s[ind] == "1" :
self.cnt1 += 1

else :
self.cnt0 += 1

def waysToSelect(self, s) :

length = len(s)
self.findLeft(s,length)
ways = 0

for ind in range(1,length) :

if s[ind] == "1" :

onLeft = self.cntLeft0[ind]
onRight = self.cnt0 - onLeft

else :

onLeft = self.cntLeft1[ind]
onRight = self.cnt1 - onLeft

# Number of subsets formed in given ways with arr[ind]=1 as 2nd page out of 3 is
# (Number of 0's in left) * (Number of 0's in right) and vice-versa
ways += (onLeft*onRight)

return ways

# TAKING INPUT
s = input()
print(Solution().waysToSelect(s))

#INPUT
# 011000011

#OUTPUT
# 24

``````
by Expert (111,530 points)
0 like 0 dislike

# Idea : possible selections = 101 and 010

## Approach 1 : Straight Forward | Maths

for 101 when curr page is 0 count the left ones and right ones so total combinations = left Ones * rightOnes
for 010 when curr page is 1 count the left zeroes and right zeroes so total combinations = left zeroes* right zeroes

``````def findWays(book:str)->int:
# count total Zeroes and Ones
n = len(book)
totZeroes, totOnes = 0,0
for c in book :
totZeroes += (c == '0')
totOnes   += (c == '1')

# find ways
leftZeroes = book[0] == '0'
leftOnes   = book[0] == '1'
res = 0
for i in range(1,n-1) :     # 1 to n-2
if book[i] == '0' :
rightOnes = totOnes-leftOnes
res += leftOnes*rightOnes    # possible combinations
leftZeroes +=1
else :
rightZeroes = totZeroes-leftZeroes
res += leftZeroes*rightZeroes   # possible combinations
leftOnes +=1
return res

print(findWays('10111'))
``````

## Approach 2 : DP

``````def findWays(book:str)->int:
dp = [[0, 0, 0], [0, 0, 0]]    # [ "0", "01", "010"] and  [ "1", "10", "101"]

for x in book:
if x == '0':
dp[0][0] += 1                 # increase the count of "0"
dp[1][1] += dp[1][0]        # "10" required "1" solutions
dp[0][2] += dp[0][1]        # '010' required '01' solutions
else:
dp[1][0] += 1                 # increase the count of "1"
dp[0][1] += dp[0][0]        # "01" required "0" solutions
dp[1][2] += dp[1][1]        #'101' required '10' solutions

return dp[0][2] + dp[1][2]          # '010' solutions + '101' solutions

print(findWays('10111'))``````
by Expert (111,530 points)