Add solutions of 8 problems of CTCI tutorial

rajatgoyal715 · rajatgoyal715 · commit b3258a2f6182 · 2018-08-01T14:59:53.000+05:30
- A tale of two stacks
- Balanced Brackets
- Contacts
- Davis Staircase
- Fibonacci Numbers
- FInd The Running Median
- Is this a binary search tree
- Lonely Integer
diff --git a/CrackingTheCodingInterview/ATaleOfTwoStacks.java b/CrackingTheCodingInterview/ATaleOfTwoStacks.java
@@ -0,0 +1,50 @@
+import java.io.*;
+import java.util.*;
+
+public class ATaleOfTwoStacks {
+
+    public static class MyQueue<T> {
+        Stack<T> stackNewestOnTop = new Stack<T>();
+        Stack<T> stackOldestOnTop = new Stack<T>();
+
+        public void enqueue(T value) { // Push onto newest stack
+            stackNewestOnTop.add(value);
+        }
+
+        public T peek() {
+            if(!stackOldestOnTop.isEmpty()) return stackOldestOnTop.peek();
+            while(!stackNewestOnTop.isEmpty()){
+                stackOldestOnTop.add(stackNewestOnTop.pop());
+            }
+            return stackOldestOnTop.peek();
+        }
+
+        public T dequeue() {
+            if(!stackOldestOnTop.isEmpty()) return stackOldestOnTop.pop();
+            while(!stackNewestOnTop.isEmpty()){
+                stackOldestOnTop.add(stackNewestOnTop.pop());
+            }
+            return stackOldestOnTop.pop();
+        }
+    }
+    
+    public static void main(String[] args) {
+        MyQueue<Integer> queue = new MyQueue<Integer>();
+        
+        Scanner scan = new Scanner(System.in);
+        int n = scan.nextInt();
+        
+        for (int i = 0; i < n; i++) {
+            int operation = scan.nextInt();
+            if (operation == 1) { // enqueue
+                queue.enqueue(scan.nextInt());
+            } else if (operation == 2) { // dequeue
+                queue.dequeue();
+            } else if (operation == 3) { // print/peek
+                System.out.println(queue.peek());
+            }
+        }
+        scan.close();
+    }
+
+}
diff --git a/CrackingTheCodingInterview/BalancedBrackets.java b/CrackingTheCodingInterview/BalancedBrackets.java
@@ -0,0 +1,37 @@
+import java.io.*;
+import java.util.*;
+
+public class BalancedBrackets {
+
+    public static boolean isBalanced(String expression) {
+        Stack<Character> stack = new Stack<>();
+        for (char curr : expression.toCharArray()) {
+            if (curr == '{' || curr == '(' || curr == '[')
+                stack.push(curr);
+            else {
+                if (stack.isEmpty())
+                    return false;
+                char last = (char) stack.pop();
+                if ((curr == '}' && last != '{') || (curr == ']' && last != '[') || (curr == ')' && last != '('))
+                    return false;
+            }
+        }
+        return stack.isEmpty();
+    }
+
+    public static void main(String[] args) {
+        Scanner sc = new Scanner(System.in);
+        int t = Integer.parseInt(sc.nextLine());
+
+        StringBuilder sb = new StringBuilder();
+
+        for (int i = 0; i < t; i++) {
+            String expression = sc.nextLine();
+            sb.append(isBalanced(expression) ? "YES\n" : "NO\n");
+        }
+
+        System.out.println(sb.toString());
+
+        sc.close();
+    }
+}
diff --git a/CrackingTheCodingInterview/Contacts.java b/CrackingTheCodingInterview/Contacts.java
@@ -0,0 +1,59 @@
+import java.io.*;
+import java.util.*;
+
+public class Contacts {
+
+    static class Trie {
+        int count;
+        Trie[] children;
+
+        public Trie() {
+            children = new Trie[26];
+        }
+
+        void addWord(String word) {
+            count++;
+            if(word.isEmpty()) return;
+            char first = word.charAt(0);
+            if(children[first-'a'] == null){
+                children[first-'a'] = new Trie();
+            }
+            children[first-'a'].addWord(word.substring(1));
+        }
+
+        int findWord(String word) {
+            if(word.isEmpty()) return count;
+            char first = word.charAt(0);
+            if(children[first-'a'] == null) return 0;
+            return children[first-'a'].findWord(word.substring(1));
+        }
+    }
+
+    public static void main(String[] args) {
+        Scanner sc = new Scanner(System.in);
+        int n = Integer.parseInt(sc.nextLine());
+
+        Trie trie = new Trie();
+        StringBuilder res = new StringBuilder();
+
+        String[] opContact = new String[2];
+        String op, contact;
+        int count;
+        for (int nItr = 0; nItr < n; nItr++) {
+            opContact = sc.nextLine().split(" ");
+            op = opContact[0];
+            contact = opContact[1];
+
+            if (op.equals("add")) {
+                trie.addWord(contact);
+            } else {
+                count = trie.findWord(contact);
+                res.append(count + "\n");
+            }
+        }
+
+        System.out.println(res.toString());
+
+        sc.close();
+    }
+}
diff --git a/CrackingTheCodingInterview/DavisStaircase.java b/CrackingTheCodingInterview/DavisStaircase.java
@@ -0,0 +1,44 @@
+import java.io.*;
+import java.util.*;
+
+public class DavisStaircase {
+
+    static int[] res;
+    static int mod = 1000000007;
+
+    //Complete the stepPerms function below.
+    public static int stepPerms(int n) {
+        if(n == 0) return 1;
+        if(n < 0) return 0;
+        if(res[n] == -1) {
+            int sum = stepPerms(n-3) + stepPerms(n-2) + stepPerms(n-1);
+            res[n] = sum;
+        }
+        return res[n];
+    }
+
+    public static void stepPerms2(int n) {
+        res[1] = 1;
+        res[2] = 2;
+        res[3] = 4;
+        for(int i=4;i<=n;i++){
+            res[i] = res[i-1] + res[i-2] + res[i-3];
+        }
+    }
+
+    public static void main(String[] args) {
+        res = new int[37];
+        for(int i=0;i<37;i++) res[i] = -1;
+        stepPerms(36);
+
+        Scanner sc = new Scanner(System.in);
+        int n = sc.nextInt();
+        int num;
+        for (int i = 0; i < n; i++) {
+            num = sc.nextInt();
+            System.out.println(res[num]);
+        }
+
+        sc.close();
+    }
+}
diff --git a/CrackingTheCodingInterview/FibonacciNumbers.java b/CrackingTheCodingInterview/FibonacciNumbers.java
@@ -0,0 +1,25 @@
+import java.util.*;
+
+public class FibonacciNumbers {
+
+    public static int fibonacci(int n) {
+        int a = 0, b = 1, c = 1;
+        if (n == 0)
+            return a;
+        else if (n == 1)
+            return b;
+        for (int i = 1; i < n; i++) {
+            c = a + b;
+            a = b;
+            b = c;
+        }
+        return c;
+    }
+
+    public static void main(String[] args) {
+        Scanner scanner = new Scanner(System.in);
+        int n = scanner.nextInt();
+        scanner.close();
+        System.out.println(fibonacci(n));
+    }
+}
diff --git a/CrackingTheCodingInterview/FindTheRunningMedian.java b/CrackingTheCodingInterview/FindTheRunningMedian.java
@@ -0,0 +1,42 @@
+import java.io.*;
+import java.text.DecimalFormat;
+import java.util.*;
+
+public class FindTheRunningMedian {
+
+    public static void main(String[] args) {
+        Scanner sc = new Scanner(System.in);
+        int n = Integer.parseInt(sc.nextLine());
+
+        PriorityQueue<Double> small = new PriorityQueue<>(1, Collections.reverseOrder());
+        PriorityQueue<Double> large = new PriorityQueue<>(1);
+
+        StringBuilder sb = new StringBuilder();
+        double num, ans;
+        DecimalFormat df = new DecimalFormat("#.0");
+        for (int i = 0; i < n; i++) {
+            num = Integer.parseInt(sc.nextLine());
+            if(small.isEmpty() || (num < small.peek())) small.add(num);
+            else if(large.isEmpty() || (num > large.peek())) large.add(num);
+            else small.add(num);
+
+            while(small.size() > large.size()+1) {
+                large.add(small.poll());
+            }
+
+            while(large.size() > small.size()) {
+                small.add(large.poll());
+            }
+
+            if(small.size() == large.size()) ans = (small.peek() + large.peek())/2;
+            else if(small.size() < large.size()) ans = large.peek();
+            else ans = small.peek();
+
+            sb.append(df.format(ans)+"\n");
+        }
+
+        System.out.println(sb.toString());
+
+        sc.close();
+    }
+}
diff --git a/CrackingTheCodingInterview/IsThisABinarySearchTree.java b/CrackingTheCodingInterview/IsThisABinarySearchTree.java
@@ -0,0 +1,19 @@
+/* Hidden stub code will pass a root argument to the function below. Complete the function to solve the challenge. Hint: you may want to write one or more helper functions.  
+
+The Node class is defined as follows:
+    class Node {
+        int data;
+        Node left;
+        Node right;
+     }
+*/
+
+boolean checkBSTUtil(Node root, int max, int min) {
+    if (root == null) return true;
+    if (root.data < max && root.data > min) return checkBSTUtil(root.left, root.data, min) && checkBSTUtil(root.right, max, root.data);
+    return false;
+}
+
+boolean checkBST(Node root) {
+    return checkBSTUtil(root, 10001, -1);
+}
diff --git a/CrackingTheCodingInterview/LonelyInteger.java b/CrackingTheCodingInterview/LonelyInteger.java
@@ -0,0 +1,29 @@
+import java.io.*;
+import java.util.*;
+
+public class LonelyInteger {
+
+    // Complete the findLonely function below.
+    static int findLonely(int[] arr) {
+        int xor = arr[0];
+        for(int i = 1; i < arr.length; i++){
+            xor = xor ^ arr[i];
+        }
+        return xor;
+    }
+
+    public static void main(String[] args) {
+        Scanner sc = new Scanner(System.in);
+        int n = Integer.parseInt(sc.nextLine());
+        String[] arrItems = sc.nextLine().split(" ");
+        int[] arr = new int[n];
+        for (int i = 0; i < n; i++) {
+            arr[i] = Integer.parseInt(arrItems[i]);
+        }
+
+        int res = findLonely(arr);
+        System.out.println(res);
+
+        sc.close();
+    }
+}
