Question

Goldman Sachs | OA | Hackerrank | Set - 30

Answer 1

Q1 :
The Game of Book Cricket is played by 2 players. Each player randomly opens the book and as you open the pages you score runs. The last digit of the even numbered page corresponds to your score.

 

So if you opened page number 236, your score is 6. Hence possible scores are either 0,2,4,6 or 8. However if the number ends with a 0 or 8, you are out and you lose your turn. Every time you open the book, note the score and keep on adding. So if you opened pages 124, 56, 22 your score is 4 +6 +2= 12.

 

Given that player 1 has scored N(totalScore) runs and the number of pages in the book is only 10, your task is to identify the number of ways you can match the score and remain not out?

 

Input:
totalScore(N): Total score of the first player

 

Example:
Sample
Input: 6
Output: 4

 

Explanation:
6 can be reached by the following combinations
[2,2,2]
[2,4] [4,2]
[6]

 

Q2 :
Number Patterns & finding the possible smallest numeric value

 

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.)

Answer 2

My Question 2 accepted solution was :

 

import java.util.*;

public class Main {
	static PriorityQueue<Integer> heap = new PriorityQueue<Integer>();;

	static int findPossibleSmallestNumberMatchingPattern(String pattern) {
		if (validatePattern(pattern))
			return -1;
		return Integer.parseInt(processString(pattern));

	}

	/**
	 * @param pattern
	 * @return
	 */
	private static boolean validatePattern(String pattern) {
		return (pattern.equals("") || pattern == "" || pattern == " " || pattern == null
				|| getMNCount(pattern) != pattern.length());
	}

	/**
	 * @param c
	 * @return
	 */
	private static int getMNCount(String pattern) {
		int mCount = 0, nCount = 0;
		for (int i = 0; i < pattern.length(); i++) {
			if (pattern.charAt(i) == 'M') {
				mCount++;
			}
			if (pattern.charAt(i) == 'N') {
				nCount++;
			}
		}
		return nCount + mCount;
	}

	public static void main(String[] args) {

		String pattern = "MNM";
		int res;

		res = findPossibleSmallestNumberMatchingPattern(pattern);
		
		System.out.println(res);

	}

	/**
	 * @param input
	 * @return
	 */
	private static String processString(String input) {
		String res = "";
		int len = input.length();
		for (int k = 1; k <= len + 1; k++)
			heap.add(k);
		int mCount = 0;
		int nCount = 0;
		for (int i = 0; i < len; i++) {
			if (input.charAt(i) == 'M') {
				mCount = getConsecutiveCount(input, i, 'M');
				res += getElement(mCount + 1);
				mCount = 0;
			} else {
				res += getElement(1);
				nCount = 0;
			}

		}
		return res + heap.poll();
	}

	public static int getConsecutiveCount(String input, int index, char ch) {
		int c = 0;
		for (int i = index; i < input.length(); i++) {
			if (input.charAt(i) == ch) {
				c++;
			} else {
				break;
			}
		}
		return c;

	}

	private static String getElement(int k) {
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		int tmp = 0;

		while (k-- > 0) {
			tmp = heap.poll();
			if (k > 0) {
				pq.add(tmp);
			} else {
				break;
			}
		}
		heap.addAll(pq);
		return tmp + "";
	}

}