Amazon0

Amazon0.java

package com.company;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Amazon {


    static <E extends Comparable<E>> ArrayList<E> mergedArray(ArrayList<E> array1, ArrayList<E> array2) {
        ArrayList<E> merged = new ArrayList<>();
        int i = 0;
        int j = 0;
        int l1 = array1.size();
        int l2 = array2.size();

        while (i < l1 && j < l2) {
            E a1i = array1.get(i);
            E a2j = array2.get(j);
            if (a1i.compareTo(a2j) < 0) {
                merged.add(a1i);
                i++;
            } else if (a1i.compareTo(a2j) > 0) {
                merged.add(a2j);
                j++;
            } else {
                merged.add(a1i);
                merged.add(a2j);
                i++;
                j++;
            }
        }

        if (i == l1) {
            merged.addAll(array2.subList(j, l2));
        } else {
            merged.addAll(array1.subList(i, l1));
        }

        return merged;
    }


    static <E> LinkedList<E> reversedLinedList(LinkedList<E> list) {
        LinkedList<E> reversed = new LinkedList<E>();
        Iterator<E> i = list.descendingIterator();
        while (i.hasNext()) {
            reversed.add(i.next());
        }
        return reversed;
    }


    static <E> E nthLastFromLinkedList(LinkedList<E> list, int n) {
        if (list.size() >= n) {
            int i = list.size() - n;
            E e = list.get(i);
            return e;
        } else {
            throw new IllegalArgumentException("nth must less than linked list size");
        }
    }


    static long intFromIP(String ip) throws NumberFormatException {
        String[] parts = ip.split("\\.");

        if (parts.length == 4) {
            long result = 0;

            for (int i = 0; i < parts.length; i++) {
                long parsed;
                try {
                    parsed = Long.parseLong(parts[i]);
                } catch (NumberFormatException inner) {
                    String m = "Can't parse every part of ip into integer";
                    NumberFormatException outer = new NumberFormatException(m);
                    outer.initCause(inner);
                    throw outer;
                }
                int l = 8 * (3 - i);
                result = result + (parsed << l);
            }

            return result;
        } else {
            throw new IllegalArgumentException("Can't split ip with '.'");
        }
    }


    static boolean isParenthesesValid(String equation) {
        return isParenthesesValid(equation, 0);
    }

    static boolean isParenthesesValid(String equation, int found) {
        int l = equation.length();
        if (l > 0) {
            char token = equation.charAt(0);
            String reset = equation.substring(1);

            if (token == '(') {
                return isParenthesesValid(reset, found + 1);
            } else if (token == ')') {
                if (found > 0) {
                    return isParenthesesValid(reset, found - 1);
                } else {
                    return false;
                }
            } else {
                return isParenthesesValid(reset, found);
            }
        } else if (l == 0 && found == 0) {
            return true;
        } else {
            return false;
        }
    }


    static Map<Character, Integer> occurrences(String s) {
        Map<Character, Integer> count = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (count.containsKey(c)) {
                int v = count.get(c);
                count.put(c, v + 1);
            } else {
                count.put(c, 1);
            }
        }
        return count;
    }


    static int[] twoSum(int target, HashMap<Integer, Integer> cache) {

        for (int k : cache.keySet()) {
            int complement = target - k;
            if (cache.containsKey(complement)) {
                if (complement == k && cache.get(k) >= 2) {
                    return new int[]{k, k};
                } else if (complement != k) {
                    return new int[]{k, complement};
                }
            }
        }

        return new int[]{};
    }

    static int[] twoSum(int[] array, int target) {
        HashMap<Integer, Integer> cache = new HashMap<>();

        for (int k : array) {
            if (cache.containsKey(k)) {
                int v = cache.get(k);
                cache.put(k, v + 1);
            } else {
                cache.put(k, 1);
            }
        }

        return twoSum(target, cache);

    }

    static int[] threeSum1(int[] array, Integer target) {

        for (int i : array) {
            int[] rest = Arrays.copyOfRange(array, i + 1, array.length);
            int[] twoSum = twoSum(rest, target - i);
            if (twoSum.length > 0) {
                return new int[]{i, twoSum[0], twoSum[1]};
            }
        }

        return new int[]{};
    }

    static int[] threeSum2(int[] array, Integer target) {
        HashMap<Integer, Integer> cache = new HashMap<>();

        for (int k : array) {
            if (cache.containsKey(k)) {
                int v = cache.get(k);
                cache.put(k, v + 1);
            } else {
                cache.put(k, 1);
            }
        }

        Set<Integer> set = IntStream.of(array).boxed().collect(Collectors.toSet());
        for (int i : set) {

            if (cache.get(i) == 1) {
                cache.remove(i);
            } else {
                cache.put(i, cache.get(i) - 1);
            }

            int[] twoSum = twoSum(target - i, cache);

            if (cache.containsKey(i)) {
                cache.put(i, cache.get(i) + 1);
            } else {
                cache.put(i, 1);
            }

            if (twoSum.length > 0) {
                return new int[]{i, twoSum[0], twoSum[1]};
            }
        }

        return new int[]{};
    }


    static class Tree {
        int current;
        Tree left;
        Tree right;

        Tree(int current) {
            this.current = current;
        }

        Tree(Tree left, int current, Tree right) {
            this.left = left;
            this.current = current;
            this.right = right;
        }
    }

    static boolean isBST(Tree t) {
        return isBST(t, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    static boolean isBST(Tree t, int min, int max) {
        if (t.left == null && t.right == null) {
            return true;
        } else if (t.left != null && t.right != null) {
            if (t.current >= min && t.current <= max) {
                boolean valid1 = isBST(t.left, min, t.current - 1);
                boolean valid2 = isBST(t.right, t.current + 1, max);
                return valid1 && valid2;
            } else {
                return false;
            }

        } else {
            return false;
        }
    }


    static int[] deduplicated(int[] a1, int[] a2) {
        Stream<Integer> stream = IntStream.concat(
                IntStream.of(a1),
                IntStream.of(a2)
        ).boxed();
        Set<Integer> set = stream.collect(Collectors.toSet());
        return set.stream().mapToInt(i -> i).toArray();
    }


    static class Point {
        double x;
        double y;
        double distance;


        public Point(double x, double y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString(){
            return String.format("x: <%f> y: <%f> distance: <%f>", x, y, distance);
        }
    }

    static class PointComparator implements Comparator<Point> {
        @Override
        public int compare(Amazon.Point p1, Amazon.Point p2) {
            return Double.compare(p1.distance, p2.distance);
        }
    }

    static Point[] nearestPoints(Point[] points, Point target, int count) {

        for (Point p : points) {
            p.distance = Math.pow(target.x - p.x, 2) + Math.pow(target.y - p.y, 2);
        }

        Comparator<Point> c = new PointComparator();
        PriorityQueue<Point> heap = new PriorityQueue<>(count, c);

        int i = 0;
        while (i < count) {
            heap.add(points[i]);
            i++;
        }

        while(i < points.length){
            Point nearest = heap.peek();
            if (points[i].distance < nearest.distance) {
                if (heap.size() == count) {
                    heap.poll();
                }
                heap.add(points[i]);
            }
            i++;
        }

        Point[] nearest = new Point[count];
        heap.toArray(nearest);
        return nearest;
    }

    static char firstFromStream(InputStream s) throws IOException {
        int readed;

        try {
            readed = s.read();
        } catch (IOException inner) {
            String m = "Can't read the first byte of stream";
            IOException outer = new IOException(m);
            outer.initCause(inner);
            throw outer;
        }

        return (char) readed;

    }


    public static void main(String[] args) {

        //    3232235777
        //    true
        //    true
        //    true
        //    false
        //    false
        //    true
        //    [1, 2, 3, 4, 5, 6, 8]
        //    [3, 2, 1]
        //    2
        //    {q=2, a=2, s=2, d=2, e=2, w=2}
        //    [2, 2]
        //    [1, 2, 4]
        //    [1, 2, 4]
        //    [1, 2, 3, 4, 6]
        //    [x: <1.000000> y: <2.000000> distance: <1.000000>, x: <1.000000> y: <3.000000> distance: <4.000000>, x: <1.000000> y: <4.000000> distance: <9.000000>]
        //    h

        System.out.println(intFromIP("192.168.1.1"));

        Tree t = new Tree(
                new Tree(
                        new Tree(0),
                        1,
                        new Tree(2)
                ),
                3,
                new Tree(
                        new Tree(4),
                        5,
                        new Tree(6)
                )
        );
        System.out.println(isBST(t));
        t = new Tree(3);
        System.out.println(isBST(t));

        System.out.println(isParenthesesValid("(1+2)-3"));
        System.out.println(isParenthesesValid("(1+2)(-3"));
        System.out.println(isParenthesesValid("(1+2))-3"));
        System.out.println(isParenthesesValid("((1+2))-3"));

        ArrayList<Integer> a1 = new ArrayList<Integer>() {{
            add(1);
            add(3);
            add(5);
            add(8);
        }};
        ArrayList<Integer> a2 = new ArrayList<Integer>() {{
            add(2);
            add(4);
            add(6);
        }};
        System.out.println(mergedArray(a1, a2));

        LinkedList<Integer> l = new LinkedList<Integer>() {{
            add(1);
            add(2);
            add(3);
        }};
        System.out.println(reversedLinedList(l));

        System.out.println(nthLastFromLinkedList(l, 2));

        System.out.println(occurrences("qweqweasdasd"));

        System.out.println(Arrays.toString(
                twoSum(new int[]{1, 2, 2, 4}, 4))
        );

        System.out.println(Arrays.toString(
                threeSum1(new int[]{1, 2, 2, 4, 6, 3}, 7))
        );
        System.out.println(Arrays.toString(
                threeSum2(new int[]{1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 6, 3}, 7))
        );

        System.out.println(Arrays.toString(
                deduplicated(
                        new int[]{3, 4, 4, 6, 3},
                        new int[]{1, 2, 2, 2, 2, 2, 2, 2,}
                )
        ));

        System.out.println(Arrays.toString(
                nearestPoints(new Point[]{
                                new Point(1, 2),
                                new Point(1, 3),
                                new Point(1, 4),
                                new Point(1, 5),
                                new Point(1, 6),
                                new Point(1, 7),
                                new Point(1, 8),
                        },
                        new Point(1, 1),
                        3
                )));

        try {
            System.out.println(firstFromStream(
                    new ByteArrayInputStream(
                            "hello world".getBytes()
                    )
            ));
        } catch (IOException e) {
            e.printStackTrace();
            System.out.println(e.getMessage());
        }


    }
}

amazon0.py

import sys


def int_from_ip(ip):
    if type(ip) is str:
        parts = ip.split(".")
        if len(parts) == 4:
            try:
                parts = [int(i) for i in parts]
            except ValueError:
                return False
            r = (parts[0] << 24) + (parts[1] << 16) + (parts[2] << 8) + (parts[3])
            return r
        else:
            return False
    else:
        return False


class Tree:
    def __init__(self, current, left=None, right=None):
        self.current = current
        self.left = left
        self.right = right


def is_bst(tree, min=-sys.maxsize, max=sys.maxsize):
    if type(tree) is int:
        return True
    elif type(tree) is Tree:
        if tree.left is not None and tree.right is not None:
            if min <= tree.current <= max:
                valid1 = is_bst(tree.left, min, tree.current - 1)
                valid2 = is_bst(tree.right, tree.current + 1, max)
                return valid1 and valid2
            else:
                return False
        elif tree.left is None and tree.right is None:
            return True
        else:
            return False
    else:
        return False


def is_parentheses_valid(equation, found=0):
    if type(equation) is str:
        l = len(equation)
        if l > 0:
            token = equation[0]
            rest = equation[1:]

            if token == "(":
                return is_parentheses_valid(rest, found + 1)
            elif token == ")":
                if found > 0:
                    return is_parentheses_valid(rest, found - 1)
                else:
                    return False
            else:
                return is_parentheses_valid(rest, found)
        elif l == 0 and found == 0:
            return True
        else:
            return False
    else:
        return False


# 3232235777
# True
# True
# True
# False
# False
# True

print(int_from_ip("192.168.1.1"))

t = Tree(3, Tree(1, 0, 2), Tree(5, 4, 6))
print(is_bst(t))
t = Tree(3)
print(is_bst(t))

print(is_parentheses_valid("(1+2)-3"))
print(is_parentheses_valid("(1+2)(-3"))
print(is_parentheses_valid("(1+2))-3"))
print(is_parentheses_valid("((1+2))-3"))