Google Interview Question
Country: United States
Interview Type: In-Person
this is almost right, you need to check for length equality. otherwise,
abcdefghijk encodes to "1234567891011"
abcdefghijaa also encodes to "1234567891011"
but this should clearly return false.
Basically make a hash of the given pattern with different letters taking different values, regardless of character value. Check the entries for matching hashes. O(n).
package main
import "fmt"
/*
Given a Pattern and a dictionary, print out all the strings that match the pattern,
where a character in the pattern is mapped uniquely to a character in the dictionary.
e.g.
1. ("abc" , <"cdf", "too", "hgfdt" ,"paa">) -> output = "cdf"
2. ("acc" , <"cdf", "too", "hgfdt" ,"paa">) -> output = "too", "paa"
*/
func main() {
m := map[string][]string{
"abc": []string{"cdf", "too", "hgfdt", "paa"},
"acc": []string{"cdf", "too", "hgfdt", "paa"},
}
for k, _ := range m {
fmt.Println(uniquePatterns(m, k))
}
}
func uniquePatterns(m map[string][]string, pat string) []string {
var result []string
h := hash(pat)
for _, s := range m[pat] {
if hash(s) == h {
result = append(result, s)
}
}
return result
}
func hash(s string) string {
var start byte
var result []byte
m := map[byte]byte{}
for _, c := range []byte(s) {
if v, ok := m[c]; ok {
result = append(result, v)
} else {
m[c] = start
result = append(result, start)
start++
}
}
return string(result)
}
public static void main(String[] args) {
String pattern = "acc";
String[] dictionary = { "cdf", "too", "hfgdt", "paa" };
System.out.println(findMatch(dictionary, pattern));
}
private static List<String> findMatch(String[] dictionary, String pattern) {
List<String> result = new ArrayList<String>();
String encodePattern = encode(pattern);
for (String s : dictionary) {
if (encode(s).equals(encodePattern)) {
result.add(s);
}
}
return result;
}
private static String encode(String pattern) {
Map<Character, Integer> encoder = new HashMap<Character, Integer>();
StringBuilder sb = new StringBuilder();
int counter = 1;
for (char c : pattern.toCharArray()) {
if (null == encoder.get(c)) {
encoder.put(c, counter++);
}
sb.append(encoder.get(c));
}
return sb.toString();
}
public static void main(String[] args) {
String pattern = "acc";
String[] dictionary = { "cdf", "too", "hfgdt", "paa" };
System.out.println(findMatch(dictionary, pattern));
}
private static List<String> findMatch(String[] dictionary, String pattern) {
List<String> result = new ArrayList<String>();
String encodePattern = encode(pattern);
for (String s : dictionary) {
if (encode(s).equals(encodePattern)) {
result.add(s);
}
}
return result;
}
private static String encode(String pattern) {
Map<Character, Integer> encoder = new HashMap<Character, Integer>();
StringBuilder sb = new StringBuilder();
int counter = 1;
for (char c : pattern.toCharArray()) {
if (null == encoder.get(c)) {
encoder.put(c, counter++);
}
sb.append(encoder.get(c));
}
return sb.toString();
}
public class Solution {
public static void main(String [] args) {
String [] array1 = {"cdf", "too", "hgfdt" ,"paa"};
System.out.println(isMatch("abc", "too"));
System.out.println(Arrays.toString(getMatchedWords("abc", array1)));
System.out.println(Arrays.toString(getMatchedWords("acc", array1)));
}
public static String [] getMatchedWords(String pattern, String [] words) {
return Arrays.stream(words)
.filter(s -> isMatch(pattern, s))
.toArray(String[]::new);
}
public static boolean isMatch(String pattern, String word) {
if (pattern.length() != word.length()) {
return false;
}
Map<Character, Character> map = new HashMap<>();
Set<Character> occupied = new HashSet<>();
for (int i = 0; i < pattern.length(); i++) {
if (!map.containsKey(pattern.charAt(i))) {
if (!occupied.contains(word.charAt(i))) {
map.put(pattern.charAt(i), word.charAt(i));
occupied.add(word.charAt(i));
} else {
return false;
}
} else {
if (map.get(pattern.charAt(i)) != word.charAt(i)) {
return false;
}
}
}
return true;
}
}
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Solution {
public:
vector<string> findMatch(string pattern, unordered_set<string> dict) {
vector<string> result = {};
if (pattern.empty() || dict.empty())
return result;
string hash = encode(pattern);
for (auto iter = dict.begin(); iter != dict.end(); iter++) {
if (hash.compare(encode(*iter)) == 0) {
result.push_back(*iter);
}
}
return result;
}
string encode(string s) {
unordered_map<char,int> _encode;
int count = 1;
string sb;
for (int i = 0; i < s.size(); i++) {
auto iter = _encode.find(s[i]);
if (iter == _encode.end()) {
_encode[s[i]] = count++;
}
sb.append(to_string(_encode[s[i]]));
}
return sb;
}
};
void printResult(vector<string> v) {
for (int i = 0; i < v.size(); i++)
cout << v[i] << " ";
}
int main () {
Solution s;
std::unordered_set<std::string> dict1 = {"cdf","too","hgft", "paa"};
vector<string> result = s.findMatch("abc", dict1);
cout << endl << "Result for dict1 is: "; printResult(result);
std::unordered_set<std::string> dict2 = {"cdf","too","hgft", "paa"};
result = s.findMatch("acc", dict2);
cout << endl << "Result for dict2 is: "; printResult(result);
std::unordered_set<std::string> dict3 = {};
result = s.findMatch("acc", dict3);
cout << endl << "Result for dict3 is: " ; printResult(result);
std::unordered_set<std::string> dict4 = {"abc"};
result = s.findMatch("", dict3);
cout << endl << "Result for dict4 is: "; printResult(result);
return 0;
}
Swift 2.2
func getNumberedPattern(word: String) -> [Int] {
var identifier = 0;
var patternHash = [Character: Int]()
var pattern = [Int]()
for character in word.characters {
if (patternHash[character] == nil) {
patternHash[character] = identifier
identifier += 1
}
pattern.append(patternHash[character]!)
}
return pattern
}
func match(pattern: String, words:[String]) -> [String]{
var matches = [String]()
for word in words {
if (getNumberedPattern(word) == getNumberedPattern(pattern)) {
matches.append(word)
}
}
return matches;
}
match("abc", words: ["cdf", "too", "hgfdt", "paa"]) // ["cdf"]
match("acc", words: ["cdf", "too", "hgfdt", "paa"]) // ["too", "paa"]
One line in Python:
def check_patterns(words, p):
return [word
for word in words
if len(word) == len(p) and\
len(set(zip(word, p))) == len(set(word)) == len(set(p))
]
words = ["cdf", "too", "hgfdt" ,"paa"]
p = "abc"
p1 = "acc"
print(check_patterns(words, p))
print(check_patterns(words, p1))
Python 3:
import re
import string
class PatternMatcher:
def __init__(self, pattern):
self.pattern = pattern.lower()
self.clean_pattern = self.make_clean_pattern()
self.re = self.make_re()
def re_part(self, n):
if n == 0:
return "(.)"
else:
regex = "("
for i in range(n):
regex += '(?!\\{0})'.format(i+1)
regex += ".)"
return regex
def make_clean_pattern(self):
nth = 0
clean_pattern = self.pattern
for i in clean_pattern:
if i in string.ascii_lowercase:
clean_pattern = clean_pattern.replace(i, str(nth))
nth += 1
return clean_pattern
def make_re(self):
seen = []
regex = "^"
for i in self.clean_pattern:
if i in seen:
regex += "\\{0}".format(str(int(i)+1))
else:
regex += self.re_part(int(i))
seen.append(i)
regex += "$"
return re.compile(regex)
def get_matches(self, *strings):
return [i for i in strings if self.re.match(i) is not None]
abc = PatternMatcher("abc")
print(abc.get_matches("cdf", "too", "hgfdt", "paa"))
acc = PatternMatcher("acc")
print(acc.get_matches("cdf", "too", "hgfdt", "paa"))
import java.util.*;
class Animal{
String type;
Animal(String type){
this.type=type;
}
}
class Cat extends Animal{
String family;
Cat(String family){
super("mammal");
this.family=family;
}
}
public class Test{
public static void main(String[] args){
HashMap<Character,Character> dict=new HashMap<Character,Character>();
Scanner sc=new Scanner(System.in);
System.out.print("Enter Pattern:");
String pattern= sc.nextLine();
char[] a=pattern.toCharArray();
char[] b;int flag=0;
System.out.print("\nEnter words:");
String line=sc.nextLine();
String[] words=line.split("\\s");
char t1,t2;
for(String word:words){
if(word.length()>length){
flag=0;
continue;
}
flag=0;
b=word.toCharArray();
for(int i=0;i<pattern.length();++i){
if(dict.containsKey(a[i])){
t1=dict.get(a[i]);
if(t1!=b[i]){
flag=0;break;
}
else{
flag=1;
continue;
}
}
else{
//But if
if(dict.containsValue(b[i])){
flag=0;
break;
}
dict.put(a[i],b[i]);
flag=1;
}
dict.put(a[i],b[i]);
}
if(flag==1){
System.out.println(word);
}
dict.clear();
}
}
}
public static void main(String args[]) {
String pattern = "acc";
String dictionary[] = { "cdf", "too", "hgfdt", "paa" };
findMatchingPattern(pattern, dictionary).forEach(System.out::println);
}
public static List<String> findMatchingPattern(String pattern, String dictionary[]) {
int patternLength = pattern.length();
long uniqueLength = getUniqueChars(pattern);
return Arrays.stream(dictionary)
.filter(string -> string.length() == patternLength)
.filter(string -> getUniqueChars(string) == uniqueLength)
.collect(Collectors.toList());
}
private static long getUniqueChars(String string) {
return string.chars().distinct().count();
}
complexity = O(n). getUniqueChars = O(n), findMatchingPattern = O(n)
public static void main(String[] args) {
String pattern = "acc";
String[] dictionary = { "cdf", "too", "hfgdt", "paa" };
if(!Arrays.equals(findMatch(dictionary, pattern), new String[]{"too","paa"})){
throw new IllegalStateException("Test failed!");
}
}
static String[] findMatch(String[] dictionary, String pattern)
{
ArrayList<String> results = new ArrayList<String>(dictionary.length);
for(String entry:dictionary){
if(matches(entry,pattern)){
results.add(entry);
}
}
return results.toArray(new String[results.size()]);
}
private static boolean matches(String entry, String pattern)
{
if(entry.length()!=pattern.length()){
return false;
}
boolean[] vocabulary = new boolean[27];
Character[] lookupTable = new Character[27];
StringBuilder encoding = new StringBuilder(pattern.length());
for(int i=0;i<pattern.length();i++){
char p = pattern.charAt(i);
char e = entry.charAt(i);
int index = e - 'a';
int vocabIndex = p - 'a';
if(lookupTable[index] == null){
if(vocabulary[vocabIndex]){
return false;
}
lookupTable[index] = p;
vocabulary[vocabIndex] = true;
}
encoding.append(lookupTable[index]);
}
return pattern.equals(encoding.toString());
}
import java.util.*;
public class Solution {
public static void main(String args[]) {
if (args.length < 1) return;
String pattern = args[0];
String[] dictionary = new String[]{"abc", "eee", "ebe", "asdfdsa", "uhe"};
for (int i=0; i<dictionary.length; i++) {
System.out.print( (patternCheck(pattern, dictionary[i])) ? dictionary[i]+" " : "");
}
System.out.println();
}
public static boolean patternCheck(String pat, String str) {
HashMap<Character, Character> d = new HashMap<Character, Character>(26);
if (str.length() != pat.length()) return false;
int len = str.length();
for (int i=0; i<len; i++) {
char s = str.charAt(i), p = pat.charAt(i);
if (!d.containsKey(s)) {
if (d.containsValue(p)) return false;
d.put(s, p);
continue;
}
if (p != d.get(s)) return false;
}
return true;
}
}
import java.util.ArrayList;
import java.util.Enumeration;
import java.util.Hashtable;
public class PatternMatching {
public static String findPattern(Hashtable<String, Integer> patternMatcher){
Enumeration<String> keys = patternMatcher.keys();
String key;
String pattern = "";
while(keys.hasMoreElements()){
key = (String) keys.nextElement();
if(patternMatcher.get(key) > 0){
pattern += patternMatcher.get(key)+"";
}
}
return pattern;
}
public static Hashtable<String, Integer> initializePatternMatcher(){
Hashtable<String, Integer> patternMatcher = new Hashtable<String, Integer>();
for(int i = 97; i <= 122; i++ ){
patternMatcher.put(Character.toString ((char) i), 0);
}
return patternMatcher;
}
public static Hashtable<String, Integer> computePattern(Hashtable<String, Integer> patternMatcher, String s){
char[] key;
key = s.toCharArray();
for(char k : key){
if(patternMatcher.containsKey(Character.toString(k))){
int value = patternMatcher.get(Character.toString (k));
patternMatcher.put(Character.toString(k), ++value);
}
}
return patternMatcher;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<String> dict = new ArrayList<String>();
dict.add("cdf");
dict.add("too");
dict.add("hgfdt");
dict.add("paa");
Hashtable<String, Integer> patternMatcher = initializePatternMatcher();
String pattern = "caa";
patternMatcher = computePattern(patternMatcher, pattern);
String testPattern = findPattern(patternMatcher);
patternMatcher = initializePatternMatcher();
int patLen = pattern.length();
for(String s : dict)
{
if(s.length() == patLen){
patternMatcher = computePattern(patternMatcher, s);
String finalPattern = findPattern(patternMatcher);
if(testPattern.equalsIgnoreCase(finalPattern)){
System.out.println(testPattern +" "+ finalPattern);
System.out.println(s);
}
patternMatcher = initializePatternMatcher();
}
}
}
}
import java.util.ArrayList;
import java.util.Enumeration;
import java.util.Hashtable;
public class PatternMatching {
public static String findPattern(Hashtable<String, Integer> patternMatcher){
Enumeration<String> keys = patternMatcher.keys();
String key;
String pattern = "";
while(keys.hasMoreElements()){
key = (String) keys.nextElement();
if(patternMatcher.get(key) > 0){
pattern += patternMatcher.get(key)+"";
}
}
return pattern;
}
public static Hashtable<String, Integer> initializePatternMatcher(){
Hashtable<String, Integer> patternMatcher = new Hashtable<String, Integer>();
for(int i = 97; i <= 122; i++ ){
patternMatcher.put(Character.toString ((char) i), 0);
}
return patternMatcher;
}
public static Hashtable<String, Integer> computePattern(Hashtable<String, Integer> patternMatcher, String s){
char[] key;
key = s.toCharArray();
for(char k : key){
if(patternMatcher.containsKey(Character.toString(k))){
int value = patternMatcher.get(Character.toString (k));
patternMatcher.put(Character.toString(k), ++value);
}
}
return patternMatcher;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<String> dict = new ArrayList<String>();
dict.add("cdf");
dict.add("too");
dict.add("hgfdt");
dict.add("paa");
Hashtable<String, Integer> patternMatcher = initializePatternMatcher();
String pattern = "caa";
patternMatcher = computePattern(patternMatcher, pattern);
String testPattern = findPattern(patternMatcher);
patternMatcher = initializePatternMatcher();
int patLen = pattern.length();
for(String s : dict)
{
if(s.length() == patLen){
patternMatcher = computePattern(patternMatcher, s);
String finalPattern = findPattern(patternMatcher);
if(testPattern.equalsIgnoreCase(finalPattern)){
System.out.println(testPattern +" "+ finalPattern);
System.out.println(s);
}
patternMatcher = initializePatternMatcher();
}
}
}
}
import java.util.ArrayList;
import java.util.Enumeration;
import java.util.Hashtable;
public class PatternMatching {
public static String findPattern(Hashtable<String, Integer> patternMatcher){
Enumeration<String> keys = patternMatcher.keys();
String key;
String pattern = "";
while(keys.hasMoreElements()){
key = (String) keys.nextElement();
if(patternMatcher.get(key) > 0){
pattern += patternMatcher.get(key)+"";
}
}
return pattern;
}
public static Hashtable<String, Integer> initializePatternMatcher(){
Hashtable<String, Integer> patternMatcher = new Hashtable<String, Integer>();
for(int i = 97; i <= 122; i++ ){
patternMatcher.put(Character.toString ((char) i), 0);
}
return patternMatcher;
}
public static Hashtable<String, Integer> computePattern(Hashtable<String, Integer> patternMatcher, String s){
char[] key;
key = s.toCharArray();
for(char k : key){
if(patternMatcher.containsKey(Character.toString(k))){
int value = patternMatcher.get(Character.toString (k));
patternMatcher.put(Character.toString(k), ++value);
}
}
return patternMatcher;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<String> dict = new ArrayList<String>();
dict.add("cdf");
dict.add("too");
dict.add("hgfdt");
dict.add("paa");
Hashtable<String, Integer> patternMatcher = initializePatternMatcher();
String pattern = "caa";
patternMatcher = computePattern(patternMatcher, pattern);
String testPattern = findPattern(patternMatcher);
patternMatcher = initializePatternMatcher();
int patLen = pattern.length();
for(String s : dict)
{
if(s.length() == patLen){
patternMatcher = computePattern(patternMatcher, s);
String finalPattern = findPattern(patternMatcher);
if(testPattern.equalsIgnoreCase(finalPattern)){
System.out.println(testPattern +" "+ finalPattern);
System.out.println(s);
}
patternMatcher = initializePatternMatcher();
}
}
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
public class PatternMatching {
ArrayList <String> matchPattern ( String pattern, ArrayList <String> dict){
ArrayList <String> result = new ArrayList <String> ();
for ( String word: dict ){
if ( word.length()==pattern.length()){
HashMap <Character, Character > match = new HashMap <Character, Character > ();
boolean possiblyValid=true;
for ( int i = 0; i < word.length() && possiblyValid; i++ ){
char patternC = pattern.charAt(i);
char c = word.charAt(i);
if ( match.containsKey(c)){
if ( match.get(c)!= patternC)
possiblyValid=false;
}
else
match.put(c,patternC);
}
if (possiblyValid) result.add(word);
}
}
return result;
}
public static void main(String[] args) {
String pattern = "abc";
ArrayList <String> dict = new ArrayList <String> (Arrays.asList("cdf", "too", "hgfdt" ,"paa", "xyz"));
ArrayList <String> matches = new PatternMatching().matchPattern(pattern, dict);
for (String s:matches)
System.out.println(s);
}
}
void printMatch(String str, ArrayList<String> dict)
{
if(str == null || dict.size() <=0)
return;
String encodedStr = encodeString(str);
for(String match : dict)
{
if (str.length() != match.length())
continue;
String encodedMatch = encodeString(match);
if(encodedStr.Equals(encodedMatch));
print match;
}
return;
}
String encodeString(string str)
{
// We are encoding acc = > 122 , toot => 1221
// acca = 1221 = toot = 1221
// This stores the char and the first occurance in the string
HashTable<char, int> ht = new HashTable<char, int> ();
char[] arr = str.ToCharArray();
for(int i=0 ; i < arr.length; i++)
{
if(ht.ContainsKey(arr[i]))
continue;
ht.put(arr[i], i+1);
}
StringBuilder sb = new StringBuilder();
for(int i=0 ; i < arr.length; i++)
{
sb.Append(ht.get(arr[i]).ToString());
}
return sb.ToString();
}
void printMatch(String str, ArrayList<String> dict)
{
if(str == null || dict.size() <=0)
return;
String encodedStr = encodeString(str);
for(String match : dict)
{
if (str.length() != match.length())
continue;
String encodedMatch = encodeString(match);
if(encodedStr.Equals(encodedMatch));
print match;
}
return;
}
String encodeString(string str)
{
// We are encoding acc = > 122 , toot => 1221
// acca = 1221 = toot = 1221
// This stores the char and the first occurance in the string
HashTable<char, int> ht = new HashTable<char, int> ();
char[] arr = str.ToCharArray();
for(int i=0 ; i < arr.length; i++)
{
if(ht.ContainsKey(arr[i]))
continue;
ht.put(arr[i], i+1);
}
StringBuilder sb = new StringBuilder();
for(int i=0 ; i < arr.length; i++)
{
sb.Append(ht.get(arr[i]).ToString());
}
return sb.ToString();
}
- Priyesh August 02, 2016public static void main(String[] args) { String pattern = "acc"; String[] dictionary = { "cdf", "too", "hfgdt", "paa" }; System.out.println(findMatch(dictionary, pattern)); } private static List<String> findMatch(String[] dictionary, String pattern) { List<String> result = new ArrayList<String>(); String encodePattern = encode(pattern); for (String s : dictionary) { if (encode(s).equals(encodePattern)) { result.add(s); } } return result; } private static String encode(String pattern) { Map<Character, Integer> encoder = new HashMap<Character, Integer>(); StringBuilder sb = new StringBuilder(); int counter = 1; for (char c : pattern.toCharArray()) { if (null == encoder.get(c)) { encoder.put(c, counter++); } sb.append(encoder.get(c)); } return sb.toString(); }