Grokking Microsoft Coding Interview
0% completed
Hidden Document
Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content
.....
.....
.....
Like the course? Get enrolled and start learning!
Mohammed Dh Abbas
· 2 years ago
class Solution: def largestPalindromic(self, num: str) -> str: # count the frequencies of the numbers from 9 - 0 in a map def build_counter(): counter = {str(i): 0 for i in range(10)} for n in num: counter[n] += 1 return counter counter = build_counter() remain = 0 # store the largest remaining number first_half = [] # store the first left half of the result result = [] # for the entire result # loop for all the number from 9 to 0 in decreasing order for i in range(9,0, -1): div = counter[str(i)] // 2 # take the division result rem = counter[str(i)] % 2 # the remaining # repeat
Show 1 reply
Miguel
· 2 years ago
Space complexity should be O(N). We construct and hold half of the palindrome, which at worst is N/2.
Show 1 reply
Venkata Narayanan
· 3 years ago
There is a small issue in the solution provided. if the input is "0009", then the output should be 9 (which is largest palindromic number) but this solution returns "0", as the first half is full zeroes. May be the below code will help.
class Solution {
largestPalindromic(num) {
const freq = {};
let firstHalf = '',
middle = '';
for (let i = 0; i < num.length; i++) {
freq[num[i]] = (freq[num[i]] || 0) + 1;
}
for (let i = 9; i >= 0; i--) {
if (freq[i] && freq[i] % 2 !== 0 && middle === '') {
middle = i.toString();
}
firstHalf += i.toString().repeat(Math.floor(freq[i] / 2));
}
if (firstHalf === '' ||firstHalf.match(/^0+$/) ) {
return middle === '' ? 0 : middle;
}
/* else if (firstHal
Show 2 replies
Reading Progress
0%