My Notes some of this and some of that

How to clear PSM 1

Recently, I cleared PSM 1 with 95% on first attempt, so I thought of sharing my experience and how I prepared for the same. Many thanks to everyone whose tips helped me. I am trying to share the summary of those tips and what worked for me.

Preparation Material

  • Scrum Guide Scrum Guide is the most important artifact. Get very, very familiar with it. Each and every sentence is worth it’s weight in gold. I read this around 10 times. Try to understand it really well. You can also try and create notes for it in Q&A format. I found that very useful way to learn and remember things.

  • Nexus Guide
    Nexus is about scaling scrum. You need to get familiar with this, at least to the level of clearing Nexus Open assessment.

  • Scrum Glossary
    Few of the terms stated in glossary are not in Scrum Guide but shows up in actual exams like Burn Down Chart, Technical Debt etc

Few more topics, which can be read in detail on Internet:

  • Burn Up/Down Charts
  • Cone of Uncertainty
  • Velocity
  • Technical Debt

Assessments

Start with assessments first without going through any preparation material to see where you stand, and create a baseline for yourself.
Then go through the cycle of going through preparation material and then attempting these assessments to see how you are improving.
Your goal should be to get 100% in these assessments taking under 5 min for open assessments and under 20 min for Mikhail Lapshin preparation quiz. You should be able to get 100% scores consistently on multiple attempts.
Few of the questions from assessments do show up in the real assessments and since time is of essence, getting comfortable and quick with these questions would help you to get that extra edge and devote more attention to other questions.

About the real assessment

  • Find a quiet place and keep water, pen and notepad handy.
  • Questions cannot be skipped without answering, so if you are not able to make up your mind about the answer then just note down the question number and come back to it later.
  • Better have a attempt at all questions first, marking the ones which needs to be revisited as that would bring in some comfort factor.
  • At the last question, dont hit finish too soon. Look for link to “display all answered questions” and scroll down to see all questions with their preview and numbers. Click on the one you want to revisit and then choose the best possible answer. Repeat this until you have done the same for all questions you wanted to revisit.
  • If you still get time then just re-check the questions you have answered. Utilize all the time you have and do not be in a hurry to hit the finish button.

All the best!

Kadane's Algo

Problem Statement: This is one of my favorite algorithms! Given an array containing both negative and positive integers. Find the contiguous sub-array with maximum sum.

Reference URL: Kadane’s Algo

Example:

Input: 1 2 3 Output: 6

Input: -1 -2 -3 -4 Output: -1

import java.util.Scanner;

//URL: https://practice.geeksforgeeks.org/problems/kadanes-algorithm/0
//Description: Given an array containing both negative and positive integers. Find the contiguous sub-array with maximum sum.
public class Kadane {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCases = scanner.nextInt();

        for (int i = 0; i < testCases; i++) {
            int arrLength = scanner.nextInt();
            int[] arr = new int[arrLength];

            for (int j = 0; j < arrLength; j++) {
                arr[j] = scanner.nextInt();
            }

            System.out.println(maxSum(arr));
        }
    }

    public static int maxSum(int[] arr) {
        int sum = 0;
        int maxSum = Integer.MIN_VALUE;

        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            //keep track of maximum sum
            maxSum = Math.max(sum, maxSum);

            //if sum is negative then reset sum
            //this ensures that we consider any sub-array which yield positive sum
            if (sum < 0) {
                sum = 0;
            }
        }

        return maxSum;
    }
}

Minimum Window Substring

Problem Statement: Given a string S and text t. Output the smallest window in the string having all characters of the text. Both the string and text contains small case letters.

Reference URL: Minimum Window Substring

Example:

Input: String: “timetopractice”, Pattern: “toc” Output: “toprac”

Input: String: “zoomlazapzo”, Pattern: “oza” Output: “apzo”

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

//URL: https://practice.geeksforgeeks.org/problems/smallest-window-in-a-string-containing-all-the-characters-of-another-string/0
//Description: Given a string S and text t. Output the smallest window in the string having all characters of the text. Both the string and text contains small case letters.
public class SmallestWindow {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCases = scanner.nextInt();

        for (int i = 0; i < testCases; i++) {
            String str = scanner.next();
            String text = scanner.next();
            System.out.println(getSmallestWindow(str, text));
        }
    }

    public static String getSmallestWindow(String longString, String pattern) {
        if (pattern.length() > longString.length()) {
            return "-1";
        }

        //left and right pointers to create sliding window
        int left = 0;
        int right = pattern.length();

        String minWindow = "-1";
        int minLen = Integer.MAX_VALUE;

        char[] chars = longString.toCharArray();
        while (right <= chars.length) {
            String substring = longString.substring(left, right);

            //if long string contain pattern, then increment left pointer until pattern is found to find minimum window string
            while (doesStringContainsPattern(substring, pattern)) {

                //keep track of minimum length of window and minimum window string found so far
                if (substring.length() < minLen) {
                    minLen = substring.length();
                    minWindow = substring;
                }
                left++;
                substring = longString.substring(left, right);
            }

            //increment right pointer
            right++;
        }

        return minWindow;
    }

    //to check whether long string contains the pattern, also check count of each character
    private static boolean doesStringContainsPattern(String str, String text) {
        Map<Character, Integer> strMap = getCharCountMap(str);
        Map<Character, Integer> textMap = getCharCountMap(text);

        Set<Character> set = textMap.keySet();

        for (Character ch : set) {
            if (!strMap.containsKey(ch) || strMap.get(ch) < textMap.get(ch)) {
                return false;
            }
        }

        return true;
    }

    //create a map of character counts in the string
    private static Map<Character, Integer> getCharCountMap(String str) {
        Map<Character, Integer> map = new HashMap<>();
        char[] chars = str.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            if (map.containsKey(chars[i])) {
                map.put(chars[i], map.get(chars[i]) + 1);
            } else {
                map.put(chars[i], 1);
            }
        }

        return map;
    }

}

Zero Sum Subarrays

Problem Statement: Given an array of size N , print the total count of sub-arrays having their sum equal to 0

Reference URL: Zero Sum Subarrays

Example:

Input: 0 0 5 5 0 0 Output: 6

Input: 6 -1 -3 4 -2 2 4 6 -12 -7 Output: 4

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//URL: https://practice.geeksforgeeks.org/problems/zero-sum-subarrays/0
//Description: Given an array of size N , print the total count of sub-arrays having their sum equal to 0
public class ZeroSumSubArrays {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCases = scanner.nextInt();

        for (int i = 0; i < testCases; i++) {
            int arrLength = scanner.nextInt();
            int[] arr = new int[arrLength];

            for (int j = 0; j < arrLength; j++) {
                arr[j] = scanner.nextInt();
            }

            System.out.println(zeroSumSubArrays(arr));
        }
    }

    public static int zeroSumSubArrays(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();

        int sum = 0;
        int zeroSumSubArraysCount = 0;

        //add a entry in map to handle zero sum
        map.put(0, 1);

        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];

            //if the sum repeats then count all the subarrays between occurences of sum
            //for example if the sum s repeats once then count = 1, but if it repeats twice then count = 1+2 = 3
            //if it repeats thrice then count=1+2+3 = 6 (n * n+1)/2 where n is the number of occurence and that's what below logic does
            if (map.containsKey(sum)) {
                zeroSumSubArraysCount += map.get(sum);
                map.put(sum, map.get(sum) + 1);
            } else {
                map.put(sum, 1);
            }

        }

        return zeroSumSubArraysCount;
    }
}

Longest consecutive sub-sequence

Problem Statement: Given an array of integers, find the length of the longest sub-sequence such that elements in the sub-sequence are consecutive integers, the consecutive numbers can be in any order.

Reference URL: Longest consecutive sub-sequence

Example:

Input: 2 6 1 9 4 5 3 Output: 6

Input: 1 9 3 10 4 20 2 Output: 4

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//URL: https://practice.geeksforgeeks.org/problems/longest-consecutive-subsequence/0
//Description: Given an array of integers, find the length of the longest sub-sequence
//such that elements in the sub-sequence are consecutive integers, the consecutive numbers can be in any order.

public class LongestConsecutiveSubSequence {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int testCases = scanner.nextInt();
        for (int i = 0; i < testCases; i++) {
            int arrLength = scanner.nextInt();
            int[] arr = new int[arrLength];

            for (int j = 0; j < arrLength; j++) {
                arr[j] = scanner.nextInt();
            }

            System.out.println(getLengthOfLongestConsecutiveSubSequence(arr));
        }
    }

    //Logic: is to add all array elements to map
    //Then iterate array, and for any element, increment by 1 and find in map, decrement by 1 and find in map
    //increment counter if found, and remove entry from hashmap if found
    //keep track of max count and return once all elements are iterated
    public static int getLengthOfLongestConsecutiveSubSequence(int[] arr) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int count = 0, maxCount = 0, key = 0;

        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i], 1);
        }

        for (int i = 0; i < arr.length; i++) {
            key = arr[i];
            count = 1;
            map.remove(key);

            //keep on adding 1 to key and incrementing counter if found
            while (true) {
                ++key;
                if (map.containsKey(key)) {
                    count++;
                    map.remove(key);
                } else {
                    break;
                }
            }

            key = arr[i];
            //keep on subtracting 1 from key and incrementing counter if found
            while (true) {
                --key;
                if (map.containsKey(key)) {
                    count++;
                    map.remove(key);
                } else {
                    break;
                }
            }

            maxCount = Math.max(maxCount, count);
        }

        return maxCount;
    }
}