Adobe Interview Question
Java DevelopersCountry: United States
Interview Type: In-Person
If my assumption is correct, then I would handle the problem with recursive approach like
pseudo code:
public void ShowAllCombinations(string inputString, string carry, int point)
{
if (point >= inputString.Length) return;
for (int i = point; i < inputString.Length; i++)
{
string newString = carry == null or empty ? inputString[i] : carry + inputString[i];
// Conversion method from char to string is needed here....
print(newString);
ShowAllCombinations(inputString, newString, point + 1);
}
}
can we design a hash function which give same hash value if palindrome are passed....
position of char need to be assigned in a different way starting from both ends upto mid point.
like no of char+for each char(ascii of char*position);
eg,
abcde;
edcba;
no of char= 5
ascii =97,98,99,100,101
position=12321
hash value for abcde=5+(97*1+98*2+99*3+100*2+101*1) = 891
hash value for abcde=5+(101*1+100*2+99*3+98*2+99*1) = 891
just one more way to do it.
print all the subsets one by one and while printing each subset, keep adding them in reversed format in a prefix tree. each time you add a subset, check if its already present.
if it is discard it otherwise, add print and add it to prefix tree in reversed format.
This is subset problem.
Generate all subsets of a given set.
s("",abcd)
/ \
s(a,bcd) s("",bcd)
/ \ / \
s(ab,cd) s(ab,d) s(ac,d) s(a,d)
/ \ / \ / \ / \
abcd abc abd ab acd ac ad a
C ++ CODE
void RecSubsets(string scanned, string unscanned)
{
if(unscanned == "")
cout<<scanned;
RecSubsets(scanned+unscanned[0] , unscanned.substr(1);
RecSubsets(scanned, unscanned.substr(1));
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Powerset {
private String str = "abcde"; // our string
private List<String> list = new ArrayList<>();
public static void main(String[] args) {
Powerset ps = new Powerset();
for (int i = 0; i < ps.str.length(); i++) { // traverse through all
// characters
ps.subs("", i);
}
Collections.sort(ps.list);
System.out.println("List-> " + ps.list + "size-> " + ps.list.size());
}
void subs(String substr, int index) {
String s = "" + str.charAt(index); // very important, create a variable
// on each stack
s = substr + s; // append the subset so far
//System.out.println(s); // print
list.add(s);
for (int i = index + 1; i < str.length(); i++)
subs(s, i); // call recursively
}
}
public class Combination {
public static void main(String[] args) {
String str = "abcde";
String tmp="";
System.out.println("Print all combinations: ");
for(int i=0; i<str.length(); ++i) {
tmp += str.charAt(i);
printCombiantion(tmp, str.substring(i+1, str.length()), String.valueOf(str.charAt(i)));
}
}
public static void printCombiantion(String s, String t, String indi) {
System.out.println(indi);
for(int i=0; i<t.length(); i++) {
System.out.println(s+t.charAt(i));
}
}
}
I'm guessing 'avoiding pallindrome' means the combinations like "ab" "ba" is not sllowed, right??
- TS July 12, 2012