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.

- jadonv January 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ?

- deep.kulshreshtha January 28, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- jadonv January 28, 2019 | Flag
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.

- Vitaly January 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- jadonv January 28, 2019 | Flag
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.

- AD January 29, 2019 | Flag Reply
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.

- AD January 29, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- jadonv January 29, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- AD January 30, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- AD January 30, 2019 | Flag
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.

- dr ADM January 31, 2019 | Flag Reply
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

- yfedorovsky January 31, 2019 | Flag Reply
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 )
                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;
    }

- DevilDeepu February 08, 2019 | Flag Reply
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 )
                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;
    }

- DevilDeepu February 08, 2019 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More