Facebook Interview Question


Country: United States
Interview Type: Phone Interview




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

No recursion, O(N) time where N is the larger string, O(1) space.

public static boolean oneEditApart(String a, String b) {
    String small = a.length() <= b.length() ? a : b;
    String large = a.length() <= b.length() ? b : a;

    int operations = 0;
    if (large.length() - small.length() > 1) {
      return false;
    } else if (large.length() == small.length()) { 
      for (int i = 0; i < small.length(); i++)
        if (small.charAt(i) != large.charAt(i) && ++operations > 1)
          return false;
    } else {
      int i = 0;
      while (i < small.length()) {
        if (small.charAt(i) != large.charAt(i + operations)) {
          if (++operations > 1)
            return false;
        } else {
          i++;
        }
      }
    }

    return true;
  }

- Sir CodesALot April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice!

- Anonymous April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Beautiful!!!

- Anon April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Doesn't work for input "at", "cat"

- dude April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Simple and elegant. Took me some time to convince myself, that this will work for all cases, it does..

- puneet.sohi April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Shouldn't oneEditApart("cat", "cat") return false as there is no insertion, removal or replacement required to get string2?

or are we removing an empty string -> '' from "cat" to get "cat"????

- peeterparker April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what about time complexity of length function.

- codedore April 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Returns the length of the underlying char array, complexity of which is O(1).

- Dan.Stahr April 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public boolean oneEditApart (String s1 , String s2) {
    int l1 = s1.length();
    int l2 = s2.length();
    if (Math.abs (l2-l1) > 1) {
        return false;
    }
    if(l1 == l2) {
        return checkOneDiff(s1,s2);
    }
    if(l1 > l2) {
        return checkOneExtra(s1,s2);
    } else {
        return checkOneExtra(s2,s1);
    }
}

private boolean checkOneDiff(String s1 , String s2) {
    int count = 0;
    for(int i=0;i<s1.length();i++) {
        if(s1.charAt(i) != s2.charAt(i)) {
            count++;
        }
        if(count > 1) return false;
    }
    return true;
}

private boolean checkOneExtra(String s1 , String s2) {
    int count=0;
    int inc =0;
    for(int i=0;i<s1.length();i++) {
        if(s1.charAt(i) != s2.charAt(i+count)) {
            count++;
            i--;
        }
        if (count > 1) return false;
    }
    
    return true;
}

- Manpreet May 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Manpreet: Your condition should be as:

if(l1 > l2) {
	return checkOneExtra(s2, s1);
} else {
	return checkOneExtra(s1, s2);
}

- KetRic August 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

The idea behind the code is similar to the distance problem, but we don't need to create the whole table. The code below runs in O(N) time and O(N) extra space and could be optimized to achieve O(1) extra space.

public static boolean oneEditApart(String first, String second) {
        // Just to make sure that the change doesn't occur at the last position of the string 
        // which saves us from handling a few corner cases
        return oneEditApart(first + "#", second + "#", true);
    }

    public static boolean oneEditApart(String first, String second, boolean canDiffer) {
        int indexF = 0;
        int indexS = 0;
        while (indexF < first.length() && indexS < second.length()) {
            if (first.charAt(indexF) == second.charAt(indexS)) {
                ++indexF;
                ++indexS;
            }
            else {
                if (canDiffer) {
                    String newFirst = first.substring(indexF);
                    String newSecond = second.substring(indexS);
                    return oneEditApart(newFirst, newSecond.substring(1), false) ||
                            oneEditApart(newFirst.substring(1), newSecond, false) ||
                            oneEditApart(newFirst.substring(1), newSecond.substring(1), false);
                } else {
                    return false;
                }
            }
        }
        return (indexF == first.length() && indexS == second.length());
    }

- Danstahr April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

What about the case

OneEditApart("cat", "dog") = ????

.

In your case, it returns true.

- peeterparker April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Huh?

ideone.com/Xmawkh

- Dan.Stahr April 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, I meant to say

OneEditApart("cat", "cat") =

should it return true or false? and why?

- Peter April 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This'd be a nice question for the interviewer. My implementation returns true for such cases. If you want to identify the cases that are exactly one edit apart, add && !canDiffer to the very last condition.

Running : ideone.com/dBiAQT

- Dan.Stahr April 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This could be done by modifying the edit distance problem slightly.So After calculating edit distance value return true if it is one else return false.

- arunkumar267 April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Using a cannon to kill the mosquito.

- Anonymous April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

edit distance n^2. this solution can be n. This is an example where using existing tools is big NO

- Anonymous April 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Levenshtein distance, compute it in O(n*m) Vagner-Fisher algo.

- Anonymous April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

LOL.

- Anonymous April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{ public boolean oneEditApart(String s1, String s2) {
if (s1 == null || s2 == null || Math.abs(s1.length() - s2.length()) > 1 || s1.equals(s2)) {
return false;
}

int dp[] = {1, 0, 1};

for (int i = 0; i < s1.length() && i<s2.length(); i++) {
int[] newDp = new int[3];

newDp[1] = Math.min(Math.min(dp[0] + 1, dp[2] + 1), s1.charAt(i) == s2.charAt(i)? dp[1] : dp[1] + 1);

if (i < s1.length()-1){
newDp[0] = Math.min(newDp[1] + 1, s1.charAt(i+1) == s2.charAt(i) ? dp[0] : dp[0] + 1);
}

if (i < s2.length()-1){
newDp[2] = Math.min(newDp[1] + 1, s1.charAt(i) == s2.charAt(i+1) ? dp[2] : dp[2] + 1);
}

dp = newDp;
}

if (s1.length() == s2.length()) {
return dp[1] == 1;
}
else if (s2.length() > s1.length()) {
return dp[2] == 1;
}
else {
return dp[0] == 1;
}
}

}}

- Anonymous April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool OneEditApart(string1, string2)
{
	char str1[] = string1.toCharArray();
	char str2[] = string2.toCharArray();	

	if( str1.len > str2.len)
		return IsInsert( str2, str1);
	else if(str1.len < str2.len)
		return IsInsert(str1, str2);
	else
		return IsReplace(str1, str2);
}


bool IsReplace(char a[], char b[]) //array b is the result of one char replacement on array a
{
	if( a.len <> b.len)
		return false;

	int i = 0;
	int j = 0;
	int ndiff = 0;

	while(ndiff<2)
	{
		if(a[i++] <> b[j++])
			ndiff++;
	}	
	return ndiff == 1;			
}


bool IsInsert(char a[], char b[]) //array b is the result of one char insert on array a
{
	if(b.len - a.len <> 1)
		return false;

	int i = 0;
	int j = 0;
	int ndiff = 0;

	while(ndiff<2)
	{
		if(a[i] == b[j])
		{
			i++; 
			j++;
		}else{
			ndiff++;
			j++;
		}
	}	
	return ndiff == 1;

}

- mikezebin April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static  boolean OneEditApart(String s1, String s2){
		
		return editDisance(s1, s2) == 1 ;
	}
	
	
	public static int editDisance(String s1, String s2){
		int [] [] dp = new int [s1.length() + 1] [s2.length() + 1] ;
		
		for (int i = 0 ; i <= s1.length() ; ++i){
			dp [i][0] = i;
		}
		
		for (int j = 0 ; j <= s2.length(); ++j ){
			dp [0][j] = j;
		}
		
		for (int i = 1 ; i <= s1.length() ; ++i){
			for (int j = 1 ; j <= s2.length() ; ++j){
				// replacement
				int replace  = dp[i-1][j-1] + (s1.charAt(i -1 ) == s2.charAt(j - 1)? 0 : 1);
				// remove
				int remove  = dp [i-1][j] + 1 ;
				// insert
				int insert = dp [i][j-1] + 1 ;
				
				int min = Math.min(replace, remove) ;				
				min = Math.min(insert, min);				
				dp[i][j] = min ;
				
			}
		}
		
		return dp[s1.length()][s2.length()];
	}

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

This is quite easy. Just break down into cases to simplify
1. Take two variables of String smaller and biger
2. put small string between s1 and s2 in small and big in bigger
3. Now break down into sub cases
3.1 If smaller.size() == bigger.size()
{...} // Easy operation, see code below for inner details
3.2 If smaller.size()+1 == bigger.size()
{...} // Easy operation, see code below for inner details
3.3 return false;

public static boolean OneEditApart(String s1, String s2) {
		int i = 0;
		String small = s1.length() <= s2.length() ? s1 : s2;
		String big = s1.length() > s2.length() ? s1 : s2;

		if (small.length() == big.length()) {
			while (i < small.length()) {
				if (small.charAt(i) == big.charAt(i))
					i++;
				else
					return small.substring(i + 1, small.length()).equals(
							big.substring(i + 1, big.length()));
			}
			// Here both the Strings are same
			return false;
		} else if (small.length() + 1 == big.length()) {
			while (i < small.length()) {
				if (small.charAt(i) == big.charAt(i))
					i++;
				else
					return small.substring(i, small.length()).equals(
							big.substring(i + 1, big.length()));
			}
			return true;
		} else
			return false;
	}

- Avsa April 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is O(n) in complexity and O(n) in space. We can reduce space to O(1) easily without using additional Strings.

- Avsa April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool one_edit_helper(const std::string& str1, const std::string& str2)
{
	if (str2.length() - str1.length() > 1) return false;

	int i = 0;
	while (i < str1.length() && str1[i] == str2[i]) ++i;

	if (i == str2.length()) return true;
	if (i == str2.length() - 1) return true;

	if (str1.substr(i + 1) == str2.substr(i + 1))
		return true;

	if (str1.substr(i) == str2.substr(i + 1))
		return true;

	if (str1.substr(i + 1) == str2.substr(i))
		return true;

	return false;
}



bool one_edit(const std::string& str1, const std::string& str2)
{
	int l1 = str1.length();
	int l2 = str2.length();
	if (l1 <= l2) return one_edit_helper(str1, str2);
	return one_edit_helper(str2, str1);
}

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

Credit goes to Sir CodesALot

void oneEditApart(NSString *a, NSString *b) {
    if ([a length] - [b length] == 1 || [a length] - [b length] == -1) {
        printf("false\n");
        return;
    } else if ([a length] == [b length]){
        int opts = 0;
        for (int i=0; i< [a length];i++) {
            if ([a characterAtIndex:i] != [b characterAtIndex:i])
                opts++;
            if (opts > 1) {
                printf("false\n");
                return;
            }
        }
    } else {
        NSString *s = ([a length] > [b length])? b : a;
        NSString *l = ([a length] > [b length])? a : b;
        int opts = 0;
        for (int i=0; i < [s length]; i++) {
            if ([s characterAtIndex:i] != [l characterAtIndex:i+opts]) {
                opts++;
            }
            if (opts > 1) {
                printf("false\n");
                return;
            }
        }
    }
    printf("true\n");
}

- peeterparker April 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursion:

boolean OneEditApart(string s1, string s2) {
	return isOneEditApart(s1, s2, 0);
}

public boolean isOneEditApart(String a, String b, int editCount){
	if(Math.abs(a.length()-b.length()) > 1 || editCount >1){
		return false;	
	}

	if(a.equals("") || b.equals("")){
		
		if(a.equals("") && b.equals("")){
			if(editCount == 0){
				return false;
			}else{
				return true;
			}
		}else if(editCount == 0){
			return true;
		}else{
			return false;
		}
		
	}

	if(a.charAt(0) == b.charAt(0)){
		return isOneEditApart(a.substring(1),b.substring(1),editCount);
	}else{
		++editCount;
		return isOneEditApart(a.substring(1),b.substring(1),editCount) ||
				isOneEditApart(a.substring(1),b.substring(0),editCount) ||
				isOneEditApart(a.substring(0),b.substring(1),editCount);
	}
}

Non-recursive, the code can probably be way more concise.

public boolean oneEditApart(String s1, String s2){
	
	if(Math.abs(s1.length() - s2.length())>1){
		return false;
	}
	
	if(s1.length() == s2.length()){
		int count = 0;
		for(int i = 0; i<s1.length();i++){
			if(s1.charAt(i) != s2.charAt(i)){
				count++;
				if(count > 1){
					break;
				}
			}
		}	
		if(count == 1){
			return true;
		}else{
			return false;
		}
		
	}else{
		int cur_short = 0;
		int cur_long = 0;
		String shortString = null;
		String longString = null;
		int shortLen = 0;
		int count = 0;
		if(s1.length()>s2.length()){
			longString = s1;
			shortString = s2;
			shortLen = s2.length();
		}else{
			longString = s2;
			shortString = s1;
			shortLen = s1.length();
		}
	
		while(cur_short< shortLen){
			if( shortString.charAt(cur_short) != longString.charAt(cur_long) ){
				cur_long++;
				count++;
				if(count>1){
					break;
				}
			}else{
				cur_short++;
				cur_long++;
			}
		}
		
		if(count <= 1){
			return true;
		}else{
			return false;
		}
	}
}

- sh88990 April 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if(str_1.length > str_2.length)
str =str_1;
str_othr =str_2
else
str = str_2;
str_othr = str_1
int count =0;

for (i=0; i <str.length; i++)
if(str.charat(i) == str_othr.charat(i-count);
i++;
else
if (count >2) exit;
else count++;

- kartikkhatri01 April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static bool OneEditApart(string s1, string s2)
{
	var i1 = 0;
	var i2 = 0;

	var edits = 0;

	while (i1 < s1.Length && i2 < s2.Length)
	{
		if (s1[i1] != s2[i2])
		{
			edits++;
			if (edits > 1)
				return false;

			if (s1.Length < s2.Length)
			{
				i2++;
			}
			else if (s2.Length < s1.Length)
			{
				i1++;
			}
			else
			{
				i1++;
				i2++;
			}
		}
		else
		{
			i1++;
			i2++;
		}
	}

	if (i1 < s1.Length - 1 || i2 < s2.Length - 1)
		return false;

	// for "cat" == "cat" case
	if (edits == 0 && s1.Length == s2.Length)
		return false;

	return true;
}

- v.shashenko April 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<conio.h>
#include<string.h>
using namespace std;
bool editstring(char *p,char *q,int,int);
bool replacement(char *,char *,int);
bool removestring(char *,char *,int,int);
bool insertstring(char *,char *,int ,int);
int main()
{
char a[10],b[10];
int i;
cout<<"enter first strings:\n";
cin>>a;
while(1)
{
cout<<"enter second string:\n";
cin>>b;
int l,m;
l=strlen(a);
m=strlen(b);
i=editstring(a,b,l,m);
if(i==1)
cout<<"true:";
else
cout<<"false";
}
getch();
return 0;

}
bool editstring(char *p,char *q,int x,int y )
{
if(x==y)
{
return replacement(p,q,x);
}
else
{
if(x>y)
return removestring(p,q,x,y);
else
return insertstring(p,q,x,y);
}
}
bool replacement(char *M,char *N,int w)
{
int i=0,count1=0,count2=0;
while(i<w)
{
if(*M==*N)
{
M++;
N++;
count2++;
}
else
{
count1++;
N++;
M++;
}
i++;
}
if(count1==1&&count2==w-1)
return true;
else
return false;
}
bool removestring(char *M,char *N,int w,int z)
{
int i=0,count1=0,count2=0;
while(i<w)
{
if(*M==*N)
{
M++;
N++;
count1++;
}
else
{
M++;
count2++;
}
i++;
}
if(count1==z&&count2==1)
return true;
else
return false;
}
bool insertstring(char *M,char *N,int w,int z)
{
int i,count1,count2=0;
i=0;
count1=0;
while(i<z)
{
if(*M==*N)
{
M++;
N++;
count1++;
}
else
{
N++;
count2++;
}
i++;
}
if(count1==w&&count2==1)
return true;
else
return false;
}

- Ashok kumar Bhukhar April 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this is a clean solution that runs in O(n). Any feedback on this approach appreciated :)

public static boolean OneEditApart (String s1, String s2)
    {
        final int s1Length        = (null == s1)?0:s1.length();
        final int s2Length        = (null == s2)?0:s2.length();
        int s1Index         = 0;
        int s2Index         = 0;
        int unmatched       = 0;
        
        // general case check
        if (0 == s1Length || 0 == s2Length || 
            1 < Math.abs(s1Length-s2Length))
        {
            return false;
        }
        else
        {
            // loop until 
            while (s1Length > s1Index && s2Length > s2Index)
            {
                if (s1.charAt(s1Index) == s2.charAt(s2Index))
                {
                    s1Index++;
                    s2Index++;
                }
                else
                {
                    unmatched++;
                    
                    if (s1Length > s1Index+1 && 
                        s1.charAt(s1Index+1) == s2.charAt(s2Index))
                    {
                        s1Index++;
                    }
                    else if (s2Length > s2Index+1 && 
                        s1.charAt(s1Index) == s2.charAt(s2Index+1))
                    {
                        s2Index++;
                    }
                    else
                    {
                        s1Index++;
                        s2Index++;
                    }
                }
                
                if (1 < unmatched)
                {
                    return false;
                }
            }
        }
        
        return true;
    }

- Jona May 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Iterative approach in PHP, runs O(n)

function OneEditApart($s1, $s2) {
	// only calc these once
	$s1Len = strlen($s1);
	$s2Len = strlen($s2);

	// 0 edits apart, return false
	if ($s1 == $s2) {
		return false;
	}

	// we want the shorter as the first param
	if ($s1Len > $s2Len) {
		return OneEditApart($s2, $s1);
	}

	// if lengths differ by more than 1, return false
	if ($s2Len - $s1Len > 1) {
		return false;
	}

	// keep current indexes of both words
	$s1i = $s2i = $edits = 0;

	while ($s1i < $s1Len && $s2i < $s2Len) {
		// break processing and return if we have achieved more than one edit
		if ($edits > 1) {
			return false;
		}

		// if letters match, next
		if ($s1[$s1i] == $s2[$s2i]) {
			$s1i++;
			$s2i++;
			continue;
		}

		// insert case
		if ($s1[$s1i] == $s2[$s2i + 1]) {
			$edits++;
			$s1i++;
			$s2i = $s2i + 2;
			continue;
		}

		// remove case
		if ($s1[$s1i + 1] == $s2[$s2i]) {
			$edits++;
			$s1i = $s1i + 2;
			$s2i++;
			continue;
		}

		// replace case
		$edits++;
		$s1i++;
		$s2i++;
	}

	// get index difference, as it will impact our remaining length calc
	$iDiff = $s2i - $s1i;

	// add any differences in word lengths minus previous diff to inserts
	$edits = $edits + ($s2Len - $s1Len - $iDiff);

	if ($edits == 1) {
		return true;
	}

	// more or less than 1
	return false;

}

- jasonj79 May 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python

def OneEditApartImpl(big,small,limit,lag):
    hit = 0  
    for index, letters in enumerate(zip(big,small)):
        if letters[0]!=letters[1]:
            hit+=1
            if hit > limit:
                return False     
            return OneEditApartImpl (big[index+1:],small[index+1-lag:],0,0)
    return True       

def OneEditApart(word1,word2):
    len1 = len(word1)
    len2 = len(word2)
    
    #trival: lenght greater than 1
    if abs(len1 - len2) > 1:
        return False
    
    #trival: string are equal 
    if word1 == word2:
        return True
    
    #non trial cases
    if(len1==len2):
        return OneEditApartImpl(word1,word2,1,0)
    elif(len1>len2):
        return OneEditApartImpl(word1,word2,1,1)
    else:
        return OneEditApartImpl(word2,word1,1,1)
        

assert OneEditApart("cat", "dog") == False 
assert OneEditApart("cat", "cats") == True 
assert OneEditApart("cat", "cut") == True 
assert OneEditApart("cat", "cast") == True 
assert OneEditApart("cat", "at") == True 
assert OneEditApart("cat", "acts") == False

- maitreyak May 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Many of these solution are really redundant. First of all to check if the lengths differ for more than 1 it is sufficient use the absolute value: `ABS(len1 - len2) > 1`. Then there is just a check to do, remembering if the we have already used "our change to wrong" and increment the correct index:

- (BOOL)oneEditAPartFromString:(NSString *)string1 andString:(NSString *)string2 {
    
    		int len1 = [string1 length], len2 = [string2 length];
    
    		if (ABS(len1 - len2) > 1)
        		return NO;
    
    		BOOL errorAvailable = YES;
    		int i = 0, j = 0;
    
    		while (i < len1 && j < len2) {
        
        		if ([string1 characterAtIndex:i] != [string2 characterAtIndex:j]) {
          			if (!errorAvailable)
                			return NO;
            
            			errorAvailable = NO;
            
           			 if (len1 == len2) {
                			++i;
                			++j;
            			} else if(len1 > len2) {
             			   	++i;
           			} else {
               				++j;
           			}
        		} else {
           			++i;
            			++j;
        		}
   	 	}
    
    		return YES;
	}

- matteogobbi.jobs July 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

here's my code o(n) time o(1) space

bool oneeditapart(string s1,string s2)
{
    int i;int f1;
    int n=s1.size(),m=s2.size();
    if(abs(n-m)>1){return false;}
    if(s1.size()==s2.size())
    {
        f1=0;
        for(i=0;i<s1.size();i++)
        {
            if(s1[i]!=s2[i])
            {
                f1++;
            }

        }
        if(f1>1){return false;}else {return true;}

    }
    else
    {
        if(s2.size()>s1.size())
        {
            string s=s1;
            s1=s2;
            s2=s;
        }
        f1=0;
        int j=0;i=0;
        while(i<m && j<n)
        {
            if(s1[j]==s2[i]){i++;j++;}
            else {f1++;j++;}
        }
        if(f1>1){return false;}
        return true;
    }

}

int main()
{
   string s1,s2;
   cin>>s1>>s2;
   if(oneeditapart(s1,s2)){cout<<"Match\n";}
   else {cout<<"NOT Match\n";}
   return 0;

}

- kevseb1993 August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple python code:

def oneapart(a, b):
  pre, post = 0, 0
  # Find length of common prefix (pre)
  for i in xrange(len(a)):
    if i < len(b) and a[i] == b[i]:
      pre += 1
    else:
      break
  # Find length of common suffix (post)
  for i in xrange(len(a)):
    if i < len(b) and a[-i - 1] == b[-i - 1]:
      post += 1
    else:
      break
  # Compute lengths of {a, b} minus common {prefix, suffix}
  la = len(a) - pre - post
  lb = len(b) - pre - post
  return (la, lb) in (
    (0, 1),  # Insert
    (1, 0),  # Remove
    (1, 1),  # Change
    )

- Very simple, working? August 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args){

		
		String a="cat";
		String b="aata";
		System.out.println(OneEditApart(a,b));
	
	}	
	
	static boolean OneEditApart(String a,String b){
						
		char[] arr = b.toCharArray();
		int index=0;
		int count=0;
		if(Math.abs(a.length()-b.length())>1)
			return false;
		
		for(int i=0;i<a.length();i++){
			index=b.indexOf(a.charAt(i));
			if(index>=0){
				arr[index]='\u0000';
			}
			else
				count++;
			
			if(count>1)
				return false;			
		}
		
		String result=String.valueOf(arr).trim();
		if(result.length()<=1)
			return true;
		else
			return false;
	}

- Youngsam September 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My C solution is:

#define MAX(X, Y) ((X) > (Y) ? (X) : (Y))

int oneEditApart(char* s1, char* s2)
{
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int len = MAX(len1, len2);
    int last_found = 0, i, j;
    int same_char = 0;

    if (abs(len1 - len2) > 2)
        return 0;

    for (i = 0; i < len1; ++i)
        for (j = last_found; j < len2; ++j)
            if (s1[i] == s2[j])
            {
                last_found = j+1;
                same_char++;
            }

    if (len == (same_char+1))
        return 1;
    else
        return 0;

}

- Andrew September 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 *
 * Implement a function OneEditApart with the following signature:
 * bool OneEditApart(string s1, string s2)
 *
 * OneEditApart("cat", "dog") = false
 * OneEditApart("cat", "cats") = true
 * OneEditApart("cat", "cut") = true
 * OneEditApart("cat", "cast") = true
 * OneEditApart("cat", "at") = true
 * OneEditApart("cat", "acts") = false
 * Edit is: insertion, removal, replacement
 *
 */
public class OneEditApartChecker {

    public static void main(String[] args) {
	    System.out.println(check("cat", "dog"));
        System.out.println(check("cat", "cats"));
        System.out.println(check("cat", "cut"));
        System.out.println(check("cat", "cast"));
        System.out.println(check("cat", "at"));
        System.out.println(check("cat", "acts"));
        System.out.println(check("bt", "abt"));
        System.out.println(check("cat", "catsy"));
        System.out.println(check("tb", "bt"));
        System.out.println(check("bt", "bb"));
        System.out.println(check("bt", "bbt"));
        System.out.println(check("but", "bot"));
    }

    private static boolean check(String string1, String string2) {

        System.out.println("Value1: " + string1 + "; Value2: " + string2);

        int min = Math.min(string1.length(), string2.length());
        int max = Math.max(string1.length(), string2.length());

        if(max - min > 1) {
            // If the difference between string lengths is more than 1, return false.
            return false;
        }

        String smallString;
        String longString;
        if(min == max) {
            smallString = string1;
            longString = string2;
        } else if(string1.length() < string2.length()) {
            smallString = string1;
            longString = string2;
        } else {
            smallString = string2;
            longString = string1;
        }

        int mismatchCount = 0;
        if(min != max && !smallString.startsWith("" + longString.charAt(0))) {
            smallString = "_" + smallString; // Equating the lengths of both strings by adding an irrelevant char at the beginning.
            mismatchCount++; // Noting the mismatch at the beginning.
        }

        // Iterate on small string.
        // Start with mismatchCount, if a mismatch found at beginning, we will start from next char.
        for(int i = mismatchCount; i < smallString.length(); i++) {

            if(smallString.charAt(i) != longString.charAt(i)) {
                mismatchCount++;
            }

            if(mismatchCount > 1) {
                return false;
            }
        }

        return true;

    }
}

- leogps September 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

boolean OneEditApart(String first, String second) {
    String small = (first.length() <= second.length()) ? first : second;
    String large = (first.length() <= second.length()) ? second : first;
    int lengthDiff = large.length() - small.length();

    if (lengthDiff > 1) {
      return false;
    } else if (lengthDiff == 0) {
      int diffs = 0;
      for (int i = 0; i < small.length(); i++) {
        if ((small.charAt(i) != large.charAt(i))) {
          diffs++;
        }
      }
      return (diffs > 1) ? false : true;
    } else if (lengthDiff == 1) {
      if (small.equals(large.substring(1))) {
        return true;
      }
      if (small.equals(large.substring(0, large.length() - 2))) {
        return true;
      }
      return false;
    }

    return false;
  }

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

No recursion. O(N) time & O(1) space complexity. This algorithm is using the fact that if one edit is made, the remaining string should be same.

auto one_edit_apart = [](const string& s, const string& t) {
	auto n = s.length(), m = t.length();
	auto is_same_str = [&](size_t i, size_t j) {
		while (i < n && j < m) {
			if (s[i++] != t[j++]) {
				return false;
			}
		}
		return i >= n && j >= m ? true : false;
	};
	for (size_t i = 0, j = 0; i < n && j < m; ++i, ++j) {
		if (s[i] != t[j]) {
			return is_same_str(i+1,j+1) ||	// replace
				is_same_str(i,j+1) ||		// insertion
				is_same_str(i+1,j);		// deletion
		}
	}
	return false;
};

- anonymous November 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function oea($str1, $str2)
{
    if ($str1 == $str2) {
        return false;
    }

    $length1 = strlen($str1);
    $length2 = strlen($str2);

    if ($length2 > $length1) {
        return oea($str2, $str1);
    }

    $theSame = false;
    if ($length1 == $length2) {
        $theSame = true;
    }
    $i = 0;
    $bubble = null;
    while ($i < $length1) {
        if ($str1[$i] != @$str2[$i]) {
            if (!is_null($bubble)) {
                return false;
            }
            if (!$theSame) {
                $bubble = $str1[$i];
                $str1 = substr($str1, 0, $i) . substr($str1, $i + 1);
                $length1 = strlen($str1);
                continue;
            }
            $bubble = true;
        }
        $i++;
    }
    return true;
}

- Pidoras November 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++

bool Calculator_Percent(int Longger_Len, char *temp_s1, char *temp_s2)
{
double Correct_Counter = 0.0;
double Percent = 0;

for (int i = 0; i < Longger_Len; i++)
{
if (temp_s1[i]==temp_s2[i])
{
Correct_Counter++;
}
}

**Percent = (Correct_Counter / Longger_Len) * 100;
** return (Percent >= 50);
}

**
bool OneEditApart(char *s1, char *s2)**
{
int Longger_Len = strlen(s1) >= strlen(s2) ? strlen(s1) : strlen(s2); //store longer string len
bool result = false;

char *temp_s1 = new char[Longger_Len + 1];
strcpy_s(temp_s1, strlen(s1) + 1, s1);

char *temp_s2 = new char[Longger_Len + 1];
strcpy_s(temp_s2, strlen(s2) + 1, s2);

if (Calculator_Percent(Longger_Len, temp_s1, temp_s2))
{
result = true;
}
else if (!(strlen(temp_s1) == strlen(temp_s2)) )
{

char *shorter = strlen(temp_s1) > strlen(temp_s2) ? temp_s2 : temp_s1; //select short string

for (int i = strlen(shorter); i > 0; i--)
{
shorter[i] = shorter[i - 1];
}
shorter[0] = '\0';

if (Calculator_Percent(Longger_Len, temp_s1, temp_s2))
{
result= true;
}
else
{
result= false;
}
}

delete[] temp_s1;
delete[] temp_s2;

return result;
}

- Jung HO April 15, 2016 | 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