Facebook Interview Question SDE1s
Country: United States
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class PermuteString {
public List<String> getPermutation(String s) {
List<String> ret = new ArrayList<String>();
if (s.length() == 1) {
char c = s.charAt(0);
if (Character.isLetter(c)) {
ret.add(s.toLowerCase());
ret.add(s.toUpperCase());
} else {
ret.add(s);
}
} else {
List<String> retInternal = getPermutation(s.substring(1));
Character c = s.charAt(0);
if (Character.isLetter(c)) {
Iterator<String> iter = retInternal.iterator();
while (iter.hasNext()) {
String iterStr = iter.next();
ret.add(Character.toString(Character.toLowerCase(c)) + iterStr);
ret.add(Character.toString(Character.toUpperCase(c)) + iterStr);
}
} else {
Iterator<String> iter = retInternal.iterator();
while (iter.hasNext()) {
String iterStr = iter.next();
ret.add(c.toString() + iterStr);
}
}
}
return ret;
}
public static void main(String[] args) {
PermuteString obj = new PermuteString();
List<String> perm = obj.getPermutation("a1b");
Iterator<String> iter = perm.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
}
}
The corner cases can be improved a little bit but this is a working version in python
def permutations(s):
if len(s) == 1: return [s.lower(), s.upper()]
solutions = []
buf = s[0]
x = 1
while s[x].isdigit():
buf += s[x]
x += 1
solutions.extend(map(lambda y: buf.lower() + y,
permutations(s[x:])))
solutions.extend(map(lambda y: buf.upper() + y,
permutations(s[x:])))
return solutions
vector<string> Combs(string const &s, int idx = 0)
{
vector<string> combs;
if (idx == s.size()) {
if (idx != 0) {
combs.push_back("");
}
return combs;
}
if (idx < 0 ||
idx > s.size())
{
return combs;
}
vector<string> sub_combs = Combs(s, idx + 1);
vector<char> prefixes{s[idx]};
if (isalpha(s[idx])) {
prefixes.push_back(isupper(s[idx]) ? tolower(s[idx]) : toupper(s[idx]));
}
for (char prefix : prefixes) {
for (auto const &sub_comb : sub_combs) {
combs.push_back(prefix + sub_comb);
}
}
return combs;
}
#include "iostream"
#include "string"
#include "algorithm"
void function(std::string str, std::string str_result, int int_pos){
if (int_pos == str.size()){
std::cout << str_result << ", ";
}else {
if ((int)str.at(int_pos) < 65){
function(str, str_result + str.at(int_pos), int_pos+1);
}else {
function(str, str_result + str.at(int_pos), int_pos+1);
str[int_pos] = tolower(str[int_pos]);
function(str, str_result + str.at(int_pos), int_pos+1);
}
}
}
int main()
{
std::string str;
std::cout << "input string: ";
getline(std::cin, str);
std::transform(str.begin(), str.end(), str.begin(), ::toupper);
function(str, "", 0);
return 0;
}
import java.util.ArrayList;
import java.util.List;
public class PermuteString {
public List<String> run(String str) {
List<String> list = new ArrayList<>();
recur(str, 0, "", list);
return list;
}
public void recur(String str, int i, String temp, List<String> list) {
if (str.length() <= i) {
list.add(temp);
return;
}
String c = String.valueOf(str.charAt(i));
String lower = c.toLowerCase();
String upper = c.toUpperCase();
if (lower.equals(upper)) {
recur(str, i + 1, temp + lower, list);
} else {
recur(str, i + 1, temp + lower, list);
recur(str, i + 1, temp + upper, list);
}
}
public static void main(String[] args) {
String str = "ab";
String str2 = "a1b";
PermuteString s = new PermuteString();
System.out.println(s.run(str));
System.out.println(s.run(str2));
}
}
import java.util.ArrayList;
import java.util.List;
public class PermuteString {
public List<String> run(String str) {
List<String> list = new ArrayList<>();
recur(str, 0, "", list);
return list;
}
public void recur(String str, int i, String temp, List<String> list) {
if (str.length() <= i) {
list.add(temp);
return;
}
String c = String.valueOf(str.charAt(i));
String lower = c.toLowerCase();
String upper = c.toUpperCase();
if (lower.equals(upper)) {
recur(str, i + 1, temp + lower, list);
} else {
recur(str, i + 1, temp + lower, list);
recur(str, i + 1, temp + upper, list);
}
}
public static void main(String[] args) {
String str = "ab";
String str2 = "a1b";
PermuteString s = new PermuteString();
System.out.println(s.run(str));
System.out.println(s.run(str2));
}
}
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.LinkedBlockingQueue;
public class FindAllPossibleCombinationsOfUpperAndLowercaseChar {
public static void main(String[] args) {
String e1 = "a12b";
String e2 = "abc";
printAllPermutations(e1);
printAllPermutations(e2);
}
static void printAllPermutations(String input) {
Queue<char[]> queue = new LinkedBlockingQueue<>();
char[] data = input.toCharArray();
String uppercase = input.toUpperCase();
String lowercase = input.toLowerCase();
for (int i = 0; i < data.length; i++) {
if(queue.size() == 0) {
if(Character.isDigit(data[i]))
continue;
else {
char[] newData = new char[data.length];
char upperChar = uppercase.charAt(i);
char lowerChar = lowercase.charAt(i);
newData[0] = upperChar;
queue.add(Arrays.copyOf(newData, data.length));
newData[0] = lowerChar;
queue.add(Arrays.copyOf(newData, data.length));
}
} else {
int wordsToElaborate = queue.size();
for (int j = 0; j < wordsToElaborate; j++) {
char[] intermediateResult = queue.poll();
if(Character.isDigit(data[i])) {
intermediateResult[i] = data[i];
queue.add(Arrays.copyOf(intermediateResult, data.length));
} else {
char upperChar = uppercase.charAt(i);
char lowerChar = lowercase.charAt(i);
intermediateResult[i] = upperChar;
queue.add(Arrays.copyOf(intermediateResult, data.length));
intermediateResult[i] = lowerChar;
queue.add(Arrays.copyOf(intermediateResult, data.length));
}
}
}
}
int wordsFound = queue.size();
for (int i = 0; i < wordsFound; i++) {
System.out.println(queue.poll());
}
}
}
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.LinkedBlockingQueue;
public class FindAllPossibleCombinationsOfUpperAndLowercaseChar {
public static void main(String[] args) {
String e1 = "a12b";
String e2 = "abc";
printAllPermutations(e1);
printAllPermutations(e2);
}
static void printAllPermutations(String input) {
Queue<char[]> queue = new LinkedBlockingQueue<>();
char[] data = input.toCharArray();
String uppercase = input.toUpperCase();
String lowercase = input.toLowerCase();
for (int i = 0; i < data.length; i++) {
if(queue.size() == 0) {
if(Character.isDigit(data[i]))
continue;
else {
char[] newData = new char[data.length];
char upperChar = uppercase.charAt(i);
char lowerChar = lowercase.charAt(i);
newData[0] = upperChar;
queue.add(Arrays.copyOf(newData, data.length));
newData[0] = lowerChar;
queue.add(Arrays.copyOf(newData, data.length));
}
} else {
int wordsToElaborate = queue.size();
for (int j = 0; j < wordsToElaborate; j++) {
char[] intermediateResult = queue.poll();
if(Character.isDigit(data[i])) {
intermediateResult[i] = data[i];
queue.add(Arrays.copyOf(intermediateResult, data.length));
} else {
char upperChar = uppercase.charAt(i);
char lowerChar = lowercase.charAt(i);
intermediateResult[i] = upperChar;
queue.add(Arrays.copyOf(intermediateResult, data.length));
intermediateResult[i] = lowerChar;
queue.add(Arrays.copyOf(intermediateResult, data.length));
}
}
}
}
int wordsFound = queue.size();
for (int i = 0; i < wordsFound; i++) {
System.out.println(queue.poll());
}
}
}
public List<String> getPermutation(String s) {
List<String> result = new ArrayList<String>();
getPermutation("", s, result);
return result;
}
private void getPermutation(String prefix, String suffix, List<String> result) {
if(suffix.length() == 0) {
result.add(prefix);
return;
}
char currChar = suffix.charAt(0);
String newSuffix = suffix.substring(1);
if(Character.isAlphabetic(currChar)) {
getPermutation(prefix + Character.toUpperCase(currChar), newSuffix, result);
getPermutation(prefix + Character.toLowerCase(currChar), newSuffix, result);
} else {
getPermutation(prefix + currChar, newSuffix, result);
}
}
public static void main(String[] args) {
System.out.println(getPermutation("a1b"));
}
private static List<String> getPermutation(String s) {
List<String> result = new ArrayList<String>();
getPermutation("", s, result);
return result;
}
private static void getPermutation(String prefix, String suffix, List<String> result) {
if(suffix.length() == 0) {
result.add(prefix);
return;
}
char currChar = suffix.charAt(0);
String newSuffix = suffix.substring(1);
if(Character.isAlphabetic(currChar)) {
getPermutation(prefix + Character.toUpperCase(currChar), newSuffix, result);
getPermutation(prefix + Character.toLowerCase(currChar), newSuffix, result);
} else {
getPermutation(prefix + currChar, newSuffix, result);
}
}
Or, without using prefix and suffix:
private static List<String> getPermutation(String s) {
List<String> result = new ArrayList<String>();
getPermutation(s, 0, result);
return result;
}
private static void getPermutation(String s, int i, List<String> result) {
if(s.length() == i) {
result.add(s);
return;
}
char currChar = s.charAt(i);
if(Character.isAlphabetic(currChar)) {
String newSUp = s.substring(0,i) + Character.toUpperCase(currChar) + s.substring(i+1,s.length());
String newSLow = s.substring(0,i) + Character.toLowerCase(currChar) + s.substring(i+1,s.length());
getPermutation(newSUp, i+1, result);
getPermutation(newSLow, i+1, result);
} else {
getPermutation(s, i+1, result);
}
}
Or without recursion
private static List<String> getPermutatuion(String s) {
List<String> result = new ArrayList<String>();
int len = s.length();
for(int i=0; i<len; i++) {
char currChar = s.charAt(i);
if(Character.isAlphabetic(currChar)) {
result.add(s.substring(0,i) + Character.toLowerCase(currChar) + s.substring(i+1,len));
result.add(s.substring(0,i) + Character.toUpperCase(currChar) + s.substring(i+1,len));
}
}
return result;
}
public List<String> getPermutatuion(String s) {
List<String> list = new ArrayList<String>();
List<String> tempList = new ArrayList<String>();
list.add(new String(s));
tempList.add(new String(s));
for(int i=s.length()-1; i>=0; i--) {
for(String str : tempList) {
char[] temp = Arrays.copyOf(str.toCharArray(), str.length());
temp[i] = (char)(temp[i]&'_');
list.add(new String(temp));
}
tempList.clear();
tempList.addAll(list);
}
return list;
}
public List<String> getPermutatuion(String s) {
List<String> list = new ArrayList<String>();
List<String> tempList = new ArrayList<String>();
list.add(new String(s));
tempList.add(new String(s));
for(int i=s.length()-1; i>=0; i--) {
for(String str : tempList) {
char[] temp = Arrays.copyOf(str.toCharArray(), str.length());
temp[i] = (char)(temp[i]&'_');
list.add(new String(temp));
}
tempList.clear();
tempList.addAll(list);
}
return list;
}
def get_permutations(s):
if s == "":
return [s]
ans= [s]
idx = 0
while idx != len(s):
if s[idx].isalpha():
#check if alphabet is lower
if s[idx].islower():
#change it to uppercase
new = s[idx].upper()
#if not, it will be upper case --> change it to lower
else:
new = s[idx].lower()
for i in range(len(ans)):
word = ans[i]
new_word = word[:idx] + new + word[idx+1:]
ans.append(new_word)
idx = idx + 1
else:
idx = idx + 1
return ans
s = "aB"
k = get_permutations(s)
print k
'''
Given a string, find all possible combinations of the upper
and lower case of each Alphabet char, keep the none Alphabet char as it is.
example1 s = "ab", return: "Ab", "ab", "aB", "AB"
example2 s = "a1b", return: "A1b", "a1b", "a1B", "A1B"
'''
import sys
def permute(input_str, result_str, result_list):
if not len(input_str):
result_list.append(result_str)
return
c = input_str[0]
if c.isalpha():
new_result_str = result_str + c
permute(input_str[1:], new_result_str, result_list)
if c.islower():
new_result_str = result_str + c.upper()
permute(input_str[1:], new_result_str, result_list)
else:
new_result_str = result_str + c.lower()
permute(input_str[1:], new_result_str, result_list)
else:
new_result_str = result_str + c
permute(input_str[1:], new_result_str, result_list)
def getPermutation(string):
result_list = []
result_str = ''
if not len(string):
return result_list
permute(string, result_str, result_list)
return result_list
def main():
example = 'ab'
permutaion_list = getPermutation(example)
print 'Permutations : ' + str(permutaion_list)
if __name__ == '__main__':
sys.exit(main())
- NoOne May 15, 2017/* What you want is cardinal product Given a string is c_0,c_1,c_2, .... We need a cardinal product of [lower(c_0),upper(c_0)] X [lower(c_1),upper(c_1)] X ... */ word = 'ab' // generate the options args = list( word.value ) as { [ str($.o).toLowerCase(), str($.o).toUpperCase() ] } // use the options for join - and map the tuple into a word by using str with seperator '' result = join( @ARGS = args ) as { str($.o,'') } println(result)