Microsoft Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
Using Recursion should yield the required answer
#include<ctype.h>
#include<stdio.h>
#include<string.h>
#include<assert.h>
void toggler(char* x, int pos){
if(pos==0){ printf("%s\n",x); return; }
// printf("String is now: %s\n",x);
x[pos-1] = toupper(x[pos-1]);
toggler(x, pos-1);
x[pos-1] = tolower(x[pos-1]);
toggler(x, pos-1);
return;
}
int main(void){
char str[500];
scanf("%s",str);
toggler(str, strlen(str));
return 0;
}
Java Implementation based on this approach. Will also work if the string has numbers
public class CaseCombination {
char[] str;
public CaseCombination(char[] str){
this.str = str;
}
public static void main(String[] args){
System.out.println("Enter the string");
Scanner input = new Scanner(System.in);
String str = input.nextLine();
input.close();
CaseCombination thisObj = new CaseCombination(str.toCharArray());
printCases(thisObj, thisObj.str.length);
}
private static void printCases(CaseCombination obj, int index){
if(index == 0){
System.out.println(obj.str);
return;
}
if(Character.isAlphabetic(obj.str[index - 1])){
obj.str[index - 1] = Character.toUpperCase(obj.str[index - 1]);
printCases(obj, index-1);
obj.str[index - 1] = Character.toLowerCase(obj.str[index - 1]);
printCases(obj, index-1);
} else {
printCases(obj, index-1); // if this char is digit just recurse without generating upper and lower case
}
return;
}
}
public class PrintCases {
public static void main(String[] args) {
String word = "THE";
print(word, "", word.length());
}
public static void print(String str, String result, int length) {
if (result.length() == length) {
System.out.println(result);
} else {
int switchCase = (str.charAt(0) > 'a' ? 32 : -32);
print(str.substring(1), result + str.charAt(0), length);
print(str.substring(1), result + (char) ((int) str.charAt(0) - switchCase), length);
}
}
}
#include <iostream>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
using namespace std;
#define LOWER 0
#define UPPER 1
#define SIZE 100
void generate(char *s)
{
int strLength = strlen(s);
unsigned long maxValue = pow((double)2, strLength) - 1;
for(int generator = 0; generator <= maxValue; generator++)
{
int i, j;
bitset<SIZE> map(generator);
i = strLength - 1;
for(j = 0; s[j] != '\0' ; i--, j++)
{
char c;
if(map[i] == LOWER)
c = tolower(s[j]);
else
c = toupper(s[j]);
cout << c;
}
cout << endl;
}
}
#include <iostream>
#include <cctype>
#include <cstring>
using namespace std;
void generateRec(char *s, int pos, int len)
{
if(pos >= len)
{
cout << s << endl;
return;
}
s[pos] = tolower(s[pos]);
generateRec(s, pos+1, len);
s[pos] = toupper(s[pos]);
generateRec(s, pos+1, len);
}
int main(void)
{
char str[] = "THE";
generateRec(str, 0, strlen(str));
return 0;
}
Using The truth table ideal. For example if we have the word "the" it corresponds to 3 bits. So the possible combinations are ranging from 000 -- 111. Where 000 is case0 and 111 is case7. Note that in number in the computer is represented inside the computer as binary. So, if we have num = 3. i.e., num = 0011. I will use some shifting and masking operations to do the task.
C# code
-------------
using System;
using System.Collections.Generic;
using System.Text;
namespace StringSmallCap
{
class Program
{
static void PrintCase(string str, int num)
{
int index = str.Length - 1;
char[] charArr = str.ToCharArray();
while(num != 0)
{
if ((num & 0x00000001) != 0)
charArr[index] = char.ToUpper(charArr[index]);
num >>= 1;
index--;
}
Console.WriteLine(charArr);
}
static void Main(string[] args)
{
Console.Write("Word: ");
string word = (Console.ReadLine()).ToLower();
Console.WriteLine(word);
for (int caseNum = 1; caseNum < Math.Pow(2,word.Length); caseNum++)
{
PrintCase(word, caseNum);
}
}
}
}
using System;
using System.Collections.Generic;
using System.Text;
namespace StringSmallCap
{
class Program
{
static void PrintCase(string str, int num)
{
int index = str.Length - 1;
char[] charArr = str.ToCharArray();
do
{
if ((num & 0x00000001) != 0)
charArr[index] = char.ToUpper(charArr[index]);
index--;
}
while ((num >>= 1) != 0);
Console.WriteLine(charArr);
}
static void Main(string[] args)
{
Console.Write("Word: ");
string word = (Console.ReadLine()).ToLower();
Console.WriteLine(word);
for (int caseNum = 1; caseNum < Math.Pow(2,word.Length); caseNum++)
{
PrintCase(word, caseNum);
}
}
}
}
Hi,
Is there a way we can avoid recomputation of same substring again? Say the original string is 'the'.
Now we take two versions of t i.e. 't' and 'T' and append to it the result obtained with string being 'he'. Here we are computing for the same substring again.
Can memoization (as in Dynamic programming) be of some help?
TRY THIS ONE :)
JUST THE MODIFICATION REQUIRED IN TH ESUBSET PROBLEM :)
#include<string.h>
#include<stdio.h>
int main(int argc,char *argv[])
{
void possible(char str[],int n,int i,char net[]);
char st[100];
char net[100];
int n;
gets(st);
n=strlen(st);
possible(st,n,0,net);
return 0;
}
void possible(char *str,int n,int i,char *net)
{
if(i==n)
{
puts(net);
return;
}
net[i]=str[i];
possible(str,n,i+1,net);
net[i]=str[i]+'a'-'A';
possible(str,n,i+1,net);
}
#include <cstdlib>
#include <cmath>
#include <iostream>
using namespace std;
//TASK print all combinations of upper/lowercase letters
int PrintAll(const char *s, int size)
{
if (!s) return 0; // nothing to print
if (size < 1) return 0; // nothing to print
if (size > 31) return 0; // too much to print, does not fit in x86 int
// also, why are we printing 4 billion strings?
// perhaps management should think this through
// before deciding to print
int max = pow(2.0, size);
// or int max = 1<<size;
for (int i=0; i<max; i++)
{
int tmp = i;
for (int j=0; j<size; j++)
{
if (tmp&0x1)//potentially depends on 1-byte addressable memory
{
putchar(toupper(s[j]));
}
else
{
putchar(tolower(s[j]));
}
tmp = tmp>>1;//divide by two -- bit-shift 1 bit
}
printf("\n");
}
}
int main(int argc, char *argv[])
{
const char* b = "FOOBAR";
PrintAll(b, strlen(b));
system("PAUSE");
return EXIT_SUCCESS;
}
#include <iostream>
#include <string>
#include <vector>
std::vector <std::vector<char>>myChars(26,2);
void makeCombination(const std::string &str, int index,const int &length, std::string combination){
if(index == length){
std::cout << combination <<std::endl;
return ;
}
for(int i = 0; i < myChars[str[index] - 'a'].size(); ++i){
makeCombination(str,index + 1, length,combination + myChars[str[index] - 'a'][i]);
}
}
void makeCombinationsAux(const std::string & str){
std::string temp = str;
for(int i = 0; i < str.length(); ++i){
if(str[i] <= 90){
temp[i] = str[i] + 32;
}
}
std::string combination = "";
makeCombination(temp,0,temp.length(),combination);
}
int main(){
for(int i = 0; i < myChars.size(); ++i ){
myChars[i][0] = 'A' + i;
myChars[i][1] = 'a' + i;
}
std::string str = "The";
makeCombinationsAux(str);
std::cin.get();
return 0;
}
int main()
{
// String to be printed in upper and lower case permutation and combination.
// Asuming input is always lower case.
char strarr[] = "the";
int strlen = 0;
char* tempstr = strarr;
// Calculating the length of the string.
while (*tempstr != '\0')
{
strlen++;
tempstr++;
}
// Calculating the number of permutation = strlen^2 - 1.
int num_comb = strlen * strlen -1;
// Calculating the difference between upper and lower case characters ASCII value.
int diff = (int)'a' - (int)'A';
for (int r = 0; r < num_comb; r++)
{
for (int l = 0; l < strlen; l++)
{
// Checking if the bit is set, if set then upper case.
if (r & 1 << l)
{
printf("%c", ((int)strarr[l] - diff));
}
else
{
printf("%c", strarr[l]);
}
}
printf("\n");
}
return 0;
}
Idea is very Simple,We can use the concept of subset generation but here for
- Rex September 14, 20110-Lower case
1-Upper Case
With the given example "the/THE"
000-the
001-thE
010-tHe
011-tHE
100-The
101-ThE
110-THe
111-THE
Hope the solution is clear
-Rex