Amazon SDE1 Final interview (Video interview on Amazon chime)

Job Hunting Interview
, , , ,
1

Given a list of words and list of letters. Words can be formed by using letters given and each letter can only be used once.Find maximum no of letters that can be used from the given list to form the words from the word list.

For example
(1) words=[‘dog’,‘og’,‘cat’]
letters=[‘o’,‘g’,‘d’]
Output: “dog’”
Explanation: Using the given letters we can form [“dog”] and [“og”] but output the longer word

(2) words=[“dog”,“do”,“go”]
letters=[“d”,“o”,“g”,“o”]
Output: “do”,“go”
Explanation: Here we can either form [“dog”] or [“do”,“go”] but pick the one which requires more leters.

Was asked to solve in O(n). But could not come up with the required solution. Any leads on how to solve this?

2

It is similar to leetcode 1225 problem except this one doesn’t have the score. I have used Backtracking for this problem

import collections
results = []
def maxWords(self, words, letters):

    dataset = [collections.Counter(w) for w in words]
    letters = collections.Counter(letters)

    result_so_far = []
    self.startAmazonRecursion(0, words, dataset, letters, 0, result_so_far)

def startAmazonRecursion(self, i, words, dataset, letters, current_char_count, result_so_far):

    if i == len(dataset):
        if current_char_count > self.maxCharCount:
            self.maxCharCount = current_char_count
            self.results = result_so_far
        return

    if all( letters[w[0]] >= dataset[i][w[0]] for w in dataset[i].items()):

        temp_count = 0
        for w in dataset[i].items():
            letters[w[0]] -= dataset[i][w[0]]
            temp_count += dataset[i][w[0]]
        result_so_far.append(words[i])

        self.startAmazonRecursion(i+1, words, dataset, letters, current_char_count + temp_count, result_so_far)
        result_so_far.pop()

        for w in dataset[i].items():
            letters[w[0]] += dataset[i][w[0]]
    self.startAmazonRecursion(i+1, words, dataset, letters, current_char_count, result_so_far)
3

How many rounds of interviews did you get?