## Amazon Interview Question for SDE1s

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

I am not sure if the approach mentioned above is the right way to solve the problem. Please help with any better solutions.

Comment hidden because of low score. Click to expand.
0

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 ?

Comment hidden because of low score. Click to expand.
0

@deep.kulshreshtha square can only be formed if all 4 edges are given in the input. We just need to return the count of total number of squares.

Comment hidden because of low score. Click to expand.
0
of 0 vote

If all ages are in parallel to one of the axises they do not form any squares.

Comment hidden because of low score. Click to expand.
0

2 edges parallel to X axis and 2 edges parallel to y axis form a square as shown above in given example

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

If you're sorting, then 3 O(1) lookups from both the hashsets of edges.

Comment hidden because of low score. Click to expand.
0

And we only need to sort edges parallel to the x-axis. So, less than Nlog N

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I feel like this problem boils down to finding the sum of all possible square matrices in NxN square matrix

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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 )
else
}

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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 )
else
}

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

for (auto &e : edges) {
if (e.is_vertical) {
}
else {
}
}
}

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
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;
};

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;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.