CareerCup

Bit Manipulation problem (c#)

public bool IsMetaString(char[] A, char[] B)
        {
            count = 0;
            var bitsA = 0;
            var bitsB = 0;

            for (int i = 0; i < A.Length; i++)
            {
                var valA = A[i] - 'a';
                var valB = B[i] - 'a';
                bitsA |= (1 << valA);
                bitsB |= (1 << valB);
                var xOr = (1 << valA) ^ (1 << valB);
                if (xOr > 0)
                    count++;
            }

            return (bitsA ^ bitsB) == 0 && count == 2;
        }

Implementation in Java. (I've assumed that 'aba' and 'aba' are meta words, but 'abc' and 'abc' are not)

static boolean isMetaWords(String firstWord, String secondWord) {
    if (firstWord.length() != secondWord.length()) {
      return false;
    }
    int firstDiff = -1, secondDiff = -1;
    Map<Character, Integer> wordStatistic = new HashMap<>();
    for (int i = 0; i < firstWord.length(); i++) {
      char symbol = firstWord.charAt(i);
      wordStatistic.put(symbol, wordStatistic.getOrDefault(symbol, 0) + 1);
      if (symbol != secondWord.charAt(i)) {
        if (firstDiff == -1) {
          firstDiff = i;
        } else if (secondDiff == -1) {
          secondDiff = i;
        } else {
          return false;
        }
      }
    }
    if (firstDiff == -1 && secondDiff == -1) {
      // both strings are the same, just check that the string has repeatable symbols
      for (int v : wordStatistic.values()) {
        if (v > 1) {
          return true;
        }
      }
      return false;
    }
    if (secondDiff == -1) {
      return false;
    }
    return firstWord.charAt(firstDiff) == secondWord.charAt(secondDiff)
        && firstWord.charAt(secondDiff) == secondWord.charAt(firstDiff);
  }

Subset of tests is:

{"Converse", "Conserve", true},
        {"test", "test", true},
        {"false", "true", false},
        {"test", "text", false},
        {"change", "cgahne", false},
        {"change", "cganhe", true},
        {"abcd", "abcd", false},
        {"abcda", "abcda", true},

def checkMeta(s1, s2):
    if len(s1) != len(s2):
        return False
    diff_values = {x1 for x1, x2 in zip(s1, s2) if x1 != x2}
    if len(diff_values) != 2:
        return False
    d1, d2 = diff_values
    swapped_s1 = ''.join(d2 if v == d1 else d1 if v == d2 else v for v in s1)
    return swapped_s1 == s2

assert checkMeta('abcd', 'cbad')
assert checkMeta('abcda', 'cbadc')
assert not checkMeta('abcd', 'abcd')
assert not checkMeta('abcx', 'abcd')

Simple python solution

def checkMeta(s1, s2):
    if len(s1) != len(s2):
        return False
    diff_values = {x1 for x1, x2 in zip(s1, s2) if x1 != x2}
    if len(diff_values) != 2:
        return False
    d1, d2 = diff_values
    swapped_s1 = ''.join(d2 if v == d1 else d1 if v == d2 else v for v in s1)
    return swapped_s1 == s2

assert checkMeta('Converse', 'Conserve')
assert checkMeta('abcd', 'cbad')
assert checkMeta('abcda', 'cbadc')
assert not checkMeta('abcd', 'abcd')
assert not checkMeta('abcx', 'abcd')

public boolean conserve(){
        String str1 = "Converse";
        String str2 = "Conserve";

        int[] map = new int[2];
        int mapIndex=0;
        if(str1.length()!=str2.length()) return false;
        for (int i = 0; i<str1.length() ; i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                if (mapIndex == 2) return false;
                map[mapIndex] = i;
                mapIndex++;
            }
        }

        char temp = str1.charAt(map[0]);
        str1 = str1.substring(0,map[0])+str1.charAt(map[1])+str1.substring(map[0]+1,map[1])+temp+str1.substring(map[1]+1,str1.length());
        return  (str1.equals(str2));

    }

import java.io.IOException;

import org.apache.commons.lang3.text.StrTokenizer;


public class CheckMetaString {

public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub


String x = "converse";
String y = "conserve";
int stratIndex = 0;
int lastIndex = 0;
boolean isflag = true;
if(x.length() != y.length())
throw new IOException("Strings are not meta Strings");
for (int i = 0; i < x.length(); i++) {
int value = x.charAt(i);
int value1 = y.charAt(i);
if(value != value1){
if(isflag){
stratIndex = x.indexOf(x.charAt(i));
isflag = false;
}
else {
lastIndex = x.indexOf(x.charAt(i));
}

}
}
char xx = x.charAt(stratIndex);
char yy = x.charAt(lastIndex);
char[] c = x.toCharArray();
c[stratIndex] = yy;
c[lastIndex] = xx;
String xxx = new String(c);
System.out.println(xxx);
if(xxx.equalsIgnoreCase(y)){
System.out.println("Strings are meta String");
}



}

}

public class MetaStrings {
    /**
     * The idea is that the strings must be different maximum with two characters
     * ANd for the positions that are different should be equal in crossing order
     */
    public boolean areMetaStrings(final String str1, final String str2) {
        if (str1.length() != str2.length()) {
            return false;
        }
        int len = str1.length();
        int firstDiffIndex = -1, secondDiffIndex = -1;
        for (int i = 0; i < len; ++i) {
            if (str1.charAt(i) != str2.charAt(i)) {
                if (firstDiffIndex == -1) {
                    firstDiffIndex = i;
                } else if (secondDiffIndex == -1) {
                    secondDiffIndex = i;
                } else {
                    return false;
                }
            }
        }

        return (firstDiffIndex != -1 && secondDiffIndex != -1)
                && (str1.charAt(firstDiffIndex) == str2.charAt(secondDiffIndex)
                && str1.charAt(secondDiffIndex) == str2.charAt(firstDiffIndex));
    }

}

public static bool isMeta(string first, string second)
        {
            if (first == null || second == null || first.Length != second.Length) return false;
            Mode metaMode = Mode.BeforeMeta;
            int indexOfMismatch = -1;
            for (int i = 0; i < first.Length; i++)
            {
                if (first[i] != second[i])
                {
                    switch (metaMode)
                    {
                        case Mode.BeforeMeta:
                            indexOfMismatch = i;
                            metaMode = Mode.Meta;
                            break;
                        case Mode.AfterMeta:
                            return false;
                        case Mode.Meta:
                            if (first[i] == second[indexOfMismatch]
                                && first[indexOfMismatch] == second[i])
                            {
                                metaMode = Mode.AfterMeta;
                            }
                            else
                            {
                                return false;
                            }
                            break;
                    }
                }
            }
            return metaMode == Mode.AfterMeta;
        }

public enum Mode {
    BeforeMeta, Meta, AfterMeta

}

#include <iostream>
#include <string>

using namespace std;

bool AreMetaString(string a, string b)
{
	char diff_in_a;
	char diff_in_b;
	bool diff = false;
	bool found = false;

	if (a.length() != b.length())
		return false;

	for (int i = 0; i < a.length(); ++i)
	{
		if (a[i] != b[i])
		{
			if (found == true)
				return false;

			if (diff == true)
			{
				if (a[i] == diff_in_b && b[i] == diff_in_a)
					found = true;
				else
					return false;
			}
			else
			{
				diff = true;
				diff_in_a = a[i];
				diff_in_b = b[i];
			}
		}
	}
	return true;
}

void main_meta_strings(void)
{
	string s1 = "Conversa";
	string s2 = "Consarve";

	cout << AreMetaString(s1, s2);
}

change @Dhruva.Bharadwaj's codes to makes sure it is correct!

private static boolean IsMetaString(String string1, String string2) {
        String s1 = string1.toLowerCase();
        String s2 = string2.toLowerCase();
        int diff = 0;
        int diffIndex = 0;
        if (s1.length() != s2.length() || s1.length() == 0) {
            return false;
        }
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) == s2.charAt(i)) {
                continue;
            }
            diff++;
            if (diff > 2) {
                return false;
            } else if (diff == 1) {
                diffIndex = i;
            }else{
                if (s2.charAt(i) == s1.charAt(diffIndex) && s2.charAt(diffIndex)==s1.charAt(i)) {
                        continue;
                }else{
                    return false;
                }
            }
        }

        return diff==2;
    }

int isMeta(char *str1, char *str2)
{
	int nr_diff = 0;
	int diff[2];

	for (int i = 0; str1[i] && str2[i]; i++)
		if (str1[i] != str2[i]) {
			if (nr_diff == 2)
				return 0;
			diff[nr_diff++] = i;
		}

	if (nr_diff != 2)
		return 0;

	if (str1[diff[0]] != str2[diff[1]] || str1[diff[1]] != str2[diff[0]])
		return 0;

	return 1;
}

package google;

public class MetaString {
	public static void main(String args[]) {
		String s1 = "Converse";
		String s2 = "Conserve";

		System.out.println(isMetaString(s1, s2));
	}

	private static boolean isMetaString(String string1, String string2) {
		String s1 = string1.toLowerCase();
		String s2 = string2.toLowerCase();
		int diff = 0;
		int diffIndex = 0;
		if (s1.length() != s2.length() || s1.length() == 0) {
			return false;
		}
		for (int i = 0; i < s1.length(); i++) {
			if (s1.charAt(i) == s2.charAt(i)) {
				continue;
			}
			diff++;
			if (diff > 2) {
				break;
			} else if (diff == 1) {
				diffIndex = i;
			} else {
				if (s2.charAt(i) == s1.charAt(diffIndex)) {
					continue;
				} else {
					diff++;
					break;
				}
			}
		}

		if (diff > 2) {
			return false;
		}
		return true;
	}
}