Yahoo Interview Question for Software Engineer / Developers






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

pseudo code: (with two examples in parentheses)

- Convert the number into string. (1224, 39999)

- take half of the string. ( "12", "399" )

- copy first half to second half in reverse order (take care of no of chars)
  ( "12" -> "1221", "399" -> "39993" )

- convert to number and measure the abs. difference with original number - diff1
  ( |1221 - 1224| = 3, |39993-39999| = 6)

- add 1 to half string and now copy first half to second half in reverse order
  ( 12+1 = 13, 399 + 1 = 400, 13-> 1331, 400->40004)

- convert to number and measure the abs. difference with original number - diff2
  ( |1331-1224| = 107, |40004-39999| = 5 )

- if diff1<diff2 return first number else return second number
  ( 1221, 40004)

There can be better way. This is just the first answer I came up with. :)

- KeepTrying November 01, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

awesome! the only time when just copying left to right wont wor is when we have '9' in between. so checking by adding 1 as you suggest will solve that problem.. so i think this is the best polynomial time solution

- clrs March 02, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question seems incomplete. Can you provide more information?

- SDE2 October 30, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Convert the number to a string - (function usage might be incorrect.. just the algo).
int n = 1224;
char str[10] = {0};
str = itoa(n);
find the middle of the string - we are dividing the string into two parts.
copy each character starting from the last character of the first part to the
first character of second part --
example

two parts --

12 && 24.
copy '2' to '2'
copy '1' to '4'.

str is now -- '1221'

n = atoi(str)

not very efficient but should work.

- Girish. October 30, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Not very sure this will work all the time.. comments please..

- Girish October 30, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

That'll not work. Consider the i/p 1299. This should return 1331 and not 1221.

- Anonymous October 31, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yes.. and for 2999.. it should be 3003

- Anonymous October 31, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int closestPalindrome(int num)
{
  int len = 0, temp = num;
  int closest = 0;
  while(temp)
    {
      temp /= 10;
      len++;
    }
  int i = 1;
  temp = num;
  while(i<=len/2)
    {
      int prefix = temp/(pow(10, len-i));
      int suffix = temp%(int)(pow(10, i));
      num = num + pow(10, --i)*(prefix-suffix);
      break;
    }
  printf("%d\n", num);
}

- saraks November 01, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@keeptrying

Good Try!!!
But i think rather than incrementing the left copy and following the procedure...
U have to copy the right half to the left and follow the same procedure in the second trial.
We have to give the output wrt palindrome not wrt value.

It just my understanding....let me know if i am wrong :)

- Shwetank Gupta November 01, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Shwetank, tell me if I didn't get your solution right.

Let's take 2998 for example. Closest palindrome would be 3003. If we follow ur solution, we will get
2992 - ( for the first step)
9889 - ( or 9999 if we increment left half after copying)

So, in this case we won't get closest palindrome.

- KeepTrying November 01, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

i don't get this one. Isn't it an infinite loop. We r not incrementing i anywhere inside the loop body and the loop cond. is i <= len/2.
could you plz explain.

- Rats November 01, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i don't get this one. Isn't it an infinite loop. We r not incrementing i anywhere inside the loop body and the loop cond. is i <= len/2.
could you plz explain.

- Rats November 01, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

None of the solutions provided till now works
This one does. Written in C# and I could do more optimization. But this will give you idea

static string reverse(string w)
{
string z = string.Empty ;
List<char> q = new List<char>();
for (int i = w.Length - 1; i >= 0; i--)
q.Add (w[i]);

foreach (char c in q)
z = z + c.ToString();

return z;



}

static double nearestPalindromicNumber(int x)
{

string z = x.ToString();
int mid = z.Length % 2 == 0 ? z.Length / 2 : (z.Length + 1) / 2;
string w = z.Substring(0, mid );
int mayBe = Convert.ToInt16(w + reverse(w));
double s = 0;
for (double i = x; ; i++)
{
s = Math.Ceiling(i);
if (reverse(s.ToString()).Equals(s.ToString()))
{
if (Math.Abs(x-s) < Math.Abs (mayBe-x))
return s;
}



}
return mayBe;
}

- Sudipta November 01, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please tell me why my pseudo code will not work? thanks..

- KeepTrying November 01, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

urs works.. in fact thats the best

- clrs March 02, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry my last post is incorrect
This one is perfect
-------------------------------

static double  nearestPalindromicNumber(int x)
        {

            string z = x.ToString();
            int mid = z.Length % 2 == 0 ? z.Length / 2 : (z.Length + 1) / 2;
            string w = z.Substring(0, mid );
            int mayBe = Convert.ToInt16(w + reverse(w));
            double s  = 0;
            int far = Math.Abs(x - mayBe);
            for (double  i = x,loop = 0; loop <=far  ; i++,loop ++)
            {
                s = Math.Ceiling(i);
                if (reverse(s.ToString()).Equals(s.ToString()))
                {
                    if (Math.Abs(x-s) < Math.Abs (mayBe-x))
                        return s;
                }


                
            }
            return mayBe;
        }

- Sudipta November 01, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

KeepTrying, your solution is not only correct, it also finds the correct solution way faster than Sudipta's. Sudipta's solution does brute force checking for the upper palindrome case, while you directly compute it, making yours much faster.

- soc November 02, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I was just wondering if I missed any special cases for which the pseudo code would not work..

- KeepTrying November 02, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

9701 --> Closet Palindrome is 9669, not 9779 based on your solution

You can add 1 to the first half, and also you can deduct 1 from the first half.

- leileicats November 09, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@leileicats: Good catch..

- KeepTrying November 12, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Approach: -
1) Check if the number itself is a palindrome
2) If not
initialize count=0, i=1
temp1=number + i
temp2=number - i
a=is_palindrome(temp1) //Returns true if arg IS a palindrome
b=is_palindrome(temp2)
if(!a && !b)
count++;
Repeat (1)

- Anonymous December 07, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Lil errors: -

if(!a && !b)
count ++
i++
Repeat (2)

- Anonymous December 07, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void testFindNearestPalindrome(int n) {
		class NearPalindromeFinder {		
			int findNearPalindrome(int start) {
				if (testPalindrome(start))
					return start;
				else {
					int neg = start;
					int pos = start;
					for (int i = 0; i < start; i++) {
						if (testPalindrome(start-i)) {
							neg = start-i;
							break;
						}
						if (testPalindrome(start+i)) {
							pos = start+i;
							break;
						}							
					}
					return (start == neg) ? pos : neg;
				}
			}
			
			boolean testPalindrome(int start) {
				if (start == 0 || start == 1)
					return true;
				String str = String.valueOf(start);
				String rev = new StringBuffer(str).reverse().toString();
				if (str.equals(rev))
					return true;
				else
					return false;
				
			}
		}

                public static void main(String[] args){
		NearPalindromeFinder f = new NearPalindromeFinder();
		int palindrome = f.findNearPalindrome(n);
		System.out.println("Nearest Palindrome = " + palindrome);
	}}

- tim December 17, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Tim,

How does this work with the class inside a method? Really interested in your coding here though looks really useful :)

Thanks,
Han

- han March 16, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Inner class - java.sun.com/docs/books/tutorial/java/javaOO/innerclasses.html

- Singleton July 03, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simplified version using the one provided from @Tim.

public class NearestPalindrome {

	public static void main(String[] args) {
		NearPalindromeFinder f = new NearPalindromeFinder();
		int palindrome = f.findNearPalindrome(1299);
		System.out.println("Nearest Palindrome = " + palindrome);
	}
}

class NearPalindromeFinder {
	int findNearPalindrome(int number) {
		if (testPalindrome(number))
			return number;
		int palindrome = number;
		for (int i = 0; i < number; i++) {
			if (testPalindrome(number - i)) {
				palindrome = number - i;
				break;
			} else if (testPalindrome(number + i)) {
				palindrome = number + i;
				break;
			}
		}
		return palindrome;
	}

	boolean testPalindrome(int start) {
		if (start == 0 || start == 1) {
			return true;
		}
		String str = String.valueOf(start);
		String rev = new StringBuffer(str).reverse().toString();
		return str.equals(rev);
	}
}

Let me know if there are any test cases failing with it.

- Singleton July 03, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Car parking problem
topcoder.com/tc?module=Static&d1=hs&d2=match_editorials&d3=hs_srm22

- Singleton July 03, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find The Mid Number & then store half number & append it into in reverse order to original.say it a.

2nd subtract 1 from mid of number & append this half number into reverse number to itself. it will show the number that is palindrome thats is less then given number.
say it b.

3rd add 1 to mid of number & then add reverse of this to itself it will represent the number thats palindrome greater then original number
say it c.

now we have to find which is near to original number so basically we have to find the minimum of 3 number.

Note: Need to Review. As This Algorithm Will Suffer With Integer Over Flow

#include
#include
using namespace std;
long long int abs(long long int a)
{
if (a>0)
return a;
return (-a);
}

int count(long long int a)
{
int count=0;
while (a>0)
{
a=a/10;
count++;
}

return count;

}
long long int reverse(long long int a)
{
long long int b=0;
while(a>0)
{
b=b*10+(a%10);
a=a/10;
}
return b;

}

long long int NearestPalindrom(long long int a,int size)
{
long long rev;

if(size%2==0)
rev=reverse(a);
else rev=reverse(a/10);

long long int num=a;

for (int i=0; i num=num*10;

num=num+rev;
return num;
}

int main()
{

long long int a;
cin>>a;
long long int num=a;

int sizea=count(a);
for(int i=0; i num=num/10;

long long int pa = NearestPalindrom(num,sizea);
long long int pb = NearestPalindrom(num-1,sizea);
long long int pc = NearestPalindrom(num+1,sizea);

int da,db,dc;
da=abs(pa-a);
db=abs(pb-a);
dc=abs(pc-a);
if (da cout< if (db cout< if (dc cout<
}

- kumsaha November 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm:
1) Convert the number to a string.
2) Take the substring from the start to the middle digit. Reverse that substring and append it to the result = substring(0,n/2) + reverseOf(subString(0,n/2))
3) Convert it back to integer.
4) If this number is less than the number, add 1 to the substring from 0 to n/2 and repeat the reverse and append process. If greater, subtract one and do the reverse and append.
5) Now you have the possible closest 2 palidromes.
Return the one which has a minimum distance from the original number

- wolfengineer February 23, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More