Amazon Interview Question for SDE1s


Country: India




Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming that everything fits into memory and we don't need an iterator I would use a sliding window approach. O(m) space and O(n) time while m represents the words of the lookup paragraph words and n the number of characters in the entire paragraph.

public int shortestDistance(@Nonnull final String paragraph, @Nonnull final String lookupParagraph) {
        if (lookupParagraph.length() == 0) {
            throw new IllegalArgumentException();
        }

        String[] lookupWords = lookupParagraph.split(" ");
        Map<String, Integer> foundWordCount = new HashMap<>();
        Set<String> searchWords = new HashSet<>();
        initialize(lookupWords, foundWordCount, searchWords);

        int startSlidingWindow = 0;
        int currentWordCount = 0;
        int minWordCount = Integer.MAX_VALUE;
        StringBuilder currentWord = new StringBuilder();
        for (int i = 0; i < paragraph.length(); ++i) {
            char c = paragraph.charAt(i);

            if (isInWord(c)) {
                currentWord.append(c);
            } else {
                String word = currentWord.toString();
                currentWord = new StringBuilder();
                // test the current word
                if (word.length() > 0) {
                    currentWordCount++;
                    // found the word, remove it from the search words and increment the existence count for the
                    // sliding window
                    if (foundWordCount.containsKey(word)) {
                        foundWordCount.put(word, foundWordCount.get(word) + 1);
                        if (searchWords.contains(word)) {
                            searchWords.remove(word);
                        }
                    }

                    if (searchWords.size() == 0) {
                        for (int j = startSlidingWindow; j < i; ++j) {
                            char c2 = paragraph.charAt(j);
                            if (isInWord(c2)) {
                                currentWord.append(c2);
                            } else {
                                if (currentWord.length() > 0) {
                                    String tmpWord = currentWord.toString();
                                    if (foundWordCount.containsKey(tmpWord)) {
                                        if (foundWordCount.getOrDefault(tmpWord, 0) > 1) {
                                            foundWordCount.put(tmpWord, foundWordCount.get(tmpWord) - 1);
                                        }
                                        // stop sliding
                                        else {
                                            break;
                                        }
                                    }
                                    startSlidingWindow = j;
                                    currentWordCount--;
                                }
                                currentWord = new StringBuilder();
                            }
                        }
                        minWordCount = Math.min(currentWordCount, minWordCount);
                    }
                }
                currentWord = new StringBuilder();
            }
        }
        return minWordCount;
    }


    private void initialize(final String[] lookupWords, final Map<String, Integer> foundWordCount, final Set<String>
            searchWords) {
        for (String lookupWord : lookupWords) {
            searchWords.add(lookupWord);
            foundWordCount.put(lookupWord, 0);
        }
    }


    private boolean isInWord(final char c) {
        return (c >= 65 && c <= 90) || (c >= 97 && c <= 122);
    }

- Scavi January 09, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Suppose N is less than large paragraph length M. O(M) time is required.

#include <unordered_map>
#include <string>
#include <deque>
#include <iostream>

class Slider {
 public:
  Slider(const std::deque<std::string>& para, const std::deque<std::string>& words) : para_(para) {
    if (para.size() < words.size())
      return;
    for (auto& w : words)
      words_[w]++;
    words_left_ = words.size();
    min_para_ = std::make_pair(0, -1);
  }

  bool next_word() {
    if (!words_left_) {
      next_site();
    }
    if (idx_ >= para_.size())
      return false;
    auto w = para_[idx_++];
    auto it = words_.find(w);
    if (it == words_.end()) {
      if (length_ == 0) {
        // if slider is empty then start with the next word; this condition can be removed.
        ++site_;
        return true;
      } else {
        ++length_;
      }
    } else {
      ++length_;
      // negative is ok, but if positive then less words left to find
      if ((--it->second) >= 0) {
        --words_left_;
      }
    }
    return true;
  }

  int site() const {
    return min_para_.first;
  }

  int length() const {
    return min_para_.second;
  }
 private:
  void next_site()
  {
    while (!words_left_) {
      // if no words to find left then check if new subparagraph is less than prev one
      if (min_para_.second == -1 || min_para_.second > length_) {
        min_para_.first = site_;
        min_para_.second = length_;
      }
      // try move slider right
      --length_;
      auto w = para_[site_++];
      auto it = words_.find(w);
      if (it != words_.end() && (++it->second) > 0) {
        ++words_left_;
      }
    }
  }

  const std::deque<std::string> &para_;
  std::unordered_map<std::string, int> words_; // words and word counts
  int words_left_;  // number of words left to find
  int site_ = 0;    // slider start
  int length_ = 0;  // slider length
  int idx_ = 0;     // next word following slider
  std::pair<int, int> min_para_;  // subparagraph idx and length
};

int main() {
  std::deque<std::string> para = {"alpha", "beta", "gamma", "beta", "aba", "beta", "zeta", "beta", "zen", "cat", "car", "beta", "aba", "beta", "broad"};
  std::deque<std::string> words = {"aba", "beta", "cat", "beta"};

  Slider slider(para, words);
  while (slider.next_word())
    ;
  if (slider.length() > 0)
    std::cout << "Min subparagraph length is " << slider.length() << std::endl;
}

- S.M. January 09, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N) solution taking constant space:fill a counting bloom filter with the needed value.
Create a window of M elements, fill another counting bloom filter with that, move the window by one word, and test if the new bloom filter is equivalent to the one needed. Continue till a match is found or end of word list. If match is found, check if the match is correct by using a hashmap equivalence which is O(M). So worst case, O(MN), best case is O(N). Minor optimisations, if a word is not in the list, then move the window to after that word.

- Steffy January 13, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More