Amazon Interview Question SDE1s
Country: 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;
}
This is basically an undirected graph connectivity problem:
1. each "edge" can be mapped into an "edge" in the graph.
2. do a dfs from each vertex of the graph, add some restriction to the next neighbor to forma a rectangle:
2.1. the next vertex must be vertical with current vertex.
2.2. limit the dfs steps only for 4, if not reach the starting point at step 4, then this branch failed.
2.3 use backtracking to find all valid path.
#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>
#include <algorithm>
using namespace std;
typedef pair <int, int> coordinate;
struct edge {
int src;
int dst;
bool is_vertical;
edge(int x, int y, bool z) : src(x), dst(y), is_vertical(z) {}
};
class graph {
public:
graph(vector <edge> &edges, int v)
{
vertices = v;
adja_v.resize(v);
adja_h.resize(v);
for (auto &e : edges) {
if (e.is_vertical) {
adja_v[e.src].push_back(e.dst);
adja_v[e.dst].push_back(e.src);
}
else {
adja_h[e.src].push_back(e.dst);
adja_h[e.dst].push_back(e.src);
}
}
}
void dfs(int start, int end, int m, bool is_vertical, vector <bool> &visited, vector <int> &path, vector <vector <int>> &paths)
{
if (m == 0)
return;
visited[start] = true;
path.push_back(start);
//only search one direction of adjacent vertices
auto& adja = is_vertical ? adja_v[start] : adja_h[start];
for (auto &i : adja) {
if (i == end && m == 1) {
paths.push_back(path);
path.pop_back();
visited[start] = false;
return; //from the third point, only one way to reach final end/start point, so stop dfs here.
}
if (!visited[i])
dfs(i, end, m - 1, !is_vertical, visited, path, paths);//next vertex shoud be at vertical dir of curr vertex
}
path.pop_back();
visited[start] = false;
}
private:
int vertices;
vector <vector <int>> adja_v;
vector <vector <int>> adja_h;
};
class solution {
public:
int get_num_of_rect(vector <pair <coordinate, coordinate>> &input)
{
int vertices;
vector <edge> edges;
get_all_edges(input, edges, vertices);
graph g(edges, vertices);
unordered_map <string, bool> result;
vector <bool> visited(vertices, false);
for (int i = 0; i < vertices; i++) {
vector <int> path;
vector <vector <int>> paths;
if (!visited[i]) // if a point is visited, means all rects including it have been found, no need to revisit it again.
g.dfs(i, i, 4, true, visited, path, paths); //for each point, only need to start searching from one dir.
for (auto &j : paths)
parse_result(j, result);
}
return result.size();
}
private:
void get_all_edges(vector <pair <coordinate, coordinate>> &input, vector <edge> &edges, int &vertices)
{
set <coordinate> points;
for (auto &i : input) {
points.insert(i.first); //set will automaticall reject dup elem to be inserted
points.insert(i.second);
}
vertices = points.size();
for (auto &i : input) {
int vertex_u, vertex_v;
get_vertex(i, points, vertex_u, vertex_v);
if (is_vertical(i))
edges.push_back(edge(vertex_u, vertex_v, true));
else if (is_horizontal(i))
edges.push_back(edge(vertex_u, vertex_v, false));
}
}
bool is_vertical(pair <coordinate, coordinate> &i)
{
return i.first.second == i.second.second;
}
bool is_horizontal(pair <coordinate, coordinate> &i)
{
return i.first.first == i.second.first;
}
void get_vertex(pair <coordinate, coordinate> &i, set <coordinate> &points, int &vertex_u, int &vertex_v)
{
auto it = find(points.begin(), points.end(), i.first);
vertex_u = distance(points.begin(), it);
it = find(points.begin(), points.end(), i.second);
vertex_v = distance(points.begin(), it);
}
void parse_result(vector <int> &path, unordered_map <string, bool> &result)
{
string key;
sort(path.begin(), path.end()); //travel order should not matter in this case
for (auto &i : path)
key = key + "|" + to_string(i);
result[key] = true;
}
};
int main(int argc, char **argv)
{
/*
|
6 | * * * *
|
4 | * *
3 | * *
|
1 | * * *
|________________________________________
1 4 6 12
*/
vector <pair <coordinate, coordinate>> input = {
pair <coordinate, coordinate>(coordinate(1, 1), coordinate(6, 1)),
pair <coordinate, coordinate>(coordinate(6, 1), coordinate(6, 4)),
pair <coordinate, coordinate>(coordinate(6, 4), coordinate(1, 4)),
pair <coordinate, coordinate>(coordinate(1, 4), coordinate(1, 1)), //first rect
pair <coordinate, coordinate>(coordinate(6, 1), coordinate(6, 6)),
pair <coordinate, coordinate>(coordinate(6, 6), coordinate(1, 6)),
pair <coordinate, coordinate>(coordinate(1, 6), coordinate(1, 1)), //second rect, share one edge with first one
pair <coordinate, coordinate>(coordinate(1, 4), coordinate(6, 4)),
pair <coordinate, coordinate>(coordinate(6, 4), coordinate(6, 6)),
pair <coordinate, coordinate>(coordinate(1, 6), coordinate(1, 4)), //third rect, share one with second
pair <coordinate, coordinate>(coordinate(4, 3), coordinate(12, 3)),
pair <coordinate, coordinate>(coordinate(12, 3), coordinate(12, 6)),
pair <coordinate, coordinate>(coordinate(12, 6), coordinate(4, 6)),
pair <coordinate, coordinate>(coordinate(4, 6), coordinate(4, 3)), //fourth rect
pair <coordinate, coordinate>(coordinate(6, 1), coordinate(12, 1)),
pair <coordinate, coordinate>(coordinate(12, 1), coordinate(12, 6)),
pair <coordinate, coordinate>(coordinate(12, 6), coordinate(6, 6)),
pair <coordinate, coordinate>(coordinate(6, 6), coordinate(6, 1)), //fifth rect
pair <coordinate, coordinate>(coordinate(1, 1), coordinate(12, 1)),
pair <coordinate, coordinate>(coordinate(12, 1), coordinate(12, 6)),
pair <coordinate, coordinate>(coordinate(12, 6), coordinate(1, 6)), //sixth rect
pair <coordinate, coordinate>(coordinate(1, 1), coordinate(4, 3)), //invalid edge
pair <coordinate, coordinate>(coordinate(4, 3), coordinate(12, 6)), //invalid edge
pair <coordinate, coordinate>(coordinate(1, 4), coordinate(12, 4)), //invalid edge
pair <coordinate, coordinate>(coordinate(1, 1), coordinate(20, 1)), //invalid edge
pair <coordinate, coordinate>(coordinate(1, 1), coordinate(1, -20)), //invalid edge
pair <coordinate, coordinate>(coordinate(1, -20), coordinate(-20, 12)), //invalid edge
};
solution s;
int ret = s.get_num_of_rect(input);
cout << ret << endl;
}
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