Google Interview Question Software Engineer / Developers
Country: India
library functions is something above brute force
still any idiots can solve most of the recent questions posted on here
Maybe brute force is not enough? Almost always after any first solution you would have question: how can you improve your program? And then you have to rewrite with processor/memory optimization or without recursion etc.
How do you think, how much time you need to find quite large palindromes?
Can you write a program that would find within few minutes numbers like:
03150522442250513 (oct) == 112745383547211 (dec)?
Question doesn't say what the input to the function, so let's throw out ideas ourselves.
My first idea is to have outter function take a certain "width" of octal numbers...
1) Then we create all octal numbers that are of that width from the endpoints (we can backtrack to create all such palindromic octal numbers).
2) We pack the octal 3 bits together to create binary representation (you can do it as part of 1)
3) Convert to BCD (can optimize above to make this part fast as part of shift and add algorithms or whatnot). Then we scan the BCD numbers from the ends to see if they are palindromic too.
Might try coding it in evening.
Generate palindromes in decimal, then for every one check if they are also palindromes in octal. Here is an example of my method finding all palindromes smaller than int max that fit the criteria. It runs in under 0.01s and is O(n), n being the number of digits of the largest palindrome to be generated.
char num[20];
bool isOctPal(unsigned int n) {
int s = sprintf(num, "%o", n);
for (int i = 0; i < s/2; i++)
if (num[i] != num[s-i-1]) return false;
printf("%d %o\n", n, n);
return true;
}
int main() {
int max = 21474;
for (int n = 0; n < max; n++) {
int number = n, rem = 0, reverse = 0, pdrome, no_digits = 1;
while (number != 0)
reverse = reverse * 10 + number % 10, number /= 10 , no_digits *= 10;
pdrome = n <= 9 ? n : (no_digits / 10) * n + reverse % (no_digits / 10);
isOctPal(pdrome);
}
return 0;
}
why it's downvoted? I suppose this solution is quite close of the best one I've know. Because palindromes are quite rare in big numbers, I suppose the best solution is:
1. Implement own class BigNumber with function getNextPalindrome()
2. Create 2 instances for decimal and octal
3. Use algorithm below (pseudo code):
d = Decimal(0);
e = Octal(0);
while True
{
d.getNextPalindrome();
o.setvalue(d.getvalue());
if o.isPalindrome() { outstream << "Found palindrome: " << d << " (in octal: " << o << ")"; }
o.getNextPalindrome();
d.setvalue(o.getvalue());
if d.isPalindrome() { outstream << "Found palindrome: " << d << " (in octal: " << o << ")"; }
}
Can be generated by partial and full number reflections, here createAll function can be run twice for 10 and 8 base and just retain two lists (or merge it). Also can be changed to more sophisticated step by step approach.
public static List<Integer> createAll( int n, int base ){
final List<Integer> result = new ArrayList<>();
if ( n < 0 ) return result;
result.add(0);
int d = base;
int a = 0;
boolean partial = true;
while ( true ) {
a++;
if ( a % d == 0 ) {
partial = !partial;
if ( partial ) {
d *= base;
} else {
a /= base;
}
}
int v = create( a, partial, d, base );
if ( v > n ) break;
result.add( v );
}
return result;
}
private static int create( int v, boolean partial, int d, int base ){
int second = 0;
int m = 1;
for ( int i = d; i >= base; i /= base ) {
if ( partial && (i==base) ) break;
int c = (v / (i/base)) % base;
second += m*c;
m *= base;
}
int result = 0;
if ( partial ) {
result = v*(d / base) + second;
} else {
result = v*d + second;
}
return result;
}
function f()
{
for(i=0;i<10000;i++)
{
var ostr = '' + covertToOctal(i);
var dstr = '' + i;
var retd = check_palindrome(ostr);
var reto = check_palindrome(dstr);
if(retd && reto)
{
console.log(ostr + ',' + dstr);
}
}
}
function check_palindrome(str)
{
return str == str.split('').reverse().join('');
}
function covertToOctal(i)
{
if(i ==0)
{
return "0";
}
var temp = i;
var str = "";
while(temp)
{
str = str + '' + temp%8;
temp = Math.floor(temp/8);
}
str = str.split('').reverse().join('');
return str;
}
Brute force can be made faster if you use a little math: I believe the number must be divisible by 99.
0, 1, 2, 3, 4, 5, 6, 7 are counter examples
I would be angry at someone if he/she asked such a question as if it was a pure coding exercise then expected some neat O(1) formula for generating the kth such number.
The 99 idea although really smart works only if the representation has an even number of digits in both bases. 121 (171 otcal) for example is a palindromic in both bases and not dividible by 99.
Hi,
How about instead of checking all the numbers starting from 1(decimal) to an upper limit, we generate the first 10000 (say) decimal palindromic numbers. Then convert them to octal and check if the octal representation is palindromic or not.
Below is the working C++ code to print the numbers that are palindromic in both decimal and octal representations.
Function descriptions
i) next_palindrome - This function takes a palindrome number as argument and returns the next larger palindrome. Initially started with 0 as seed.
Ex - next_palindrome(99)=101
next_palindrome(999)=1001
next_palindrome(12321)=12421
This function uses a folding technique to find out the next larger palindrome.
ii) itoa - integer to string
iii) reverse - reverse a string
iv) dec_oct - convert from decimal to octal
v) is_palindrome - to check if a string is a palindrome
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
int next_palindrome(int palindrome);
void itoa(int p, char s[]);
void reverse(char s[]);
void dec_oct(int dec, char oct[]);
bool is_palindrome(char s[]);
int main()
{
int start=0;
char oct[20];
cout<<setw(10)<<"Decimal"<<setw(10)<<"Octal"<<endl;
for(int i=0; i<10000; i++)
{
dec_oct(start, oct);
if(is_palindrome(oct))
cout<<setw(10)<<start<<" "<<setw(10)<<oct<<endl;
start=next_palindrome(start);
}
return 0;
}
int next_palindrome(int pal)
{
char s[15];
char t[15];
char temp[15];
char help[15];
int nt;
itoa(pal, s);
if(strlen(s)%2)
{
memcpy(t, s, strlen(s)/2 + 1);
t[strlen(s)/2 + 1]='\0';
nt=atoi(t);
itoa(nt+1, temp);
if(strlen(temp) != strlen(t))
{
temp[strlen(t)]='\0';
memcpy(help, temp, strlen(temp)+1);
reverse(help);
strcat(temp, help);
return atoi(temp);
}
else
{
memcpy(help, temp, strlen(temp)-1);
help[strlen(temp)-1]='\0';
reverse(help);
strcat(temp, help);
return atoi(temp);
}
}
else
{
memcpy(t, s, strlen(s)/2);
t[strlen(s)/2]='\0';
nt=atoi(t);
itoa(nt+1, temp);
if(strlen(temp) != strlen(t))
{
memcpy(help, temp, strlen(temp)-1);
help[strlen(temp)-1]='\0';
reverse(help);
strcat(temp, help);
return atoi(temp);
}
else
{
memcpy(help, temp, strlen(temp)+1);
reverse(help);
strcat(temp, help);
return atoi(temp);
}
}
}
void dec_oct(int dec, char oct[])
{
int i=0;
if(dec==0)
{
oct[0]='0';
oct[1]='\0';
return;
}
while(dec>0)
{
oct[i]=dec%8+'0';
dec=dec/8;
i++;
}
oct[i]='\0';
reverse(oct);
}
bool is_palindrome(char s[])
{
char temp[20];
strcpy(temp, s);
reverse(temp);
if(strcmp(temp, s)==0)
return true;
return false;
}
void itoa(int p, char s[])
{
int i=0;
while(p>0)
{
s[i]=p%10 + '0';
p=p/10;
i++;
}
s[i]='\0';
reverse(s);
}
void reverse(char s[])
{
int i;
int len=strlen(s);
char temp;
for(i=0; i<len/2; i++)
{
temp=s[i];
s[i]=s[len-i-1];
s[len-i-1]=temp;
}
}
Output ( first 15 lines)
Decimal Octal
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
9 11
121 171
292 444
333 515
373 565
414 636
Here's a 2 line brute force -
p = lambda n : (n==n[::-1])
print [(x,oct(x)) for x in xrange(1000) if p(str(x)) and p(oct(x)[1:]) ]
Output -
[(0, '0'), (1, '01'), (2, '02'), (3, '03'), (4, '04'), (5, '05'), (6, '06'), (7, '07'), (9, '011'), (121, '0171'), (292, '0444'), (333, '0515'), (373, '0565'), (414, '0636'), (585, '01111')]
Any idiot can do a brute force.
- Anonymous November 01, 2013