## Facebook Interview Question for SDE1s

Country: United States

Comment hidden because of low score. Click to expand.
2
of 2 vote

Solution in python, no recursion

``````def compute_combinations(s):
res = ['']
for c in s:
res = [x + c.lower() for x in res] + [x + c.upper() for x in res]
return res``````

Comment hidden because of low score. Click to expand.
2
of 2 vote

Efficient algorithm which works for any input size.
Time efficient because of use of bit shift.

Thanks to Stackoverflow for the awesome trick!

``````/*
*
* 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");
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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';
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
});
};

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
});
};``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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++) {
}

return combos;
}
}

console.log(getCombos('abc'));``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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++) {
}

return combos;
}
}

console.log(getCombos('abc'));``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
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)
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void permuteLowerCase(char[] val, int l, int h) {
if (l == h) {
System.out.println(val);
return;
}
for (int i = l; i < h; i++) {
val[i] = Character.toLowerCase(val[i]);
permuteLowerCase(val, l + 1, h);
val[i] = Character.toUpperCase(val[i]);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#!/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);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def combinations(string, result='', index=0):
if index >= len(string):
print result
return

combinations(string, result + string[index].lower(), index+1)
combinations(string, result + string[index].upper(), index+1)

if __name__ == '__main__':
combinations('abc')``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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')``````

Comment hidden because of low score. Click to expand.
0

Chris, the original question seems to suggest *only* all possible combinations of lower case and upper case, *without* changing the order of characters.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.