Amazon OA

1. 2SumUniquePairs

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

public class twoSumUnique {
    public static int uniquepairs(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int res = 0;
        Map<Integer, Boolean> mapForPrev = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int diff = target - nums[i];
            if (mapForPrev.containsKey(diff)) {
                if (!mapForPrev.get(diff)) {
                    mapForPrev.put(diff, true);
                    res++;
                }
                mapForPrev.put(nums[i], true);
            } else {
                mapForPrev.put(nums[i], false);
            }
        }
        return res;
    }
    
    public static void main(String[] args) {
        int[] nums1 = { 1, 1, 2, 45, 46, 46 };
        int target1 = 47;
        System.out.println(uniquepairs(nums1, target1));
        System.out.println("-------------------------------");
        int[] nums2 = {1, 5, 1, 5};
        int target2 = 6;
        System.out.println(uniquepairs(nums2, target2));
    }
}

2. SubTree

public class subtree {    
    public boolean isSubtree(TreeNode s, TreeNode t){
        return isSubtree(s, t, false);
    }
    
    public boolean isSubtree(TreeNode s, TreeNode t, boolean flag) {
        if (s == null || t == null) {
            if (s == null && t == null) {
                return true;
            } else {
                return false;
            }      
        }

        if (s.val != t.val && flag){
            return false;
        }
        
        if (s.val == t.val) {
            flag = true;
            if (isSubtree(s.left, t.left, true) && isSubtree(s.right, t.right, true)) {
                 return true;
            }
        }        
        return isSubtree(s.left, t, false) || isSubtree(s.right, t, false);        
    }
    
}

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
}

3. Search 2D

public class search2D {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        
        int row = matrix.length, col = matrix[0].length;
        int i = 0, j = col - 1;
        while (i < row && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                i++;
            } else if (matrix[i][j] > target) {
                j--;
            }
        }
        return false;
    }
}

4. Spiral Matrix

public class spiralMatrix {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        if (n <= 0) {
            return res;
        }
        int rowBegin = 0, rowEnd = n - 1;
        int colBegin = 0, colEnd = n - 1;
        int num = 1;
        while (rowBegin <= rowEnd && colBegin <= colEnd) {
            for (int j = colBegin; j <= colEnd; j++) {
                res[rowBegin][j] = num++;
            }
            rowBegin++;
            
            for (int i = rowBegin; i <= rowEnd; i++) {
                res[i][colEnd] = num++;
            }
            colEnd--;
            
            for (int k = colEnd; k >= colBegin; k--) {
                res[rowEnd][k] = num++;
            }
            rowEnd--;
            
            for (int m = rowEnd; m >= rowBegin; m--) {
                res[m][colBegin] = num++;
            }
            colBegin++;
        }
        return res;
    }
}

5. Merge 2 sorted Linked List

//import java.util.LinkedList;

public class mergeTwoLists {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        }
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        if (l1 != null) {
            prev.next = l1;
        }
        if (l2 != null) {
            prev.next = l2;
        }
        return dummy.next;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

6. Copy Random Pointer

import java.util.*;

class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};

public class copyRandomPointer {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        
        Node temp = head;
        while (temp != null) {
            Node next = temp.next;
            temp.next = new Node(temp.val, null, null);
            temp.next.next = next;
            temp = next;
        }
        
        temp = head;
        while (temp != null) {
            if (temp.random != null) {
                temp.next.random = temp.random.next;
            }
            temp = temp.next.next;
        }
        
        temp = head;
        Node copyHead = head.next;
        Node copy = copyHead;
        while (copy.next != null) {
            temp.next = temp.next.next;
            temp = temp.next;
            copy.next = copy.next.next;
            copy = copy.next;
        }
        
        temp.next = temp.next.next;
        return copyHead;
    }
}

7. Critical Connections

8. Favorite Geren