Amazon OA2 Coding(Part 2)

amazon_logo_500500-_v323939215_

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

16. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.

Code:

public class Solution {
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++)
        {
            if(map.containsKey(target - nums[i])) return new int[]{map.get(target - nums[i]), i};
            else map.put(nums[i], i);
        }
        return null;
    }
}

17. Window Sum
注意(arraylist == null || arraylist.size() == 0)要return一个已经初始化的arrayList而不是null。
注意 corner cases。

import java.util.*;
public class Solution {
	public static List<Integer> windowSum(List<Integer> input, int k)
	{
		List<Integer> res = new ArrayList<>();
		if(input == null || input.size() == 0 || k <= 0) return res;
		if(k >= input.size())
		{
			int sum = 0;
			for(int i: input) sum += i;
			res.add(sum);
			return res;
		}
		else
		{
			int sum = 0;
			for(int i = 0; i < input.size(); i++)
			{
				sum += input.get(i);
				if(i >= k) sum -= input.get(i - k);
				if(i >= k - 1) res.add(sum);
			}
		}
		return res;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		List<Integer> input = new ArrayList<>();
		input.addAll(Arrays.asList(2,3,4,2,5,7,8,9,6));
//		List<Integer> input1 = new ArrayList<>();
//		input1.addAll(Arrays.asList(1,2));
		List<Integer> output = windowSum(input, 4);
		for(int i: output) System.out.print(i + " ");
	}

}

18. Tree Amplitude
In a binary tree T, a path P is a non-empty sequence of nodes of tree such that, each consecutive node in the sequence is a subtree of its preceding node. In the example tree, the sequences [9, 8, 2] and [5, 8, 12] are two paths, while [12, 8, 2] is not. The amplitude of path P is the maximum difference among values of nodes on path P. The amplitude of tree T is the maximum amplitude of all paths in T. When the tree is empty, it contains no path, and its amplitude is treated as 0.
For exmaple.

Input:

         5
       /   \
     8       9
   /  \     /  \ 
  12   2   8   4
          /    /
        2    5

Output:
7
Explanation:
The paths [5, 8, 12] and [9, 8, 2] have the maximum amplitude 7.
Code:
public static int amplitude(TreeNode root) is answer, others are helper functions for testing.

import java.util.*;
class TreeNode
{
	public TreeNode left, right;
	public int  val;
	public TreeNode(String val)
	{
		this.val = Integer.parseInt(val);
	}
}
public class Solution {

	public static TreeNode buildTree(String[] input)
	{
		int index = 0;
		TreeNode root = new TreeNode(input[index++]);
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		while(index < input.length)
		{
			
			int size = queue.size();
			for(int i = 0; i< size; i++)
			{
				TreeNode t = queue.poll();
				if(index >= input.length) return root;
				if(!input[index].equals("*"))
				{
					t.left = new TreeNode(input[index]);
					queue.offer(t.left);
				}
				index++;
				if(index >= input.length) return root;
				if(!input[index].equals("*"))
				{
					t.right = new TreeNode(input[index]);
					queue.offer(t.right);
				}
				index++;
				if(index >= input.length) return root;
			}
		}
		return root;
	}
	
	public static int amplitude(TreeNode root)
	{
		if(root == null) return 0;
		return DFS(root, Integer.MAX_VALUE, Integer.MIN_VALUE);
	}
	private static int DFS(TreeNode root, int min, int max)
	{
		if(root == null) return max - min;
		if(root.val < min) min = root.val;
		if(root.val > max) max = root.val;
		return Math.max(DFS(root.left, min, max), DFS(root.right, min, max));
		
	}

	public static void main(String[] args)
	{
		String[] input = {"5", "-8", "9", "-12", "2", "8", "4", "*", "*", "*", "*", "2", "*", "5"};
		TreeNode root = buildTree(input);
		System.out.println(amplitude(root));
	}
}

Output:

20

19.Arithmetic Sequence
find out number of arithmetic sequence in array, if result > 1 billion return -1.
[0,1,2,3,2,1] -> 4 ({0 ,1, 2},{1, 2, 3},{0, 1, 2, 3},{3, 2, 1})

public class Solution {
	public static int count(int[] input)
	{
		if(input == null || input.length < 3) return 0;
		int sum = 0, diff = Integer.MAX_VALUE, i = 0;
		for(int j = 1; j < input.length; j++)
		{
			int curdiff = input[j] - input[j - 1];
			if(curdiff == diff) sum += (j - i - 1);
			else
			{
				i = j - 1;
				diff = curdiff;
			}
		}
		return sum > 1000000000 ? -1: sum;
	}
	public static void main(String[] args)
	{
		int[] input = {0, 1, 2, 3, 4, 3, 2, 1};
		System.out.println(count(input));
	}
}

Output:

9

20 BST Minimum Path Sum
Return the minimum sum of a path in a BST from node to leaf.

Code(Untested):

public static int DFS(TreeNode root)
{
      if(root == null) return 0;
      else return root.val + Math.min(DFS(root.left), DFS(root.right));
}

21 Day change
Given an array and number of days. Rules: if arr[i-1] == arr[i+1], arr = 0 else arr = 1, do that for n days.
Code:
can not infer from problem whether input array only contains 1s and 0s, so preprocess.

public class Solution {
	public static int[] dayChange(int[] input, int day)
	{
		if(input == null || input.length == 0 || day <= 0) return input;
		for(int k = 0; k < day; k++)
		{
			for(int i = 0; i < input.length; i++)
			{
				if(i - 1 >= 0 && i + 1 < input.length && (input[i - 1] & 1) != (input[i + 1] & 1)) input[i] += 2;
			}
			for(int i = 0; i < input.length; i++) input[i] >>= 1;
		}
		return input;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] input = {1,0,0,0,0,1,0,0};
		int[] output = dayChange(input, 4);
		for(int i: output) System.out.print(i);
	}

}

Output:

01001100

22. Insert Into Cycle Linked List
please refer to http://www.jianshu.com/p/fc64ced753ad
23. Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.

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

24. LRU Cache Count Miss

import java.util.*;
public class Solution {
	public static int countMiss(int[] input, int size)
	{
		List<Integer> list = new LinkedList<>();
		int count = 0;
		for(int i: input)
		{
			if(list.contains(i)) list.remove(new Integer(i));
			else
			{
				if(list.size() == size) list.remove(0);
				count++;
			}
			list.add(i);
		}
		return count;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] input = {1, 1, 3, 4, 5, 6, 1};
		System.out.println(countMiss(input, 4));
	}
}

26. Round Robin
一个处理器要处理一堆request,一次只能处理一条,每次执行一个任务最多执行时间q,接着执行等待着的下一个任务。若前一个任务没执行完则放到队尾,等待下一次执行。
假设只要有任务开始以后cpu是不会空闲的,也就是说cpu开始后如果空闲了就说明没有任务了,另外Robin Round最后返回值是float。
080622f3u59u39aazvzsr3

import java.util.*;

public class Solution {
	static class Task
	{
		int arrive;
		int remain;
		public Task(int arrive, int remain)
		{
			this.arrive = arrive;
			this.remain = remain;
		}
	}
	public static double roundRobin(int[] arriveTime, int[] runTime, int slot)
	{
		Queue<Task> queue = new LinkedList<>();
		int i = 0, t = 0, wait = 0;
		while(i < arriveTime.length || !queue.isEmpty())
		{
			if(!queue.isEmpty())
			{
				Task peek = queue.poll();
				wait += (t - peek.arrive);
				if(peek.remain > slot) 
				{
					t += slot;
					peek.remain -= slot;
					peek.arrive = t;
				}
				else
				{
					t += peek.remain;
					peek.remain = 0;
					peek.arrive = t;
				}
				while(i < arriveTime.length && arriveTime[i] <= t)
				{
					queue.offer(new Task(arriveTime[i], runTime[i]));
					i++;
				}
				
				if(peek.remain != 0) queue.offer(peek);
			}
			else
			{
				queue.offer(new Task(arriveTime[i], runTime[i]));
				t = arriveTime[i];
				i++;
			}
		}
		return (wait + 0.0) / arriveTime.length;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arriveTime = {0, 1, 3, 9};
		int[] runTime = {2, 1, 7, 5};
		System.out.println(roundRobin(arriveTime, runTime, 2));
	}

}

3954total visits,4visits today