Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

We can put all the words in hashset, and then for every character in input word, try to change it and lookup in hashset. overall complexity O(ALPH * N), where N is the length of word and ALPH is the size of alphabet. Usually we skip constants in big O notation, so the complexity O(N)

- Darkhan.Imangaliev October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Fine solution when the difference is 1 character. When we have to search for difference >1, prefix tree is better.

- damluar October 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the complexity is O(N + M), where M is size of array, you will spend time to create a hashmap.

- zr.roman January 09, 2016 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

When you say one character difference can the other string have one character deleted as well? Like 'banana' and 'banan', or do they have to be the same length?

- Anonymous October 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>
using namespace std;

// To execute C++, please define "int main()"

bool isOneCharDiffStringExist(vector<string> list, string s)
{
  int length = (int)list.size();
  
  if(length == 0 || s.size() ==0)
    return false;
  
  for(int i=0;i<length;i++)
  {
    if(list[i].size()!=s.size())
      continue;
    
    bool oneCharDiffFound = false;
    for(int j =0;j<(int)list[i].size();j++)
    {
      if(list[i][j] != s[j] )
      {
          if(!oneCharDiffFound)
            oneCharDiffFound = true;
          else
          {
            oneCharDiffFound = false;
            break;
          }
      }
    }
    
    if(oneCharDiffFound)
      return true;
  }
  
  return false;
}

int main() {
  
  vector<string> list;
  list.push_back("bana");
  list.push_back("apple");
  list.push_back("banacb");
  list.push_back("bonanza");
  list.push_back("banamf");
  
  cout<<isOneCharDiffStringExist(list,"banana");
  return 0;
}

- Anonymous October 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

May be we can construct a prefix tree. And than run a dfs with parameter 1 from the root, which will go to the child if and only if the path to that node is equal to a some prefix or you have one point (parameter) which you can use to go to this child if the path to parent equal to some prefix but the letter in child doesn't equal to the next letter in string.

- Nick October 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this should be the right solution

- Tony October 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

One should be careful when to return true. I thought the task asked that the difference is at most 1. But after re-reading think we should find the difference equal exactly 1.
So when we traverse prefix tree and parameter == 0 and we find some node, then we can return true. But if parameter stays 1, we have to search further, because all characters are equal so far.

- damluar October 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

May be we can construct a prefix tree. And than run a dfs with parameter 1 from the root, which will go to the child if and only if the path to that node is equal to a some prefix or you have one point (parameter) which you can use to go to this child if the path to parent equal to some prefix but the letter in child doesn't equal to the next letter in string.

- Nick October 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I gave the same answer and he asked me to implement it.. :)

- kpraveen420 October 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

- Brute force solution comes out to be O(n^2) i.e you go through each string and compare char by char then if difference of char > 1 you break out of the loop so on.
- Another approach : finding edit distance but thats O(n^2) so if we do it for each string in array then it would be O(n^3)
- Third approach longest subsequence - that is also O(n^2) so overall running time is O(n^3).

- justaguy October 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the query is frequent, we can use a Trie to store the array of string. I omit the code of build Trie for simplify

struct Node {

	bool exist;
	Node *children[256];
};

Node *root;

bool dfs(Node *n, const string &s, int pos, int cnt) {
	if (cnt > 1)
		return false;
	if (pos == s.size())
		return cnt == 1;

	for (int i = 0; i < 256; ++i) {
		Node *c = n->children[i];
		if (c != nullptr) {
			if (s[pos] == i && dfs(c, s, pos + 1, cnt) ||
					s[pos] != i && dfs(c, s, pos + 1, cnt + 1))
				return true;
		}
	}
}

bool hasSimilar(const string &s) {
	return dfs(root, s, 0, 0);
}

- malinbupt October 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

after for loop in dfs function return false is missing.

- Mansi October 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I was pretty close to solve this using trie almost identical way, and gave up at some point, So thank you for posting the solution . Same code could possibly be used for more than one character mis-match, I believe

- Didar Alam October 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we use XOR ing of the characters and keep a track of whether there is more than one time, the XOR produced non-null result ?

- happyCoder October 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why not generate all the words that are one edit (replace/insert/remove one character) away from the input word and look for matches in the dictionary (We need to build a O(1) dictionary out of the list of given words using a hashmap or trie)?

- random October 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Assumption: The word which is 1 character different from the query string may not have its characters in the same order as that of the query string.
public boolean hasSimilarWord(String[] arr,String s)throws NullPointerException;
{
	if(arr==null||s==null)
	{
		throw new NullPointerException();
	}
	
	
	return isOneCharDiff(s,arr);
	
	
}

private boolean isOneCharDiff(String s,String[] words)
{

//Examine each word and see if there's one which only differs by 1 character 
	for(int i=0;i<words.length;i++)
	{
           String x=words[i].length();
             if(x==s.length())
              {
		//Create a HashMap of all the characters in this string
		HashMap<Character,Integer> mp=new HashMap<Character,Integer>();
		for(int i=0;i<x.length();i++)
		{
			if(!mp.containsKey(x.charAt(i)))
			{
				mp.put(x.charAt(i),1);
			}else
			{
				int currCount=mp.get(x.charAt(i)).intValue();
				mp.put(x.charAt(i),++currCount);
			}
		}
		//Check query word against characters in hash map
		for(int j=0;j<s.length();j++)
		{
			if(mp.containsKey(s.charAt(j))
			{
				int currCount=mp.get(s.charAt(j)).intValue();
				--currCount;
				if(currCount==0)
				{
					mp.remove(s.charAt(j));
				}else
				{
					mp.put(s.charAt(j),currCount);
				}
			}
		}
		if(mp.size()==1)
		{
			return true;//If we find a string that differs by just one character, return true.
		}
         }
	}
	return false;
}
//Time complexity: O(kn)--From comparing whether each string has matching characters with the query string (k is the number of strings whose length matches the query string, n is the number of characters in the query string).Space complexity O(k+n)--From the list of words with the same length as the query string and the hash map of characters.

- divm01986 October 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class OneOff {

	private static boolean isOffByOne(String main, String sub) {
		if (main==null || sub == null || main.length() != sub.length())
			return false;
		boolean oneOff= false;
		for (int i=0;i<main.length(); i++) {
			if (main.charAt(i) != sub.charAt(i))
			{
				if (!oneOff) oneOff=true;
				else return false;
			}
		}
		return oneOff;
	}
	public static boolean findOfByOne(String str, String[] candidates) 
	{
		if (str==null || str.length() <1 || candidates.length ==0 )
			return false;
		for (int i=0;i <candidates.length; i++) {
			boolean isOff = isOffByOne(str,  candidates[i]);
				if (isOff) return true;
		}
		return false;
	}
	
	public static void main(String[] args) {
		String[] cands = {"bana", "apple", "banaba", "bonanza", "banamf" };
		System.out.println(findOfByOne("banana", cands));

	}

}

- AbstractInstance October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple sample solution in Python:
Increased space complexity because of additional dictionary for counting common chars for each string

def diff_one(s1, list):
    dict = {}
    for i in list:
        dict[i]=0

    for i,j in enumerate(s1):
        for k in list:
            if i <len(k) and j==k[i]:
                dict[k]+=1
    if len( filter(lambda x: x>len(s1)-2,dict.values()) ):
        return True


if __name__=="__main__":
    if diff_one("banana", ["bana", "apple", "banaba", "bonanza", "banamf", "bananaa"] ):
        print "found"
    else:
        print "not found"

- spyroslal October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

We can build a trie of n strings in O(n) time if we assume that strings are of limited length dictionary words and alphabet size is limited (e.g. 256). Then there is a O(n) solution using the Trie.

After the trie has been built then for any given search word search down the word in the trie. If we find that there is no child in the current trie node for the current character at i of the search string, then we allow to the mismatch and go down to all the childs (maxm (256-1)=255). Now, we search for next character in all the child and stop as soon as we found a mismatch again. This way we will exhaust the search string and we check each of the current nodes in the trie (maxm 255) if it it contains an end word. If yes, then the words at those nodes are the result.

The worst case complexity assuming constant A of alphabet size and maximum string length K - is when we have mismatch in first position and the root node contains a node for all letters in the alphabet but the first character in the search string. So worst case complexity for search is (A-1)*(K-1) = O(K).

- zahidbuet106 October 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice solution!

- dhs.du.08 October 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

If the search word is banana and the array is
[aanana, canana, danana, eanana ....... zanana]
then in this case using your trie method would have a time complexity of O(NK) to find all such strings where N is number of strings in array and K is the max length of any string.
Please correct me if I am wrong.

- alexander October 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you think about real english word search then we can consider length of search word within a max limit i.e. O(1) length. Then the search through each path will be constant and overall complexity is of course can't be less then O(n).

- zahidbuet106 October 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well if you're counting the string length as constant, then the brute force solution is also O(n) isn't it?

- oguzyildiz1991 January 30, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*program to find string with one difference character */
#define ROW 5
#define COLUMN 20
#include<stdio.h>
#include<string.h>
int main()
{
char str[ROW][COLUMN],check[COLUMN];
int i,j,x,y,a,k;
printf("Enter 5 words:\n");
while(i<ROW) //while loop to enter elements in the string array.
{
scanf("%s",str[i++]);
} //end of whil loop.
printf("Enter string to check:\n");
scanf("%s",check);
i=0;
printf("check string : %s\n",check);
x=strlen(check);
i=0;
k=0;
while(k < 5) //begining of main while loop.
{
y=strlen(str[k]);
if(x==y)
{
if (strcmp(check,str[k])==0) //begining of inner if.
{
// printf("string matched:%s\n",str[k]);
} //end of inner if.
else // begining of inner else
{
a=0;
for(j=0;j<x;j++) //for loop for going character wise match of each string.
{
if(check[j]!= str[k][j])
{
a++;
}

} // end of for loop.
if(a==1)
{
printf("Element found:%s\n",str[k]);
}
} //end of inner else.
} //end of outter if.
k++;
} // end of main while loop.
return 0;
} // end of main().

- kames sashi October 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*program to find string with one difference character */
#define ROW 5
#define COLUMN 20
#include<stdio.h>
#include<string.h>
int main()
{
char str[ROW][COLUMN],check[COLUMN];
int i,j,x,y,a,k;
printf("Enter 5 words:\n");
while(i<ROW) //while loop to enter elements in the string array.
{
scanf("%s",str[i++]);
} //end of whil loop.
printf("Enter string to check:\n");
scanf("%s",check);
i=0;
printf("check string : %s\n",check);
x=strlen(check);
i=0;
k=0;
while(k < 5) //begining of main while loop.
{
y=strlen(str[k]);
if(x==y)
{
if (strcmp(check,str[k])==0) //begining of inner if.
{
// printf("string matched:%s\n",str[k]);
} //end of inner if.
else // begining of inner else
{
a=0;
for(j=0;j<x;j++) //for loop for going character wise match of each string.
{
if(check[j]!= str[k][j])
{
a++;
}

} // end of for loop.
if(a==1)
{
printf("Element found:%s\n",str[k]);
}
} //end of inner else.
} //end of outter if.
k++;
} // end of main while loop.
return 0;
} // end of main().

- kameswar October 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple python solution, linear runtime, constant space

def oneCharDiff(arr, root):
        length = len(root)
        for word in arr:
                differences = 0
                if length != len(word):
                        continue
                for i in range(length):
                        if word[i] != root[i]:
                                differences += 1
                        if differences == 1:
                                return True
        return False

- m. October 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple python solution-- linear runtime and constant space

def oneCharDiff(arr, root):
        length = len(root)
        for word in arr:
                differences = 0
                if length != len(word):
                        continue
                for i in range(length):
                        if word[i] != root[i]:
                                differences += 1
                        if differences == 1:
                                return True
        return False

- m. October 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

abyz and ayzz will return false instead of true

- rew October 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Scanner;

public class StringDifference {
	public void inputString(String checkThisString, String s){
		int j = 0;
		for(int i=0;i<checkThisString.length();i++){
			if(checkThisString.length()!= s.length()){
				System.out.println("False");
				break;
			}
			if(checkThisString.charAt(i) != s.charAt(i)){
				j++;
				if(j ==2){
					System.out.println("more difference than 2");
					break;
				}
			}	
			if(i== checkThisString.length()-1 && j==1){
				System.out.println("true");
				break;
			}
		}
	}
	
	public void isOneCharDiff(String inputString, String []words){
		int counter = 0;
		for(int i=0; i<words.length;i++){
			String x = words[i];
			int wordLength = x.length();
			for(int j=0;j<wordLength;j++){
				if(inputString.length() != wordLength){
					System.out.println("length not equal of   " + x +" and " + inputString);
					break;
				}
				if(inputString.charAt(j) != x.charAt(j)){
					counter++;
					if(counter == 2){
						System.out.println("More than 2 different characters between strings  "  + x + " and  " + inputString);
						counter = 0;
						break;
					}
				}
				if(j == inputString.length()-1 && counter ==1){
					System.out.println("one difference found between String " + x + " and  " + inputString);
					counter = 0;
					break;

				}
			}	
		}					
	}
	
	
	public static void main(String[] args) {
		
		//string difference
		StringDifference stringDifference = new StringDifference();
		
		Scanner scanner = new Scanner(System.in);
		System.out.println("Enter String to compare ! \n");
		String checkThisString = scanner.nextLine();
		System.out.println("Enter String to be compared ! \n");
		String s = scanner.nextLine();
		stringDifference.inputString(checkThisString, s);;
		
		String wordsArray[] = { "bananaa","bannna","bannan", "mmmmmm"};
		
		stringDifference.isOneCharDiff(checkThisString, wordsArray);
		
	}
}

- akshay talathi October 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find the one statement solution.

bool FindSingleCharDiff(const string& input, const vector<string> &listInputs)
{
	int count = count_if(listInputs.begin(), listInputs.end(), [&input](const string &each)
	{
		int bRet = false;
		if (input.size() != each.size())
		{
			bRet = false;
		}
		else if (input.compare(each) == 0)
		{
			bRet = true;
		}
		else
		{
			int index = -1;
			int diffCount = count_if(each.begin(), each.end(), [&input, &index](const char ch)
			{
				index++;
				return (input.at(index) != ch);
			});
			bRet = diffCount <= 1;
		}
		return bRet;
	});
	return count > 0;
}

int _tmain(int argc, _TCHAR* argv[])
{
	string text("banana");
	vector<string> listText = { "banaba", "banaaa", "apple" };
	bool ans = FindSingleCharDiff(text, listText);
	
	return 0;
}

- Shubha Debnath October 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java implementation in linear time and essentially constant space
Mapping original string to a hasmap, then removing from a copy of it for each item in array to determine if matches 3 possibilities. Logic is commented in code

import java.util.HashMap;

/*
 * 
 * Given a string and array of strings, find whether the array contains a string with one character difference from the given string. Array may contain string of different lengths. 
Ex: Given string banana
and array is [bana, apple, banaba, bonanza, banamf]
and the outpost should be true as banana and banaba are one character difference.
 * 
 * 
 * n = total number of characters in all input
 * m = average length of a  string
 * Performance = O(n)
 * Storage = O(2m) at any given time
 */
public class OffByOne {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String input = "abcde";
		String[] array = {"ebcda"};
		
		System.out.println(OffByOne(input, array));
	}
	
	static boolean OffByOne(String string, String[] array){
		HashMap<Character, Integer> map = mapChars(string);
		String current;
		for(int i=0;i<array.length;i++){
			current = array[i];
			if(Math.abs(string.length()-current.length())>1)
				continue;
			else{
				HashMap<Character, Integer> copy = new HashMap<Character, Integer>(map);
				for(int j = 0;j<current.length();j++){
					Integer val = copy.get(current.charAt(j));
					if(val==null)
						continue;
					else{
						if(val==1)
							copy.remove(current.charAt(j));
						else
							copy.put(current.charAt(j), val-1);
					}
				}
				//array's string is same except it has 1 more char = map will have only 0 element remaining, string size diff by 1
				if(current.length()-string.length()==1 && copy.size()==0)
					return true;
				//1 less char = map only has 1 element left, length diff by 1
				if(current.length()-string.length()==-1 && copy.size()==1)
					return true;
				//1 substituted char = same length and 1 element left in map
				if(current.length()==string.length() && copy.size()==1)
					return true;
			}
			
		}
		return false;
		
		
		
	}
	
	static HashMap<Character, Integer> mapChars(String string){
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		for(int i=0;i<string.length();i++){
			Character c = string.charAt(i);
			Integer num = map.get(c);
			if(num==null)
				map.put(c, 1);
			else
				map.put(c,num+1);
		}
		
		return map;
	}

}

- Ben October 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Might be good, but it doesn't consider order of the characters: "abcd" and "ecba"
will be considered similar which is, evidently, incorrect.

- Alex M. November 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;

/*
 * 
 * Given a string and array of strings, find whether the array contains a string with one character difference from the given string. Array may contain string of different lengths. 
Ex: Given string banana
and array is [bana, apple, banaba, bonanza, banamf]
and the outpost should be true as banana and banaba are one character difference.
 * 
 * 
 * n = total number of characters in all input
 * m = average length of a  string
 * Performance = O(n)
 * Storage = O(2m) at any given time
 */
public class OffByOne {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String input = "abcde";
		String[] array = {"ebcda"};
		
		System.out.println(OffByOne(input, array));
	}
	
	static boolean OffByOne(String string, String[] array){
		HashMap<Character, Integer> map = mapChars(string);
		String current;
		for(int i=0;i<array.length;i++){
			current = array[i];
			if(Math.abs(string.length()-current.length())>1)
				continue;
			else{
				HashMap<Character, Integer> copy = new HashMap<Character, Integer>(map);
				for(int j = 0;j<current.length();j++){
					Integer val = copy.get(current.charAt(j));
					if(val==null)
						continue;
					else{
						if(val==1)
							copy.remove(current.charAt(j));
						else
							copy.put(current.charAt(j), val-1);
					}
				}
				//array's string is same except it has 1 more char = map will have only 0 element remaining, string size diff by 1
				if(current.length()-string.length()==1 && copy.size()==0)
					return true;
				//1 less char = map only has 1 element left, length diff by 1
				if(current.length()-string.length()==-1 && copy.size()==1)
					return true;
				//1 substituted char = same length and 1 element left in map
				if(current.length()==string.length() && copy.size()==1)
					return true;
			}
			
		}
		return false;
		
		
		
	}
	
	static HashMap<Character, Integer> mapChars(String string){
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		for(int i=0;i<string.length();i++){
			Character c = string.charAt(i);
			Integer num = map.get(c);
			if(num==null)
				map.put(c, 1);
			else
				map.put(c,num+1);
		}
		
		return map;
	}

}

- Ben October 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;

/*
 * 
 * Given a string and array of strings, find whether the array contains a string with one character difference from the given string. Array may contain string of different lengths. 
Ex: Given string banana
and array is [bana, apple, banaba, bonanza, banamf]
and the outpost should be true as banana and banaba are one character difference.
 * 
 * 
 * n = total number of characters in all input
 * m = average length of a  string
 * Performance = O(n)
 * Storage = O(2m) at any given time
 */
public class OffByOne {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String input = "abcde";
		String[] array = {"ebcda"};
		
		System.out.println(OffByOne(input, array));
	}
	
	static boolean OffByOne(String string, String[] array){
		HashMap<Character, Integer> map = mapChars(string);
		String current;
		for(int i=0;i<array.length;i++){
			current = array[i];
			if(Math.abs(string.length()-current.length())>1)
				continue;
			else{
				HashMap<Character, Integer> copy = new HashMap<Character, Integer>(map);
				for(int j = 0;j<current.length();j++){
					Integer val = copy.get(current.charAt(j));
					if(val==null)
						continue;
					else{
						if(val==1)
							copy.remove(current.charAt(j));
						else
							copy.put(current.charAt(j), val-1);
					}
				}
				//array's string is same except it has 1 more char = map will have only 0 element remaining, string size diff by 1
				if(current.length()-string.length()==1 && copy.size()==0)
					return true;
				//1 less char = map only has 1 element left, length diff by 1
				if(current.length()-string.length()==-1 && copy.size()==1)
					return true;
				//1 substituted char = same length and 1 element left in map
				if(current.length()==string.length() && copy.size()==1)
					return true;
			}
			
		}
		return false;
		
		
		
	}
	
	static HashMap<Character, Integer> mapChars(String string){
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		for(int i=0;i<string.length();i++){
			Character c = string.charAt(i);
			Integer num = map.get(c);
			if(num==null)
				map.put(c, 1);
			else
				map.put(c,num+1);
		}
		
		return map;
	}

}

- 246810ben October 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean checkString(String string, String[] array) {
if (array.length > 0 && string.length() > 0) {
for (String s : array) {
if (s.length() == string.length()) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == string.charAt(i)) {
count++;
}
}
if (count == string.length() - 1) {
return true;
}
}
}

} else {
System.err.println("program error");
}
return false;
}

- Ranjith Subramaniam October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean checkString(String string, String[] array) {
        if (array.length > 0 && string.length() > 0) {
            for (String s : array) {
                if (s.length() == string.length()) {
                    int count = 0;
                    for (int i = 0; i < s.length(); i++) {
                        if (s.charAt(i) == string.charAt(i)) {
                            count++;
                        }
                    }
                    if (count == string.length() - 1) {
                        return true;
                    }
                }
            }

        } else {
            System.err.println("program error");
        }
        return false;
    }

- Ranjith Subramaniam October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<string.h>
void main()
{
char *fruits[5] = {"bana", "apple", "banaba", "abnaba", "banamf" };
char fruit[10] = "banana";
unsigned int i,j,count = 0;
//printf("Enter fruit na");
for(i = 0; i < 5; i++)
{
if(strlen(fruits[i]) == strlen(fruit))
{
for(j = 0; j < strlen(fruit); j++)
{
if(fruits[i][j] != fruit[j])
{
if( count > 1)
break;
else
count++;
}

}
count = 0;
printf("%s\t",fruits[i]);
}
}
}

- kumar October 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<string.h>
void main()
{
	char *fruits[5] = {"bana", "apple", "banaba", "abnaba", "banamf" };
	char fruit[10] = "banana";
	unsigned int i,j,count = 0;
	//printf("Enter fruit na");
	for(i = 0; i < 5; i++)
	{
		if(strlen(fruits[i]) == strlen(fruit))
		{
			for(j = 0; j < strlen(fruit); j++)
			{
				if(fruits[i][j] != fruit[j])
				{
					if( count > 1)
						break;
					else
						count++;
				}
				
			}
			count = 0;
			printf("%s\t",fruits[i]);
		}
	}
}

- kumar October 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What I wrote, without cheating:
1. put all the words from array into an R-way Trie;
– Trie should support wildcard matching ('?' symbol)
2. generate an array of words with one '?' wildcard symbol at each position of the input word;
3. if any word generated at step 2 can be found in a Trie – return true, false - otherwise.
Code:

class StringDifference {	

	static boolean have1CharDifference(String in, String[] arr){
		/* first we could filter out strings of different length,
		 put the rest in a prefix tree */
		Trie trie = new Trie();
		for (String s: arr) 
			if(in.length() == s.length()) { trie.add( s ); }
		/* match each word from the list (*) against this trie */	
		for (String s: generateWildcardStrings(in)) 
			if ( trie.contains(s) ) { return true; } 
		return false;
	}
    /* (*) generates an array of strings with single wildcard
       symbol at each position of the input string */
    static String[] generateWildcardStrings(String s) {
    	String[] result = new String[s.length()];
		for (int i=0; i< s.length(); i++) {
			char[] arr = s.toCharArray();
			arr[i] = '?';
			result[i] = new String(arr);			
		}		
    	return result;
    }  
}

class Trie { // R-way trie
	private final int a_letter = (int)'a',
					  z_letter = (int)'z',
					  R = z_letter - a_letter + 1; 
	private Node root = new Node(); 
	private class Node { Node[] nodes = new Node[R]; }

	public void add(String word) {
		Node current = root;
		for (int c: word.toCharArray()){
			int ix = c - a_letter;
			if (current.nodes[ix] == null) { current.nodes[ix] = new Node(); }			
			current = current.nodes[ix]; // go down the prefix tree
		}
	}

	public boolean contains(String word) {						
		Node current = root;
		char[] inWord = word.toCharArray();
		for (int i=0; i<inWord.length; i++){
			if (inWord[i] == '?') {	// treat the wildcard differently									
				// if this is the last symbol - return true
				if (i == inWord.length-1) { return true; }
				else { // else - look ahead 1 symbol					
					int ix = inWord[i+1] - a_letter;								
					int j=0;
					for (; j<R; j++) {						
						if (current.nodes[j] != null 
							&& current.nodes[j].nodes[ix] != null) {							
							current = current.nodes[j]; // go down the tree													
						}
					}
					/* if none of the sub-branches matches 
					  the given letter - return false */
					if ( j == R-1 ) { return false; }
				}
			} else { // process a normal letter				
				int ix = inWord[i] - a_letter;				
				if (current.nodes[ix] == null) { return false; }				
				current = current.nodes[ix]; // go down the tree
			}
		}
		return true;
	}	
}

- ivan.golubev.spb October 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Should we break after

current = current.nodes[j]; // go down the tree

?

- Alex M. November 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This approach is good but implies that input and target strings have the same length which is not mentioned in the description.

- Alex M. November 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

However, it might be applied to different lengths strings, but generateWildcardStrings method needs to be modified in this case, for example:
- add '*' symbol to (target.Lenght + 1) positions to specify one additional character
- add '\' symbol to (target.Lenght) positions to specify one missing character

- Alex M. November 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* To my understanding:
1. the interviewer actually asked for the same array, how to make queries fast - each using different word.
    If for only one time query, brutal force word by word comparison should work.

 2. two words one char different means:
   a. they are the same length but one char is different. OR
   b. one is one char shorter or longer than the other.

Below is java code using trie and dfs.
 */
public class GG_OneOffCompare {
    class DepMinMax {
        int max;
        int min;
        DepMinMax(int max, int min)
        {
            this.max = max;
            this.min = min;
        }
    }
    class Node {
        char ch;
        ArrayList<Node> children;
        int minDep;
        int maxDep;
        Node(char ch)
        {
            this.ch = ch;
            children = new ArrayList<>();
            this.minDep = this.maxDep = 1;
        }

        boolean isSentinel()
        {
            return children.size() == 0;
        }

        boolean isBeforeSentinel()
        {
            for(int i=0; i<children.size(); ++i)
            {
                if(children.get(i).isSentinel())
                    return true;
            }
            return false;
        }
    }

    boolean query(String[] arr, String word) {
        Node trie = buildTrie(arr);
        getDepth(trie);
        print(trie, "");

        for(int i=0; i<trie.children.size(); ++i) {
            if(queryEqualLength(trie.children.get(i), word, false))
                return true;

            if(queryShorterLength(trie.children.get(i), word, false))
                return true;

            if(queryLongerLength(trie.children.get(i), word, false))
                return true;
        }

        return false;
    }

    boolean queryShorterLength(Node trie, String word, boolean alreadyOneOff) {
        // check if there is a word in the trie that is one char shorter
        if (trie.isSentinel())
            return (alreadyOneOff && word.length() == 0) ||
                    (!alreadyOneOff && word.length() == 1);

        if (alreadyOneOff) {
            if (word.length() < trie.minDep - 1 || trie.maxDep - 1 < word.length())
                return false;
        } else {
            if (word.length() - 1 < trie.minDep - 1 || trie.maxDep - 1 < word.length() - 1)
                return false;
        }

        if (trie.ch == word.charAt(0)) {
            for (int i = 0; i < trie.children.size(); ++i) {
                if (alreadyOneOff) {
                    if (queryShorterLength(trie.children.get(i), word.substring(1), true))
                        return true;
                } else {
                    if (queryShorterLength(trie.children.get(i), word.substring(1), false) ||
                            queryShorterLength(trie, word.substring(1), true))
                        return true;
                }
            }
        } else {
            if (alreadyOneOff) return false;
            for (int i = 0; i < trie.children.size(); ++i) {
                if (queryShorterLength(trie, word.substring(1), true))
                    return true;
            }
        }

        return false;
    }

    boolean queryLongerLength(Node trie, String word, boolean alreadyOneOff) {
        // check if there is a word in the trie that is one char longer than the parameter word
        if (word.length() == 0)
            return (alreadyOneOff && trie.isSentinel()) ||
                    (!alreadyOneOff && trie.isBeforeSentinel());

        if (alreadyOneOff) {
            if (word.length() < trie.minDep - 1 || trie.maxDep - 1 < word.length())
                return false;
        } else {
            if (word.length() + 1 < trie.minDep - 1 || trie.maxDep - 1 < word.length() + 1)
                return false;
        }

        if (trie.ch == word.charAt(0)) {
            for (int i = 0; i < trie.children.size(); ++i) {
                if (alreadyOneOff) {
                    if (queryShorterLength(trie.children.get(i), word.substring(1), true))
                        return true;
                } else {
                    if (queryLongerLength(trie.children.get(i), word.substring(1), false) ||
                            queryLongerLength(trie.children.get(i), word, true))
                        return true;
                }
            }
        } else {
            if (alreadyOneOff) return false;
            for (int i = 0; i < trie.children.size(); ++i) {
                if (queryLongerLength(trie.children.get(i), word, true))
                    return true;
            }
        }

        return false;
    }

    boolean queryEqualLength(Node trie, String word, boolean alreadyOneOff)
    {
        // check if there is a word in trie that have the
        // same length as the parameter word but one char different.

        if(trie.isSentinel())
            return (alreadyOneOff && word.length() == 0);

        if(word.length() < trie.minDep-1  || trie.maxDep-1 < word.length())
            return false;

        // pre-order dfs
        if(trie.ch == word.charAt(0))
        {
            for(int i=0; i<trie.children.size(); ++i) {
                if (queryEqualLength(trie.children.get(i), word.substring(1), alreadyOneOff))
                    return true;
            }
        }
        else
        {
            if (alreadyOneOff) return false;
            for(int i=0; i<trie.children.size(); ++i) {
                if (queryEqualLength(trie.children.get(i), word.substring(1), true))
                    return true;
            }
        }

        return false;
    }

    void print(Node trie, String buf) {
        if(trie.isSentinel()) {
            System.out.println(buf + trie.ch);
            return;
        }

        buf = buf + trie.ch + ",";
        for(int i=0; i<trie.children.size();++i)
        {
            print(trie.children.get(i), buf);
        }
    }

    // get min and max depths for each node.
    DepMinMax getDepth(Node trie)
    {
        // postorder DFS
        if(trie.isSentinel())
            return new DepMinMax(1, 1);

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i=0; i<trie.children.size(); ++i)
        {
            DepMinMax dep = getDepth(trie.children.get(i));
            min = Math.min(min, dep.min);
            max = Math.max(max, dep.max);
        }

        trie.maxDep = max + 1;
        trie.minDep = min + 1;
        return new DepMinMax(trie.maxDep, trie.minDep);
    }

    Node buildTrie(String[] arr) {
        Node root = new Node('#');
        for(int i=0; i<arr.length; ++i)
        {
            buildTreeHelper(root, arr[i]);
        }
        return root;
    }

    void buildTreeHelper(Node root, String s)
    {
        if(s.length() == 0) {
            root.children.add(new Node('$')); //important: add sentinel node - required.
            return;
        }

        Node child = null;
        for(int i=0; i<root.children.size(); ++i)
        {
            if(root.children.get(i).ch == s.charAt(0))
            {
                child = root.children.get(i);
                break;
            }
        }

        if(child == null)
        {
            Node s0Node = new Node(s.charAt(0));
            root.children.add(s0Node);
            child = s0Node;
        }

        buildTreeHelper(child, s.substring(1));
    }
}

- jiangok2006 November 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The time and space complexity are both O(n) where n is the number of characters of all words in the array. Due to ambiguous search, we have to search all paths in the worst case to get the final match. So trie does not improve the worst case time complexity compared with the brutal force word by word comparing.

Like above trie algo, the brutal force algo can also use string length and char difference count to early terminate the comparison. So I am a little confused how trie is useful at all. :( Any insight will be highly appreciated.

- jiangok2006 November 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class OneCharDifference {
public static void main(String[] args) {

System.out.println("Enter the String");

Scanner in = new Scanner(System.in);
String str = in.nextLine();

String[] arr = {"bana", "apple", "banaba", "bonanza", "bonamf"};
int count = 0;

for(int i=0; i<arr.length; i++) {
if(arr[i].length() == str.length()) {
for(int j=0; j <str.length(); j++) {
if(arr[i].charAt(j)!=str.charAt(i)) {
count++;
}
}
if(count == 1) {
System.out.println(arr[i]);
}
}
}

}

}

- Anonymous November 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class OneCharDifference {
	public static void main(String[] args) {
		
		System.out.println("Enter the String");
		
		Scanner in = new Scanner(System.in);
		String str = in.nextLine();
		
		String[] arr = {"bana", "apple", "banaba", "bonanza", "bonamf"};
		int count = 0;
		
		for(int i=0; i<arr.length; i++) {
			if(arr[i].length() == str.length()) {
				for(int j=0; j <str.length(); j++) {
					if(arr[i].charAt(j)!=str.charAt(i)) {
						count++;
					}
				}
				if(count == 1) {
					System.out.println(arr[i]);
				}
			}
		}
		
	}

}

- Win November 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

public class OneCharDifference {
	public static void main(String[] args) {
		String str = "banana";
		
		String[] arr = {"bana", "apple", "banaba", "bonanza", "bonamf"};
		int count = 0;
		
		for(int i=0; i<arr.length; i++) {
			if(arr[i].length() == str.length()) {
				count = 0;				
				for(int j=0; j <str.length(); j++) {
					if(arr[i].charAt(j)!=str.charAt(j)) {
						count++;
					}
				}				
				if(count == 1) {
					System.out.println(arr[i]);
				}
			}
		}		
	}
}

- Suresh February 11, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class OneCharDifference {
	public static void main(String[] args) {
		
		System.out.println("Enter the String");
		
		Scanner in = new Scanner(System.in);
		String str = in.nextLine();
		
		String[] arr = {"bana", "apple", "banaba", "bonanza", "bonamf"};
		int count = 0;
		
		for(int i=0; i<arr.length; i++) {
			if(arr[i].length() == str.length()) {
				for(int j=0; j <str.length(); j++) {
					if(arr[i].charAt(j)!=str.charAt(i)) {
						count++;
					}
				}
				if(count == 1) {
					System.out.println(arr[i]);
				}
			}
		}
		
	}

}

- Anonymous November 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class OneCharacterDiff {

public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("bana");
list.add("apple");
list.add("bananb");
String testString = "banana";
System.out.println("Is one diff?? "+isOneDiff(list, testString));
}

private static Boolean isOneDiff(List<String> list, String testString) {
List<String> str = new ArrayList<>();
HashMap<String, String> map = new HashMap<>();
HashSet<Integer> hs = new HashSet<Integer>();
for(String s:list){
map.put(s,getSorted(s));
}
testString = getSorted(testString);
int c = 0;
int diff =0;
for(String s: list){
if(s.length()==testString.length()){
String m = map.get(s);
for(int i=0;i<m.length();i++){
if(m.charAt(i)!=testString.charAt(i)){
c++;
}
//hs.add(c);
}
if(c==1)
return true;
}
}
//if(hs.contains(1))
//return true;
//else
return false;

}

private static String getSorted(String s) {
char[] arr = s.toCharArray();
Arrays.sort(arr);
return new String(arr);
}

}

- NikhilRao November 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class OneCharacterDiff {

	public static void main(String[] args) {
		List<String> list = new ArrayList<String>();
		list.add("bana");
		list.add("apple");
		list.add("bananb");
		String testString = "banana";
		System.out.println("Is one diff?? "+isOneDiff(list, testString));
	}

	private static Boolean isOneDiff(List<String> list, String testString) {
		List<String> str = new ArrayList<>();
		HashMap<String, String> map = new HashMap<>();
		HashSet<Integer> hs = new HashSet<Integer>();
		for(String s:list){
			map.put(s,getSorted(s));
		}
		testString = getSorted(testString);
		int c = 0;
		int diff =0;
		for(String s: list){
			if(s.length()==testString.length()){
				String m = map.get(s);
				for(int i=0;i<m.length();i++){
					if(m.charAt(i)!=testString.charAt(i)){
						c++;
					}
					//hs.add(c);
				}	
				if(c==1)
					return true;
			}
		}
		//if(hs.contains(1))
			//return true;
		//else
			return false;

	}

	private static String getSorted(String s) {
		char[] arr = s.toCharArray();
		Arrays.sort(arr);
		return new String(arr);
	}

}

- NikhilRao November 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class OneCharacterDiff {

	public static void main(String[] args) {
		List<String> list = new ArrayList<String>();
		list.add("bana");
		list.add("apple");
		list.add("bananb");
		String testString = "banana";
		System.out.println("Is one diff?? "+isOneDiff(list, testString));
	}

	private static Boolean isOneDiff(List<String> list, String testString) {
		List<String> str = new ArrayList<>();
		HashMap<String, String> map = new HashMap<>();
		HashSet<Integer> hs = new HashSet<Integer>();
		for(String s:list){
			map.put(s,getSorted(s));
		}
		testString = getSorted(testString);
		int c = 0;
		int diff =0;
		for(String s: list){
			if(s.length()==testString.length()){
				String m = map.get(s);
				for(int i=0;i<m.length();i++){
					if(m.charAt(i)!=testString.charAt(i)){
						c++;
					}
					//hs.add(c);
				}	
				if(c==1)
					return true;
			}
		}
		//if(hs.contains(1))
			//return true;
		//else
			return false;

	}

	private static String getSorted(String s) {
		char[] arr = s.toCharArray();
		Arrays.sort(arr);
		return new String(arr);
	}

}

- Rao N November 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can someone please tell me whats wrong with this simple c# solution ?

string[] arr = { "apple","banaga","orange"};
string test = "banana";
char[] a1;
char[] a2;
int count=0;
a2 = test.ToCharArray();
for (int i = 0; i < arr.Length; i++)
{
a1= arr[i].ToCharArray();

for (int j = 0; j < a1.Length; j++)
{
if (a1[j] != a2[j])
count++;
if (count > 1) break;
}


if (count == 0 || count == 1)
Console.WriteLine("TRUE");
count = 0;
}

- master113 January 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

in perl

my $string = "banana";
my @array = ('bana','apple','banaba','nonanza','banamf');

foreach my $str (@array) {
	if (length($str) == length($string)) {
		my $result = {};
		for (0..length($str)){
			if (substr($str,($_-1),1) eq substr($string,($_-1),1)) {
				$result{'match'} += 1;
			} else {
				$result{'mismatch'} += 1;
			}
		}
		if ($result{'mismatch'} == 1) {
			print "found a match with one character difference at: $str\n";
		}
	}
}

- discobeta February 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my $string = "banana";
my @array = ('bana','apple','banaba','nonanza','banamf');

foreach my $str (@array) {
if (length($str) == length($string)) {
my $result = {};
for (0..length($str)){
if (substr($str,($_-1),1) eq substr($string,($_-1),1)) {
$result{'match'} += 1;
} else {
$result{'mismatch'} += 1;
}
}
if ($result{'mismatch'} == 1) {
print "found a match with one character difference at: $str\n";
}
}
}

- Anonymous February 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my $string = "banana";
my @array = ('bana','apple','banaba','nonanza','banamf');

foreach my $str (@array) {
	if (length($str) == length($string)) {
		my $result = {};
		for (0..length($str)){
			if (substr($str,($_-1),1) eq substr($string,($_-1),1)) {
				$result{'match'} += 1;
			} else {
				$result{'mismatch'} += 1;
			}
		}
		if ($result{'mismatch'} == 1) {
			print "found a match with one character difference at: $str\n";
		}
	}
}

- discobeta February 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
		// TODO Auto-generated method stub
         String s1 = "banana";
         String[] a1 = {"nana", "baban", "banaba", "abfsdc", "bayana", "banxna"};
         
         findmatch(s1, a1);
	}
	
	public static void findmatch(String s, String[] sa){
		
		
		char[] chars = s.toCharArray();
		
		
		for(int i = 0; i< sa.length;i++){
			char[] s1 = sa[i].toCharArray();
		
			
			int counter = 0;
			if(chars.length == s1.length){
			
			for(int k=0; k<chars.length || k<s1.length;){
				
					if(chars[k] == (s1[k]))
						k++;
					
					else{
					  counter++;
					  k++;
					}
				}
				
			}
		
			if (counter == 1)
			  System.out.println(sa[i]);
		}
	}

- rewanth19 March 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

boolean oneDiff(String s, String t) {
if(s.length() != t.length())
return false;
for(int i = 0; i < s.length(); i++) {
if(s.charAt(i) != t.charAt(i)) {
return s.substring(i+1).equals(t.substring(i+1));
}
}
return false;
}
boolean oneEditDiff(String s, String[] strs) {
if(strs == null || strs.length == 0)
return false;
for(String str : strs ) {
if(str.equals(s)) continue;
if(oneDiff(s, str)) return true;
}
return false;
}
public static void main(String[] args) {
Test test = new Test();
String[] strs = {"banana", "bana" , "banaa"};
System.out.println(test.oneEditDiff("banana", strs));
}

- hive April 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

String banana="banana";
		String[] findBanana = {"bana", "apple", "banaba", "bonanza", "banamf","bananaw"};

		System.out.println("banana length: "+banana.length());
		System.out.println("findBanana length: "+findBanana.length);
		System.out.println("findBanana[0] value: "+findBanana[0]);
		
		for(int i=0;i<findBanana.length;i++){
				int count=0;
				for(int j=0;j<findBanana[i].length();j++){
					if (j>=banana.length()) continue;
					if(banana.charAt(j)!=findBanana[i].charAt(j)){
						count++;
					}
				}
				if (count==1) System.out.println("Matching String is: "+findBanana[i]);

}

- Ali Nasim May 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hey All find my solution..!!

String banana="banana";
String[] findBanana = {"bana", "apple", "banaba", "bonanza", "banamf","bananaw"};

System.out.println("banana length: "+banana.length());
System.out.println("findBanana length: "+findBanana.length);
System.out.println("findBanana[0] value: "+findBanana[0]);

for(int i=0;i<findBanana.length;i++){
int count=0;
for(int j=0;j<findBanana[i].length();j++){
if (j>=banana.length()) continue;
if(banana.charAt(j)!=findBanana[i].charAt(j)){
count++;
}
}
if (count==1) System.out.println("Matching String is: "+findBanana[i]);
}

- Ali Nasim May 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class StringFinder {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String input = "banana";
		String[] arrayInput = {"bana", "apple", "banaba", "bonanza", "banamf"};
		System.out.println(stringFind(input, arrayInput));
	}

	public static boolean stringFind(String str, String[] arrString){
		int notMatch=0;
		for(int i=0; i<arrString.length; i++){
			int x = arrString[i].length();
			if(x==str.length()){

				char[] arr = arrString[i].toCharArray();
				char[] inputStr = str.toCharArray();

				for(int j =0; j<inputStr.length; j++){
					if(inputStr[j]!=arr[j]){
						notMatch++;
						if(notMatch>1)
							return false;
					}
				}
				return true;
			}
		}
		return false;
	}
}

- sahilchalke3 August 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{def one_char_diff(a,s): for i in s: if len(i)!=len(a): continue c = 0 for j in xrange(len(i)): if a[j] != i[j]: c+=1 if c == 1: #yield i return True a = 'banana' s = ["bana", "apple", "banaba", "bonanza", "banamf", "bananaa"] #print [i for i in one_char_diff(a,s)] print one_char_diff(a,s)}} - mkdivis07 September 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python:

s = 'banana'
list1 = ['bana', 'apple', 'banaba', 'bonanza', 'banamf', 'banana']

def check(s,list1):
	if len(s) == 0 or len(list1) == 0:
		return False

	list2 = []

	for items in list1:
		if len(s) == len(items):
			count = 0
			for i in range(0,len(s)):
				if s[i] != items[i]:
					count += 1

			if count <= 1:
				list2.append(items)


	return list2


list2 = check(s,list1)

if len(list2) > 0:
	print "True"
	print list2

- koolkhush February 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

given

$g = "banana"; # given string
@ary = qw(
     bana apple banaba nonanza banamf
    anana banan ananas banaa bnana
);

if strings have to be of equal length:

print $_,$/ for grep { 
    1 == grep !/0/, unpack "C*", $g ^ $_
        if length $g == length $_
} @ary;
__END__
banaba

including strings which have one char missing somewhere:

print $_,$/ for grep {         
    my ($lg, $lc) = map { length $_ } $g, $_;
    my $ret;
    if ($lg - $lc == 1) {
        my $re = join'.?','',(split//,$_),'';
        $ret = $g =~ /$re/;    
    } elsif ($lg == $lc) {     
        $ret = (1 == grep !/0/, unpack "C*", $g ^ $_);
    }
    $ret;
} @ary;
__END__
banana
anana
banan
banaa
bnana

- shmem September 13, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

given

$g = "banana";
@ary = qw(
     bana apple banaba nonanza banamf
    anana banan ananas banaa bnana
);

if strings have to be of equal length:

print $_,$/ for grep { 
    1 == grep !/0/, unpack "C*", $g ^ $_
        if length $g == length $_
} @ary;
__END__
banaba

including strings which have one char missing somewhere:

print $_,$/ for grep {         
    my ($lg, $lc) = map { length $_ } $g, $_;
    my $ret;
    if ($lg - $lc == 1) {
        my $re = join'.?','',(split//,$_),'';
        $ret = $g =~ /$re/;    
    } elsif ($lg == $lc) {     
        $ret = (1 == grep !/0/, unpack "C*", $g ^ $_);
    }
    $ret;
} @ary;
__END__
banana
anana
banan
banaa
bnana

- shmem September 13, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if strings have to be of the same length:

# $g is given string, @ary is array of strings
print 0 < grep {
    1 == grep !/0/, unpack "C*", $g ^ $_ if length $g == length $_
} @ary;

if strings 1 char shorter or larger are allowed:

print 0  < grep { 
    my ($lg, $lc, $ret) = map { length $_ } $g, $_;
    if (abs (my $d = $lg - $lc) == 1) {
        my $re = join '.?', '', (split//,$d > 0 ? $_: $g), '';
        $ret = ($d > 0 ? $g : $_) =~ /$re/;
    } elsif ($lg == $lc) {
        $ret = (1 == grep !/0/, unpack "C*", $g ^ $_)
    }
    $ret
} @ary;

- shmem September 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I don't see an efficient solution other than looking iteratively for any character in any word until I find the first match:

using static System.Console;
using static System.Math;
using System.Collections.Generic;
using System.Linq;
using System;

namespace Coding {

  public static class CareerCup {

    public static string Run(string[] args) {
      return HasSimilarWords(args[0], args.Skip(1).ToList()).ToString();
    }

    // return only the words in the array that differ from the input
    // words by one character
    public static bool HasSimilarWords(string word, IList<string> words) {
      return words.Any(word.IsSimilar);
    }

    public static bool IsSimilar(this string a, string b) {
      if(a.Length != b.Length) return false;
      var wrong = false;
      for(var i = 0; i < a.Length; i++) {
        if(a[i] != b[i]) {
          if(wrong) return false;
          else wrong = true;
        }
      }
      return true;
    }

  }
}

- Giacomo October 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

/*program to find string with one difference character */
#define ROW 5
#define COLUMN 20
#include<stdio.h>
#include<string.h>
int main()
{
char str[ROW][COLUMN],check[COLUMN];
int i,j,x,y,a,k;
printf("Enter 5 words:\n");
while(i<ROW) //while loop to enter elements in the string array.
{
scanf("%s",str[i++]);
} //end of whil loop.
printf("Enter string to check:\n");
scanf("%s",check);
i=0;
printf("check string : %s\n",check);
x=strlen(check);
i=0;
k=0;
while(k < 5) //begining of main while loop.
{
y=strlen(str[k]);
if(x==y)
{
if (strcmp(check,str[k])==0) //begining of inner if.
{
// printf("string matched:%s\n",str[k]);
} //end of inner if.
else // begining of inner else
{
a=0;
for(j=0;j<x;j++) //for loop for going character wise match of each string.
{
if(check[j]!= str[k][j])
{
a++;
}

} // end of for loop.
if(a==1)
{
printf("Element found:%s\n",str[k]);
}
} //end of inner else.
} //end of outter if.
k++;
} // end of main while loop.
return 0;
} // end of main().

- Anonymous October 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <iostream>
#include <vector>
using namespace std;

// To execute C++, please define "int main()"

bool isOneCharDiffStringExist(vector<string> list, string s)
{
  int length = (int)list.size();
  
  if(length == 0 || s.size() ==0)
    return false;
  
  for(int i=0;i<length;i++)
  {
    if(list[i].size()!=s.size())
      continue;
    
    bool oneCharDiffFound = false;
    for(int j =0;j<(int)list[i].size();j++)
    {
      if(list[i][j] != s[j] )
      {
          if(!oneCharDiffFound)
            oneCharDiffFound = true;
          else
          {
            oneCharDiffFound = false;
            break;
          }
      }
    }
    
    if(oneCharDiffFound)
      return true;
  }
  
  return false;
}

int main() {
  
  vector<string> list;
  list.push_back("bana");
  list.push_back("apple");
  list.push_back("banacb");
  list.push_back("bonanza");
  list.push_back("banamf");
  
  cout<<isOneCharDiffStringExist(list,"banana");
  return 0;
}

- Anonymous October 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this code will not work for given string "banana"-"abnaba",even though there is difference of one character only.Please give suggestions.

- nanhi October 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@nanhi: I see a difference of 3 characters...

@OP: This won't work when there is a word of different sizes but still have a one character difference, take this example:

banana --> bananaa

There is a 1 character difference only, but this function will skip it as the sizes aren't equal.

- Greg October 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@nanhi: I count 3 differences in the above. They're most likely counting a difference as str[i] != str1[i]. In your above example str[0] doesn't match, str[1] doesn't match, and str[4] doesn't match.

@OP:
I don't think your function works when the strings are different sizes, yet still only differ by 1 character, take the following example:

banana --> bananaa

There is only 1 character difference (the last char), but it will not be found because it will get skipped due to the size difference.

- Greg October 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We no need to handle the scenario of banana --> bananas.
The length of the strings needs to matcha and one character changed between the strings.

- kpraveen420 October 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

As I understand, is ambigus to think wich means "one character of difference", thus "banana" and "bananas" can be considerated as 1 char diff.

- miguelangel.rodel October 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Same concept as LCS(longest common sub sequence):

#include <stdio.h>
int max = -1;
int maximum(int a, int b)
{
    return a>b?a:b;
}

int foo(char *target, char *a[10], int i, int j, int size, int cost)
{
    if (i >= size) {
        if (cost+abs(strlen(a[i])-strlen(target)) > 1) {
            return foo(target, a, i+1, 0, size, 0);
        }
        printf("%s\n", a[i]);
        return 0;
    }
    if (j >= strlen(a[i])) {
        if (cost+abs(strlen(a[i])-strlen(target)) > 1) {
            return foo(target, a, i+1, 0, size, 0);
        }
        printf("%s\n", a[i]);
        return 0;
    }
    if (a[i][j] == target[j]) {
        return foo(target, a, i, j+1, size, cost);
    } else {
        return foo(target, a, i, j+1, size, cost + 1);
    }
}

int main(void) {
    char *s = {"banana"};
    char *a[10] = {"bana", "apple", "sanana", "banaba", "bonanza", "banamf"};
    printf("%d\n", foo(s, a, 0, 0, 5, 0));
    return 0;
}

- aka[1] October 04, 2015 | 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