Google Interview Question Software Engineer / Developers
Country: United States
function check (pattern, string) {
var map = {}
for (var i = 0; i < pattern.length; ++i) {
if (map[pattern[i]] === undefined) {
map[pattern[i]] = null
}
}
var string = string.split(' ')
if (pattern.length !== string.length) {
return false
}
for (i = 0; i < string.length; ++i) {
if (!map[pattern[i]]) {
map[pattern[i]] = string[i]
} else {
if (map[pattern[i]] !== string[i]) {
return false
}
}
}
return true
}
var pattern = ['a', 'b', 'b', 'a']
var string = 'cat dog dog cat'
console.log(check(pattern, string))
// Here is one way to resolve this problem in linear time.
/*
0 1 2 3
a b b a --> 0 1 1 0
= 0 1 2 3
cat dog dog cat --> 0 1 1 0
*/
#include <map>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
class PatternBuilder {
map<string, int> patternCollection;
vector<string> tmpStrList;
vector<int> patternList;
string inputStr;
public:
PatternBuilder(string input): inputStr(input) {
// Separate the input string into the tmpStrList.
string tmpStr="";
for( auto & ch: input){
if( ch != ' ' ){
tmpStr+=ch;
}
else if(!tmpStr.empty()){
tmpStrList.push_back(tmpStr);
tmpStr = "";
}
}
if(!tmpStr.empty()){
tmpStrList.push_back(tmpStr);
tmpStr = "";
}
// Build the patternCollection.
for( unsigned i=0 ; i<tmpStrList.size() ; i++){
// If the Key (tmpStrList[i]) exist, the insertion will be ignored.
patternCollection.insert( {tmpStrList[i], i} );
}
for( auto & str: tmpStrList ){
patternList.push_back( patternCollection[str] );
}
}
friend bool operator== (const PatternBuilder & lhs, const PatternBuilder & rhs){
if( lhs.patternList.size() != rhs.patternList.size() ) return false;
for( unsigned ii = 0 ; ii<lhs.patternList.size() ; ii++ ){
if( lhs.patternList[ii] != rhs.patternList[ii] ) return false;
}
return true;
}
string getString(){ return inputStr; }
};
int main(){
PatternBuilder patternA(" a b b a "),
patternB(" cat dog dog cat");
if( patternA == patternB ){
cout<< "Pattern:" << patternA.getString() << "=" <<endl
<< "Pattern:" << patternB.getString() <<endl;
}
return 0;
}
public static void main(String[] args) {
String [] pattern = { "a","b","b","a" };
String [] inputs = {
"cat dog cat cat",
"cat dog dog cat",
"dog cat cat dog",
"cat cat cat cat",
"cat dog cat dog"
};
System.out.println("Pattern:" + "a,b,b,a" );
for( String input: inputs ){
System.out.println( "Does String Match the Pattern: " + input + "\t:" + patternMatch( input.split(" "), pattern ));
}
}
private static boolean patternMatch( String [] input, String [] pattern ){
if( input.length != pattern.length){
return false;
}
Map<String, String> dic = new HashMap<String, String>();
for( int i = 0; i < input.length; i++ ){
if( !dic.containsKey( pattern[i]) && !dic.containsKey( input[i])){
dic.put( pattern[i], input[i]);
dic.put( input[i] , pattern[i]);
}else if( dic.get( pattern[i]) == null || !dic.get( pattern[i]).equals( input[i]) ){
return false;
}
}
return true;
}
In ZoomBA :
/*
1. we start with the values, and assigning them the keys from pattern
2. If we find a key whose value does not match the word, we failed
3. Else we have succeeded
*/
def matches( pattern , str_list ){
if ( size(pattern) != size(str_list) ) return false
keys = dict()
fold ( str_list , true ) -> {
key = pattern[$.i]
word = $.o
if ( key @ keys ){ // key exists
// if the value pointed by the key is the word?
// then ok, else fail
break ( keys[key] != word ) { false }
} else {
// this is new word, make a key,value out of it
keys[key] = word
}
$.p
}
}
pattern = [ 'a' , 'b', 'b' , 'a' ]
string = [ 'cat', 'dog', 'dog', 'cat' ]
println ( matches ( pattern, string ) )
function matchPattern(pattern, string) {
var strArray = string.split(' ');
if (strArray.length != pattern.length) return false;
var patternWordMap = {};
for (let i = 0; i < strArray.length; i++) {
if (patternWordMap[strArray[i]] != undefined) {
var recordedCode = patternWordMap[strArray[i]];
if (recordedCode != pattern[i]) return false;
continue;
}
patternWordMap[strArray[i]] = pattern[i];
}
return true;
}
In Python 2.7
pattern = [ 'a','b','b','a', 'a', 'c' ]
s = [ 'cat', 'dog', 'bulldog', 'cat', 'cat', 'mouse']
def encodeString(pattern,s):
# Find distinct symbols in pattern
distinctSymbols = set(pattern)
print "The distinct symbols in the pattern are : %s\n" % (distinctSymbols)
# Find first occurences of all distinct patterns
firstOccurence = {}
for symbol in distinctSymbols:
firstOccurence[symbol] = pattern.find(symbol)
# Find the mapping between pattern and string
mapping = {}
for i in firstOccurence.values():
mapping[pattern[i]] = s[i]
print mapping
# Constrcut a new list from the mapping
newList = []
for symbol in pattern:
newList.append(mapping[symbol])
print "\nThe newly constructed string : %s" % newList
print newList == s
return newList == s
if encodeString(''.join(pattern),s):
print "The given pattern %s matches the list of strings %s.\n" % (pattern,s)
else:
print "The given pattern %s does not match the list of strings %s.\n" % (pattern,s)
"""
Pseudocode
find first occurence of a,b,c
map this first occurence on s to get the coressponding values for a,b,c in s, build a hash table with that mapping
replace contents in s with their coressponding map
check if str(pattern) == str(s)
"""
import java.util.LinkedHashMap;
import java.util.Map;
public class PatternStr {
private static String pattern = "[a b b a]";
private static String words = "cat dog dog cat";
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(match(pattern, words));
}
public static boolean match(String pat, String s) {
String[] p = pat.replaceAll("[\\]\\[]", "").trim().split("\\s+");
Map<String, String> sToP = new LinkedHashMap<>();
String[] sArr = s.split("\\s+");
if (p.length != sArr.length) {
return false;
}
for (int i = 0; i < sArr.length; i++) {
String patt = p[i];
if (sToP.containsKey(sArr[i])) {
patt = sToP.get(sArr[i]);
if (!patt.equals(p[i])) {
return false;
}
} else if (sToP.containsValue(p[i])) {
return false;
}
sToP.put(sArr[i], patt);
}
return true;
}
}
import java.util.HashMap;
import com.google.common.collect.HashBiMap;
public class Main {
public static void main(String[] args) {
char[] pattern = {'a','a','b','a'};
String s = "cat dog dog cat";
if(checkPattern(pattern,s)){
System.out.println("String follows pattern.");
}else{
System.out.println("String doesn't follow pattern.");
}
}
private static boolean checkPattern(char[] pattern, String s) {
String[] array = s.split(" ");
if(array.length != pattern.length){
return false;
}
HashBiMap<Character, String> map = HashBiMap.create();
for(int i=0; i<pattern.length; i++){
if(!map.containsKey(pattern[i]) && !map.inverse().containsKey(array[i])){
map.put(pattern[i], array[i]);
}else if(map.containsKey(pattern[i])){
if(!map.get(pattern[i]).equals(array[i])){
return false;
}
}else{
return false;
}
}
return true;
}
}
Simplest of all
def match_pattern(pattern,inputStr):
d = {}
pattern = pattern.split(' ')
inputStr = inputStr.split(' ')
match = True
for i in range(len(pattern)):
if pattern[i] not in d.keys():
d[pattern[i]] = inputStr[i]
else:
if d[pattern[i]] != inputStr[i]:
match = False
break
return match
pattern = 'a b b a'
inputStr = 'cat dog dog mat'
print(match_pattern(pattern,inputStr))
{public static bool StringMatchingPattern(string pattern, string stringOfStrings)
{
var patternAsArray = pattern.Split(' ').ToArray();
var stringsAsArray = stringOfStrings.Split(' ').ToArray();
//basic validation
if (patternAsArray.Length != stringsAsArray.Length)
return false;
//store each string (as key) and its corresponding patter symbole (as value)
//e.g [cat --> a] [dog --> b]
Dictionary<string, string> MappingTable = new Dictionary<string, string>();
for (int i = 0; i < stringsAsArray.Length; i++)
{
if (!MappingTable.ContainsKey(stringsAsArray[i]))
{
MappingTable.Add(stringsAsArray[i], patternAsArray[i]);
}
else
{
if (MappingTable[stringsAsArray[i]] != patternAsArray[i])
return false;
}
}
return true;
}}
def matchpatternkey(string, pattern):
map={}
reversemap={}
string=string.split()
if len(string)!=len(pattern):
return False
for index in xrange(0,len(pattern)):
try:
if pattern[index] not in map.keys() and string[index] not in reversemap.keys():
map[pattern[index]]=string[index]
reversemap[string[index]]=pattern[index]
else:
if map[pattern[index]]!=string[index] or \
reversemap[string[index]]!=pattern[index]:
return False
except:
return False
return True
print matchpatternkey('',['a']) --False
print matchpatternkey("dog dog cat meow bark",['a','a','b','c','e']) --True
print matchpatternkey("dog dog cat meow dog",['a','a','b','c','e']) -- False
A basic C++ brute force approach without
abstracting away with STL maps.
bool match(const std::string& pats,
const std::vector<std::string>& strs)
{
if (pats.size() != strs.size) return false;
int count = pattern.size();
for (int i = 0; i < cout; ++i)
{
for (int j = i; j < count; ++j)
{
if (pats[i] == pats[j] && strs[i] != strs[j]) ||
(pats[i] != pats[j] && strs[i] == strs[j])
return false;
}
}
return true;
}
Two C++ solutions, based on STL. The first solution may or may not be
good enough as it considers {a, b}, {cat, cat} to be a match, but that
depends on the nature of the problem
bool matched(const std::vector<std::string>& pat,
const std::vector<std::string>& str)
{
if (pat.size() != str.size()) return false;
std::map<std::string, std::string> match;
for (size_t i = 0; i < pat.size(); ++i)
{
if (match.insert(std::make_pair(pat[i], str[i]))
.first->second != str[i])
return false;
}
return true;
}
//a,a == cat,dog => false
//a,b == cat,dog => true
//a,b == cat,cat => true (Is this OK?)
//a,b == cat,dog,moo => false
Now lets say we want to match the pattern with the strings, and the
strings back with the pattern, thus avoiding the third result above.
We simply add another map to match in reverse.
bool matched(const std::vector<std::string>& pat,
const std::vector<std::string>& str)
{
if (pat.size() != str.size()) return false;
std::map<std::string, std::string> patMatch;
std::map<std::string, std::string> strMatch;
for (size_t i = 0; i < pat.size(); ++i)
{
if (patMatch.insert(std::make_pair(pat[i], str[i]))
.first->second != str[i] ||
strMatch.insert(std::make_pair(str[i], pat[i]))
.first->second != pat[i])
return false;
}
return true;
}
//a,a == cat,dog => false
//a,b == cat,dog => true
//a,b == cat,cat => false
//a,b == cat,dog,moo => false
Some code to test
#include <iostream>
#include <string>
#include <map>
#include <vector>
void test(const std::vector<std::string>& pat,
const std::vector<std::string>& str)
{
if (pat.size() > 0) std::cout << pat[0];
for (size_t i = 1; i < pat.size(); ++i)
std::cout << "," << pat[i];
std::cout << " == ";
if (str.size() > 0) std::cout << str[0];
for (size_t i = 1; i < str.size(); ++i)
std::cout << "," << str[i];
std::cout << " => " << std::boolalpha
<< matched(pat, str) << std::endl;
}
int main()
{
typedef std::vector<std::string> array;
test(array({"a", "a"}), array({"cat", "dog"}));
test(array({"a", "b"}), array({"cat", "dog"}));
test(array({"a", "b"}), array({"cat", "cat"}));
test(array({"a", "b"}), array({"cat", "dog", "moo"}));
}
Obviously could be written better but you could just loop through the words in the string and use a dictionary to keep track and compare:
var pattern = [1,2,1,2];
var string = "hello world fan world";
var stringArray = string.split(" ");
var dict = {};
isSamePattern();
function isSamePattern(){
if(pattern.length !== stringArray.length) return false;
for(var i = 0; i<stringArray.length; i++){
if(dict[pattern[i]]) {
if(dict[pattern[i]] !== stringArray[i]) return false;
} else {
dict[pattern[i]] = stringArray[i];
}
}
return true;
}
Obviously this could be written better but you could do a loop and use a dictionary to keep track
var pattern = [1,2,1,2];
var string = "hello world fan world";
var stringArray = string.split(" ");
var dict = {};
isSamePattern();
function isSamePattern(){
if(pattern.length !== stringArray.length) return false;
for(var i = 0; i<stringArray.length; i++){
if(dict[pattern[i]]) {
if(dict[pattern[i]] !== stringArray[i]) return false;
} else {
dict[pattern[i]] = stringArray[i];
}
}
return true;
}
Obviously this could be written better but you could do a loop and use a dictionary to keep track.
var pattern = [1,2,1,2];
var string = "hello world fan world";
var stringArray = string.split(" ");
var dict = {};
isSamePattern();
function isSamePattern(){
if(pattern.length !== stringArray.length) return false;
for(var i = 0; i<stringArray.length; i++){
if(dict[pattern[i]]) {
if(dict[pattern[i]] !== stringArray[i]) return false;
} else {
dict[pattern[i]] = stringArray[i];
}
}
return true;
}
Obviously this could be written better but you could do a loop and use a dictionary to keep track.
var pattern = [1,2,1,2];
var string = "hello world fan world";
var stringArray = string.split(" ");
var dict = {};
isSamePattern();
function isSamePattern(){
if(pattern.length !== stringArray.length) return false;
for(var i = 0; i<stringArray.length; i++){
if(dict[pattern[i]]) {
if(dict[pattern[i]] !== stringArray[i]) return false;
} else {
dict[pattern[i]] = stringArray[i];
}
}
return true;
}
Obviously this could be written better but you could do a loop and use a dictionary to keep track
var pattern = [1,2,1,2];
var string = "hello world fan world";
var stringArray = string.split(" ");
var dict = {};
isSamePattern();
function isSamePattern(){
if(pattern.length !== stringArray.length) return false;
for(var i = 0; i<stringArray.length; i++){
if(dict[pattern[i]]) {
if(dict[pattern[i]] !== stringArray[i]) return false;
} else {
dict[pattern[i]] = stringArray[i];
}
}
return true;
}
var pattern = [1, 2, 2, 1];
var string = "cat dog dog cat";
var stringArray = string.split(" ");
var dict = {};
isSamePattern();
function isSamePattern() {
if (pattern.length !== stringArray.length) return false;
for (var i = 0; i < stringArray.length; i++) {
if (dict[pattern[i]]) {
if (dict[pattern[i]] !== stringArray[i]) return false;
} else {
dict[pattern[i]] = stringArray[i];
}
}
return true;
}
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,i,j,cnt=1;
cin>>n;
char p[n];
string str[n];
for(i=0;i<n;i++)
cin>>p[i];
for(i=0;i<n;i++)
cin>>str[i];
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(p[i]==p[j])
{
if(str[i]!=str[j])
{
cnt=0;
}
}
if(p[i]!=p[j])
{
if(str[i]==str[j])
{
cnt=0;
}
}
if(cnt==0)
{
cout<<"n0";
break;
}
}
if(cnt==0)
{
break;
}
}
if(cnt==1)
{
cout<<"yes";
}
}
}
- Weshall December 03, 2016import java.util.HashMap; import java.util.Map; public class PatternMatch { public static void main(String... args) { String[] strings = {"cat", "dog", "dog"}; String[] pattern = {"a", "b", "b"}; boolean matched = true; if(strings.length != pattern.length) { matched = false; } else { Map<String, String> map = new HashMap(); for (int i = 0; i < strings.length; i++) { if(map.containsKey(strings[i])) { if(!map.get(strings[i]).equals(pattern[i])) { matched = false; } } else { map.put(strings[i], pattern[i]); } } } if(matched) { System.out.println("Matched pattern"); } else { System.out.println("Pattern not found"); } } }