Microsoft Interview Question
Software Engineer in TestsCountry: United States
Interview Type: In-Person
Cool..works great :). Can u tell me the significance of "n--" here? Why is it used? I don't get it.
@ Nasser Ghazali, the code is fine. You can check the output here: ideone.com/fZ8LE
Regarding direction of output, check against input 52
nerd's solution is almost correct, just need to take care of some offset
template<class T>
string Translate(T input) {
static const char kLookUp[26] = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
string res = "";
while (input > 0) {
T idx = (input - 1) % 26;
res = kLookUp[idx] + res;
input = (input - 1) / 26;
}
return res;
}
hey can you please explain how the following requirement is met in ur code....
"One additional consideration here is, the user is free to provide any length of integer (bigint long int etc), no restriction there."
is template has any role in that???
as I understand the question, the function just need to be able to take different types of input, unless there's some other interpretation?
is my code fits to this problem
void encrypt(int n)
{
int r,q=n;
char *res="";
while(q>0){
r=q%26;
if(r==0){
q=q-1;
r=26;
}
if(r>0 && r<=26){
res=appendAtLeft(res,r);
if(q>0){
q=q/26;
}
}
}
printf("%s\n",res);
}
@ airfang613 : Excellent !!! It works perfectly with below changes :
int idx = (input - 1) % 26;
instead of
T idx = (input - 1) % 26;
Also there is not constructor which convert char to string, so you need to create char [26][2] array with string like "A\0", "B\0"...etc
There is no constructor available which will change char to string.so below statement need to modify :
res = kLookUp[idx] + res;
as
res.insert(res.begin(), kLookUp[idx]);
Following is the recursive method to change a number into base 26 and then converting
the resultant number to string.
Recursive because: I wanted to print the last remainder's corresponding char.
This because recall that in binary conversion of decimal number, the last remainder obtained was the most significant.
There can be other versions along with iterative equvalents of it.
void convertToAlpha(long long int num)
{
long long int q = num;
long long int r = 0;
if (num < 1)
return;
r = q % 26;
q = q / 26;
if (r == 0)
{
q = q - 1;
r = 26;
}
if (q == 0)
printf("%c", (char) (r + 'A' - 1));
else
{
convertToAlpha(q);
printf("%c", (char) (r + 'A' - 1));
}
return;
}
Your o/p will be printing the string equivalent in reverse order. Eg: for x=28 (or take any other number), it will be printing: "BA", which is reverse order. It should be printing "AB".
Thats why I have used recursion (You can impl iterative version as well)
Even for other programs listed here (except mine) will also be printing the string in reverse order.
we need to do %26 but need to take care that 0 has no representation over here....
i.e. when we do % 8 out values are from 0 to 7
but here 0 has no representation ... so every time remainder is 0 we take it as 26 and print 'Z' and subtract 1 from Quotient ....
#include<stdio.h>
#include<math.h>
int main()
{
long long int x = 704;
char *ptr = (char *)malloc(sizeof(char));
// we are skipping any of the decimal points
//from input... i.e. error handling is not there
//right now
int i=0;
while(x > 0)
{
int r = x%26;
x = x/26;
if(r==0)
{
*(ptr+i)='Z';
i++;
x = x-1;
}
else
{
*(ptr+i)=(char)r+'A'-1;
i++;
}
}
*(ptr+i)='\0';
for(i=i-1;i>=0;i--)
printf("%c",*(ptr+i));
return 0;
}
/* Disclaimer: This Solution will work upto 2-characters i.e. from A,B,C ------ upto: ZZ */
#include <stdio.h>
#define INVALID_VAL -1
int main()
{
int numb = INVALID_VAL;
char array_alphabets[26] = {'A','B','C','D','E','F','G','H','I','J','K',
'L','M','N','O','P','Q','R','S','T','U','V',
'W','X','Y','Z'};
int Q = INVALID_VAL;
int R = INVALID_VAL;
int row_index = INVALID_VAL;
int col_index = INVALID_VAL;
printf ("\nEnter number: ");
scanf ("%d", &numb);
/* Calculate the position of this number in the Hypothetical 2-D Array
* Hypothetical 2-D Array:
* Row-0: A | B | C | D | .......................... | Z |
* Row-1: AA | AB | AC | AD | .......................... | AZ |
* Row-2: BA | BB | BC | BD | .......................... | BZ |
*
*/
/* Algorithm to determine the Index of Number in Hypothetical 2-D Array:
*
* Step-1: Divide Number by 26, collect the Quotient (Q) & Remainder (R)
Example: Number = 55
55/26 => Q = 2, R = 3
Q => Row No. in Hypothetical Array
R => Column No. in Hypothetical Array
* Step-2: Allocate an Actual 1-D Array of 26 characters
| A | B | C | D | ......................... | Z |
Row-Index of Hypothetical Array = Q-1; [Map to 1-D Array]
Column-Index of Hypothetical Array = R-1; [Map to 1-D Array]
*/
if (numb>26)
{
Q = numb/26;
R = numb%26;
row_index = Q-1;
if (0==R)
{
col_index = 0;
}
else
{
col_index = R-1;
}
printf ("\nAlphabet Equivalent to the Number %d is: %c%c\n", numb,array_alphabets[row_index],array_alphabets[col_index]);
}
else if (numb<=26)
{
printf ("\nAlphabet Equivalent to the Number %d is: %c\n", numb,array_alphabets[numb-1]);
}
return 0;
}
#include "stdafx.h"
#include <string.h>
void reverseOutput(char *output)
{
int last = strlen(output);
int first=0;
while(first < last )
{
char str = *(output+first);
*(output+first) = *(output+last-1);
*(output+last-1)=str;
last--;first++;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
long int input,store;
printf("Enter the number: ");
scanf("%ld",&input);
store = input;
char output[100];
int j=0;
memset(output,0,100);
while(store != 0)
{
char c = (char)(((store - 1)%26)+97);
output[j++] = c;
store = (store-1)/26;
}
reverseOutput(output);
printf("%s\n",output);
return 0;
}
import java.io.*;
class A
{
int i=0,j=-1,x,m=1;
void intToAplha(int x)
{
int n=0,k=0,counter=0;
while(true)
{
n=i*26;
if(x>n)
{
i++;
j++;
}
else
break;
}
while(true)
{
k=702*m ;
if(x>k)
{
counter++;
j=j%26;
m++;
}
else
{
break;
}
}
System.out.print("The Equivalent String: ");
if(counter>0)
{
for(int t=0;t<counter;t++)
System.out.print("A");
if(j==0)
System.out.print("Z");
}
n=x%26;
if(j>0)
{
System.out.print((char)(64+j));
if(n==0)
System.out.print("Z");
else
System.out.print((char)(64+n));
}
else
{
if(n==0)
System.out.print("Z");
else
System.out.print((char)(64+n));
}
}
void input()
{
try{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter Int Val : ");
String s=br.readLine();
x=Integer.parseInt(s);
br.close();
}
catch(Exception e){System.out.println(e);}
intToAplha(x);
}
public static void main(String args[])
{
A a=new A();
a.input();
}
}
by firoz
i tried test cases those obvious ones and result is satisfactory. this is simplest and complete code for the given problem. let me know if it voilate some test cases.
void encrypt(int n)
{
int r,q=n;
char *res="";
while(q>0){
r=q%26;
if(r==0){
q=q-1;
r=26;
}
if(r>0 && r<=26){
res=appendAtLeft(res,r);
if(q>0){
q=q/26;
}
}
}
printf("%s\n",res);
}
public static string ConvertToAlphabet(int number)
{
int temp = number;
char[] alphabets = new char[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
string Alphabet = string.Empty;
int Index = 0;
if (number <= 0)
{
Console.WriteLine("input number {0} is invalid", temp);
return string.Empty;
}
if (number < 27)
{
Console.WriteLine("input number {0} , output alphabet {1}", temp, alphabets[number - 1]);
return alphabets[number - 1].ToString();
}
while (number > 0)
{
Index = number % 26;
number = number / 26; ;
if (Index == 0)
{
Index = 26;
number = number - 1;
}
Alphabet = alphabets[Index - 1] + Alphabet;
}
Console.WriteLine("input number {0} , output alphabet {1}", temp, Alphabet);
return Alphabet;
}
input
Microsoft.ConvertToAlphabet(-11);
Microsoft.ConvertToAlphabet(1);
Microsoft.ConvertToAlphabet(26);
Microsoft.ConvertToAlphabet(52);
Microsoft.ConvertToAlphabet(28);
Microsoft.ConvertToAlphabet(702);
Microsoft.ConvertToAlphabet(703);
output
input number -11 is invalid
input number 1 , output alphabet A
input number 26 , output alphabet Z
input number 52 , output alphabet AZ
input number 28 , output alphabet AB
input number 702 , output alphabet ZZ
input number 703 , output alphabet AAA
public static String convertToInt(int num)
{
String alpha ="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
char character = 0;String res ="";
while( num > 0)
{
int id = ( num-1)%26;
res = alpha.charAt(id)+res;
num = (num -1)/26;}
return res;
}
Try this one:
void convertAphabet(int intx, int base)
{
int inttx = intx;
if(inttx/base > 26)
{
if(inttx%(26*base) == 0)
{
convertAphabet(inttx-26*base, base*26);
putchar('Z');
}else
{
convertAphabet(inttx, base*26);
putchar('A' + (inttx/base)%26 -1);
}
}else
{
putchar('A' + (inttx/base -1));
}
}
public class ConvertToAlphabet {
static char[] array;
static {
array = new char[27];
for (int i = 1; i <= 26; i++) {
array[i] = (char) (i + 96);
}
}
public static String convert(int n) {
if (n <= 0) {
return "";
}
int remainder = n % 26;
if (remainder == 0) {
return "z" + convert((n - 1) / 26);
} else {
return array[remainder] + convert(n / 26);
}
}
public static void main(String[] args) {
System.out.println(convert(702));
}
}
a similar code here
codes-to-problem.blogspot.in/2012/07/wap-to-return-numbered-index-if-input.html
Base 26 representation from 1 to 26.
- Aashish July 12, 2012