Mark and Toys

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

public class Solution {

    // Complete the maximumToys function below.
    static int maximumToys(int[] prices, int k) {
        Arrays.sort(prices);
        int max = 0;
        int total = 0;
        for (int i = 0; i < prices.length; i++) {
            total += prices[i];
            if (total < k)
                max++;
            else
                return max;

        }
        return max;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nk = scanner.nextLine().split(" ");

        int n = Integer.parseInt(nk[0]);

        int k = Integer.parseInt(nk[1]);

        int[] prices = new int[n];

        String[] pricesItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < n; i++) {
            int pricesItem = Integer.parseInt(pricesItems[i]);
            prices[i] = pricesItem;
        }

        int result = maximumToys(prices, k);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

Find the Running Median

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

public class Solution {

    /*
     * Complete the runningMedian function below.
     */
    static double[] runningMedian(int[] a) {
        /*
         * Write your code here.
         */

        
        double[] out = new double[a.length];
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return -Integer.compare(o1, o2);
            }
        });
        double median = 0;
        if(a.length == 1) {
            out[0] = a[0];
            return out;
        }
        for (int i = 0; i < a.length; i++) {
            if( i == 0) {
                out[0] = a[0];
            } else if (i == 1) {
                minHeap.add(Integer.max(a[0], a[1]));
                maxHeap.add(Integer.min(a[0], a[1]));
                out[i] = ((double) a[i - 1] + (double) a[i]) / 2;
                median = out[i];
            } else {
                       
                if(a[i] > median) {
                   minHeap.add(a[i]);
               } else if(a[i]<= median) {
                   maxHeap.add(a[i]);
               }
                
                if(Math.abs(minHeap.size() - maxHeap.size())>1) {
                    if(minHeap.size() > maxHeap.size())
                        maxHeap.add(minHeap.remove());
                    else minHeap.add(maxHeap.remove());
                }
                
                
                if(minHeap.size() == maxHeap.size())
                out[i] = ((double)minHeap.peek() + (double) maxHeap.peek())/2;
                else if (minHeap.size() > maxHeap.size())
                    out[i] = minHeap.peek().doubleValue();
                else if (maxHeap.size() > minHeap.size())
                    out[i] = maxHeap.peek().doubleValue();
                median = out[i];
                
            }
        }
        return out;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int aCount = Integer.parseInt(scanner.nextLine().trim());

        int[] a = new int[aCount];

        for (int aItr = 0; aItr < aCount; aItr++) {
            int aItem = Integer.parseInt(scanner.nextLine().trim());
            a[aItr] = aItem;
        }

        double[] result = runningMedian(a);

        for (int resultItr = 0; resultItr < result.length; resultItr++) {
            bufferedWriter.write(String.valueOf(result[resultItr]));

            if (resultItr != result.length - 1) {
                bufferedWriter.write("\n");
            }
        }

        bufferedWriter.newLine();

        bufferedWriter.close();
    }
}

Pairs

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

public class Solution {

// Complete the pairs function below.
   static int pairs(int k, int[] arr) {
        HashSet<Integer> d = new HashSet<Integer>();
        for (int i = 0; i < arr.length; i++) {
            d.add(arr[i]);
        }
        int count = 0;
        for (int i : d) {
            if (d.contains(i + k)) {
                count++;
            }
        }
        return count;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nk = scanner.nextLine().split(" ");

        int n = Integer.parseInt(nk[0]);

        int k = Integer.parseInt(nk[1]);

        int[] arr = new int[n];

        String[] arrItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < n; i++) {
            int arrItem = Integer.parseInt(arrItems[i]);
            arr[i] = arrItem;
        }

        int result = pairs(k, arr);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

Contacts

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

public class Solution {

// Alphabet size (# of symbols)
    static final int ALPHABET_SIZE = 26;

    // trie node
    static class TrieNode {
        TrieNode[] children = new TrieNode[ALPHABET_SIZE];
        int repeats;
        // isEndOfWord is true if the node represents
        // end of a word
        boolean isEndOfWord;

        TrieNode() {
            isEndOfWord = false;
            repeats = 1;
            for (int i = 0; i < ALPHABET_SIZE; i++)
                children[i] = null;
        }
    };

    static TrieNode root;

    // If not present, inserts key into trie
    // If the key is prefix of trie node,
    // just marks leaf node
    static void insert(String key) {
        int level;
        int length = key.length();
        int index;

        TrieNode pCrawl = root;

        for (level = 0; level < length; level++) {
            index = key.charAt(level) - 'a';
            if (pCrawl.children[index] == null)
                pCrawl.children[index] = new TrieNode();
            else
                pCrawl.children[index].repeats++;

            pCrawl = pCrawl.children[index];
        }

        // mark last node as leaf
        pCrawl.isEndOfWord = true;
    }

    // Returns true if key presents in trie, else false
    static int countInTrie(String key) {
        int level;
        int length = key.length();
        int index;
        TrieNode pCrawl = root;

        for (level = 0; level < length; level++) {
            index = key.charAt(level) - 'a';

            if (pCrawl.children[index] == null)
                return 0;

            pCrawl = pCrawl.children[index];
        }
        return pCrawl.repeats;
    }

    // }
    /*
     * Complete the contacts function below.
     */
    static int[] contacts(String[][] queries) {
        root = new TrieNode();
        ArrayList<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < queries.length; i++) {
            if (queries[i][0].equals("add")) {
                insert(queries[i][1]);
            } else if (queries[i][0].equals("find")) {
                res.add(countInTrie(queries[i][1]));
            }
        }
        int[] result = new int[res.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = res.get(i);
        }
        return result;
    }


    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int queriesRows = Integer.parseInt(scanner.nextLine().trim());

        String[][] queries = new String[queriesRows][2];

        for (int queriesRowItr = 0; queriesRowItr < queriesRows; queriesRowItr++) {
            String[] queriesRowItems = scanner.nextLine().split(" ");

            for (int queriesColumnItr = 0; queriesColumnItr < 2; queriesColumnItr++) {
                String queriesItem = queriesRowItems[queriesColumnItr];
                queries[queriesRowItr][queriesColumnItr] = queriesItem;
            }
        }

        int[] result = contacts(queries);

        for (int resultItr = 0; resultItr < result.length; resultItr++) {
            bufferedWriter.write(String.valueOf(result[resultItr]));

            if (resultItr != result.length - 1) {
                bufferedWriter.write("\n");
            }
        }

        bufferedWriter.newLine();

        bufferedWriter.close();
    }
}

Tree: Level Order Traversal

import java.util.*;
import java.io.*;

class Node {
    Node left;
    Node right;
    int data;
    
    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class Solution {

    /* 
    
    class Node 
        int data;
        Node left;
        Node right;
    */
    public static void levelOrder(Node root) {
        StringBuilder out = new StringBuilder();
        Queue<Node> q = new LinkedList<Node>();
        q.add(root);
        
        while(!q.isEmpty()) {
            Node current= q.poll();
            out.append(current.data+" ");
            
            if(current.left != null) 
                q.add(current.left);
            
            if(current.right !=null)
                q.add(current.right);
            
        }
      
      System.out.println(out.toString());
      
      
    }

    public static Node insert(Node root, int data) {
        if(root == null) {
            return new Node(data);
        } else {
            Node cur;
            if(data <= root.data) {
                cur = insert(root.left, data);
                root.left = cur;
            } else {
                cur = insert(root.right, data);
                root.right = cur;
            }
            return root;
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        Node root = null;
        while(t-- > 0) {
            int data = scan.nextInt();
            root = insert(root, data);
        }
        scan.close();
        levelOrder(root);
    }   
}

BFS: Shortest Reach in a Graph

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

public class Solution {
    public static class Graph {

        ArrayList<ArrayList<Integer>> adj;
        int size;

        public Graph(int size) {
            adj = new ArrayList<ArrayList<Integer>>(size);
            for (int i = 0; i < size; i++)
                adj.add(new ArrayList<Integer>());
            this.size = size;
        }

        public void addEdge(int first, int second) {
            adj.get(first).add(second);
            adj.get(second).add(first);
        }

        public int[] shortestReach(int startId) { // 0 indexed
            int[] dist = new int[this.size];
            Arrays.fill(dist, -1);
            Queue<Integer> q = new LinkedList<Integer>();
            boolean v[] = new boolean[this.size];
            q.add(startId);
            v[startId] = true;
            dist[startId] = 0;

            while (!q.isEmpty()) {
                int current = q.poll();

                for (Integer distNode : adj.get(current)) {
                    if (!v[distNode]) {
                        v[distNode] = true;
                        dist[distNode] = dist[current] + 6;
                        q.add(distNode);
                    }
                }
            }

            return dist;
        }
    }

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

        int queries = scanner.nextInt();

        for (int t = 0; t < queries; t++) {

            // Create a graph of size n where each edge weight is 6:
            Graph graph = new Graph(scanner.nextInt());
            int m = scanner.nextInt();

            // read and set edges
            for (int i = 0; i < m; i++) {
                int u = scanner.nextInt() - 1;
                int v = scanner.nextInt() - 1;

                // add each edge to the graph
                graph.addEdge(u, v);
            }

            // Find shortest reach from node s
            int startId = scanner.nextInt() - 1;
            int[] distances = graph.shortestReach(startId);

            for (int i = 0; i < distances.length; i++) {
                if (i != startId) {
                    System.out.print(distances[i]);
                    System.out.print(" ");
                }
            }
            System.out.println();
        }

        scanner.close();
    }
}