Given a character array with a set of characters

Interview Questions

Given a character array with a set of characters.....

Microsoft Interview Questions and Answers

77. Given a character array with a set of characters.....

Question:
Given a character array with a set of characters, there might be repetitions as well, given two characters, you should give the minimum distance between these two characters in the whole array. O(n^2) and O(n) solutions are possible.

maybe an answer:

int minDistance(char s[], char c1, char c2)
{
int i,j,k;
j = k = -1;
int minDist = INT_MAX;
int len = strlen(s);
int dist;
for(i=0;i<len;i++)
{
if(s[i] == c1 || s[i] == c2)
{
if(c1 == c2)
return 0;
if(s[i] == c1)
j = i;
else
k = i;
if(j>=0 && k>=0)
{
dist = abs(j-k);
if(dist < minDist)
minDist = dist;
}
}
}
return (minDist < INT_MAX ? minDist : -1);
}

maybe an answer2:

we need is a list of indices at which either A or B occurs in the string. Then we must traverse the list and look at the adjacent entries and find their distance and keep track of minimum distance. Here is the code that does that and it will work for all permutations of strings:

/// <summary>
/// Given a character array with a set of characters, there might be repetitions as well,
/// given two characters, you should give the minimum distance between these two characters
/// in the whole array. O(n^2) and O(n) solutions are possible.
/// </summary>
[TestMethod]
public void FindMinimumDistanceBetweenCharacters()
{
string str = "ACDBEACDUIA";

char a = 'A';
char b = 'B';

int len = str.Length;
List<int> bothPos = new List<int>();

for (int i = 0; i < len; i++)
{
if ((str[i] == a) || (str[i] == b))
{
bothPos.Add(i);
}
}

int minimum = int.MaxValue;

for (int i = 1; i < bothPos.Count; i++)
{
if (str[bothPos[i]] != str[bothPos[i - 1]])
{
int distance = bothPos[i] - bothPos[i - 1] - 1;

if (distance < minimum)
{
minimum = distance;
}
}
}

Assert.AreEqual(1, minimum);
}

(Continued on next question...)