Amazon Interview Question
SDE1sCountry: United States
Interview Type: In-Person
Can you elaborate on the question:
Lets say we have two edges : (0, 0), (0, 3) and (0, 0), (0, 5). Since each edge will create a single square - the total number of squares will be 2.
Meaning the number of squares = number of edges.
Ofcourse we need to find the co-ordinates of the remaining square points. What else needs to be done ?
As per my understanding of the question:
You can have two sets of edges, s1 parallel to the x-axis and s2 parallel to the y-axis.
For each edge in s1:
1. edge = (x1, y1) (x2, y1)
len = abs(x2 - x1)
2. check if [(x1, y1 + len), (x2, y1 + len)] [(x1, y1), (x2, y1 + len)] [(x2, y1), (x2, y1 + len)] are valid edges increment totalEdges (add square to set)
3. check if [(x1, y1 - len), (x2, y1 - len)] [(x1, y1), (x2, y1 - len)] [(x2, y1), (x2, y1 - len)] are valid edges increment totalEdges (add square to set)
In 2 and 3 you can take the top left and bottom right points to mark the square and add to a set to avoid duplicates or sort the edges parallel to x-axis by ordinates and just check for edges below the current edge to form a square.
As per my understanding:
1. Maintain a set with edges parallel to the x-axis.
2. For each edge say (x1, y1) (x2, y1):
len = x2 - x1
i. Check if [(x1, y1), (x1 + len, y1)], [(x2, y1),(x2 + len, y1)] and [(x1 + len, y1), (x2 + len, y1)] are valid edges, if so add the square to a set.
ii. Check if [(x1, y1), (x1 - len, y1)], [(x2, y1),(x2 - len, y1)] and [(x1 - len, y1), (x2 - len, y1)] are valid edges, if so add the square to a set.
Instead of checking above and below the edge for valid square, sort the edges parallel to x-axis by ordinates and just check below.
so what's the time complexity? sorting will take O(NLogN). How will you check if other 3 edges are present or not and what will be time complexity of that operation?
Write functions that given if we assume a segment is on the left will return the top right and bottom segments
If the segment is vertical that is x1 == x2 y1 < y2 and if it is horizontal x1 < x2 y1 == y2
Take all the lines you have and sort then interlay so that this constraint holds
So if you had a vertical segment were x1 == x2 y1 > y2 was true swap y1 and y2 similarly for the horizontal segments.
Now build a hash table of all your segments. All 4 coordinates need to be used to compute the key. C++ STL unordered set will do this for you but if you had some other language you might just append the bytes in the 4 numbers to make the keys.
Now loop through all your segments
If a segment is vertical search the hash table for the top left and right segments that would make up a square
Increment the count if you find all 3 of them.
This will take O(n) time and O(n) additional space for the table.
If you cannot afford extra space for the table but can rearrange the initial list you can sort it by these keys in O(nlog(n)) time spend O(log(n)) on the O(n) searchers you will need to do.
If you cannot mess up the table then you will need to do O(n) O(n) searches -> (n^2)
If you can have corners where segments cross in the middle, you will either need to compute intersections and create a lot of new overlapping segments of different lengths and use the above algorithm or render each line onto in binary array representing the absence of 1 block long segments that are horizontal and one where they are vertical. In this latter case you will need to scan these arrays for progressively larger emergent squares.
private static int bigSquare(Point []points) {
ArrayList<Point> starting = new ArrayList<>();
ArrayList<Point> ending = new ArrayList<>();
for( int i = 0 ; i < points.length ; ++i ) {
if( i % 2 == 0 )
starting.add( points[i] );
else
ending.add( points[i] );
}
Collections.sort( starting, (a, b)-> a.x == b.x ? a.y - b.y : a.x - b.x );
Collections.sort( ending, (a, b)-> a.x == b.x ? a.y - b.y : a.x - b.x );
int s = 0, e = ending.size()-1;
int cnt=0;
while (s < e) {
if( starting.get(s).x - ending.get(e).x == starting.get(s).y - ending.get(e).y ) {
if( starting.get(e).x == ending.get(e).x &&
starting.get(e).y == starting.get(s).y &&
ending.get(s).x == starting.get(s).x &&
ending.get(s).y == ending.get(e).y
) {
++cnt;
}
}
++s;
--e;
}
return cnt;
}
private static int bigSquare(Point []points) {
ArrayList<Point> starting = new ArrayList<>();
ArrayList<Point> ending = new ArrayList<>();
for( int i = 0 ; i < points.length ; ++i ) {
if( i % 2 == 0 )
starting.add( points[i] );
else
ending.add( points[i] );
}
Collections.sort( starting, (a, b)-> a.x == b.x ? a.y - b.y : a.x - b.x );
Collections.sort( ending, (a, b)-> a.x == b.x ? a.y - b.y : a.x - b.x );
int s = 0, e = ending.size()-1;
int cnt=0;
while (s < e) {
if( starting.get(s).x - ending.get(e).x == starting.get(s).y - ending.get(e).y ) {
if( starting.get(e).x == ending.get(e).x &&
starting.get(e).y == starting.get(s).y &&
ending.get(s).x == starting.get(s).x &&
ending.get(s).y == ending.get(e).y
) {
++cnt;
}
}
++s;
--e;
}
return cnt;
}
I am not sure if the approach mentioned above is the right way to solve the problem. Please help with any better solutions.
- jadonv January 26, 2019