Question

Microsoft | OA Coding Questions and Solutions | Set - 71 | 2022

Answer 1

public class Main {

  public String maxPalindromeNumber(String number) {

    Function < Character, Integer > charToIdx = ch -> ch - '0';
    Function < Integer, Character > idxToChar = i -> (char)(i + '0');

    int[] counter = new int[10];

    for (char ch: number.toCharArray()) {
      counter[charToIdx.apply(ch)]++;
    }

    int maxNumberHavingOddFrequency = -1;
    for (int i = 0; i < counter.length; ++i) {
      if (counter[i] % 2 == 1) maxNumberHavingOddFrequency = i;
    }
    StringBuilder sb = new StringBuilder();
    if (maxNumberHavingOddFrequency != -1) sb.append(maxNumberHavingOddFrequency);

    //Running loop till 1 only to avoid cases like 090, 000
    for (int i = 9; i >= 1; --i) {
      int count = counter[i];
      if (counter[i] == 0) continue;
      if (counter[i] % 2 == 1) count = counter[i] - 1;

      for (int j = 0; j < count / 2; ++j) {
        sb.append(i);
        sb.insert(0, i);
      }
    }
    return sb.toString();
  }

  public static void main(String[] args) {
    Main main = new Main();
    System.out.println(main.maxPalindromeNumber("112"));
    System.out.println(main.maxPalindromeNumber("900"));
    System.out.println(main.maxPalindromeNumber("000"));
    System.out.println(main.maxPalindromeNumber("0000"));
    System.out.println(main.maxPalindromeNumber("39878"));
    System.out.println(main.maxPalindromeNumber("54321"));

  }
}

Answer 2

#include<bits/stdc++.h>
using namespace std;

string removeZeros(string s) {
    while (!s.empty() && s.back() == '0')
        s.pop_back();
    reverse(s.begin(), s.end());
    while (!s.empty() && s.back() == '0')
        s.pop_back();
    reverse(s.begin(), s.end());
    if (s.empty())
        return "0";
    return s;
}

string func(string &s) {
    int arr[10] = {0};
    for (char ch : s) {
        arr[ch - '0']++;
    }
    int len = 0;
    int odd = 0;
    for (int i = 0; i < 10; i++) {
        if (arr[i] & 1) odd = 1;
        len += arr[i] / 2;
    }
    len *= 2;
    len += odd;
    string ans(len, ' ');
    int ptr = 0;
    for (int i = 9; i >= 0; i--) {
        int cnt = arr[i] / 2;
        arr[i] %= 2;
        while (cnt--) {
            ans[ptr] = ans[len - ptr - 1] = i + '0';
            ptr++;
        }
    }
    if (len & 1) {
        for (int i = 9; i >= 0; i--) {
            if (arr[i]) {
                ans[ptr] = i + '0';
                break;
            }
        }
    }
    if (ans[0] != '0')
        return ans;
    return removeZeros(ans);
}

int main() {
    int t = 1;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        cout << func(s) << endl;
    }
    return 0;
}

/*
INPUT
5
39878
00900
0000
54321
88889999
*/

Answer 3

public String solution(String s) {
  Deque<Integer> front = new ArrayDeque<>(), back = new ArrayDeque<>();
  int[] cnts = new int[10];
  int n = s.length();
  for(int i=0; i<n; i++) {
   cnts[s.charAt(i)-'0']++;
  }
  for(int i=9; i>=0; i--) {
   if(cnts[i]<2) continue;
   int rep = cnts[i]/2;
   for(int r = 0; r<rep; r++) {
    front.offerLast(i);
    back.offerFirst(i);
    cnts[i]-=2;
   }
  }
  while(!front.isEmpty() && front.peekFirst()==0) {
   front.pollFirst();
   back.pollLast();
  }
  StringBuilder sb = new StringBuilder();
  while(!front.isEmpty()) {
   sb.append(front.pollFirst());
  }
  for(int i=9; i>=0; i--) {
   if(cnts[i]==0) continue;
   sb.append(i);
   break;
  }
  while(!back.isEmpty()) {
   sb.append(back.pollFirst());
  }
  return sb.isEmpty()? "0" : sb.toString();
 }

Answer 4

You are given a string S, which consists entirely of decimal digits (0−9). 
Using digits from S, create a palindromic number with the largest possible decimal value. 
You should use at least one digit and you can reorder the digits. 

A palindromic number remains the same when its digits are reversed; for instance, "7", "44" or "83238". 
Any palindromic number you create should not, however, have any leading zeros, such as in "0990" or "010".
For example, decimal palindromic numbers that can be created from "8199" are: 
"1", "8", "9", "99", "919" and "989".

Among them, “989” has the largest value.

Write a function:
class Solution { public String solution(String S); }
that, given a string S of N digits, returns the string representing the palindromic number with the largest value.
Examples:
1. Given "39878", your function should return "898".
2. Given "00900", your function should return "9".
3. Given "0000", your function should return "0".
4. Given "54321", your function should return "5".
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..100,000];
string S consists only of digits (0−9).