Amazon Interview Question
Software Engineer / DevelopersCountry: India
I think your approach is correct but incomplete.
What if the input is 2021/12/02? With your approach you will get output 2101/10/02 which is not a palindrome. So you also need to increment first digit of day if you happen increment 2 digit of year and increment 2 digit of day if you happen to increment first digit of year.
@Martin:
His approach is correct even for 2021/12/02. His approach returns 2030/03/02 but not 2101/10/02 as u said!
@Martin:
His approach is correct even for 2021/12/02. His approach returns 2030/03/02 but not 2101/10/02 as u said!
1) split the string into half (2001 and 1002)
2)reverse the second one and convert both into integer(1002 ->2001)
3)increment both by one
4) reverse the second one and combine both
(make conditions for checking the date limit and month limit)
It asks for the date just after, so reversing the first string would be the right approach, and since the year can be in any format, you just need to check one string if mm/dd is valid or dd/mm (whichever format is presented).
num = 20011002
counter = date.length()-1
i = date.length()/2
date[] = {'2','0','0','1','1','0','0',2} is the date:
1. num+1
General Rule: IF(MSB>LSB) THEN Diff = MSB-LSB ELSE Diff = 10+MSB-LSB
3. LSB[counter --)+Diff[i++] {i == No of elements in date[] array}
4. Continue
5. while date[(date.length()/2)-1] = MSB && date[date.length()/2] = LSB
then IF Diff+LSB > 10 THEN Diff[when i == date.length()/2] +1 ELSE Diff[when i == date.length()/2]
6. num+ Add all the Diff[i=0 TO i<date.length()/2] = RESULT
Here is my idea:
(a)start looking at the last tow digits of the year and the two digits of the month.
(b)Keep incrementing month till it reaches 12 mean while compare if they form a palindrome when we append them together.
(c)if the month exceeds 12 bring it back to 01 and increment the year by one.
(d)we can skip some of the years [2013 2019].
your comments are most appreciated.
1. Spilt the date into two groups: [2001, 1002]
2. Convert the numbers into arrays of characters: [[2,0,0,1], [1,0,0,2]]
3. Increase the 4th character in the 1st array and the 1st character in the 2nd array
: [[2,0,0,2], [2,0,0,2]]. Convert to date and do validation->Invalid date(2002/20/02)
->repeat until ((the increased date is valid and palindrome) OR (the increased character in the 2nd array is equal to the original character))
(You can use the modulation to reduce the number of computations)
-> if the increased date is valid and palindrome, return the date. Otherwise, do same thing to the next characters
e.g. (with modulation for increament)
2001/10/02 -> increase 1st character in the 2nd array and the corresponding character in the 1st array -> 2000/00/02 -> invalid date so increase them again -> 2001/10/02 -> equal to the given characters-> increase 2nd character in the 2nd array and the 3rd character in the 1st array ->2011/11/02 -> valid date and palindrome->return 2011/11/02.
The key idea is to find the smallest year since we can't avoid changing the year when we change the month or day part
Here year is one thing that we do not want to change much.
now we are given that input date is a palindrome.
So in any way we need to change the year because by just manupulating dd and mm you can not get the same combination of year.
So , if we take date in form of yyyy/mm/dd
than y1y2y3y4 has y4y3 as mm and y2y1 as dd
So we just need to check the validity of year as year can take any number of 4 digits but mm can take up to 01-12 and dd to 01-31 also depending on month.
One solution is to keep increasing year by 1 and check the validity.
* Base assumption in 1 year there can't be two date like the palindrom 2001/10/02
Start from year 2002 ..reverse this string..
Convert to int 2002 in this case check if first two digit is a "valid month*"and last two digits a "valid date*"...both are True then that's your answer :D
**"Valid month "={01,02,....12}
**"valid date"={01,02,.........28} for all ..29,30,31 depends on month and year ....
public String getNextPalindromeDate(String date) throws ParseException,
NotAPalindromeException {
SimpleDateFormat sdf = new SimpleDateFormat("yyyyMMdd");
sdf.setLenient(false);
// Check if entered date is a valid yyyyMMdd format date
sdf.parse(date);
int year = Integer.parseInt(date.substring(0, 4));
// Throw user defined exception if date is not a palindrome
if (!date.equals(new StringBuilder(date.substring(0, 4)).reverse()
.insert(0, year).toString()))
throw new NotAPalindromeException();
while (true) {
String yearString = String.valueOf(++year);
StringBuilder sb = new StringBuilder(yearString);
sb.reverse().insert(0, yearString);
try {
sdf.parse(sb.toString());
return sb.toString();
} catch (ParseException e) {
// Skip this date. Not valid.
}
}
}
Assuming that the number of digits are even. Though the algo can be changed to odd digit too..(only year can make it an odd digit if it is less than 1000. say 976-12-11 is an odd digit)
ALGO:-
First choose the pivot elements. In an even digit number there are 2 pivots.
Date : 2001-10-02
Pivot ^ ^
| |
i.e 1 and 1
Next increment the Pivot Elements by 1 . So now the date becomes
2002-20-02
Check if it is a valid date of not
It is not, as the month > 12 here
Next again increment it.
2003-30-02
Again not a valid date.
Next we check all this until 9 . Which again leads to not a valid date.
Now we move to the next pivot element
Date : 2001-10-02
Pivot ^ ^
| |
i.e 0 and 0
Now again be do the same. But we also replace the in between digits by the least number .
i.e 0
So the next valid date comes as
Date : 2011-11-02
Replacing the between digits of pivot to 0 . We get. 2010-01-02
This is a valid date, And hence the Next Palindrome Date.
-------RETURN ------
Given date is [2001/10/02]
store the digits as they are in an array int/char whatever:
int date[8] = {2,0,0,1,1,0,0,2};
now take middle four digits i.e. "0110" and check when they will form new palindrom just after it with a condition that last 2 digits of this sub-array must not exceed 12 (as soon as it does exceed reset it to 01 and set first 2 digits with reverse digits of last two digits i.e. 01->10 will make this four digit seq as 1001).
so with this approach we can get next palindrom date => 2010/01/02
good one
bool palindrom( int& n1, int& n2, int& n3, int& n4 )
{
return (n1 == n4) && (n2 == n3);
}
static void test5()
{
int date[8] = {2,0,0,1,1,0,0,2};
for( int y = 01; y < 99; y++ )
{
int y1 = y > 9 ? y / 10 : 0;
float nn = y - ( int( float(y) / 10.0) * 10 );
int y2 = y > 9 ? nn : y;
for( int m = 1; m <= 12; m++ )
{
int m1 = m > 9 ? m / 10 : 0;
float nn = m - ( int( float(m) / 10.0) * 10 );
int m2 = m > 9 ? nn : m;
int month_start = ( y1 * 10 + y2 ) * 12 + m1 * 10 + m2;
int data_start = ( date[2] * 10 + date[3] ) * 12 + date[4] * 10 + date[5];
if( month_start > data_start )
if( palindrom( y1, y2, m1, m2 ) )
{
cout << "result: " << date[0] << date[1] << y1 << y2 << '.' << m1 << m2 << '.' << date[6] << date[7] << '\n';
return;
}
}
}
}
Cant we optimize based on the year ???
1. None of the years > XX21 can be a palindrome.
a. XX12 - XX19 can never be a palindrome
2. None of the years > ABYY where A can be at MAX 9 and B can be at max 3 would be a palindrome
Only on escaping the criteria, I would go for string reversal because most of the years would fall inside the above range.
An even more optimized solution would be building a hash set before the program starts which has all the possible 4 digit years which determines if its a palindrome or not.
import java.text.ParsePosition;
import java.text.SimpleDateFormat;
import java.util.Calendar;
public class NextPalindromeDate {
public static void main(String [] args){
String strDate="2001/10/02";
String str[] = strDate.split("/");
int year =Integer.parseInt(str[0]);
int date;
int month;
do{
date = 0;
month = 0;
year++ ;
int yearToOperateOn = year;
for(int i=0;i<4;i++){
int digit =yearToOperateOn%10;
if(i<2){
month = month*10 + digit;
}else {
date = date*10 +digit;
}
yearToOperateOn = yearToOperateOn /10;
}
}while(!isLegalDate(date,month));
SimpleDateFormat sdf = new SimpleDateFormat("yyyy/MM/dd");
Calendar cal = Calendar.getInstance();
cal.set(Calendar.MONTH, month-1 );
cal.set(Calendar.YEAR, year);
cal.set(Calendar.DATE, date);
System.out.println(sdf.format(cal.getTime()));
}
private static boolean isLegalDate(int date, int month) {
SimpleDateFormat sdf = new SimpleDateFormat("M-d");
sdf.setLenient(false);
String dateString = month+"-"+date;
return sdf.parse(dateString, new ParsePosition(0)) != null;
}
}
Add 1 to the year and then reverse the last 2 digits of the year and check if its a valid month.
2001/10/02
2001+1=2002, Now reverse last 2 digits of the year its 20 , so not a valid month.
Repeat this till we get the valid month. the answer for this example will be 2010/01/02.
I am not very sure about this approach . Please correct me if I am wrong.
2001/10/02
- Anonymous May 01, 2012keep incrementing the year by 1 (2001+1=2002) then reverse the last 2 digits i.e.20 is it a valid month? No.so keep incrementing the year and reversing the last 2 digits till it gives us a valid month. That will be the next palindrome date i.e. 2010/01/02 and the next will be 2011/11/02 and next 2020/02/02 and so on