Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
I believe this code should do the trick in log(N)*N time (going along the lines freshboy also suggested). It uses priorityqueues which remain sorted and insertions cost log(N), so since we do N insertions we have log(N)*N. One keeps track of the "houseEnds" points, and one of the largest houses in order. There are while loops in there that look worrying, but in fact we at most look at any element in either of the priority queues once so all added up they should work out to N over the whole run.
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Vector;
public class DrawHouses {
public static class House
{
public House(int _x, int _width, int _height)
{
x = _x;
width = _width;
height = _height;
}
public int x;
public int width;
public int height;
public String strRep() {
return x + ", " + width + ", " + height;
}
}
/**
* @param args
*/
public static void main(String[] args)
{
//5R 10U, 5R 10 U, R
//(5,10,25),(10,20,15),(15,5,5)
House h1 = new House(5, 25, 10);
House h2 = new House(10, 15, 20);
House h3 = new House(15, 5, 5);
Vector <House> houses = new Vector();
houses.add(h1);
houses.add(h2);
houses.add(h3);
PriorityQueue <House> housesByHeight = new PriorityQueue(
100, new Comparator <House>()
{
@Override
public int compare(House arg0, House arg1)
{
return arg1.height - arg0.height;
}
});
PriorityQueue <House> housesByRemoval = new PriorityQueue(
100, new Comparator <House>()
{
@Override
public int compare(House arg0, House arg1)
{
return (arg0.x+arg0.width) - (arg1.x+arg1.width);
}
});
housesByHeight.offer(h1);
housesByHeight.offer(h2);
housesByHeight.offer(h3);
while(!housesByHeight.isEmpty())
{
System.out.println(housesByHeight.poll().strRep());
}
System.out.println("\n\n");
housesByRemoval.offer(h1);
housesByRemoval.offer(h2);
housesByRemoval.offer(h3);
while(!housesByRemoval.isEmpty())
{
House h = housesByRemoval.poll();
System.out.println(h.strRep() + " = " + (h.x + h.width));
}
System.out.println("\n\n");
System.out.println(drawStr3(houses));
//5R 10U 5R 10U 15R 10D 5R 10D
}
public static String drawStr3(Vector <House> houses)
{
String drawStr = "";
PriorityQueue <House> housesByHeight = new PriorityQueue <House>(
100, new Comparator <House>()
{
@Override
public int compare(House arg0, House arg1)
{
return arg1.height - arg0.height;
}
});
PriorityQueue <Integer> houseRemovalSpots = new PriorityQueue <Integer>(
100, new Comparator <Integer>()
{
@Override
public int compare(Integer arg0, Integer arg1)
{
return arg0 - arg1;
}
});
int curMaxHeight = 0;
int curX = 0;
String s = "";
for(int i = 0; i < houses.size(); i++)
{
if(houses.get(i).height > curMaxHeight)
{
s += "R" + (houses.get(i).x-curX) + ", " + "U" + (houses.get(i).height-curMaxHeight) + ", ";
curMaxHeight = houses.get(i).height;
curX = houses.get(i).x;
}
housesByHeight.offer(houses.get(i));
houseRemovalSpots.offer(houses.get(i).x + houses.get(i).width);
while((i == houses.size()-1 && !houseRemovalSpots.isEmpty())
|| (i < houses.size()-1 && houseRemovalSpots.peek() < houses.get(i+1).x))
{
int removalSpot = houseRemovalSpots.poll();
System.out.println("Checking out removal spot " + removalSpot);
cleanQueue(housesByHeight, removalSpot);
if(housesByHeight.isEmpty())
{
System.out.println("HousesByHeight is empty");
s += "R" + (removalSpot-curX) + ", " + "D" + (curMaxHeight) + ", ";
break;
}
else
{
if(housesByHeight.peek().height < curMaxHeight)
{
System.out.println("Using removal spot " + removalSpot + " which contains " + housesByHeight.peek().strRep());
s += "R" + (removalSpot-curX) + ", " + "D" + (curMaxHeight - housesByHeight.peek().height) + ", ";
curMaxHeight = housesByHeight.poll().height;
curX = removalSpot;
}
else
{
System.out.println("Not using removal spot " + removalSpot);
}
}
}
}
return s;
}
public static void cleanQueue(PriorityQueue <House> pq, int xVal)
{
while(!pq.isEmpty() && (pq.peek().width + pq.peek().x) <= xVal)
{
System.out.println("Cleaning away " + pq.peek().strRep());
pq.poll();
}
}
}
@startup : if u know the answer, why don't u write u'r algo here. Others will learn. Please write algorithm not code
I underestimated this question. freshboy's solution is as good as I can imagine. If you assume the x-coordinates are bounded, use count-sort, you can get it in O(n). And also, to determine the shadow-effect when walking through, you only need a stack to do it in constant time. So, if the input's x-coordinates are unbounded. O(nlgn), otherwise O(n)
Here is an O(nlgn) solution in java. It creates a TreeMap of events (so that all events are in sorted order of occurrence), and maintains a maxHeap for masking active heights of buildings (If removing an element from Heap is not O(lgn), we can use another TreeMap instead of maxHeap).
static void getSideView (int[] dist, int[][] dim) {
int numBuildings = dist.length;
Map<Integer, Integer> events = new TreeMap<Integer, Integer>();
for (int i = 0; i < numBuildings; i++) {
events.put(dist[i], dim[i][0]);
events.put(dist[i]+dim[i][1], (-1) * dim[i][0]);
}
int prevMask = 0;
int prevIndex = 0;
Queue<Integer> activeHeights = new PriorityQueue<Integer>
(numBuildings, Collections.reverseOrder());
for (Map.Entry<Integer, Integer> e : events.entrySet()) {
int newMask = 0;
if(e.getValue() > 0) {
activeHeights.offer(e.getValue());
newMask = activeHeights.peek();
if(newMask > prevMask) {
System.out.print((e.getKey() - prevIndex) + "R ");
System.out.print((newMask - prevMask) + "U ");
prevMask = newMask;
prevIndex = e.getKey();
}
}
else {
activeHeights.remove((Integer)(e.getValue() * (-1)));
if(activeHeights.isEmpty()) {
newMask = 0;
}
else {
newMask = activeHeights.peek();
}
if(newMask < prevMask) {
System.out.print((e.getKey() - prevIndex) + "R ");
System.out.print((prevMask - newMask) + "D ");
prevMask = newMask;
prevIndex = e.getKey();
}
}
}
System.out.println();
}
public static void main (String[] args) {
int[] dist = new int[] {5,10,15};
int[][] dim = new int[][] {{10,25},{20,15},{5,5}};
getSideView(dist, dim);
}
If we can consider the total length of x-axis as n, then we have a simpler O(n) solution as follows:
static void getSideView (int[] dist, int[][] dim) {
int numBuildings = dist.length;
int totalWidth = 0;
for (int i = 0; i < numBuildings; i++) {
totalWidth = Math.max(totalWidth, dist[i] + dim[i][1]);
}
int[] mask = new int [totalWidth+1];
for (int i = 0; i < numBuildings; i++) {
for(int j = dist[i]; j < dist[i] + dim[i][1]; j++) {
mask[j] = Math.max(dim[i][0], mask[j]);
}
}
int prevMask = 0;
int prevIndex = 0;
for (int i = 0; i <= totalWidth; i++) {
if(mask[i] == prevMask) {
continue;
}
System.out.print((i-prevIndex) + "R ");
if(mask[i] > prevMask) {
System.out.print((mask[i] -prevMask) + "U ");
}
else if(prevMask > mask[i]) {
System.out.print((prevMask - mask[i] ) + "D ");
}
prevMask = mask[i];
prevIndex = i;
}
System.out.println();
}
Haven't thought it thoroughly, but this is the rough idea:
- freshboy December 04, 2012Sort the starting and ending x-values of the building blocks. These are the "event points" (n*logn time)
Imagine a line sweeping from left to right, passing through each event point
At each event point, update the highest y-value, by either deleting an old building block or adding a new building block. The highest y-value marks the top of the side view that we are interested in. By maintaining a sorted data structure, like RB-tree, each update can be done in log(n) time.
After sweeping all the event points, we get the side view. There are O(n) event points, so the total time complexity is O(n*logn)
The code that implements this idea is non-trivial... I think it's hard to finish within the time of an interview.