Question

Amazon | London | OA | SDE1 | Coding Questions and Solutions | 2022 | Set-83

Answer 1

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.

Answer 2

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

Answer 3

Ques 2 : https://leetcode.com/problems/number-of-ways-to-select-buildings/

Python Solution : # TC : O(n)

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'))