Grokking Microsoft Coding Interview
Vote

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

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

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

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%


Vote for new content