Directi Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static Map<String, Integer> map = new HashMap<String, Integer> ();
static int f (String s, String d, int count) {
if (s == null) {
return Integer.MAX_VALUE;
}
if (map.containsKey(s)) {
return map.get(s);
}
if (s.equals(d)) {
return count;
}
map.put (s, Integer.MAX_VALUE);
int min = minimunOf (
f(rule1(s), d, count+1),
f(rule2(s), d, count+1),
f(rule3(s), d, count+1),
f(rule4(s), d, count+1)
);
map.put(s, min);
return min;
}
private static int minimunOf(int... n) {
ArrayList<Integer> list = new ArrayList<Integer> ();
for (int i: n) {
list.add(i);
}
Integer [] in = list.toArray(new Integer[0]);
Arrays.sort(in);
return in[0];
}
private static String rule1(String s) {
int i = s.indexOf('_');
if (i == s.length()-1) {
return null;
}
char[] temp = s.toCharArray();
temp[i] = temp[i+1];
temp[i+1] = '_';
return new String (temp);
}
private static String rule2(String s) {
int i = s.indexOf('_');
if (i == 0) {
return null;
}
char[] temp = s.toCharArray();
temp[i] = temp[i-1];
temp[i-1] = '_';
return new String (temp);
}
private static String rule3(String s) {
int i = s.indexOf('_');
if (i == s.length()-1 || i == s.length()-2 ) {
return null;
}
char[] temp = s.toCharArray();
if (temp[i+1] == temp[i+2]) {
return null;
}
temp[i] = temp[i+2];
temp[i+2] = '_';
return new String (temp);
}
private static String rule4(String s) {
int i = s.indexOf('_');
if (i == 0 || i == 1 ) {
return null;
}
char[] temp = s.toCharArray();
if (temp[i-1] == temp[i-2]) {
return null;
}
temp[i] = temp[i-2];
temp[i-2] = '_';
return new String (temp);
}
public static void main(String[] args) {
String s = "abaa_a";
String d = "b_aaaa";
String[][] input = {
{"abaa_a", "b_aaaa"},
{"abc_abc", "abca_bc"},
{"abc_abc", "abc_bac"},
{"abc_abc", "ab_cabc"},
{"abc_abc", "abc_abc"},
{"abc_abc", "abcabc"},
};
for (int i = 0; i < input.length; i++) {
map.clear();
int min = f (input[i][0], input[i][1], 0);
if (min == Integer.MAX_VALUE)
System.out.println("No Result");
else
System.out.println("Result: " + min);
}
}
}
Launch a search over the state space using breadth-first search. Each state can branch to a maximum 4 more states, according to the rules defined.
You just need to be careful to store all states you already explored in order to avoid processing the same state more than once.
#include <iostream>
#include <string>
#include <deque>
#include <set>
// first: intermediate string; second: underscore position
typedef std::pair<std::string, int> StringPair;
// first: above; second: number of steps so far
typedef std::pair<StringPair, int> StatePair;
typedef std::deque<StatePair> Queue;
typedef std::set<std::string> StringSet;
int Swap(const std::string &input, const std::string &output)
{
Queue Q;
// Used to keep track of what states we have already explored
StringSet S;
// Position of the underscore
int us_pos = input.find('_');
StatePair p(StringPair(input, us_pos), 0);
Q.push_back(p);
unsigned strlength = input.length();
while (!Q.empty()) {
StatePair p = Q.front();
Q.pop_front();
const std::string state_string = p.first.first;
us_pos = p.first.second;
int len = p.second;
// Finished?
if (state_string == output)
return len;
// Have we already explored this state?
if (S.count(state_string)) continue;
S.insert(state_string);
std::string next_state_string;
// First branch
if (us_pos > 0) {
next_state_string = state_string;
next_state_string[us_pos] = next_state_string[us_pos-1];
next_state_string[us_pos-1] = '_';
p = StatePair(StringPair(next_state_string, us_pos-1), len+1);
Q.push_back(p);
}
// Second branch
if (us_pos < strlength-1) {
next_state_string = state_string;
next_state_string[us_pos] = next_state_string[us_pos+1];
next_state_string[us_pos+1] = '_';
p = StatePair(StringPair(next_state_string, us_pos+1), len+1);
Q.push_back(p);
}
// Third branch
if (us_pos > 1) {
next_state_string = state_string;
char c1 = next_state_string[us_pos-2];
char c2 = next_state_string[us_pos-1];
if (c1 != c2) {
next_state_string[us_pos] = c1;
next_state_string[us_pos-2] = '_';
p = StatePair(StringPair(next_state_string, us_pos-2), len+1);
Q.push_back(p);
}
}
// Fourth branch
if (us_pos < strlength-2) {
next_state_string = state_string;
char c1 = next_state_string[us_pos+2];
char c2 = next_state_string[us_pos+1];
if (c1 != c2) {
next_state_string[us_pos] = c1;
next_state_string[us_pos+2] = '_';
p = StatePair(StringPair(next_state_string, us_pos+2), len+1);
Q.push_back(p);
}
}
}
return -1;
}
but this is a very inefficient process for both time and space ?? what will be complexity of your program, can you please confirm ?
This is a common kind of search in artificial intelligence. The time complexity is the same as DFS, O(b^h), where b is the branching factor (4 in this case = number of rules), and h is the height of the state space tree (edit distance between input and output).
In memory, it's also O(b^h). It can be problematic if we deal with large strings, however I believe it's worthy since we have the minimum number of steps by the first time we arrive at the output, as opposed to other kinds of search.
Furthermore, there is one question in the book about transforming one word into another by using only intermediary words that exist in the dictionary. The solution for that problem is very similar.
I believe having only two characters doesn't make difference really. But I could be wrong.
Can you give me some testcases
- saurabh January 19, 2015simpe rule
1. build 4 string based on 4 rules
2. call this function for each string type
3. with each call, pass counter by incremented by 1
4. when target string is achieved, return counter which was passed
5. return min of all function calls.
https: // ideone.com/hKrfYv
its working with given test case and some more custom test-cases