Chris
BAN USER- 0of 0 votes
AnswersDesign an elevator system for a high rise building.
- Chris in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Application / UI Design - 0of 0 votes
AnswersDesign an alarm clock.
- Chris in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Application / UI Design - -1of 1 vote
AnswersA Load Balancer has the following functions:
getHost() addHost(String) removeHost(String)
Implement these functions using any data structure you wish. Also indicate the average performance for each function and what you expect to be its call count in a typical system with respect to each other of the three functions. In other words, how often do you expect getHost() to be called compared to addHost(...)?
- Chris in United States
Constraints:
Hosts are unique.
getHost() returns a random host from the host group| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - 1of 1 vote
AnswersGiven a multidimensional array like below:
0 1 0 0 3 0 3 3 0 0 0 0 0 0 2 0 0 1 0 2 0 0 0 0 0
"objects" are considered groups of numbers that touch along top, left, right, or bottom edges.
- Chris in United States
Find the number of objects.
For example given the above array, your code should detect 4 unique "Objects". {1,3,3}, {3}, {1}, and {2, 2}.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
My solution follows the O(m*n) scan and DFS algorithm. I'm pretty sure this is O(m*n) because each node is guaranteed to be visited once. In layman's terms this is what I do:
1. Scan each node marking the node as visited iff the node is considered a sink
2. For sink nodes, perform a DFS on the node to find the members of this basin.
3. For each member of the current basin, mark as visited and continue checking while incrementing the current count.
4. Add the basin count to the result list.
5. Once all nodes have been visited, print the basin size list in descending order.
EDIT: Fixed the output to be in-line with the required solution and removed debug printing.
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.*;
/**
* @author chris moran
*/
public class RainfallDFS {
public static void main(String[] args) {
int[][] rain = buildMatrix("rainfall.txt");
boolean[][] visited = new boolean[rain.length][rain[0].length];
for(boolean[] v : visited)
Arrays.fill(v, false);
List<Integer> basins = new ArrayList<Integer>();
for(int y = 0; y < rain.length; y++) {
for(int x = 0; x < rain[y].length; x++) {
processMatrix(rain, visited, y, x, basins);
}
}
Collections.sort(basins, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for(int basin:basins)
System.out.print(basin + " ");
}
private static List<Integer> processMatrix(int[][] rain, boolean[][] visited, int y, int x, List<Integer> basins) {
if(visited[y][x])
return basins;
if(isSink(rain, y, x)) {
int count = processDFS(rain, visited, y, x);
basins.add(count);
visited[y][x] = true;
}
return basins;
}
private static int processDFS(int[][] rain, boolean[][] visited, int y, int x) {
int count = 0;
if(visited[y][x])
return count;
visited[y][x] = true;
count++;
if(x + 1 < rain[y].length && rain[y][x + 1] > rain[y][x] && rain[y][x] == findLowest(rain, y, x+1)) {//Are we the lowest of right's neighbors?
count += processDFS(rain, visited, y, x + 1);
}
if(x - 1 >= 0 && rain[y][x - 1] > rain[y][x] && rain[y][x] == findLowest(rain, y, x-1)) {//Are we the lowest of left's neighbors?
count += processDFS(rain, visited, y, x - 1);
}
if(y + 1 < rain.length && rain[y+1][x] > rain[y][x] && rain[y][x] == findLowest(rain, y+1, x)) {//Are we the lowest of down's neighbors?
count += processDFS(rain, visited, y+1, x);
}
if(y - 1 >= 0 && rain[y-1][x] > rain[y][x] && rain[y][x] == findLowest(rain, y-1, x)) {//Are we the lowest of up's neighbors?
count += processDFS(rain, visited, y-1, x);
}
return count;
}
private static int findLowest(int[][] rain, int y, int x) {
int clow = Integer.MAX_VALUE;
if(x + 1 < rain[y].length) {//r
clow = Math.min(clow, rain[y][x+1]);
}
if(x - 1 >= 0) {//l
clow = Math.min(clow, rain[y][x-1]);
}
if(y + 1 < rain.length) {//d
clow = Math.min(clow, rain[y+1][x]);
}
if(y - 1 >= 0) {//u
clow = Math.min(clow, rain[y-1][x]);
}
return clow;
}
private static boolean isSink(int[][] rain, int y, int x) {
boolean isSink = true;
if(x + 1 < rain[y].length) {//r
isSink = rain[y][x] < rain[y][x + 1];
}
if(x - 1 >= 0) {//l
isSink &= rain[y][x] < rain[y][x - 1];
}
if(y + 1 < rain.length) {//d
isSink &= rain[y][x] < rain[y + 1][x];
}
if(y - 1 >= 0) {//u
isSink &= rain[y][x] < rain[y - 1][x];
}
return isSink;
}
private static int[][] buildMatrix(String s) {
int[][] matrix = null;
try {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(new FileInputStream(s)));
String line = bufferedReader.readLine();
int size = Integer.parseInt(line.trim());
matrix = new int[size][size];
line = bufferedReader.readLine().trim();
for(int i = 0; i < size; i++) {
StringTokenizer st = new StringTokenizer(line);
for(int j = 0; j < size; j++) {
matrix[i][j] = Integer.parseInt(st.nextToken().trim());
}
line = bufferedReader.readLine();
}
} catch(Exception ignored) {
}
return matrix;
}
}
This problem is a case of edge-detection. Think of the question like this:
Imagine if the array is a representation of an image. Each 0 represents empty or no detail. Each >0 represents a 'thing' present. 'Things' that share an edge are considered all the same thing. The goal of this exercise is to be able to detect the total number of 'things' in the image. This exercise is similar to 'flood fill' questions
My solution was like Austin's: search every node marking each one as visited and once you encounter a node > 0 perform a DFS on the node while marking each node > 0 as visited. As you perform DFS increment a counter representing the number of unique (arbitrarily shaped) objects you encounter.
public class DetectBio {
public static void main(String[] args) {
int[][] image = new int[][] {
{0,1,0,0,3},
{0,0,3,0,1},
{0,1,0,0,2},
{1,1,1,0,2},
{0,0,0,0,0}
};
boolean [][] visited = new boolean[image.length][image[0].length];
for(boolean[] visit : visited) {
Arrays.fill(visit, false);
}
int totalBios = processMatrix(image, visited, 0, 0);
System.out.println("Detected: " + totalBios);
}
private static int processMatrix(int[][] image, boolean[][] visited, int y, int x) {
int totalDFS = 0;
if(visited[y][x])
return totalDFS;
if(image[y][x] > 0) {
//If we're here, DFS
totalDFS++;
processBio(image, visited, y, x);
}
visited[y][x] = true;
if(y + 1 < image.length) {//Down
totalDFS += processMatrix(image, visited, y + 1, x);
}
if(x + 1 < image[y].length) {//Right
totalDFS += processMatrix(image, visited, y, x + 1);
}
if(x + 1 < image[y].length && y + 1 < image.length) {//Diagonal
totalDFS += processMatrix(image, visited, y+1, x+1);
}
return totalDFS;
}
private static void processBio(int[][] image, boolean[][] visited, int y, int x) {
if(visited[y][x])
return;
visited[y][x] = true;
if(image[y][x] > 0) {
if(x + 1 < image[y].length) {
processBio(image, visited, y, x + 1);
}
if(x - 1 > 0) {
processBio(image, visited, y, x - 1);
}
if(y + 1 < image.length) {
processBio(image, visited, y + 1, x);
}
if(y - 1 > 0) {
processBio(image, visited, y - 1, x);
}
}
}
}
It seems to me that there are some questions that need to be asked:
1. When you say "the order should be same as previous array", what do you mean? By switching positive and negative numbers you are, in essence, changing the order of the array.
1a. Do you mean: If there are multiple positives or negatives in a row, they should maintain their order?
2. What is the expected result if the array has only 1 negative number? e.g., [1, 2, 3, 4, 5, 6, 7, -8, 9]?
2a. Is the expected result from 2 the same if the array has only 1 positive number?
3. My initial thought was that this was a contrived question to get you to in-place sort pairs of numbers ensuring that they are in positive, negative,... order.
My solution works for most cases except the ones I listed above. My solution, though it fits the question, is ambiguous and depends on what the interviewer is looking for.
EDIT: Corrected. Thank you ravio.
public class BSTCheck {
static class TreeNode<T> {
public T val;
public TreeNode<T> left;
public TreeNode<T> right;
public TreeNode() {
}
public TreeNode(T x) {
val = x;
}
}
public static void main(String[] args) {
TreeNode<Integer> root = new TreeNode<Integer>(4);
root.left = new TreeNode<Integer>(2);
root.left.left = new TreeNode<Integer>(1);
root.left.right = new TreeNode<Integer>(3);
root.right = new TreeNode<Integer>(6);
root.right.left = new TreeNode<Integer>(5);
root.right.right = new TreeNode<Integer>(7);
boolean sorted = isSorted(root);
System.out.println("Sorted[" + sorted + "]");
}
private static boolean isSorted(TreeNode<Integer> root) {
boolean sorted = isLeftSorted(root);
sorted &= isRightSorted(root);
return sorted;
}
private static boolean isLeftSorted(TreeNode<Integer> root) {
return root.left == null || root.left.val < root.val && isSorted(root.left);
}
private static boolean isRightSorted(TreeNode<Integer> root) {
return root.right == null || root.right.val > root.val && isSorted(root.right);
}
}
Recurse left and make sure left child is less than current node. If the left child is null the default case is to return true since any false will negate the expression as a whole. Do the same to the right children except verifying that the right child is greater than the current node. Same handling of the null right child; return true.
- Chris July 30, 2014My solution works for me. The way I looked at it, we need to be able to partition on each minute. And we needed to be able to snapshot a leaderboard every minute. So I think my approach is a bit different from the others I saw on here.
First I maintain a couple hashmaps. First, booksToCustomers. This maintains the set of customers reading the keyed book. Next is the customerToPageNumbers hashmap. This map keys customers to the list of page numbers they have read to each minute.
The way I track the last N minutes of reading it by maintaining a third map: customerToSpeeds. This maps customer to a bounded array of size N (where N is the amount of history to track). So for our case, 10, since we are only interested in the last 10 minutes.
The key functions we will need are:
updateReadingSpeeds(String customerID, String bookID, int pageNumber);
printLeaderBoard(String bookID);
I've added a few helper functions to make things a bit more modular. I will explain each and my reasoning for them below.
void updateCustomerPages(String customerID, int pageNumber, int timeBucket);
void updateCustomerSpeed(String customerID, int timeBucket, int currentSpeed);
void addCustomerToBook(String customerID, String bookID);
int fetchTimeBucket();
int calculateReadingSpeed(String customerID);
The interesting function to note is fetchTimeBucket(). I did this because I figure that we will have many clients hitting us at once. The simplest way I could think of to maintain parity and ensure that all of the speeds are kept logically is to take the time and mod it with the max history time. This function only takes current time and converts it to minutes and mods it with N. This returns the bucket of time the speed should go into for any given customer.
updateCustomerPages updates the current customer for the current time bucket.
updateCustomerSpeed will update the speed array for a given customer
addCustomerToBook simply adds a customer to a book's reader list.
calculateReadingSpeed takes the current timebucket and works its way backwards (a constant number N) and calculates the highest speed over the past N minutes.
Lastly, I've also added a helper structure/static class called LeaderEntry. This is nothing more than a value object to aid in printing the leader list.
The end result is fairly simple and could definitely use work before it is ready for prime-time. But as far as answering the question goes, I think this would suffice.
Implementation follows:
Note that I've stubbed out the time function so that I could test it in the main method. The increasePages function is just a helper for faking some data.
Hope this helps.
import java.util.*;
/**
* @author chris moran
*/
public class KindleReadingSpeed {
private static int time = 1;
private static final int HISTORY_TO_TRACK = 10;
private static Random random = new Random();
public static void main(String[] args) {
int[] pages = new int[4];
int timeLength = 4;//minutes
for(int i = 0; i < timeLength; i++) {
increasePages(pages);
updateReadingSpeeds("customer0", "book0", pages[0]);
updateReadingSpeeds("customer1", "book0", pages[1]);
updateReadingSpeeds("customer2", "book0", pages[2]);
updateReadingSpeeds("customer3", "book1", pages[3]);
time++;
}
// int speed = calculateReadingSpeed("customerID");
// System.out.println("speed = " + speed);
printLeaderBoard("book1");
System.out.println();
}
private static void increasePages(int[] pages) {
for(int i = 0; i < pages.length; i++) {
pages[i] += random.nextInt(25);
}
}
private static final Map<String,Set<String>> bookToCustomers = new HashMap<String, Set<String>>();
private static final Map<String,List<Integer>> customerToPageNumbers = new HashMap<String, List<Integer>>();
private static final Map<String,int[]> customerToSpeeds = new HashMap<String, int[]>();
static class LeaderEntry implements Comparable<LeaderEntry>{
private String customerID;
private int speed;
LeaderEntry(String customerID, int speed) {
this.customerID = customerID;
this.speed = speed;
}
@Override
public int compareTo(LeaderEntry o) {
return o.speed == this.speed ? -1 : o.speed - this.speed;
}
@Override
public boolean equals(Object o) {
if(this == o) return true;
if(!(o instanceof LeaderEntry)) return false;
LeaderEntry that = (LeaderEntry) o;
if(speed != that.speed) return false;
if(!customerID.equals(that.customerID)) return false;
return true;
}
@Override
public int hashCode() {
int result = customerID.hashCode();
result = 31 * result + speed;
return result;
}
}
private static void printLeaderBoard(String bookID) {
System.out.println("Customer ID,Reading Speed,Rank");
if(!bookToCustomers.containsKey(bookID)) {
System.out.println("");
return;
}
Set<String> customers = bookToCustomers.get(bookID);
Set<LeaderEntry> leaders = new TreeSet<LeaderEntry>();
for(String customerID : customers) {
int speed = calculateReadingSpeed(customerID);
LeaderEntry entry = new LeaderEntry(customerID, speed);
leaders.add(entry);//@TODO: check for failure to add!
}
int rank = 1;
for(LeaderEntry entry : leaders) {
System.out.println(entry.customerID + "," + entry.speed + "," + rank++);
}
}
private static void updateReadingSpeeds(String customerID, String bookID, int pageNumber) {
int timeBucket = fetchTimeBucket();
addCustomerToBook(customerID, bookID);
updateCustomerPages(customerID, pageNumber, timeBucket);
}
private static void updateCustomerPages(String customerID, int pageNumber, int timeBucket) {
int currentSpeed = pageNumber;
List<Integer> pageNumbers;
if(!customerToPageNumbers.containsKey(customerID)) {
pageNumbers = new ArrayList<Integer>();
} else {
pageNumbers = customerToPageNumbers.get(customerID);
currentSpeed = pageNumber - pageNumbers.get(pageNumbers.size() - 1) ;
}
pageNumbers.add(pageNumber);
customerToPageNumbers.put(customerID, pageNumbers);
updateCustomerSpeed(customerID, timeBucket, currentSpeed);
}
private static void updateCustomerSpeed(String customerID, int timeBucket, int currentSpeed) {
final int[] speeds;
if(!customerToSpeeds.containsKey(customerID)) {
speeds = new int[HISTORY_TO_TRACK];
Arrays.fill(speeds, 0);
} else {
speeds = customerToSpeeds.get(customerID);
}
speeds[timeBucket] = currentSpeed;
customerToSpeeds.put(customerID, speeds);
}
private static void addCustomerToBook(String customerID, String bookID) {
synchronized(bookToCustomers) {
Set<String> customers = bookToCustomers.containsKey(bookID) ? bookToCustomers.get(bookID) : new HashSet<String>();
customers.add(customerID);
bookToCustomers.put(bookID, customers);
}
}
private static int fetchTimeBucket() {
//Debug
return time % 10;
// return (int) ((System.currentTimeMillis() / 60000) % HISTORY_TO_TRACK);
}
private static int calculateReadingSpeed(String customerID) {
if(!customerToSpeeds.containsKey(customerID))
return 0;
int max = Integer.MIN_VALUE, timeBucket = fetchTimeBucket();
int[] speeds = customerToSpeeds.get(customerID);
for(int j = 0; j < 10; j++) {
int current = timeBucket - j % 10;
if(current < 0) {
current = 10 + current;
}
max = Math.max(max, speeds[current]);
}
return max;
}
}
Implementing this using a scan and DFS in O(m*n) time complexity (array dimensions). There is probably a way to do this without using a static group identifier but I didn't put much effort into finding that way.
- Chris August 01, 2014