Goldman Sachs Coding Question 2 | Number Patterns & finding the possible smallest numeric value

 Number Patterns & finding the possible smallest numeric value
x

Question:

Given a Pattern containing only Ns and M's. N represents ascending and M represents descending, Each character (M or N) needs to display sequence of numbers(2 numbers) explaining the ascending or descending order (for ex: 21 ->represents descending →→M). The second character in the pattern takes the last digit from first character and builds the sequence and so on..Please look at example section below.

There could be multiple numbers satisfying the pattern. The goal is to find out the lowest numeric value following the pattern.

Constraints:

• Input can have maximum 8 characters

• Output can have Digits from 1-9 and Digits can't repeat.

• In case of no possible output or incorrect input value (like blank /null/NON M or N character) please return -1.

Example Section:

Input: M

Output: 21 

(2->1 shows descending and possible smallest numeric value. Even 65 or 74 can qualify, but 21 being the smallest numeric value is the correct answer)

Input: MNM

Output:2143 

(M represents descending 2->1, N represents ascending 1->4 (1 is coming from last character), M represents descending 4->3(4 is coming from last character sequence) -- There would be many number qualifying the pattern like 3142,8796,6241 etc.. 2143 is the lowest numeric value for this pattern sequence.)

Java Solution

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    /*
     * Complete the function below.
     */
    static int findPossibleSmallestNumberMatchingPattern(String pattern) {
        if(pattern.equals("") || pattern == "" 
        || pattern == " " || pattern == null 
        || getMNCount(pattern) != pattern.length()){
            return -1;
        }
        
        String ans = "";
        
        int i = 0;
        int curr = 1; // curr val
        int mCount = 0;
        
        while(i < pattern.length()){
            char ch = pattern.charAt(i);
            
            if(i == 0 && ch == 'N'){
                ans += curr;
                curr++;
            }
            
            if(ch =='M')
                mCount++;
            
            int j = i+1;
            while(j <pattern.length() 
                && pattern.charAt(j) == 'M'){
                    mCount++;
                    j++;
                }
            
            int k = mCount;
            while(mCount >= 0){
                ans += (curr + mCount);
                mCount--;
            }
            
            curr += (k + 1);
            mCount = 0;
            i = j;
        }
        return Integer.parseInt(ans);
    }
    private static int getMNCount(String pattern){
        int mCount = 0, nCount = 0;
        for(char ch: pattern.toCharArray()){
            if(ch == 'M'){
                mCount++;
            }
            if(ch == 'N'){
                nCount++;
            }
        }
        return mCount + nCount;
    }
   
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        final String fileName = System.getenv("OUTPUT_PATH");
        BufferedWriter bw = null;
        if (fileName != null) {
            bw = new BufferedWriter(new FileWriter(fileName));
        }
        else {
            bw = new BufferedWriter(new OutputStreamWriter(System.out));
        }

        int res;
        String pattern;
        try {
            pattern = in.nextLine();
        } catch (Exception e) {
            pattern = null;
        }

        res = findPossibleSmallestNumberMatchingPattern(pattern);
        bw.write(String.valueOf(res));
        bw.newLine();
        bw.close();
    }
}