Facebook Interview Question SDE1s
Country: United States
Efficient algorithm which works for any input size.
Time efficient because of use of bit shift.
Thanks to Stackoverflow for the awesome trick!
/*
* Asked in Facebook.
*
* Problem: Permute the String including case
*
* For example: "abc" = > abc, ABC, Abc, aBc, abC, ABc, abC, AbC
*
* Solution: If N be the string length of input then there exists 2^N maximum combinations
*
* Represent this as a bitwise operation of size input.length() which is 3
*
* 0 0 0 => 0
* 1 0 0 => Convert 0th char to upper case
* 1 1 0 => Convert 0, 1 char to upper case and so on
*
*/
public class PermuteCasewise
{
public void generatePermute(String input)
{
int max = 1 << input.length();
for(int i=0; i<max; i++)
{
input = input.toLowerCase();
char [] combination = input.toCharArray();
for(int j=0; j<input.length(); j++)
{
if( ((i >> j) & 1) == 1 )
combination[j] = Character.toUpperCase(input.charAt(j));
}
System.out.println(String.valueOf(combination));
}
}
public static void main(String[] args)
{
PermuteCasewise obj = new PermuteCasewise();
obj.generatePermute("aBc");
}
}
void permut(string s, int l, int r) {
if(l == r) {
cout << s << endl;
return;
}
for(int i = l; i <= r; i++) {
swap(s[i], s [l]);
permut(s, l+1, r);
swap(s[i], s [l]);
if(islower(s[i])) {
s[i] = s[i] - 'a' + 'A';
permut(s, l+1, r);
s[i] = s[i] - 'A' + 'a';
} else {
s[i] = s[i] - 'A' + 'a';
}
}
}
const createTree = (characters, numFixed = 0) => {
if (numFixed === characters.length) {
return console.log(characters);
}
characters.slice(numFixed, characters.length).map((character, index) => {
if (characters.length >= numFixed + index) {
const swappedArr = swapChars(numFixed, numFixed + index, characters);
const capitalizedArr = capitalizeIndex(numFixed, swappedArr);
createTree(swappedArr, numFixed + 1);
createTree(capitalizedArr, numFixed + 1);
}
});
};
const createTree = (characters, numFixed = 0) => {
if (numFixed === characters.length) {
return console.log(characters);
}
characters.slice(numFixed, characters.length).map((character, index) => {
if (characters.length >= numFixed + index) {
const swappedArr = swapChars(numFixed, numFixed + index, characters);
const capitalizedArr = capitalizeIndex(numFixed, swappedArr);
createTree(swappedArr, numFixed + 1);
createTree(capitalizedArr, numFixed + 1);
}
});
};
Solution *without* recursion
Disclaimer: Only works if string length is less than 32
public static void main(String[] args) {
String[] perms = permuteBinary("abc");
for(String perm : perms)
System.out.println(perm);
}
private static String[] permuteBinary(String given) {
given = given.toLowerCase();
int numPerms = 1 << given.length();
String[] result = new String[numPerms];
for(int i=0; i < numPerms; i++) {
result[i] = buildPerm(given, i);
}
return result;
}
private static String buildPerm(String original, int bitPositions) {
int k = bitPositions;
char[] result = original.toCharArray();
for(int i=0; i < original.length(); i++) {
if ((k&1) == 1)
result[i] = Character.toUpperCase(result[i]);
k = k >> 1;
}
return new String(result);
}
Solution *without* recursion.
Note: this only works if the given string is less than 32 characters long.
Step 1: Calculate the number of permutations. Basically, each character can have two states, either lower case or upper case. Hence total permutations = 2^n, where n = length of given string
Step 2: Iterate through 1 to 2^n. Each of these numbers represents one possible permutation. For example, 000 means all chars are lower, abc. 010 means aBc, 001 means abC, and so on.
public static void main(String[] args) {
String[] perms = permuteBinary("abc");
for(String perm : perms)
System.out.println(perm);
}
private static String[] permuteBinary(String given) {
given = given.toLowerCase();
int numPerms = 1 << given.length();
String[] result = new String[numPerms];
for(int i=0; i < numPerms; i++) {
result[i] = buildPerm(given, i);
}
return result;
}
private static String buildPerm(String original, int bitPositions) {
int k = bitPositions;
char[] result = original.toCharArray();
for(int i=0; i < original.length(); i++) {
if ((k&1) == 1)
result[i] = Character.toUpperCase(result[i]);
k = k >> 1;
}
return new String(result);
}
JavaScript solution
function addLetter(letter, combos) {
var newArray = [];
if (combos.length === 0) {
newArray = [letter.toLowerCase(), letter.toUpperCase()];
}
else {
for ( var i=0, len=combos.length; i<len; i++ ) {
newArray.push(combos[i] + letter.toLowerCase());
newArray.push(combos[i] + letter.toUpperCase());
}
}
return newArray;
}
function getCombos(str) {
var letters = str.split('');
var combos = [];
if (str.length === 0) {
console.error('Empty string');
}
else {
for (var i=0, len=str.length; i<len; i++) {
combos = addLetter(letters[i], combos);
}
return combos;
}
}
console.log(getCombos('abc'));
Here’s one way to do it in JS:
function addLetter(letter, combos) {
var newArray = [];
if (combos.length === 0) {
newArray = [letter.toLowerCase(), letter.toUpperCase()];
}
else {
for ( var i=0, len=combos.length; i<len; i++ ) {
newArray.push(combos[i] + letter.toLowerCase());
newArray.push(combos[i] + letter.toUpperCase());
}
}
return newArray;
}
function getCombos(str) {
var letters = str.split('');
var combos = [];
if (str.length === 0) {
console.error('Empty string');
}
else {
for (var i=0, len=str.length; i<len; i++) {
combos = addLetter(letters[i], combos);
}
return combos;
}
}
console.log(getCombos('abc'));
{{
input="abc"
from itertools import product
bin_list = ["".join(seq) for seq in product("01", repeat=len(input))]
output_list = [input for n in range(len(bin_list))]
print(output_list)
for bin, item in zip(bin_list, output_list):
result = ""
for bin_index in range(len(bin)):
if bin[bin_index] == '1':
result += item[bin_index].lower()
else:
result += item[bin_index].upper()
print(result)
}}
In javascript
const str = "abc";
function getPerm(s) {
const max = Math.pow(2,s.length);
for (let x = 0 ; x < max ; x++) {
const perm = x.toString(2);
const fullPerm = "000".substring(perm.length) + perm;
let currentStr = str.split('').map((v,k) => fullPerm[k]==1?v.toUpperCase():v).join('');
console.log(currentStr);
}
}
getPerm(str);
In javascript
const str = "abc";
function getPerm(s) {
const max = Math.pow(2,s.length);
for (let x = 0 ; x < max ; x++) {
const perm = x.toString(2);
const fullPerm = "000".substring(perm.length) + perm;
let currentStr = str.split('').map((v,k) => fullPerm[k]==1?v.toUpperCase():v).join('');
console.log(currentStr);
}
}
getPerm(str);
In javascriptconst
str = "abc";
function getPerm(s) {
const max = Math.pow(2,s.length);
for (let x = 0 ; x < max ; x++) {
const perm = x.toString(2);
const fullPerm = "000".substring(perm.length) + perm;
let currentStr = str.split('').map((v,k) => fullPerm[k]==1?v.toUpperCase():v).join('');
console.log(currentStr);
}
}
getPerm(str);
In javascript
const str = "abc";
function getPerm(s) {
const max = Math.pow(2,s.length);
for (let x = 0 ; x < max ; x++) {
const perm = x.toString(2);
const fullPerm = "000".substring(perm.length) + perm;
let currentStr = str.split('').map((v,k) => fullPerm[k]==1?v.toUpperCase():v).join('');
console.log(currentStr);
}
}
getPerm(str);
const str = "abc";
function getPerm(s) {
const max = Math.pow(2,s.length);
for (let x = 0 ; x < max ; x++) {
const perm = x.toString(2);
const fullPerm = "000".substring(perm.length) + perm;
let currentStr = str.split('').map((v,k) => fullPerm[k]==1?v.toUpperCase():v).join('');
console.log(currentStr);
}
}
getPerm(str);
#!/usr/bin/perl
use strict;
use warnings;
# permute the String including case change
# "abc".
#
# For example:
#
# abc
# ABC
# Abc
# aBc
# abC
# ABc
# abC
# AbC
#
# - ajay.raj July 14, 2017 in United States | Report Duplicate | Flag
sub swap_case {
my $c=shift;
if ( $c ge 'a' && $c le 'z' ) {
return uc($c); }
if ( $c ge 'A' && $c le 'Z' ) {
return lc($c); }
}
sub permute{
my %args=@_;
my $string = $args{string};
my $index = $args{index};
if ( $index >= length($string) ) { print $string . "\n"; return ; }
&permute( string => $string , index => $index+1 );
my @char_array = split // , $string;
$char_array[$index]=&swap_case($char_array[$index]);
&permute( string => join('', @char_array), index => $index + 1 );
}
print &permute(string => $ARGV[0], index => 0);
In perl using recursion
#!/usr/bin/perl
use strict;
use warnings;
# permute the String including case change
# "abc".
#
# For example:
#
# abc
# ABC
# Abc
# aBc
# abC
# ABc
# abC
# AbC
#
# - ajay.raj July 14, 2017 in United States | Report Duplicate | Flag
sub swap_case {
my $c=shift;
if ( $c ge 'a' && $c le 'z' ) {
return uc($c); }
if ( $c ge 'A' && $c le 'Z' ) {
return lc($c); }
}
sub permute{
my %args=@_;
my $string = $args{string};
my $index = $args{index};
if ( $index >= length($string) ) { print $string . "\n"; return ; }
&permute( string => $string , index => $index+1 );
my @char_array = split // , $string;
$char_array[$index]=&swap_case($char_array[$index]);
&permute( string => join('', @char_array), index => $index + 1 );
}
print &permute(string => $ARGV[0], index => 0);
Assumption for simplicity:
1) every letter is used at most once in the upper cased input string
"AaB" wouldn't be a valid input, "AbC" is ok
2) input string is a mix of lower and upper case letters (no numbers, etc.)
do permutations by swaping elements in a recursion:
recursion(string, pos) = string is a permutation, if pos = 0
recurse(swap(string, pos, j), pos - 1),
for j = pos - 1 to 0
swap(string, i, j): creates a new string that is equal to string with
characters at position i and j exchanged.
the recursion tree would look like this:
pos = 2 "ABC"
------------------------------------
/ | \
pos = 1 "ABC" "BAC" "CBA"
------ ------ ------
/ \ / \ / \
pos = 0 "ABC" "ACB" "BAC" "BCA" "CBA" "CAB"
now, adding the upper / lower case is just similar, the recursion then
is:
recursion(string, pos) = string is a permutation, if pos = 0
recurse(swap(string, pos, j), pos - 1),
for j = pos - 1 to 0
recurse(swap_lower(string, pos, j))
for j = pos - 1 to 0
swap_lower is like swap, but it will convert the character that is
placed at position pos to lowe case
it asumes the input string is all upper case
this is O(n!*2^n), where n is the length of the string or other way
to think of, there are n! permutations and for each of this every
letter can be upper or lower case, so another 2^n
'''
in python 3
def permutation_case(input):
def aux(i):
if i == n:
print(''.join(map(lambda x: chr(x), input_a)))
else:
for j in range(i, n):
# swap to get a changing prefix and recurse
input_a[i], input_a[j] = input_a[j], input_a[i]
aux(i + 1)
# change upper, lower case of the just swaped element in prefix and recurse
temp = input_a[i]
input_a[i] = input_a[i] + (ord('a') - ord('A'))
aux(i + 1)
# set the old 'string' back
input_a[i], input_a[j] = input_a[j], temp
n = len(input)
input_a = bytearray(input, 'ascii').upper()
aux(0)
permutation_case('aBc')
Solution in python, no recursion
- Fernando July 15, 2017