Amazon OA2 Coding(Part 1)

amazon_logo_500500-_v323939215_

* 如果代码没有主函数则说明此题是leetcode原题,否则都可以直接编译运行。代码仅供参考,读者有责任判断代码正确性,amethlex.com不承担由此产生的一切责任。

1.Search a 2D Matrix
Problem:
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Code:

public static boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0) return false;
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = m * n - 1;
        while(left <= right) 
        { 
            int middle = left + (right - left) / 2; 
            int i = middle / n; 
            int j = middle % n; 
            if(matrix[i][j] == target) return true; 
            else if(matrix[i][j] > target) right = middle - 1;
            else left = middle + 1;
        }
        return false;
    }

2.Valid Parentheses
Problem:
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.
Code:

import java.util.*;
public class Solution {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(char c: s.toCharArray())
        {
            if(c == ')')
            {
                if(!stack.empty() && stack.peek() == '(') stack.pop();
                else return false;
            }
            else if(c == ']')
            {
                if(!stack.empty() && stack.peek() == '[') stack.pop();
                else return false;
            }
            else if(c == '}')
            {
                if(!stack.empty() && stack.peek() == '{') stack.pop();
                else return false;
            }
            else stack.push(c);
        }
        return stack.empty();
    }
}

3.Merge Two Sorted Lists
Problem:
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        while(l1 != null && l2 != null)
        {
            if(l1.val < l2.val)
            {
                p.next = l1;
                p = p.next;
                l1 = l1.next;
            }
            else
            {
                p.next = l2;
                p = p.next;
                l2 = l2.next;
            }
        }
        if(l1 != null) p.next = l1;
        else p.next = l2;
        return dummy.next;
    }
}

4. Overlap Rectangle
Problem:
Check whether two rectangles overlaps. The bottem-left and top-right Node has been given.
Code:

class Node
{
	int x;
	int y;
	public Node(int x, int y)
	{
		this.x = x;
		this.y = y;
	}
}
public class Solution {
	// A & C is bottom-left, B & D is top-right
        public static boolean hasOverlap(Node A, Node B, Node C, Node D)
	{
		int bottomleft1_x = Math.min(A.x, B.x);
		int bottomleft1_y = Math.min(A.y, B.y);
		int topright1_x = Math.max(A.x, B.x);
		int topright1_y = Math.max(A.y, B.y);
		
		int bottomleft2_x = Math.min(C.x, D.x);
		int bottomleft2_y = Math.min(C.y, D.y);
		int topright2_x = Math.max(C.x, D.x);
		int topright2_y = Math.max(C.y, D.y);
		
		if(bottomleft1_x >= topright2_x ||bottomleft2_x >= topright1_x || bottomleft1_y >= topright2_y || bottomleft2_y >= topright1_y) return false;
		return true;
	}
	public static void main(String[] args)
	{
		Node A = new Node(0, 0), B = new Node(2, 2), C = new Node(1, 0), D = new Node(4, 4);
		System.out.println(hasOverlap(A, B, C, D));
	}
}

5. Sliding Window Maximum
Problem:
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as [3,3,5,5,6,7].
Code:

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length < k || k <= 0) return new int[0];
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int ri = 0;
        Deque<Integer> deque = new LinkedList<>();
        for(int i = 0; i < n ; i++)
        {
            while(!deque.isEmpty() && deque.peekFirst() < i - k + 1) deque.pollFirst();
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast();
            deque.offerLast(i);
            if(i >= k - 1) res[ri++] = nums[deque.peekFirst()];
        }
        return res;
    }
}

6. Search a 2D Matrix II
Problem:
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

Code:

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

7.Gray Code
Problem:
Given two hexadecimal numbers find if they can be consecutive in gray code
For example: 10001000, 10001001
return 1
since they are successive in gray code

Example2: 10001000, 10011001
return -1
since they are not successive in gray code.

Code:


public class Solution {
	public static boolean isConsecutive(byte a, byte b)
	{
		byte c = (byte)(a ^ b);
		int count = 0;
		while(c != 0)
		{
			c &= (c - 1);
			count++;
		}
		return count == 1;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		byte a = 0x31, b = 0x33;
		System.out.println(isConsecutive(a, b));
	}

}

8.Rotate String
Problem:
Given two words, find if second word is the round rotation of first word.
For example: abc, cab
return 1
since cab is round rotation of abc

Example2: ab, aa
return -1
since ab is not round rotation for aa

Code:

public class Solution {
	public static boolean isRotated(String s, String t)
	{
		if(s == null && t == null) return true;
		else if(s == null || t == null) return false;
		return (s.length() == t.length()) && ((s + s).indexOf(t) != -1);
		
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String s = "abcdef", t = "efabcd";
		System.out.println(isRotated(s, t));
	}

}

9. remove vowel

public class Solution {
	public static String removeVowel(String s)
	{
		String t = "aeiouAEIOU";
		StringBuilder sb = new StringBuilder();
		for(char c: s.toCharArray())
		{
			if(t.indexOf(c) >= 0) continue;
			sb.append(c);
		}
		return sb.toString();
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(removeVowel("abcdefghijk"));
	}

}

10. Find Optimal Weights (Close Two Sum)
题目
有一个容器double capacity, 還有一個array(double[] weights), 和int numOfContainers。

要求在array中选出两个weights總总和小于等于capacity但最接近capacity 然後指定到一個Container object並且return。

Code:

import java.util.Arrays;

class Container {
    public double first;
    public double second;
    public Container(double first, double second)
    {
    	this.first = first;
    	this.second = second;
    }
}
public class Solution {
	public static Container findOptimalWeights(double capacity, double[] weights)
	{
		if(weights == null || weights.length <= 2) return null;
		Arrays.sort(weights);
		if(weights[0] + weights[1] > capacity) return null;
		double i = weights[0], j = weights[1];
		int l = 0, r = weights.length - 1;
		while(l < r)
		{
			if(weights[l] + weights[r] == capacity) return new Container(weights[l], weights[r]);
			else if(weights[l] + weights[r] > capacity) r--;
			else
			{
				if(weights[l] + weights[r] > i + j)
				{
					i = weights[l];
					j = weights[r];
				}
				l++;
			}
		}
		return new Container(i, j);
		
	}
	public static void main(String[] args)
	{
		Container res = findOptimalWeights(35, new double[]{10, 24, 30, 9, 19, 23, 7});
		System.out.println(res.first+" "+res.second);
	}
}

11. Reverse Second Half of Linked List
题目
2->1->3->4->5->6->7->8 变成 2->1->3->4->8->7->6->5 ; 如果总是为奇数,中间的也要变 5->7->8->6->3->4->2 变成 5->7->8->2->4->3->6 。
Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode slow = head, fast = slow.next;
        while(fast.next != null && fast.next.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode pre = null, cur = slow.next;
        while(cur != null)
        {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        slow.next = pre;
        return head;
    }
}

12. GCD
题目
找一个数组中所有数的最大公约数。

public class solution {
	public static int GCD(int[] input)
	{
		if(input.length == 1) return input[0];
		int res = input[0];
		for(int i = 1; i < input.length; i++)
		{
			res = helper(res, input[i]);
		}
		return res;
	}
	private static int helper(int a, int b)
	{
		if(b == 0) return a;
		return helper(b, a%b);
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] input = {9,6,12,24};
		System.out.println(GCD(input));
	}

}

13.Same Tree
Problem:
Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Code:

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        else if(p == null || q == null) return false;
        else if(p.val != q.val) return false;
        else return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

14. Subtree Check
Please read http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-of-another-binary-tree/

15.K Closest Points
Problem:
Find the K closest points to the origin in 2D plane, given an array containing N points. You can assume K is much smaller than N and N is very large. You need only use standard math operators (addition, subtraction, multiplication, and division).
Code:
提供两种方法,注意对于距离一样的点,输入顺序和输出顺序必须一致。

import java.util.*;
class Point
{
	double  x;
	double y;
	public Point(double x, double y)
	{
		this.x = x;
		this.y = y;
	}
}
public class Solution {
	private static double distance(Point a, Point b)
	{
		return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
	}
	
	public static Point[] closestPoint(Point[] array, final Point origin, int k)
	{
		if(k > array.length) return array;
		Point[] res = new Point[k];
		Arrays.sort(array, new Comparator<Point>()
		{
			@Override
			public int compare(Point a, Point b)
			{
				return Double.compare(distance(a, origin), distance(b, origin));
			}
		
		});
		for(int i = 0; i < k; i++) res[i] = array[i];
		return res;
	}
	public static Point[] closestPoint2(Point[] array, final Point origin, int k)
	{
		if(k > array.length) return array;
		Point[] res = new Point[k];
		PriorityQueue<Point> queue = new PriorityQueue<Point>(new Comparator<Point>()
		{
			@Override
			public int compare(Point a, Point b)
			{
				return -Double.compare(distance(a, origin), distance(b, origin));
			}
		});
		for(Point p: array) queue.offer(p);
		while(queue.size() > k) queue.poll();
		for(int i = 0; i < k; i++) res[k - 1 - i] = queue.poll();
		return res;
	}
	public static void main(String[] args)
	{
		Point origin = new Point(0, 0);
		Point[] input = new Point[]{new Point(0, 2), new Point(1, 1), new Point(-1, 0), new Point(2, 0), new Point(3, 0)};
		Point[] output = closestPoint2(input, origin, 4);
		System.out.println("input");
		for(Point i : input) System.out.print("("+i.x+", "+i.y+") ");
		System.out.println("");
		System.out.println("output");
		for(Point i : output) System.out.print("("+i.x+", "+i.y+") ");
		
		
	}
}

5033total visits,6visits today