Interview notes avatarunknown
15 days ago
3.5 kB
## Candidate Name: ABC


Interview Time: 

* Amazon 1.6 yrs
* 2021 Grad
* Java, Js, HTML, CSS, JSP, AWS, ES
* Internship 

#### Question
Write a function that takes an integer as an input and return the next smallest number that is a palindrome.

Example Input: 1000
Example Output: 1001

Example Input: 1200
Example Output: 1221

* 2:04 Start interview
* C: Brute force, start with next integer, keep checking if integer is a palindrome, keep two pointers, keep comparing start and last, inc one dec other
* C: This can go on until we find a palindrome
* C: Very high number, evaluate a number is palindrome or not serveral times
* C: O(n) where n is length of integet for comparing palindrome
* I: The integer could be large like you said, what if the input is a string
* C: Instead of incrementing , we could do something like 
* Candidate gives an example of a 12 digit number and realize it is tricky
* I: You can come up with your own examples and see what it's next greater palindrome is
* C: Gives 120875 -> 120021 and realize that it's smaller
* C: I'm thinking in terms of string manipulation to not increment the numbers. 
* Candidate thinks about getting some bigger palindrome, enumerate, do binary search in between 
* C: Divide string into 2 halves (only even length example till now)
* 2:14 C: I'm thinking how it'll be just greater or not
* C: Gives an example 129985 
* I: What is the next greater palindrome on top of your head ?
* C: got one case. I need to increment the last part of the first half, i'm still not sure if it's just greater. 
* C: Also gets the 9 case, 129985 -> 130031
* C: Cases 1235421 -> 1245421
* 2:20 C: Starts to think about odd length integers now. 
* C: Divide string in 2 halves. Reverse of first half is greater than the value of second half. If not, I need to transform in a specific fashion.
* Gets two cases by now, mirror of left is greater and the other one. 
* I: You can ignore inputs with a 9 needint an increment.
* I: Gave example of 1331
* 2:25 I: You can get started with code 
* C: We'll divide string to 2 parts, reverse of first half greater than second half, we're good. Else, we'll start incrementing the last position of first half by 1. Then we'll flip and concatenate the first half with itself. 
* C: Can I assume the string is valid ? 
* I: Yes you can.
* 2:29 Candidate starts to code
* I: Will there be a case that require you to touch the middle element in odd-length cases. 
* C: If it's an odd length palindrome thats an already palindrome. 14641 -> 14741
* C: i'll define an isPalindrome function, i'll not complete for now 
* 2:50 Candidate wrote the logic and coded it
* I: Can you fill up the functions that you've left ? 
* 3:02 Working solution
* I: What is the time complexity ? 
* C: T = O(length of string) S = O(length of string)

### Requirements Gathering 
* Asked clarifying questions on the length of integers etc. 
* Asked if input  can be negative, can input string have invalid characters 
* Can input start with 0 

### Problem Solving
* Explained brute force approach 
* Produced a working solution
* Identified 2 major cases
* Identified the edge case with incrementing 9s, didn't get to all 9s though

### Coding 
* Good variable naming, method naming is not super good
* Modular: Wrote muliple small functions
* Code formatting isn't great.
* Produced a working solution

### Debugging and Testing 
* Was using print statements 

### Overall
* Clear communication