Yelp Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Same code with minor changes,
public static void printComb(String prefix,String str) {
if (str.length() == 0) {
System.out.println(prefix);
return;
}
if (Character.isAlphabetic(str.charAt(0))) {
printComb(prefix+str.substring(0,1).toLowerCase(),str.substring(1));
printComb(prefix+str.substring(0,1).toUpperCase(),str.substring(1));
}
else
printComb(prefix+str.substring(0,1),str.substring(1));
}
I have implemented the method to retrieve all the combinations of the given lower case String in both recursive and iterative way.
Iterative Algorithm:
- Keep a Set of String where you will have all the combinations
- Initially add the original String to the Set of combinations
- For each char from position 0 to position s.length-1 and for each String in the Set of combinations if this Char is a lowerCase Char add to the Set of combinations the String composed by replacing this lowerCase char with the correspondent upperCase Char. Add this new String to the Set of combinations.
public static Set<String> allCombs(String s) {
Set<String> combs = new HashSet<String>();
if(s==null || s.length()==0) {
return combs;
}
combs.add(s);
for(int i=0; i<s.length();i++) {
Set<String> newcombs = new HashSet<String>();
for(String comb: combs) {
if(Character.isLowerCase(comb.charAt(i))) {
newcombs.add(comb.substring(0,i)+Character.toUpperCase(comb.charAt(i))+comb.substring(i+1));
}
}
combs.addAll(newcombs);
}
return combs;
}
Recursive Algorithm:
- From pos 0 to s.length, if the current Char is lowerCase convert it to upperCase and attach it to all the combinations generated by the recursive call starting from pos+1; then also add the current Char (not converted) to all the combinations generated by the recursive call with pos+1; base case pos>=length, add the empty String to the Set.
public static List<String> allCombsRec(String s, int pos) {
List<String> combs = new ArrayList<String>();
if(s==null || s.length()==0) {
return combs;
}
if(pos>=s.length()) {
combs.add("");
return combs;
}
for(String srec: allCombsRec(s,pos+1)) {
if(Character.isLowerCase(s.charAt(pos))) {
combs.add(Character.toUpperCase(s.charAt(pos))+srec);
}
combs.add(s.charAt(pos)+srec);
}
return combs;
}
class Combination
{
static string input = "0a123b4525c";
static char[] arr = input.ToArray();
public static void mainFunc()
{
Rec(input.Length-1);
}
private static bool isNum(char c)
{
return c <= '9' && c >= '0';
}
private static void Rec(int ind)
{
if (ind == 0)
{
Console.WriteLine(arr);
if (!isNum(arr[0]))
{
arr[0] = char.ToUpper(arr[0]);
Console.WriteLine(arr);
arr[0] = char.ToLower(arr[0]);
}
return;
}
Rec(ind - 1);
if (!isNum(arr[ind]))
{
arr[ind] = char.ToUpper(arr[ind]);
Rec(ind - 1);
arr[ind] = char.ToLower(arr[ind]);
}
}
}
#include <string>
#include <iostream>
using namespace std;
void printAll(const string& str, string& prefix, int i) {
if( str.size() == prefix.size()) {
cout << str << endl;
}
else {
if( str[i] <= 'z' && str[i] >= 'a' ) {
prefix.push_back(str[i]);
printAll(str, prefix, i+1);
prefix.pop_back();
prefix.push_back(str[i]+'A'-'a');
printAll(str, prefix, i+1);
prefix.pop_back();
}
else {
prefix.push_back(str[i]);
printAll(str, prefix, i+1);
prefix.pop_back();
}
}
}
void printAll(const string& str) {
if( str.size() >0) {
string prefix;
printAll(str, prefix, 0);
}
}
void printAll(char *str, unsigned i){
unsigned int len = strlen(str);
if(i > len){
return;
}
printf("%s\t", str);
if((str[i] >= 'a') && (str[i] <= 'z')){
printAll(str, i+1);
str[i] += ('A' - 'a');
printAll(str, i+1);
}else if ((str[i] >= 'A') && (str[i] <= 'Z')){
printAll(str, i+1);
str[i] += ('a' - 'A');
printAll(str, i+1);
} else {
printAll(str, i+1);
}
}
void permutate2(char* str, int level, int n, char* res, int used[])
{
if(level==n)
{
//printf("now print\n");
res[level]='\0';
printf("%s\n", res);
}
else
{
for(int i=0;i<n;i++)
{
if(!used[i])
{
used[i]=1;
res[level]=str[i];
permutate2(str, level+1, n, res, used);
res[level]=str[i]=str[i]-32;
permutate2(str, level+1, n, res, used);
res[level]=str[i]=str[i]+32;
used[i]=0;
}
}
}
}
void permutate2(char* str, int level, int n, char* res, int used[])
{
if(level==n)
{
//printf("now print\n");
res[level]='\0';
printf("%s\n", res);
}
else
{
for(int i=0;i<n;i++)
{
if(!used[i])
{
used[i]=1;
res[level]=str[i];
permutate2(str, level+1, n, res, used);
res[level]=str[i]=str[i]-32;
permutate2(str, level+1, n, res, used);
res[level]=str[i]=str[i]+32;
used[i]=0;
}
}
}
}
public void convert(String str , int pos, int size){
if(size == pos){
System.out.println(str.toString());
return;
}else {
char [] partialStr = str.toCharArray();
if(Character.isDigit(partialStr[pos])){
convert(str,pos+1,size);
}else{
partialStr[pos] = Character.toUpperCase(partialStr[pos]);
str = String.valueOf(partialStr);
convert(str,pos+1,size);
partialStr[pos] = Character.toLowerCase(partialStr[pos]);
str = String.valueOf(partialStr);
convert(str,pos+1,size);
}
}
I used javascript using the binary representation to get the permutations:
function permute(s) {
var i,
ascii,
lookup = [],
n = 0;
// create a lookup array
for ( i = 0; i < s.length; i++) {
ascii = s.charCodeAt(i);
if ((ascii >= 65 && ascii <= 90) || (ascii >= 97 && ascii <= 122)) {
lookup.push(i);
}
}
// calculate the max integer needed for this operation 2 ^ n
maxN = Math.pow(2, lookup.length);
// start iterating with the integer
while (n < maxN) {
printUpperCase(s, n, lookup);
n++;
};
}
function printUpperCase(s, n , lookup) {
var index = 0;
do {
if (n & 1) {
s = s.toUpperAt(lookup[index]);
}
index++;
} while (n >>= 1)
console.log(s);
}
String.prototype.toUpperAt = function (index) {
var c = this.charAt(index).toUpperCase();
return this.substr(0, index) + c + this.substr(index + 1);
}
I used python to code.
def print_word_permute(word):
n = len(word)
permute_word("", word)
def permute_word(prefix, left):
n = len(left)
if (n == 0):
print prefix
return
for i in range(0, n):
if left[i].isalpha() == True:
permute_word(prefix + left[:i]+left[i].upper() , left[i+1:])
permute_word(prefix + left[:i]+left[i], left[i+1:])
break
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.Arrays;
public class GenerateAllCaseCombination {
public static void main(String args[]){
String inputStr = "0ab";
List<String> lowCaselist = new ArrayList();
List<String> upCaselist = new ArrayList();
List<String> combiList = new ArrayList();
StringBuffer s = new StringBuffer();
String sorted = "";
combiList.add(inputStr);
for(int i=0;i<inputStr.length();i++){
char c = inputStr.charAt(i);
Pattern pn = Pattern.compile("[0-9]");
Matcher mNum = pn.matcher(inputStr.valueOf(c));
if(mNum.find()){
s.append(inputStr.valueOf(c));
}else{
lowCaselist.add(inputStr.valueOf(c));
upCaselist.add(inputStr.valueOf(c).toUpperCase());
}
}
for(int i=0;i<lowCaselist.size();i++){
String concatedStr = "";
String lowcase = lowCaselist.get(i);
for(int j=upCaselist.size()-1;j>=0;j--){
String upcase = upCaselist.get(j);
if(!(lowcase.toUpperCase().equals(upcase))){
concatedStr=s.toString()+lowcase+upcase;
char[] chars = concatedStr.toCharArray();
Arrays.sort(chars);
sorted = new String(chars);
System.out.println("sorted::"+sorted);
}
}
combiList.add(sorted);
}
combiList.add(inputStr.toUpperCase());
System.out.println("AllCaseCombination for the given I/P String ::"+combiList.toString());
}
}
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.Arrays;
public class GenerateAllCaseCombination {
public static void main(String args[]){
String inputStr = "0ab";
List<String> lowCaselist = new ArrayList();
List<String> upCaselist = new ArrayList();
List<String> combiList = new ArrayList();
StringBuffer s = new StringBuffer();
combiList.add(inputStr);
for(int i=0;i<inputStr.length();i++){
char c = inputStr.charAt(i);
Pattern pn = Pattern.compile("[0-9]");
Matcher mNum = pn.matcher(inputStr.valueOf(c));
if(mNum.find()){
s.append(inputStr.valueOf(c));
}else{
lowCaselist.add(inputStr.valueOf(c));
upCaselist.add(inputStr.valueOf(c).toUpperCase());
}
}
for(int i=0;i<lowCaselist.size();i++){
String concatedStr = "";
String lowcase = lowCaselist.get(i);
for(int j=upCaselist.size()-1;j>=0;j--){
String upcase = upCaselist.get(j);
if(!(lowcase.toUpperCase().equals(upcase))){
concatedStr=s.toString()+lowcase+upcase;
}
}
combiList.add(concatedStr);
}
combiList.add(inputStr.toUpperCase());
System.out.println("AllCaseCombination for the given I/P String ::"+combiList.toString());
}
}
I would prefer do it using recursion
#include<iostream>
#include<vector>
#include<stack>
#include<map>
using namespace std;
void printString(string s, int i){
if(i == s.length()){
cout<<s<<endl;
return;
}
if(s[i] >= '0' && s[i] <= '9'){
printString(s, i + 1);
}else{
printString(s, i + 1);
if(s[i] >= 'A' && s[i] <= 'Z'){
s[i] = s[i] + 0x20;
printString(s, i + 1);
}else{
s[i] = s[i] - 0x20;
printString(s, i + 1);
}
}
}
int main(){
string s = "0ab";
printString(s, 0);
return 0;
}
Here is a recursive solution in C#
permutation(empty, input);
Console.Read();
static void permutation(string soFar, string remaining)
{
int n = remaining.Length;
if (n == 0)
{
Console.WriteLine(soFar);
return;
}
else
{
int index = 0;
while(Char.IsNumber(remaining[index]))
{
//remove each digit and add to soFar
soFar += remaining[index];
remaining =remaining.Substring(1, remaining.Length - 1);
index++;
}
permutation(soFar + Char.ToUpper(remaining[0]), remaining.Substring(1, remaining.Length - 1));
permutation(soFar + Char.ToLower(remaining[0]), remaining.Substring(1, remaining.Length - 1));
}
}
char []a = next().toCharArray();
int yk = 0;
int index[] = new int[a.length];
for(int i=0;i<a.length;i++) {
char c = a[i];
if (c >= '0' && c <='9') continue;
index[yk++] = i;
}
for(int mask = 0; mask < (1<<yk);mask++){
char []c = (char[])a.clone();
for(int i=0;i<yk;i++){
if ((mask & (1<<i)) > 0) {
c[index[i]] = Character.toUpperCase(c[index[i]]);
}
}
System.out.println(new String(c));
}
Did it in python using a binary tree and traversing it recursively with depth first search.
class Node:
def __init__(self,val,next):
self._val = val
self._next = next
def setVal(self, val):
self._val = val
def getVal(self):
return self._val
def setNext(self, next):
self._next = next
def getNext(self):
return self._next
def allPossiCaseCombos(str):
curr = Node(0,None)
root = Node(0,curr)
l = []
for c in str:
if c.isnumeric():
curr.setNext(Node(c, None))
else:
l.append(Node(c,None))
if c.istitle():
l.append(Node(c.lower(),None))
else:
l.append(Node(c.upper(),None))
curr.setNext(Node(l,None))
l = []
curr = curr.getNext()
return root
curr = allPossiCaseCombos("ab6cd").getNext().getNext()
def go(curr,str):
if curr.getNext() == None:
if isinstance(curr.getVal(),list):
for n in curr.getVal():
print(str+n.getVal())
else:
print(str+curr.getVal())
return
if isinstance(curr.getVal(),list):
for n in curr.getVal():
go(curr.getNext(),str+n.getVal())
else:
go(curr.getNext(),str+curr.getVal())
go(curr,"")
Using a bit vector.then dfs.
#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;
class Solution{
public:
vector<string> GenerateCase(string &str)
{
set<string>result;
if (str.length() == 0)return vector<string>();
this->selected=vector<int>(str.size(), 0);
string cur;
dfs(result, cur, 0, str);
return vector<string>(result.begin(),result.end());
}
private:
vector<int>selected;
void dfs(set<string>&result, string &cur, int start, string &str)
{
const int m = str.length();
if (start == m){
string sub;
for (int i = 0; i < m; i++)
{
if (isdigit(str[i])||!selected[i])
sub.push_back(str[i]);
else if (selected[i])
sub.push_back(str[i] ^ 32);
}
result.insert(result.begin(), sub);
return;
}
selected[start] = 0;
dfs(result, cur, start + 1, str);
selected[start] = 1;
dfs(result, cur, start + 1, str);
}
};
void print(vector<string>&result)
{
for (auto& i : result) {
cout << i << endl;
}
}
int main()
{
Solution s;
string str = "0ab";
vector<string>result = s.GenerateCase(str);
print(result);
return 0;
}
std::vector<std::string> generate(std::string& s)
{
char c = s[0];
std::vector<std::string> v;
std::string s1;
s1 += c;
std::string s2;
s2 += (c + 'A' - 'a');
if (s.length() == 1)
{
if (atoz(c))
{
v.push_back(s1);
v.push_back(s2);
}
else
{
v.push_back(s1);
}
return v;
}
std::vector<std::string>& v2 = generate(s.substr(1));
if (atoz(c))
{
for (int i = 0; i < v2.size(); ++i)
{
v.push_back(s1 + v2[i]);
v.push_back(s2 + v2[i]);
}
}
else
{
for (int i = 0; i < v2.size(); ++i)
{
v.push_back(s1 + v2[i]);
}
}
return v;
}
#include <iostream>
#include <string>
#include <locale> //for upper and lower
#include <set> //remove duplicates
void allUpperLowerCombinations(std::string& s, int cur, std::set<std::string>& str_set) {
std::locale loc;
if(cur == s.length()) { //reached the end, insert to set
str_set.insert(s);
}
else {
s[cur] = std::toupper(s[cur], loc);
allUpperLowerCombinations(s, cur + 1, str_set);
s[cur] = std::tolower(s[cur], loc);
allUpperLowerCombinations(s, cur + 1, str_set);
}
}
int main() {
std::set<std::string> string_set;
std::string message("0bc");
allUpperLowerCombinations(message, 0, string_set);
for(const std::string& s : string_set) {
std::cout << s << std::endl;
}
#include <iostream>
#include <string>
#include <locale> //to upper and lower
#include <set> //remove duplicates
void allUpperLowerCombinations(std::string& s, int cur, std::set<std::string>& str_set) {
std::locale loc;
if(cur == s.length()) {
str_set.insert(s);
//std::cout << s << std::endl;
}
else {
s[cur] = std::toupper(s[cur], loc);
allUpperLowerCombinations(s, cur + 1, str_set);
s[cur] = std::tolower(s[cur], loc);
allUpperLowerCombinations(s, cur + 1, str_set);
}
}
int main() {
std::set<std::string> string_set;
std::string message("0bc");
allUpperLowerCombinations(message, 0, string_set);
for(const std::string& s : string_set) {
std::cout << s << std::endl;
}
Description:
1. Find the indexes of all the 'letters' in the given string and only iterate over that, than the entire string, because u may have a string "557747373447abc4757838383", that'll save you added complexity.
2. Use 2 data structures, a Queue and a HashSet.
3. Queue will help you find more combinations, HashSet will help in finding if the combination has been reached before.
4. For each added element in Queue, remove it and make more combinations.
5. This solution also works for already uppercase string like "4AbD2f" as well as duplicates like "3bb"
public static void combinations()
{
String s = "000000abde0000";
//Boundary check 1, checks for string length
if(s.length() == 0)
{
System.out.println("String length too small");
return;
}
//Boundary check 2, checks if there are more than 0 'characters'
int count=0;
//Maintain an arraylist of indexes for characters, so we do not iterate over digits
//in cases like huge string with many digits and less characters
List<Integer> indexes = new ArrayList<Integer>();
for(int i = 0 ; i < s.length() ; i++)
{
if(Character.isLetter(s.charAt(i)))
{
count++;
indexes.add(i);
}
}
System.out.println(indexes);
if(count == 0)
{
System.out.println("No Combinations can be made");
return;
}
//Queue to scan elements over again
Queue<String> q = new LinkedList<>();
//Add the given string to hashset
Set<String> comb = new HashSet<String>();
comb.add(s);
q.add(s);
//Boundary check 3, checks if given string had any uppercases
s = s.toLowerCase();
if(!comb.contains(s))
{
comb.add(s);
q.add(s); //Any new combination must be added to the queue to check for more
}
String temp,lastGood;
Character c;
int iterCount = 0;
while(!q.isEmpty())
{
//Start with the first combination in the queue
temp = q.remove();
for(int i : indexes)//iterate over indexes we found than the entire string
{
iterCount++;
lastGood = temp; //copy of the original string
c = temp.charAt(i);
if(Character.isLowerCase(c))
{
temp = temp.substring(0, i) + Character.toUpperCase(c)+ temp.substring(i+1);
}
else
{
temp = temp.substring(0, i) + Character.toLowerCase(c)+ temp.substring(i+1);
}
//If the change just made is unique, add to the Set and Queue
if(!comb.contains(temp))
{
//System.out.println("Adding: " + temp + " to comb!"); //for debugging
comb.add(temp);
q.add(temp);
}
//restore lastGood and start over
temp = lastGood;
}
}
if(comb.size() == (Math.pow(2, count)))
{
System.out.println("All("+Math.pow(2, count)+") combinations have been found, over "+ iterCount + " loops!");
System.out.println(comb);
}
else
{
System.out.println("Something went wrong!");
System.out.println(comb);
}
}
I'm not yet sure how it works complexity wise, but looks like it's somewhere between n^(n-1), please help out here if you have an answer. Thank you!
- bindaas March 25, 2014