Programming practice for interviews - Don't use an IDE!

Questions.md

1. Take an absolute path and reduce it: /a/b/../foo.txt -> /a/foo.txt, /a/../b/./foo.txt -> /b/foo.txt

2. You are given an array representing integer. Write a function which increments this integer. Example: input [1,2,3] -> output [1,2,4] which represents 123 + 1 = 124

3. Given an unbalanced binary tree, write code to select a node at random (each node has an equal probability of being selected).

4. You have an array of integers. Each integer in the array should be listed three times in the array. Find the integer which does not comply to that rule.

5. Count triangles in an undirected graph where a triangle is a unique set of three vertices connected to one another.

6. Find the longest common prefix in a list of phrases. For instance; "i love all dogs", "i love cats" should return "i love ".

7. Given a binary tree, implement an iterator that will iterate through its elements.

8. Write a function to add 2 numbers without using +.

9. Write a method to replace all spaces in a string with'%20'. You may assume that the string has sufficient space at the end of the string to hold the additional characters, and that you are given the "true" length of the string. (Note: if implementing in Java, please use a character array so that you can perform this operation in place.) Input: "Mr John Smith " Output: "Mr%20John%20Smith"

10. You have two numbers represented by a linked list, where each node contains a single digit. Write a function that adds the two numbers and returns the sum as a linked list.

Solutions.java

package com.tylerrockwood.practice;

import java.util.*;

/**
 *  Using Java 8
 *  DON'T PEEK!
 */
public class Solution {


    /*
     *
     Take an absolute path and reduce it:

     Input:
     /a/b/../foo.txt
     /a/../b/./foo.txt
     Output:
     /a/foo.txt
     /b/foo.txt

     time: O(n)
     space: O(n)

     *
     */
    public static String problem1(String input) {
        String[] paths = input.split("/");
        Stack<String> output = new Stack<>();
        for (String path : paths) {
            if (path.equals("..")) {
                output.pop();
            } else if (!path.equals(".")) {
                output.push(path);
            }
        }
        return String.join("/", output.toArray(new String[output.size()]));
    }


    /*
     *
    You are given an array representing integer. Write a function which increments this integer.
    Example: input [1,2,3] (represents 123) -> output [1,2,4]

    time: O(n)
    space: O(n) in the worst case :(

     */
    public static int[] problem2(int[] num) {
        for (int i = num.length - 1; i >= 0; i--) {
            num[i] += 1;
            if (num[i] >= 10 && i == 0) {
                num[0] = 0;
                int[] newNum = new int[num.length + 1];
                newNum[0] = 1;
                System.arraycopy(num, 0, newNum, 1, num.length);
                num = newNum;
            } else if (num[i] >= 10) {
                num[i] = 0;
            } else {
                break;
            }
        }
        return num;
    }

    public static class Node {
        public int value;
        public List<Node> children = new LinkedList<>();

        @Override
        public String toString() {
            return "Node:"+ value;
        }
    }

    /*
    Given an unbalanced binary tree, write code to select a node at random
    (each node has an equal probability of being selected).

    Time: O(n)
    Space: O(2)

     */
    public static Node problem3(Node root) {
        Node selected = null;
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        int number = 1;
        while(!stack.isEmpty()) {
            Node current = stack.pop();
            for(Node child : current.children) {
                stack.push(child);
            }
            System.out.println("Node" + current.value + ": has chance 1/" + number);
            if(Math.random() <= (1.0/number)) {
                selected = current;
            }
            number++;
        }
        return selected;
    }

    /*
    You have an array of integers. Each integer in the array should be
    listed three times in the array. Find the integer which does not comply to that rule.

    O(n) in time and space

     */
    public static int problem4(int[] nums) throws Exception {
        Map<Integer, Integer> frequency = new LinkedHashMap<>();
        for (Integer num : nums) {
            frequency.put(num, frequency.getOrDefault(num, 0) + 1);

        }
        for (Integer i : frequency.keySet()) {
            if(frequency.get(i) != 3) {
                return i;
            }
        }
        throw new Exception("Valid list?!?!");
    }

    /*
    Count triangles in an undirected graph where a triangle is a
    unique set of three vertices connected to one another.

    Time: O(n^3)
    Space: O(1)
     */
    public static int problem5(int[][] graph) {
        int count = 0;
        for (int v = 0; v < graph.length; v++) {
            for(int e1 = v + 1; e1 < graph.length; e1++) {
                if(graph[v][e1] == 0) {
                    continue;
                }
                for(int e2 = e1 + 1; e2 < graph.length; e2++) {
                    if(graph[v][e2] == 0) {
                        continue;
                    }
                    count += graph[e1][e2] == 1 ? 1 : 0;
                }
            }
        }
        return count;
    }

    /*
    Find the longest common prefix in a list of phrases.
    For instance; "i love all dogs", "i love cats" should return "i love".

    Time: O(n), space: O(n)
     */
    public static String problem6(String[] input) {
        StringBuilder prefix = new StringBuilder();
        prefix.append(input[0]);
        for (int j = 1; j < input.length; j++) {
            String phrase = input[j];
            int i = 0;
            for(; i < phrase.length(); i++) {
                char c1 = phrase.charAt(i);
                char c2 = prefix.charAt(i);
                if (c1 != c2) {
                    break;
                }
            }
            prefix.delete(i, prefix.length());
        }
        return prefix.toString();
    }

    public static class BinaryNode {
        public int value;
        public BinaryNode left;
        public BinaryNode right;

        @Override
        public String toString() {
            return "Node:"+ value;
        }
    }

    /*
    Given a binary tree, implement an iterator that will iterate through its elements.
    // DFS, for BFS use a Queue
    DFS == preorder
    BFS == level order
    Time: O(n), space: O(n)
     */

    public static Iterable<BinaryNode> problem7(BinaryNode root) {
        return new Iterable<BinaryNode>() {
            @Override
            public Iterator<BinaryNode> iterator() {
                Stack<BinaryNode> stack = new Stack<>();
                stack.push(root);
                return new Iterator<BinaryNode>() {
                    public boolean hasNext() {
                        return !stack.isEmpty();
                    }

                    public BinaryNode next() {
                        BinaryNode current = stack.pop();
                        if (current.right != null) {
                            stack.push(current.right);
                        }
                        if (current.left != null) {
                            stack.push(current.left);
                        }
                        return current;
                    }
                };
            }
        };
    }
    
    	static int add(int a, int b) {
		int carryIn = 0;
		int result = 0;
		for(int i = 0; i < 32; i++) {
			int aBit = a & (1 << i);
			int bBit = b & (1 << i);
			int c = (aBit ^ bBit) ^ (carryIn << i);
			result |= c;
			if ((aBit & bBit) != 0) {
				carryIn = 1;
			} else if ((aBit ^ bBit) == 0) {
				carryIn = 0;
			}
		}
		return result;
	}
	
	static char[] replaceSpace(char[] string, int length) {
		int count = string.length - 1;
		for (int i = length - 1; i >= 0; i--) {
			if(string[i] != ' ') {
				string[count] = string[i];
			} else {
				string[count] = '0';
				string[count - 1] = '2';
				string[count - 2] = '%';
				count -= 2;
			}
			count--;
		}
		return string;
	}
	
	static class LinkedNode {
		int value;
		LinkedNode next;
	}

	static int addLinkedListNums(LinkedNode a, LinkedNode b) {
		int num1 = 0;
		int num2 = 0;
		while(a != null) {
			num1 *= 10;
			num1 += a.value;
			a = a.next;
		}
		while(b != null) {
			num2 *= 10;
			num2 += b.value;
			b = b.next;
		}
		return num1 + num2;
	}

    public static void main(String[] args) throws Exception {
        System.out.println(problem1("/a/b/../foo.txt"));
        System.out.println(problem1("/a/../b/./foo.txt"));
        System.out.println(Arrays.toString(problem2(new int[]{1, 2, 3})));
        System.out.println(Arrays.toString(problem2(new int[]{9, 9, 9})));
        Node root = new Node();
        root.value = 0;
        Node child1 = new Node();
        child1.value = 1;
        Node child2 = new Node();
        child2.value = 2;
        root.children.add(child1);
        root.children.add(child2);
        System.out.println(problem3(root));
        System.out.println(problem4(new int[]{9, 9, 9, 1, 2, 3, 0, 1, 2, 3, 1, 2, 3}));
        System.out.println(problem4(new int[]{9, 9, 9, 1, 2, 1, 2, 3, 1, 2, 3}));
        System.out.println(problem5(new int[][]{{0, 1, 1}, {1, 0, 1}, {1, 1, 0}}));
        System.out.println("prefix = |" + problem6(new String[]{"I love all dogs", "I love cats"})  + "|");
        BinaryNode stump = new BinaryNode();
        stump.value = 0;
        BinaryNode leaf1 = new BinaryNode();
        leaf1.value = 1;
        BinaryNode leaf2 = new BinaryNode();
        leaf2.value = 2;
        stump.left = leaf1;
        stump.right = leaf2;
        for (BinaryNode n : problem7(stump)) {
            System.out.println(n);
        }
        System.out.println(add(1, 2));
	System.out.println(add(0, 0));
	System.out.println(add(1, 0));
	System.out.println(add(10, 15));
	replaceSpace("Mr John Smith    ".toCharArray(), 13);
	LinkedNode a = new LinkedNode();
	a.value = 1;
	a.next = new LinkedNode();
	a.next.value = 8;
	LinkedNode b = new LinkedNode();
	b.value = 2;
	b.next = new LinkedNode();
	b.next.value = 4;
	int c = addLinkedListNums(a, b);
	System.out.println(c);
    }
}