Google Interview Question
SDE1sCountry: United States
public static void main(String[] args) {
System.out.println(getInsertedCharacter("fhsvbfdbsrgnjnvklnvgafnvjksdfnjvksfvsjbnfdjnvdjfnvksdjfnvkjsfnv", "Zfhsvbfdbsrgnjnvklnvgafnvjksdfnjvksfvsjbnfdjnvdjfnvksdjfnvkjsfnv"));
}
public static Character getInsertedCharacter(String s1, String s2){
if(s2.length()-s1.length() != 1) // Assuming s2 is always larger and not null
return null;
int mid = s1.length()/2;
return getInsertedCharacter(s1, s2, mid);
}
public static Character getInsertedCharacter(String s1, String s2, int mid){
if(s1.length() == 1 && s2.length() == s1.length())
return s2.charAt(0);
if(s2.length()==1)
return s2.charAt(0);
if(s1.substring(0, mid).equals(s2.substring(0, mid))){
String temp = s1.substring(mid, s1.length());
return getInsertedCharacter(temp, s2.substring(mid, s2.length()), temp.length()/2);
}else
return getInsertedCharacter(s1.substring(0, mid), s2.substring(0, mid), mid/2);
}
public static void main(String[] args) {
System.out.println(getInsertedCharacter("fhsvbfdbsrgnjnvklnvgafnvjksdfnjvksfvsjbnfdjnvdjfnvksdjfnvkjsfnv", "Zfhsvbfdbsrgnjnvklnvgafnvjksdfnjvksfvsjbnfdjnvdjfnvksdjfnvkjsfnv"));
}
public static Character getInsertedCharacter(String s1, String s2){
if(s2.length()-s1.length() != 1) // Assuming s2 is always larger and not null
return null;
int mid = s1.length()/2;
return getInsertedCharacter(s1, s2, mid);
}
public static Character getInsertedCharacter(String s1, String s2, int mid){
if(s1.length() == 1 && s2.length() == s1.length())
return s2.charAt(0);
if(s2.length()==1)
return s2.charAt(0);
if(s1.substring(0, mid).equals(s2.substring(0, mid))){
String temp = s1.substring(mid, s1.length());
return getInsertedCharacter(temp, s2.substring(mid, s2.length()), temp.length()/2);
}else
return getInsertedCharacter(s1.substring(0, mid), s2.substring(0, mid), mid/2);
}
}
This is a simple binary search. Just you have to update the search conditions accordingly.
int insertedString(char *s, char *p, int n)
{
int low = 0, high = n-1, mid = 0;
while(low <= high)
{
mid = (low+high)/2;
//printf("%d\n",mid);
if(p[mid] == s[mid])
{
low = mid + 1;
}
else if(p[mid] == s[mid-1])
{
high = mid - 1;
}
else
{
return mid;
}
}
return mid;
}
public String findCharacter(String s1, String s2) {
if (s2.length() == 1) {
return s2;
}
int mid = s2.length()/2;
if (s1.substring(0, mid).equals(s2.substring(0, mid))) {
return findCharacter(s1.substring(mid), s2.substring(mid));
}
return findCharacter(s1.substring(0, mid), s2.substring(0, mid));
}
public String findCharacter(String s1, String s2) {
if (s2.length() == 1) {
return s2;
}
int mid = s2.length()/2;
if (s1.substring(0, mid).equals(s2.substring(0, mid))) {
return findCharacter(s1.substring(mid), s2.substring(mid));
}
return findCharacter(s1.substring(0, mid), s2.substring(0, mid));
}
package practice;
public class StringExtraChar
{
public static void main(String[] args)
{
System.out.println(findChar("dgfgfdgdfghghfghdgdfghdfhgdfgf", "dgfgfdgdfghghfghdgdfghdfhgdfxgf"));
}
private static String findChar(String s1, String s2)
{
if (Math.abs(s2.length() - s1.length()) != 1) {
return null;
}
if (s2.length() == 1 && s1.length() == 0) { //this is our character
return s2;
}
if (s1.length() == 1 && s2.length() == 0) { //this is our character
return s1;
}
if (s1.length() == 1 && s2.length() == 2) {
final String[] split = s2.split(s1);
return split[0].isEmpty() ? split[1] : split[0];
}
int mid1 = s1.length() / 2;
String left_s1 = s1.substring(0, mid1);
String right_s1 = s1.substring(mid1);
int mid2 = s2.length() / 2;
String left_s2 = s2.substring(0, mid2);
String right_s2 = s2.substring(mid2);
if (left_s1.equals(left_s2)) {
return findChar(right_s1, right_s2);
}
else if (right_s1.equals(right_s2)) {
return findChar(left_s1, left_s2);
}
else {
return left_s1.length() == left_s2.length() ?
findChar(left_s1, left_s2 + right_s2.charAt(0)) :
findChar(right_s1.substring(1), right_s2);
}
}
}
Only works if Strings contain unique characters.
- jgriesser February 06, 2018