Amazon OA2 Coding(Part 3)

amazon_logo_500500-_v323939215_

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

26. Rotate Matrix
把一个m*n的矩阵旋转90度,给一个flag规定是向左转还是向右转。


public class Solution {
	public static int[][] rotate(int[][] matrix, int flag)
	{
		if(matrix == null || matrix.length == 0) return matrix;
		int m = matrix.length, n = matrix[0].length;
		int[][] res = new int[n][m];
		for(int i = 0; i < m; i++)
		{
			for(int j = 0; j < n; j++) res[j][i] = matrix[i][j];
		}
		if(flag == 1)
		{
			for(int i = 0; i < n; i++)
			{
				for(int j = 0; j < m / 2; j++)
				{
					int tmp = res[i][j];
					res[i][j] = res[i][m - 1 - j];
					res[i][m - 1 - j] = tmp;
				}
			}
		}
		else
		{
			for(int j = 0; j < m ;j++)
			{
				for(int i = 0; i < n / 2; i++)
				{
					int tmp = res[i][j];
					res[i][j] = res[n - 1 - i][j];
					res[n - 1 - i][j] = tmp;
				}
			}
		}
		return res;
	}
	public static void printMatrix(int[][] matrix)
	{
		int m = matrix.length, n = matrix[0].length;
		for(int i = 0; i < m; i++)
		{
			for(int j = 0; j < n; j++) System.out.print(matrix[i][j] + " ");
			System.out.println("");
		}
	}
	public static void main(String[] args)
	{
		int[][] input = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
		int[][] output1 = rotate(input, 0);
		int[][] output2 = rotate(input, 1);
		System.out.println("input");
		printMatrix(input);
		System.out.println("output1");
		printMatrix(output1);
		System.out.println("output2");
		printMatrix(output2);
	}
}

Output:

input
1 2 3 
4 5 6 
7 8 9 
output1
3 6 9 
2 5 8 
1 4 7 
output2
7 4 1 
8 5 2 
9 6 3 

27. Shortest Job First
一个处理器要处理一堆request,一次只能处理一条,如果它有几个积压着的requests,它会先执行持续时间短的那个;对于持续时间相等的requests,先执行最早到达处理器的request。问平均每个request要等多久才能被处理。input:requestTimes[],每个request到达处理器的时间; durations[] 每个request要处理的持续时间。 两个数组是一一对应的,并已按requestTimes[] 从小到大排序过。

import java.util.*;
public class Solution {
	static class Process
	{
		int arrTime;
		int exeTime;
		public Process(int arrTime, int exeTime)
		{
			this.arrTime = arrTime;
			this.exeTime = exeTime;
		}
	}
	public static double SJL(int[] req, int[] dur)
	{
		if(req == null || req.length == 0) return 0;
		PriorityQueue<Process> queue = new PriorityQueue<>(new Comparator<Process>()
		{
			@Override
			public int compare(Process a, Process b)
			{
				if(a.exeTime == b.exeTime) return a.arrTime - b.arrTime;
				else return a.exeTime - b.exeTime;
			}
		});
		int t = 0, sum = 0, i = 0;
		while(i < req.length || !queue.isEmpty())
		{
			if(queue.isEmpty())
			{
				queue.offer(new Process(req[i], dur[i]));
				t = req[i];
				i++;
			}
			else
			{
				Process p = queue.poll();
				sum += (t - p.arrTime);
				t += p.exeTime;
				while(i < req.length && req[i] <= t)
				{
					queue.offer(new Process(req[i], dur[i]));
					i++;
				}
			}
		}
		return (sum + 0.0) / req.length;
	}
	public static void main(String[] args)
	{
		int[] req = {1, 3, 3, 6, 6, 6, 7};
		int[] dur = {2 ,2 ,3 ,2, 4, 4, 2};
		System.out.println(SJL(req, dur));
	}
}

Output:

3.2857142857142856

28. maze
给个array,其中只有一格是9,其他格子是0或1,0表示此路不通,1表示可以走,判断从(0,0) 点开始上下左右移动能否找到这个是9的格子。

import java.util.*;
public class Solution {
	static final int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	public static int checkMaze(int[][] maze)
	{
		if(maze == null || maze.length == 0 || maze[0][0] == 0) return 0;
		if(maze[0][0] == 9) return 1;
		int m = maze.length, n = maze[0].length;
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[]{0, 0});
		maze[0][0] = 0;
		while(!queue.isEmpty())
		{
			int[] p = queue.poll();
			for(int k = 0; k < 4; k++)
			{
				int x = p[0] + dir[k][0];
				int y = p[1] + dir[k][1];
				if(x >=0 && x < m && y >= 0&& y < n)
				{
					if(maze[x][y] == 9) return 1;
					else if(maze[x][y] == 1)
					{
						queue.offer(new int[]{x, y});
						maze[x][y] = 0;
					}
				}
			}
		}
		return 0;
	}
	public static void printMatrix(int[][] matrix)
	{
		int m = matrix.length, n = matrix[0].length;
		for(int i = 0; i < m; i++)
		{
			for(int j = 0; j < n; j++) System.out.print(matrix[i][j] + " ");
			System.out.println("");
		}
	}
	public static void main(String[] args)
	{
		int[][] maze = {{1, 0, 0, 1}, {1, 1, 1, 1}, {1, 0, 0, 9}};
		printMatrix(maze);
		System.out.println(checkMaze(maze));
	}
}

Output:

1 0 0 1 
1 1 1 1 
1 0 0 9 
1

29. Four Integer
Given four integers, make F(S) = abs(S[0]-S[1])+abs(S[1]-S[2])+abs(S[2]-S[3]) to be largest.
Code:

import java.util.Arrays;

public class Solution {
	public static int[] fourInteger(int A, int B, int C, int D)
	{
		int[] nums = new int[]{A, B, C, D};
		Arrays.sort(nums);
		swap(nums, 0, 1);
		swap(nums, 2, 3);
		swap(nums, 0, 3);
		return nums;
	}
	private static void swap(int[] nums, int i, int j)
	{
		int tmp = nums[i];
		nums[i] = nums[j];
		nums[j] = tmp;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = fourInteger(1, 3, 2, 4);
		for(int i: nums) System.out.print(i + " ");
	}

}

Output:

3 1 4 2 

30. Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
Code 1: O(1) space

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) return head;
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode ptr = dummy;
        dummy.next = head;
        while(ptr.next != null)
        {
            RandomListNode next = ptr.next.next;
            ptr.next.next = new RandomListNode(ptr.next.label);
            ptr = ptr.next.next;
            ptr.next = next;
        }
        ptr = dummy;
        while(ptr.next != null)
        {
            if(ptr.next.random != null) ptr.next.next.random = ptr.next.random.next;
            ptr = ptr.next.next;
        }
        RandomListNode newdummy = new RandomListNode(0);
        RandomListNode newptr = newdummy;
        ptr = dummy;
        while(ptr.next != null)
        {
            newptr.next = ptr.next.next;
            newptr = newptr.next;
            ptr.next.next = ptr.next.next.next;
            ptr = ptr.next;
        }
        return newdummy.next;
    }
}

Code 2: O(n) space:

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) return null;
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode dummy1 = new RandomListNode(0), dummy2 = new RandomListNode(0);
        RandomListNode iter1 = dummy1, iter2 = dummy2;
        dummy1.next = head;
        while(iter1.next != null)
        {
            iter2.next = new RandomListNode(iter1.next.label);
            map.put(iter1.next, iter2.next);
            iter1 = iter1.next;
            iter2 = iter2.next;
        }
        iter1 = dummy1;
        iter2 = dummy2;
        while(iter1.next != null)
        {
            if(iter1.next.random != null) iter2.next.random = map.get(iter1.next.random);
            iter1 = iter1.next;
            iter2 = iter2.next;
        }
        return dummy2.next;
    }

31. Order Dependency
Use topological sort.

import java.util.*;
class Order{
    String orderName;
    public Order(String orderName)
    {
    	this.orderName = orderName;
    }
}
class OrderDependency{
    Order order;
    Order dependent;
    public OrderDependency(Order order, Order dependent)
    {
    	this.order = order;
    	this.dependent = dependent;
    }
}
public class Solution {
	public static List<Order> findOrder(List<OrderDependency> depenency)
	{
		Map<String, Integer> inmap = new HashMap<>();
		Map<String, List<String>> outmap = new HashMap<>();
		for(OrderDependency i: depenency)
		{
			if(!inmap.containsKey(i.dependent.orderName)) inmap.put(i.dependent.orderName, 0);
			if(!inmap.containsKey(i.order.orderName)) inmap.put(i.order.orderName, 0);
			inmap.put(i.order.orderName, inmap.get(i.order.orderName) + 1);
			if(!outmap.containsKey(i.dependent.orderName)) outmap.put(i.dependent.orderName, new ArrayList<String>());
			outmap.get(i.dependent.orderName).add(i.order.orderName);
		}
		List<Order> res = new ArrayList<>();
		Queue<String> queue = new LinkedList<>();
		for(String i: inmap.keySet())
		{
			if(inmap.get(i) == 0) queue.offer(i);
		}
		while(!queue.isEmpty())
		{
			String s = queue.poll();
			res.add(new Order(s));
			if(outmap.containsKey(s))
			{
				for(String o: outmap.get(s))
				{
					inmap.put(o, inmap.get(o) - 1);
					if(inmap.get(o) == 0) queue.offer(o);
				}
			}
			outmap.remove(s);
		}
		return res;
	}
	public static void main(String[] args)
	{
		List<OrderDependency> input = new ArrayList<>();
		input.add(new OrderDependency(new Order("A"), new Order("E")));
		input.add(new OrderDependency(new Order("D"), new Order("E")));
		input.add(new OrderDependency(new Order("A"), new Order("C")));
		input.add(new OrderDependency(new Order("B"), new Order("D")));
		List<Order> output = findOrder(input);
		for(Order i: output) System.out.print(i.orderName + " ");
	}
}

Output:

C E A D B 

32. Maximum Minimum Path
给一个int[][]的matirx,对于一条从左上到右下的path pi,pi中的最小值是mi,求所有mi中的最大值。只能往下或右.

public class Solution {
	public static int find(int[][] input)
	{
		int m = input.length, n = input[0].length;
		for(int i = 0; i < m; i++)
		{
			for(int j = 0; j < n; j++)
			{
				if(i == 0 && j == 0) continue;
				int a = Integer.MIN_VALUE, b = Integer.MIN_VALUE;
				if(i - 1 >= 0) a = Math.min(input[i][j], input[i - 1][j]);
				if(j - 1 >= 0) b = Math.min(input[i][j], input[i][j - 1]);
				input[i][j] = Math.max(a, b);
//				System.out.println("i = "+ i);
//				System.out.println("j = "+ j);
//				System.out.println("input[i][j] = "+ input[i][j]);
			}
		}
		return input[m - 1][n - 1];
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] input = {{2, 2, 3 ,4}, {1, 2, 3, 4},{1, 2, 3, 4}};
		System.out.println(find(input));
	}

}

output:

2

33. Minimum Spanning Tree
题目内容是这样的,给十几个城市供电,连接不同城市的花费不同,让花费最小同时连到所有的边。给出一系列connection类,里面是edge两端的城市名和它们之间的一个cost,找出要你挑一些边,把所有城市连接起来并且总花费最小。不能有环,最后所以城市要连成一个连通块。
不能的话输出空表,最后还要按城市名字排序输出,按照node1来排序,如果一样的话再排node2。
输入:
{“Acity”,”Bcity”,1}
(“Acity”,”Ccity”,2}
(“Bcity”,”Ccity”,3}
输出:
(“Acity”,”Bcity”,1}
(“Acity”,”Ccity”,2}
补充一句,test case一共有6个。

import java.util.*;
class Connection{
    String node1;
    String node2;
    int cost;
    public Connection(String a, String b, int c){
        node1 = a;
        node2 = b;
        cost = c;
    }
}
public class Solution {
	static class DisjointSet
	{
		Set<String> set;
		Map<String, String> map;
		int count;
		public DisjointSet()
		{
			count = 0;
			set = new HashSet<>();
			map = new HashMap<>();
		}
		public void MakeSet(String s)
		{
			if(!set.contains(s))
			{
				count++;
				set.add(s);
				map.put(s, s);
			}
		}
		public String Find(String s)
		{
			if(!set.contains(s)) return null;
			if(s.equals(map.get(s))) return s;
			String root = this.Find(map.get(s));
			map.put(s, root);
			return root;
		}
		public void Union(String s, String t)
		{
			if(!set.contains(s) || !set.contains(t)) return;
			if(s.equals(t)) return;
			count--;
			map.put(s, t);
		}
	}
	static class ConnectionComparator1 implements Comparator<Connection>
	{
		@Override
		public int compare(Connection a, Connection b)
		{
			return a.cost - b.cost;
		}
	}
	static class ConnectionComparator2 implements Comparator<Connection>
	{
		@Override
		public int compare(Connection a, Connection b)
		{
			if(a.node1.equals(b.node1)) return a.node2.compareTo(b.node2);
			else return a.node1.compareTo(b.node1);
		}
	}
	public static List<Connection> getMST(List<Connection> connections)
	{
		
		Comparator<Connection> comparator1 = new ConnectionComparator1();
		Comparator<Connection> comparator2 = new ConnectionComparator2();
		Collections.sort(connections, comparator1);
		DisjointSet set = new DisjointSet();
		List<Connection> res = new ArrayList<>();
		for(Connection itr: connections)
		{
			set.MakeSet(itr.node1);
			set.MakeSet(itr.node2);
		}
		for(Connection itr: connections)
		{
			String s = set.Find(itr.node1);
			String t = set.Find(itr.node2);
			if(!s.equals(t))
			{
				set.Union(s, t);
				res.add(itr);
				if(set.count == 1) break;
			}
		}
		if(set.count == 1)
		{
			Collections.sort(res, comparator2);
			return res;
		}
		else return new ArrayList<Connection>();
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ArrayList<Connection> connections = new ArrayList<>();
//	    connections.add(new Connection("Acity","Bcity",1));
//	    connections.add(new Connection("Acity","Ccity",2));
//	    connections.add(new Connection("Bcity","Ccity",3));
            connections.add(new Connection("A","B",6));
	    connections.add(new Connection("B","C",4));
	    connections.add(new Connection("C","D",5));
	    connections.add(new Connection("D","E",8));
	    connections.add(new Connection("E","F",1));
	    connections.add(new Connection("B","F",10));
	    connections.add(new Connection("E","C",9));
	    connections.add(new Connection("F","C",7));
	    connections.add(new Connection("B","E",3));
	    connections.add(new Connection("A","F",1));

	    List<Connection> res = getMST(connections);
	    for (Connection c : res){
	        System.out.println(c.node1 + " -> " + c.node2 + " cost : " + c.cost);
	    }
	}

}

Output:

A -> F cost : 1
B -> C cost : 4
B -> E cost : 3
C -> D cost : 5
E -> F cost : 1

34 Maximum Subtree of Average
就是给一棵多叉树,表示公司内部的上下级关系。每个节点表示一个员工,节点包含的成员是他工作了几个月(int),以及一个下属数组(ArrayList)。目标就是找到一棵子树,满足:这棵子树所有节点的工作月数的平均数是所有子树中最大的。最后返回这棵子树的根节点。这题补充一点,返回的不能是叶子节点(因为叶子节点没有下属),一定要是一个有子节点的节点。

import java.util.ArrayList;
class Node { 
    int val;
    ArrayList<Node> children;
    public Node(int val){
        this.val = val;
        children = new ArrayList<Node>();
    }
}
public class Solution {
	static class SumCount
	{
		int sum;
		int count;
		public SumCount(int sum, int count)
		{
			this.sum = sum;
			this.count = count;
		}
	}
	static Node ans;
	static double max = 0;
	public static Node find(Node root)
	{
		// Initialize static variables is very important for AMZAON OA!
		ans = null;
		max = 0;
		DFS(root);
		return ans;
	}
	private static SumCount DFS(Node root)
	{
		if(root == null) return new SumCount(0, 0);
		if(root.children == null || root.children.size() == 0) return new SumCount(root.val, 1);
		int sum = root.val;
		int count = 1;
		for(Node itr: root.children)
		{
			SumCount sc = DFS(itr);
			sum += sc.sum;
			count += sc.count;
		}
		if(count > 1 && (sum + 0.0) / count > max)
		{
			max = (sum + 0.0) / count;
			ans = root;
		}
		return new SumCount(sum, count);
	}
	public static void main(String[] args) {
        Node root = new Node(1);
        Node l21 = new Node(2);
        Node l22 = new Node(3);
        Node l23 = new Node(4);
        Node l31 = new Node(5);
        Node l32 = new Node(5);
        Node l33 = new Node(5);
        Node l34 = new Node(5);
        Node l35 = new Node(5);
        Node l36 = new Node(5);

        l21.children.add(l31);
        l21.children.add(l32);

        l22.children.add(l33);
        l22.children.add(l34);

        l23.children.add(l35);
        l23.children.add(l36);

        root.children.add(l21);
        root.children.add(l22);
        root.children.add(l23);

        Node res = find(root);
        System.out.println(res.val + " " + max);
    }
}

Output:

4 4.666666666666667

35. Five Scores
写好了一个叫Result的类,中文翻译成节点,题目是输入是一堆节点,节点里面有两个属性学生id和分数,保证每个学生至少会有5个分数,求每个人最高的5个分数的平均分。返回的是Map, key是id,value是每个人最高5个分数的平均分double是平均分。

import java.util.*;
class Result{
    int id;
    int value;
    public Result(int id, int value){
        this.id = id;
        this.value = value;
    }
}
public class Solution {
	public static Map<Integer, Double> getHighFive(Result[] results)
	{
		Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
		for(Result itr: results)
		{
			if(!map.containsKey(itr.id))
			{
				map.put(itr.id, new PriorityQueue<Integer>());
				map.get(itr.id).offer(itr.value);
			}
			else
			{
				if(map.get(itr.id).size() < 5) map.get(itr.id).offer(itr.value);
				else if(itr.value > map.get(itr.id).peek())
				{
					map.get(itr.id).poll();
					map.get(itr.id).offer(itr.value);
				}
			}
		}
		Map<Integer, Double> res = new HashMap<>();
		for(int id: map.keySet())
		{
			int sum = 0;
			PriorityQueue<Integer> q = map.get(id);
			while(!q.isEmpty()) sum += q.poll();
			res.put(id, (sum + 0.0) / 5);
		}
		return res;
	}
	public static void main(String[] args) {
        Result r1 = new Result(1, 95);
        Result r2 = new Result(1, 95);
        Result r3 = new Result(1, 91);
        Result r4 = new Result(1, 91);
        Result r5 = new Result(1, 93);
        Result r6 = new Result(1, 105);

        Result r7 = new Result(2, 6);
        Result r8 = new Result(2, 6);
        Result r9 = new Result(2, 7);
        Result r10 = new Result(2, 6);
        Result r11 = new Result(2, 6);
        Result[] arr = {r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11};
        Map<Integer, Double> res = getHighFive(arr);

        System.out.println(res.get(1) + " " +res.get(2));
    }
}

Output:

95.8 6.2

36.Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.
Input: "cbbd"

Output: "bb"
public class Solution {
    int max, start, end;
    public String longestPalindrome(String s) {
        max = 0;
        start = 0;
        end = 0;
        if(s == null || s.length() < 2) return s;
        for(int i = 0; i < s.length(); i++)
        {
            findPalindrome(s, i, i);
            if(i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)) findPalindrome(s, i, i + 1);
        }
        return s.substring(start, end + 1);
    }
    private void findPalindrome(String s, int l, int r)
    {
        while(l - 1 >= 0 && r + 1 < s.length() && s.charAt(l - 1) == s.charAt(r + 1))
        {
            l--;
            r++;
        }
        if(r - l + 1 > max)
        {
            max = r - l + 1;
            start = l;
            end = r;
        }
    }
}

5963total visits,6visits today