Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
letter = {}
number = {}
for i in range(65, 65 + 26):
letter[i - 65 + 1] = chr(i)
number[chr(i)] = i - 65 + 1
def convert_to_letters(col):
str = ''
if col in letter:
return letter[col]
else:
l = (col - 1) / 26
l2 = (col - 1) % 26
if l > 26:
str = convert_to_letters(l)
return str + letter[l2 + 1]
else:
return letter[l] + letter[l2 + 1]
def convert_to_numbers(col):
if len(col) <= 0:
return 1
if col in number:
return number[col]
else:
part_num = convert_to_numbers(col[1:])
part_num = (number[col[:1]] + 25) * part_num + 1
return part_num
print convert_to_letters(703)
print convert_to_numbers('AAA')
good i like your approach without recursion.
I think problem is missing the complete example. In excel, cells are named as A,B,..Z, AA,AB,..AZ, BA,BB...BZ, AAA,AAB,...AAZ.. and so on.
if this is the case, it is nothing but a base conversion of decimal number to base 26 number!
small code to solve it :
public static String convert(int number) {
String ans = "";
int base = 0;
while(number > 0) {
ans = (char)(number%26-1+'A') + ans;
number /= 26;
}
return ans;
}
I think of it this way:
1-26 (26 of them)
AA-ZZ (26*26 of them)
AAA-ZZZ (26*26*26 of them)
So it's relatively easy once we figure out which "level" we are in.
We do that with several variables:
(1) offset - it keeps getting multiplied by 26 in each iteration (eg. 26*26*26 for AAA-ZZZ)
(2) numDigits - number of characters in the current "level" (eg. 3 for AAA-ZZZ)
In each iteration, we first decrement the number by the previous offset, then multiply offset by 26 and check if number-1 is now less than the new offset.
For example, when number is 702, we first decrement it by offset (26) and get 676. Now 676-1=675, which is less than the next offset 26*26=676.
So the task becomes converting 675 to a 2 digit string, which is base arithmetic and you should get ZZ.
It should be relatively simple to do the reverse of finding out the index given the string.
class ExcelColumn {
public static String getColumnName(int num){
if(num<=26)
return "" + num;
int offset = 26;
int numDigits = 1;
while(true) {
num -= offset;
numDigits++;
offset *= 26;
if(num - 1 < offset) {
return helper(num-1, numDigits);
}
}
}
public static String helper(int num, int numDigits) {
if(numDigits == 0)
return "";
int digit = num%26;
return helper(num/26, numDigits-1) + (char)(digit + 'A');
}
public static void main(String[] args) {
System.out.println(getColumnName(Integer.parseInt(args[0])));
}
}
Java Code:
public class Practice93 {
public static void main(String[] args){
System.out.println(GetExcelColumnName(26*26+1));
System.out.println(getColumnNumber("ZA"));
}
public static int getColumnNumber(String str){
int sum=0;
for(int i =str.length()-1;i>=0;i--){
sum = sum + (int)(str.charAt(i) - 64) * (int)Math.pow(26, str.length()-i-1);
}
return sum;
}
private static String GetExcelColumnName(int n) {
String columnName = "";
while(n>0){
int val = (n-1)%26;
columnName = (char)(val+65) + columnName;
n = (n-val)/26;
}
return columnName;
}
}
outputstr="";
if(number<26)
print number
else
while(number!=0)
{
x=number%26 //0 is A ,1 is B and so on
outputstr=outputstr+"x" //string append
number=number/26
}
from string to number:
example:
xyz
z*26^0+y*26^1+x*26^2
I see 2 problems in this solution:
1. In most programming languages this is close to an infinite loop because number/26 takes a long time to become 0, i.e. starts at x.yyy... x.zzz... and so on until 0. I would use floor(number/26)
2. you need to append the "x" before the outputstr because converting it back to number with outputstr+"x" will not give you the same answer.
Basically converting base-10 input to base-26 on symbols {A, B, ..., Z}
C++:
#include <iostream>
#include <stack>
using namespace std;
int main(void)
{
stack <char> S;
char c;
unsigned int input=27;
while(input) {
S.push(input%26 +'A'-1);
input = input/26;
}
while( !S.empty() ) {cout << S.top(); S.pop();}
return 0;
}
It actually does work, but I'm not sure why. The thing is that in Hexadecimal for example 16^3 is F000 but here 26^3 is more like YYZ, it doesn't even have 4 digits... what's going on?
In 26-base the digits should go form 0 to 25 but here they go from 1 to 26, and the regular transformation algorithm still works, that's confusing.
#include <iostream>
#include <map>
#include <cmath>
#include <vector>
#include <string>
using namespace std;
double convertletters(string cur)
{
vector<char> letters;
for (unsigned int i = 0; i < 26; i++)
{
letters.push_back('A'+i);
}
map<char,int> letmap;
for (int i =1; i < letters.size()+1; i++)
{
pair<char, int> temp(letters[i-1],i);
letmap.insert(temp);
}
letters.clear();
double Num = 0;
double sum = 0;
double power = 0;
for (int i = cur.size()-1; i > -1; i--)
{
Num = letmap[cur[i]] * pow(26,power);
sum+=Num;
power++;
}
cout<<sum<<endl;
return sum;
}
void convertnum(double cur)
{
vector<char> retvals;
vector<char> letters;
for (unsigned int i = 0; i < 26; i++)
{
letters.push_back('A'+i);
}
double power = 1;
double temp = 26;
while (temp < cur)
{
temp = temp*26;
power++;
}
power--;
double div_count=0;
double powholder = pow(26,power);
bool changed = false;
while (power > 0)
{
if (changed)
{
powholder = pow(26,power);
changed = false;
}
if (cur > powholder)
{
cur = cur - powholder;
div_count++;
}
else
{
changed = true;
retvals.push_back(letters[div_count-1]);
div_count = 0;
power--;
}
}
retvals.push_back(letters[cur-1]);
for (int i = 0; i < retvals.size() ; i++)
{
cout<<retvals[i];
}
cout<<endl;
}
public static String getColRowName(int num){
String result = "";
if ( num <= 26)return String.valueOf(num);
num = num-1;
while(num != 0){
int a = 'A' + (num%26);
result = String.valueOf((char)a) + result;
num= num/26;
}
return result;
}
Sunny you are right I see the problem. here's the correct function.
public static String getCellName(int num){
String result = "";
if ( num <= 26)return String.valueOf(num);
while(num != 0){
int a = '@' + ((num)%26);
if(num%26 == 0){
a = 'Z';
num = num-1;
}
result = String.valueOf((char)a) + result;
num= num/26;
}
return result;
}
string getExcelCode(int n)
{
//int n=708;
//int n=691;
string str;
while(n!=0)
{
int char1=n%26;
// to make sure it works for 'z'
if(char1==0)
{
char1=26;
}
n-=char1;
str+=char1+'A'-1;
n=n/26;
}
int start=0, end=str.length()-1;
//reverse the string to display in correct order
while(start<end)
{
int temp=str[start];
str[start]=str[end];
str[end]=temp;
start++;
end--;
}
cout<<str;
return str;
}
int getExcelNumber(string str)
{
//string str="ZO";
int num=0;
int i=0;
while(i < str.length())
{
num=num*26+str[i]-'A'+1;
i++;
}
cout<<num;
return num;
}
public class Practice93 {
public static void main(String[] args){
System.out.println(GetExcelColumnName(26*26+1));
System.out.println(getColumnNumber("ZA"));
}
public static int getColumnNumber(String str){
int sum=0;
for(int i =str.length()-1;i>=0;i--){
sum = sum + (int)(str.charAt(i) - 64) * (int)Math.pow(26, str.length()-i-1);
char []a=new char[26]{ 'Z', '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' };
string Result(int n)
{
if (n < 27 && n > 0)
return n.ToString();
else if (n > 0)
{
if (n % 26 == 0)
return myfun(n / 26 - 1) + a[n % 26];
else
return myfun(n / 26) + a[n % 26];
}
}
}
public string myfun(int n)
{
if (n / 26 == 0)
return a[n % 26].ToString();
else
return myfun(n / 26) + a[n % 26];
}
Please test the code and reply if there are any mistakes
public class ExcelNumberConversion {
String excelConversion(int number)
{
char ch = 0;
String output="";
if(number <=26)
{
output+=number;
return output;
}
int factor=1;
number=number-26;
int i=0;
while(number > factor || (i==1)||(i==0))
{
if(i==0)
{
if(number%26==0)
{
ch=90;
}else{
ch=(char)(64+(number%26));
}
}else if(i==1)
{
ch=(char)(65+((number-1)/factor)%26);
}else{
if(number%(factor*26)==0)
{
ch=90;
}else{
ch=(char)(64+((number-1)/factor)%26);
}
}
output=ch+output;
factor*=26;
i++;
}
return output;
}
public static void main(String args[])
{
ExcelNumberConversion obj = new ExcelNumberConversion();
System.out.println(obj.excelConversion(27));
}
}
public class ExcelLetters {
public static void main(String[] args) {
int i = Integer.parseInt(args[0]);
System.out.println(convert(i));
}
public static String convert(int i) {
String s;
// Least significant character is different (0 -> A, 25 -> Z)
s = Character.toString((char)(i % 26 + (int)'A'));
i /= 26;
while (i > 0) {
s = (char)(i%26 + (int)'A' - 1) + s;
i = i / 26;
}
return s;
}
}
A = []
def convertDigit2Letter (d):
return chr(ord('A') + d)
def convertNumber2Letters (x):
x = x - 1
while x > 0:
r = x % 26
x = x / 26
A.append(r)
l = len(A)
s = ""
while (l > 0):
digit = A.pop()
print str(digit)
if (l == 1):
c = convertDigit2Letter(digit)
print str(c)
s += str(c)
else:
c = convertDigit2Letter(digit - 1)
print str(c)
s += str(c)
l = l - 1
return s
letters = convertNumber2Letters(27)
print str (letters)
String ConvertToColumn(int n){
Stack<char> s = new Stack<char>();
int base = 26;
while(n > 0){
int rem = n % 26;
n = n/26;
s.push(ConvertToLetter(rem));
}
return printStack(s);
}
int ConvertToNumber(String s){
int base = 1;
int num = 0;
for(int i = s.length() - 1; i >= 0; i--){
num+= CharTONum.charAt[i]*base;
base *= 26;
}
return num;
}
NumToChar(int i){
// ASCII 65 is A, now 1 is A, the diff is 64
// add 64 to i and converted to char
return (char)(i+64);
}
CharToNum(char c){
return (int)c - 64;
}
printStack(Stack s){
StringBuilder b = new StringBuilder();
while(s.size() > 0){
b.add(s.pop();
}
return b.toString();
}
In Javascript
function toChar(num) {
if (num < 27) {
return String.fromCharCode(num + 64);
} else {
return toCol(Math.floor(num / 26)) + toCol(num - (26 * Math.floor(num / 26)));
}
}
function toNum(str) {
var result = 0;
for (i = str.length - 1; i >= 0; i--) {
result += (str[i].charCodeAt(0) - 64) + (25 * i);
}
return result;
}
This is almost O(1) solution. Using recursion but recursive calls may be at max 3 cause maximum no=umber of columns can be 16384-> XFD.
public class Solution{
//keep index 0 as Z cause 26 % 26 is 0 so we need Z at index 0*****************************
static String[] alphabets = {"Z","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"};
public static String convertToColumn(int num){
int mod = num % 26;
int div = num / 26;
if(num > 26)
return convertToColumn(div) + alphabets[mod];
else
return alphabets[mod];
}
}
In Python:
- sandeepgiri February 27, 2014