## Yelp Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

``````private void printAllCombinations(String A,String B){
if(B.length()==0){
System.out.println(A);
return;
}
int i =0;
char c = B.charAt(i++);
while(!Character.isLetter(c)){
A+=c;
c = B.charAt(i++);
}
printAllCombinations(A + Character.toLowerCase(c), B.substring(i));
printAllCombinations(A + Character.toUpperCase(c), B.substring(i));
}``````

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

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

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

@bind ass, please try to put explanations instead of just pasting code.

kthxbye.

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

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;
}
for(int i=0; i<s.length();i++) {
Set<String> newcombs = new HashSet<String>();
for(String comb: combs) {
if(Character.isLowerCase(comb.charAt(i))) {
}
}
}
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()) {
return combs;
}
for(String srec: allCombsRec(s,pos+1)) {
if(Character.isLowerCase(s.charAt(pos))) {
}
}
return combs;
}``````

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

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

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

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

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

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

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

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

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

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

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

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

}

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

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

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

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

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

``````def permute(s, r, idx):
if len(r) == len(s):
print r
else:
if s[idx].islower():
permute(s, r + s[idx].upper(), idx+1)
permute(s, r + s[idx], idx+1)``````

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

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 = "";
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{
}
}
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);
}
}
}
System.out.println("AllCaseCombination for the given I/P String ::"+combiList.toString());
}
}

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

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();
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{
}
}
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;
}
}
}
System.out.println("AllCaseCombination for the given I/P String ::"+combiList.toString());
}
}

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

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

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

Here is a recursive solution in C#

``````permutation(empty, input);

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

}

}``````

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

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

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

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

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,"")``````

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

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

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

ur codes b too long, b

``````import itertools

def genCombo(strinput):
strinput = list(strinput)
combos = []
for i in strinput:
try:
i = int(i)
combos.append((str(i),))
except:
combos.append((i.lower(), i.upper()))

return list(itertools.product(*combos))``````

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

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

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

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

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

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

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

``````input_s = "abcdef"

def print_p(index, length, string, seg):
if(index == length):
print seg
else:
segu = seg + string[index].upper()
segl = seg + string[index].lower()
index += 1
print_p(index, length, string, segu)
print_p(index, length, string, segl)

print_p(0,len(input_s),input_s,"")``````

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

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

}
System.out.println(indexes);

if(count == 0)
{
return;
}

//Queue to scan elements over again

//Add the given string to hashset
Set<String> comb = new HashSet<String>();

//Boundary check 3, checks if given string had any uppercases
s = s.toLowerCase();
if(!comb.contains(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())
{
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
}
//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!

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

``````function generate(str) {
var r = [];
for (let i in str) {
if (parseInt(str[i]) != str[i]) {
r.push(str.substring(0, i)+str[i].toUpperCase()+str.substring(parseInt(i)+1));
}
}
return r;
}``````

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.