Amazon Interview Question for SDE-3s


Country: India
Interview Type: In-Person




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

O(n^2) time, O(n) space.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Node {
	public:
		Node()
		{
			terminal_ = false;
		}
		~Node()
		{
			for (auto it = children_.begin(); it != children_.end(); ++it) {
				delete it->second;
			}
			children_.clear();
		}
		Node *AddChild(char c)
		{
			Node *n = Child(c);
			if (n == NULL) {
				n = new Node();
				children_[c] = n;
			}
			return n;
		}
		Node *Child(char c)
		{
			auto it = children_.find(c);
			return it == children_.end() ? NULL : it->second;
		}

		bool terminal_;

	private:
		unordered_map<char, Node *> children_;
};

class Trie {
	public:
		void Add(string const &s)
		{
			Node *n = &root_;
			for (char c : s) {
				n = n->AddChild(c);
			}
			n->terminal_ = true;
		}
		Node *Root()
		{
			return &root_;
		}

	private:
		Node root_;
};

int Count(Trie &trie, string const &s, vector<int> &memo, int idx = 0)
{
	if (idx < 0 ||
		idx > s.size())
	{
		return 0;
	}
	if (idx == s.size()) {
		return (idx == 0) ? 0 : 1;
	}

	if (memo.size() < s.size()) {
		memo.resize(s.size(), -1);
	}
	if (memo[idx] != -1) {
		return memo[idx];
	}

	int count = 0;
	Node *n = trie.Root();
	for (int i = idx; i < s.size(); ++i) {
		n = n->Child(s[i]);
		if (!n) {
			break;
		}
		if (n->terminal_) {
			count += Count(trie, s, memo, i + 1);
		}
	}

	memo[idx] = count;
	return memo[idx];
}

int main()
{
	Trie trie;
	trie.Add("dog");
	trie.Add("eat");
	trie.Add("eats");
	trie.Add("scare");
	trie.Add("care");

	vector<int> memo;
	cout << Count(trie, "dogeatscare", memo) << "\n";
}

- Alex December 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'd like to store the dictionary of all combinations of words up to the string input size in a hash table. Hash of the input and count the outputs that match.

- Smiller December 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What are the pros and cons of using dictionary (hash) vs Trie.

- CoolGuy December 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@cool guy
the hash table is more space effective than a trie due to pointers etc. and therefore a hashtable can be cash friendlier if short enough. If you use hashtable in the naive way, you will need to recalculate the hash for the string with every lookup, which is not so nice. If you write your own hashtable and hash function you can avoid this by reusing the hashvalue of k-1 characters to calculate hash of k characters (expanding prefix). With a trie, you know if a prefix is not in the dict as soon as you expand a character c[k], with a hashtable you will have to expand every prefix to the max word size in order to make sure it's not in there. This makes the hash algorithm ineffective for some crafted sample input. The tries memory disadvantage can be improved using a patricia tree - sometimes compacted trie, but it will never be as compact in memory as a hashtable.

There was a question on LeetCode like this, and I tried to beat the fastest c++ implementation which used a hashtable approach. I tried using a trie and even a patricia tree implementation. It turned out, the time to create the trie dominated the advantage of the faster lookups because it was one dictionary per query, so, that's always a good thing to think about, how many queries per dictionary instance. An other thing I noticed there, the data in the testcases were just not advantageous for the trie implementation. Short dictionary (fits into cache) with relatively short words.

I could imagine a combination being good, create a sort of trie on substrings of words of fixed size, say 5 characters, so for short words it's like a single hashtable, long words that share a prefix, would behave like a trie etc... I haven't seen anybody doing that and haven't thought really about it, but it kind of jumped into my mind right now.

edited:
maybe I should have added, a ptrica trie can be more space effective than a hashtable for crafted input, but it's not the case for a regular western language.

- Chris December 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;
int main()
{
}

- Anonymous December 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Nice Information share

- Maulana Ji December 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The dynamic solution

//Recursion + memoization(DP), Time O(n), Space O(n)
public static int wordBreakDP(Set<String> dict, String str) {
	Set<String> memo = new HashSet<String>();	
	return wordBreakUtil(dict, str, "", memo);
}

public static int wordBreakUtil(Set<String> dict, String str, String ouput, Set<String> memo) {		
	int count = 0;
	if (memo.contains(str))
		return count + 1;	
	if(str.length() == 0) {
		System.out.println(ouput);
		return count + 1;
	}
	
	for (int i = 1; i <= str.length(); i++) {
		String prefix = str.substring(0, i);			
		if(dict.contains(prefix)) {
			memo.add(ouput + " " + prefix);
			count += wordBreakUtil(dict, str.substring(i), ouput + " " + prefix, memo);				
		}
	}		
	return count;
}

- lavivien17 April 09, 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