Directi Interview Question
SDE1sCountry: India
Interview Type: Written Test
using System;
/* A string can contain only a, b or c.
There cannot be 2 consecutive same character.
First and the last character cannot be the same.
Now given a string with ‘a’, ‘b’, ‘c’ or ‘?’.
We need to find the string replacing ‘?’ that
satisfy the above conditions. For multiple-answer
display lexicographically smallest string. For no
answer possible display “Not Possible”. */
namespace ReplaceQuestionMarks
{
class myClass
{
static void Main()
{
string original = "ab?";
char[] solution = replaceChars(original.ToCharArray());
Console.WriteLine($"Original: {original}, solution: {(Array.IndexOf(solution, '?') >= 0 ? "Not Possible" : new string(solution))}");
}
public static char[] replaceChars(char[] soFar)
{
if (soFar == null || soFar.Length < 1) return soFar;
int nextQuestionMark = Array.IndexOf(soFar, '?');
if (nextQuestionMark < 0) return soFar;
char[] nextAttempt = (char[])soFar.Clone();
nextAttempt[nextQuestionMark] = 'a';
if (isValid(nextAttempt)) return replaceChars(nextAttempt);
nextAttempt[nextQuestionMark] = 'b';
if (isValid(nextAttempt)) return replaceChars(nextAttempt);
nextAttempt[nextQuestionMark] = 'c';
if (isValid(nextAttempt)) return replaceChars(nextAttempt);
return soFar;
}
public static bool isValid(char[] soFar)
{
// Single character strings are always valid
if (soFar.Length < 2) return true;
// Ensure first and last are different
if (soFar[0] == soFar[soFar.Length - 1]) return false;
// Ensure no neighbors match
for (int index = 1; index < soFar.Length; index++)
{
if (soFar[index] != '?' && (soFar[index] == soFar[index - 1] || (index < soFar.Length - 1 && soFar[index] == soFar[index + 1])))
return false;
}
// It's valid
return true;
}
}
}
using System;
/* A string can contain only a, b or c.
There cannot be 2 consecutive same character.
First and the last character cannot be the same.
Now given a string with ‘a’, ‘b’, ‘c’ or ‘?’.
We need to find the string replacing ‘?’ that
satisfy the above conditions. For multiple-answer
display lexicographically smallest string. For no
answer possible display “Not Possible”. */
namespace ReplaceQuestionMarks
{
class myClass
{
static void Main()
{
string original = "ab?";
char[] solution = replaceChars(original.ToCharArray());
Console.WriteLine($"Original: {original}, solution: {(Array.IndexOf(solution, '?') >= 0 ? "Not Possible" : new string(solution))}");
}
public static char[] replaceChars(char[] soFar)
{
if (soFar == null || soFar.Length < 1) return soFar;
int nextQuestionMark = Array.IndexOf(soFar, '?');
if (nextQuestionMark < 0) return soFar;
char[] nextAttempt = (char[])soFar.Clone();
nextAttempt[nextQuestionMark] = 'a';
if (isValid(nextAttempt)) return replaceChars(nextAttempt);
nextAttempt[nextQuestionMark] = 'b';
if (isValid(nextAttempt)) return replaceChars(nextAttempt);
nextAttempt[nextQuestionMark] = 'c';
if (isValid(nextAttempt)) return replaceChars(nextAttempt);
return soFar;
}
public static bool isValid(char[] soFar)
{
// Single character strings are always valid
if (soFar.Length < 2) return true;
// Ensure first and last are different
if (soFar[0] == soFar[soFar.Length - 1]) return false;
// Ensure no neighbors match
for (int index = 1; index < soFar.Length; index++)
{
if (soFar[index] != '?' && (soFar[index] == soFar[index - 1] || (index < soFar.Length - 1 && soFar[index] == soFar[index + 1])))
return false;
}
// It's valid
return true;
}
}
}
public static void replace(String str) {
if (str == null || str.length() == 0) {
return;
}
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
if (c == '?') {
if (isEligible(chars, 'a', i)) {
chars[i] = 'a';
} else if (isEligible(chars, 'b', i)) {
chars[i] = 'b';
} else if (isEligible(chars, 'c', i)) {
chars[i] = 'c';
} else {
System.out.println("Not possible");
}
}
}
System.out.println(new String(chars));
}
private static boolean isEligible(char[] chars, char c, int i) {
int next = (i == chars.length - 1) ? 0 : i + 1;
int prev = (i == 0) ? chars.length - 1 : i - 1;
if (chars[prev] == c || chars[next] == c) {
return false;
}
return true;
}
"public static void replace(String str) {
if (str == null || str.length() == 0) {
return;
}
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
if (c == '?') {
if (isEligible(chars, 'a', i)) {
chars[i] = 'a';
} else if (isEligible(chars, 'b', i)) {
chars[i] = 'b';
} else if (isEligible(chars, 'c', i)) {
chars[i] = 'c';
} else {
System.out.println("Not possible");
}
}
}
System.out.println(new String(chars));
}
private static boolean isEligible(char[] chars, char c, int i) {
int next = (i == chars.length - 1) ? 0 : i + 1;
int prev = (i == 0) ? chars.length - 1 : i - 1;
if (chars[prev] == c || chars[next] == c) {
return false;
}
return true;
}"
public static void replace(String str) {
if (str == null || str.length() == 0) {
return;
}
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
if (c == '?') {
if (isEligible(chars, 'a', i)) {
chars[i] = 'a';
} else if (isEligible(chars, 'b', i)) {
chars[i] = 'b';
} else if (isEligible(chars, 'c', i)) {
chars[i] = 'c';
} else {
System.out.println("Not possible");
}
}
}
System.out.println(new String(chars));
}
private static boolean isEligible(char[] chars, char c, int i) {
int next = (i == chars.length - 1) ? 0 : i + 1;
int prev = (i == 0) ? chars.length - 1 : i - 1;
if (chars[prev] == c || chars[next] == c) {
return false;
}
return true;
}
{{public static void replace(String str) {
if (str == null || str.length() == 0) {
return;
}
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
if (c == '?') {
if (isEligible(chars, 'a', i)) {
chars[i] = 'a';
} else if (isEligible(chars, 'b', i)) {
chars[i] = 'b';
} else if (isEligible(chars, 'c', i)) {
chars[i] = 'c';
} else {
System.out.println("Not possible");
}
}
}
System.out.println(new String(chars));
}
private static boolean isEligible(char[] chars, char c, int i) {
int next = (i == chars.length - 1) ? 0 : i + 1;
int prev = (i == 0) ? chars.length - 1 : i - 1;
if (chars[prev] == c || chars[next] == c) {
return false;
}
return true;
}
}}}
In the input string, only two characters are important: The firsr and the 2nd last character (provided the last character is '?'). Consider the following cases:
1)If the first and the second last characters are equal, then we the output can be either of the other two letters. But we need the character which comes first in alphabetical order. So if the first character is 'a', then the output will be 'b', in all other cases it will be 'a'.
2) If the first and the second last characters are unequal, then we will have to give the remaining character as output. Eg. if the first and second last characters are 'a' and 'c' are unequal, then 'b' will be the output. So I have written the following code. It uses a bitwise XOR operator, see if it helps you:
- 123ayanjit August 31, 2019