Google Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
import java.util.*;
public class Main{
public static void main(String[] args){
System.out.println(checkAnagram("OGE","GOOGLE"));
}
public static boolean checkAnagram(String input, String input1){
String longestString = input;
String shortestString = input1;
if(input.length() < input1.length()){
longestString = input1;
shortestString = input;
}
List<String> subStrings = new ArrayList<>();
for(int i=0; i< longestString.length();i++){
if(i+shortestString.length() <=longestString.length()){
subStrings.add(longestString.substring(i,i+shortestString.length()));
}
}
for(String subString: subStrings){
HashMap<Character, Integer> map = new HashMap<>();
for(Character character :subString.toCharArray()){
if(map.containsKey(character)){
map.put(character, map.get(character)+1);
}else{
map.put(character,1);
}
}
boolean check = true;
for(Character c :shortestString.toCharArray()){
if(!map.containsKey(c)){
check = false;
break;
}else{
if(map.get(c) > 0){
map.put(c, map.get(c)-1);
}else{
check = false;
break;
}
}
}
if(check){
return true;
}
}
return false;
}
}
public static boolean hasAnagramSubstring(String sub, String word) {
if (sub == null || sub.isEmpty() || word == null || word.isEmpty()) {
return false;
}
String subHash = sortChars(sub); // this will sort the string based on
// characters and will return the
// sorted string.
for (int i = 0; i < word.length() && i + sub.length() - 1 < word.length(); i++) {
String sub2 = word.substring(i, i + sub.length());
String sub2Hash = sortChars(sub2);
if (subHash.equals(sub2Hash)) {
return true;
}
}
return false;
}
private static String sortChars(String s) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
return String.valueOf(chars);
}
Time Complexity : O(m + n) where m and n are size of input strings.
Space Complexity: Constant
bool findSubstrAnagram(string s1, string s2){
if(s1.size() > s2.size())
return false;
if(s1 == s2)
return true;
vector<char> mark_s1(256, 0);
vector<char> mark_s2(256, 0);
for(char c : s1){
mark_s1[c]++;
}
int count = 0;
for(char c : s2){
if(mark_s2[c] < mark_s1[c]){
count++;
mark_s2[c]++;
}
else{
count = 0;
fill(mark_s2.begin(), mark_s2.end(), 0);
}
if(count == s1.size())
return true;
}
return false;
}
Use sliding window with the size of the anagram on the input string
then compare each substring using characters counting.
#include "CommonHeader.h"
class Anagram
{
int chars[256];
size_t length = 0;
public:
Anagram(const std::string& str)
{
memset(chars, 0, sizeof(chars));
length = str.size();
for(size_t i = 0; i < str.size(); ++i) {
chars[(int)str[i]]++;
}
}
/**
* @brief check if this represents an anagram of the string represented between start and end iterators
* This function assumes that the string represented between start-end has the same legnth as the string
* created this object
*/
bool isAnagram(std::string::const_iterator start, std::string::const_iterator end) const
{
int tmp_chars[256];
memcpy(tmp_chars, chars, sizeof(chars));
while(start != end) {
int index = (int)(*start);
tmp_chars[index]--;
if(tmp_chars[index] < 0) {
return false;
}
++start;
}
return true;
}
/**
* @brief check if str contains an anagram of this object, we do this by using a sliding window
*/
bool isSubAnagramOf(const std::string& str) const
{
if(str.size() < length) return false;
// Use sliding window to check for anagram
std::string::const_iterator start;
std::string::const_iterator end;
for(size_t i = 0; i <= (str.size() - length); ++i) {
start = str.begin() + i;
end = str.begin() + i + length;
if(isAnagram(start, end)) {
return true;
}
}
return false;
}
};
bool is_sub_anagram(const std::string& sanag, const std::string& strfull)
{
Anagram ang(sanag);
return ang.isSubAnagramOf(strfull);
}
bool ContainsAnagram(string const s, string const small_s)
{
if (!small_s.empty() &&
small_s.size() <= s.size())
{
vector<int> char_counts;
char_counts.resize(256, 0);
int diffs_count = small_s.size();
for (char c : small_s) {
++char_counts[c];
}
for (int i = 0; i < s.size(); ++i) {
if (char_counts[s[i]] > 0) {
--char_counts[s[i]];
--diffs_count;
} else {
--char_counts[s[i]];
++diffs_count;
}
if (i >= small_s.size()) {
char c = s[i - small_s.size()];
if (char_counts[c] < 0) {
++char_counts[c];
--diffs_count;
} else {
++char_counts[c];
++diffs_count;
}
}
if (diffs_count == 0) {
return true;
}
}
}
return false;
}
C implementation which time complexity is O(M + N). Depending on the range of possible characters, memory consumption can be reduced.
int checkword(char *str1, char *str2)
{
int i, j;
char table1[255];
char table2[255];
memset(table1, 0x0, sizeof(table1));
memset(table2, 0x0, sizeof(table2));
/* this will take O(M) */
for (i = 0; str1[i]; i++)
table1[str1[i]] += 1;
/* remaining loops will take O(N) */
for (j = 0; j < i && str2[j]; j++)
table2[str2[j]] += 1;
while (memcmp(table1, table2, sizeof(table1))) {
if (!str2[j]) return 0;
table2[str2[j]] += 1;
table2[str2[j - i]] -= 1;
j++;
}
return 1;
}
C implementation.
static int checkword(char *str1, char *str2)
{
int i, j;
char table1[255];
char table2[255];
memset(table1, 0x0, sizeof(table1));
memset(table2, 0x0, sizeof(table2));
/* this will take O(M) */
for (i = 0; str1[i]; i++)
table1[str1[i]] += 1;
/* remaining loops will take O(N) */
for (j = 0; j < i && str2[j]; j++)
table2[str2[j]] += 1;
while (memcmp(table1, table2, sizeof(table1))) {
if (!str2[j]) return 0;
table2[str2[j]] += 1;
table2[str2[j - i]] -= 1;
j++;
}
return 1;
}
C implementation.
static int checkword(char *str1, char *str2)
{
int i, j;
char table1[255];
char table2[255];
memset(table1, 0x0, sizeof(table1));
memset(table2, 0x0, sizeof(table2));
/* this will take O(M) */
for (i = 0; str1[i]; i++)
table1[str1[i]] += 1;
/* remaining loops will take O(N) */
for (j = 0; j < i && str2[j]; j++)
table2[str2[j]] += 1;
while (memcmp(table1, table2, sizeof(table1))) {
if (!str2[j]) return 0;
table2[str2[j]] += 1;
table2[str2[j - i]] -= 1;
j++;
}
return 1;
}
C implementation.
static int checkword(char *str1, char *str2)
{
int i, j;
char table1[255];
char table2[255];
memset(table1, 0x0, sizeof(table1));
memset(table2, 0x0, sizeof(table2));
/* this will take O(M) */
for (i = 0; str1[i]; i++)
table1[str1[i]] += 1;
/* remaining loops will take O(N) */
for (j = 0; j < i && str2[j]; j++)
table2[str2[j]] += 1;
while (memcmp(table1, table2, sizeof(table1))) {
if (!str2[j]) return 0;
table2[str2[j]] += 1;
table2[str2[j - i]] -= 1;
j++;
}
return 1;
}
C implementation which takes O(M + N)
static int checkword(char *str1, char *str2)
{
int i, j;
char table1[255];
char table2[255];
memset(table1, 0x0, sizeof(table1));
memset(table2, 0x0, sizeof(table2));
/* this will take O(M) */
for (i = 0; str1[i]; i++)
table1[str1[i]] += 1;
/* remaining loops will take O(N) */
for (j = 0; j < i && str2[j]; j++)
table2[str2[j]] += 1;
while (memcmp(table1, table2, sizeof(table1))) {
if (!str2[j]) return 0;
table2[str2[j]] += 1;
table2[str2[j - i]] -= 1;
j++;
}
return 1;
}
Optimized for speed
/*compare only the character that is present in t1 and repetitive character comparison avoided */
uint8_t table_cmp(char * t1, char * t2, char * s2, uint32_t s)
{
uint32_t i = 0;
while (s--)
{
char c = s2[i++];
if (t2[c] != t1[c])
return 1;
}
return 0;
}
int checkword2(char *str1, char *str2)
{
int i, j;
char table1[255];
char table2[255];
char table3[255];
char t3_ele = 0;
memset(table1, 0x0, sizeof(table1));
memset(table2, 0x0, sizeof(table2));
/* this will take O(M) */
for (i = 0; str1[i]; i++)
table1[str1[i]] += 1;
/* remaining loops will take O(N) */
for (j = 0; j < i && str2[j]; j++) {
if (!table2[str2[j]])
table3[t3_ele++] = str2[j];
table2[str2[j]] += 1;
}
while (table_cmp(table1, table2, table3, t3_ele)) {
if (!str2[j]) return 0;
table2[str2[j]] += 1;
table2[str2[j - i]] -= 1;
j++;
}
return 1;
}
Using a sliding window the complexity is O(m + n). Expects that the char range is 0 - 255 so a hashmap could be better option.
boolean isSubAnagram(String text, String sub) {
// Count chars
int[] counts = new int[256];
for (int i = 0;i < sub.length();i++) {
counts[sub.charAt(i)]++;
}
int neededCount = sub.length();
// Reduce counts using sliding window
for (int i = 0;i < text.length();i++) {
if (i >= sub.length()) {
if (++counts[text.charAt(i - sub.length())] > 0) {
neededCount++;
}
}
if (--counts[text.charAt(i)] >= 0) {
neededCount--;
}
if (neededCount == 0) {
return true;
}
}
return false;
}
def sub_str_and_anagram( s, S ):
if type( s ) != str:
return False
if type( S ) != str:
return False
if s == '':
return True
if len( s ) > len( S ):
return False
d_s = {}
d_S = {}
for i in s:
if i not in d_s:
d_s[i] = 1
else:
d_s[i] += 1
for i in S[:len(s)]:
if i not in d_S:
d_S[i] = 1
else:
d_S[i] += 1
if d_s == d_S:
return True
for i, val in enumerate( S[len(s):] ):
to_remove = S[i]
if val not in d_S:
d_S[val] = 1
else:
d_S[val] += 1
if d_S[to_remove] == 1:
del d_S[to_remove]
else:
d_S[to_remove] -= 1
if d_s == d_S:
return True
return False
from collections import Counter
def anagram_substring(lhs, rhs):
if lhs is None or rhs is None:
return False
if len(lhs) > len(rhs):
return False
lcounter = Counter(lhs)
st, en = 0, len(lhs)
rcounter = Counter(rhs[st:en])
do:
if lcounter == rcounter:
return True
if en == len(rhs):
break
st, en = st+1, en+1
rcounter[rhs[st-1]] -= 1
rcounter[rhs[en-1]] += 1
while True
return False
import collections
compare = lambda x, y : collections.Counter(x) == collections.Counter(y)
def check_subgrams(array):
count = 0
for i in range(len(array) - 1):
if len(array[i]) > len(array[i+1]): continue
else:
dict = {ch:None for ch in list(array[i])}
l1 = len(array[i])
l2 = len(array[i+1])
for j in range(l2 - l1 + 1):
if compare(dict.keys(),list(array[i+1])[j:l1+j]):
count +=1
return count
def main():
in_array = map(str,raw_input().strip().split(' '))
print check_subgrams(in_array)
if __name__=="__main__":
main()
def browntown(s1:str, s2:str)->bool:
if len(s1) != len(s2):
return False
sprime = s2
for c in s1:
try:
index = sprime.index(c)
sprime = sprime[:index] + sprime[index+1:]
except:
pass
if len(sprime) == 0:
return True
return False
# do the whole thing
def elyas(shorty:str, thicc:str)->bool:
start = 0
end = len(shorty)
while end <= len(thicc):
substr = thicc[start:end]
if (browntown(substr, shorty)):
return True
start += 1
end += 1
return False
# compare two equal length strings for anagram
def hotdog(s1:str, s2:str)->bool:
if len(s1) != len(s2):
return False
sprime = s2
for c in s1:
try:
index = sprime.index(c)
sprime = sprime[:index] + sprime[index+1:]
except:
pass
if len(sprime) == 0:
return True
return False
# do the whole thing
def docta(shorty:str, thicc:str)->bool:
start = 0
end = len(shorty)
while end <= len(thicc):
substr = thicc[start:end]
if (hotdog(substr, shorty)):
return True
start += 1
end += 1
return False
print(docta( 'OBL' , 'BOBL' ))
Python/3.6.1: Finding all substrings and checking for anagram.
import sys, copy
def get_all_substrings_of_length(word, n):
subs = []
for i in range(0, len(word) - n + 1):
subs.append(word[i:i+n])
return subs
def is_anagram(subs, word, n):
ref = {}
for i in range(n):
if word[i] in ref:
ref[word[i]] += 1
else:
ref[word[i]] = 1
for sub in subs:
dist = copy.deepcopy(ref)
failed = False
for i in range(n):
if sub[i] in dist:
dist[sub[i]] -= 1
if dist[sub[i]] < 0:
failed = True
break
else:
failed = True
break
if not failed:
for v in dist.values():
if v != 0:
failed = True
break
if not failed:
return True
return False
if __name__ == '__main__':
word1 = sys.argv[1]
word2 = sys.argv[2]
n = len(word1)
subs = get_all_substrings_of_length(word2, n)
print(is_anagram(subs, word1, n))
O(m+n)
public static void main(String args[]) {
System.out.println(anagramPresent("GLE", "GOOGLE"));
}
public static boolean anagramPresent(String a, String b){
double hash = hash(a);
for(int i = 0; i <= b.length()-a.length(); i++){
String sub = b.substring(i, i+a.length());
if(hash(sub) == hash)
return true;
}
return false;
}
public static double hash(String str){
int n = str.length();
int hash = 0;
double K = 8.6534;
for(int i = 0; i < n; i++){
hash += (str.charAt(i))*K;
}
return hash;
}
Can someone post an optimal solution for this?
- anonymous October 07, 2017