## Amazon Interview Questions

- 0of 0 votes

Answersgiven a n-ary tree, find the total distance from this node to any other nodes

- ajay.raj May 04, 2018 in United States

class TreeNode {

int val;

List<TreeNode> children;

TreeNode(int val) {

this.val = val;

children = new ArrayList<>();

}

}

public int findDistance(TreeNode root, TreeNode node) {

}| Report Duplicate | Flag | PURGE

Amazon Software Engineer - 1of 1 vote

AnswersHow many squares are inside a m*n rectangle where some grids in the rectangle were grey and the gray grid could not appear in the small squares.

- ajay.raj May 03, 2018 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 - 1of 1 vote

AnswersGiven an int array, check if all the numbers can be divided into 5 consecutive numbers.

- ajay.raj May 03, 2018 in United States

Eg: [1,2,2,3,3,4,4,5,5,6] Yes: (1,2,3,4,5) (2,3,4,5,6)

Followup: ask if you know that all the numbers are between 1 and 13,

what's a good optimization.| Report Duplicate | Flag | PURGE

Amazon SDE1 - 1of 1 vote

AnswerYou have two matrixs, how to move the first matrix

(move up, down, left, and right) so that the two matrix in the two matrixs match most.`eg: matrix 1: matrix 2: 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0`

Then, after taking matrix1 (1 left shift + 1 down),

- ajay.raj May 03, 2018 in United States

the number of 1 in the match with matrix2 is 3| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

Answershow to check if two graphs are structurally identical

- ajay.raj May 03, 2018 in United States

class UndirectedGraphNode {

List<UndirectedGraphNode> neighbors;

UndirectedGraphNode() {

neighbors = new ArrayList<>();

}

}| Report Duplicate | Flag | PURGE

Amazon SDE1 - 1of 1 vote

Answersconvert a Sorted array to complete BST

- ajay.raj May 02, 2018 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswerGive a connected graph, no cycle,

- ajay.raj May 01, 2018 in United States

Find the node where the average distance from all other nodes is the smallest| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswerInput: an int array without sorting, then do a binary search on it, and find the number of digits that cannot be found by binary search.

- ajay.raj May 01, 2018 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

Answers<key = "a"; val = "3"; depend_list = null;/>; <key = "b"; val = "a * a";

- ajay.raj May 01, 2018 in United States

Depend_list = {a};/>; <key = "c"; val = "a * b"; depend_list = {a,b};/>;

Lets output a map<key, value>,a -> 3, b -> 9, c -> 27

Follow-up questions: Make a statistic for all keys and corresponding map entries with the same value.| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswersGiven an array, find an x such that all numbers less than x are equal to themselves. Numbers greater than it are equal to x, and all numbers add up to a target

- ajay.raj May 01, 2018 in United States

For example, [1 3 5 7 9] target=24, answer is8. Because when x=8, the array has only 9>8, so 1+3+5+7+8=24 is the closest to the target.| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswerGive an N-length array with only 0 and 1 inside

- ajay.raj May 01, 2018 in United States

Requires to find the minimum number of conversions needed to convert the array to 0 before all 1.

The conversion is to change a 0 to 1 or a 1 to 0,

And the number of 0 and 1 in the converted array can be arbitrary.

Just find the minimum conversion step| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswersImagine a horizontal corridor bounded by y = y1 and y = y2 lines on a 2D-plane. There are N sensors with centers (x, y) each of which operates in a range (r) on the plane . So, they cover some circular areas on the plane. See the figure below.

`o | _____o___o__|____________ y = y1 o |OOO __________oo|_____O______ y = y2 O | O _ _ _ _ _ _ | _ _ _ _ _ _ | o O | o O O | | O | |`

The question is whether a path exist from x=-inf to x=+inf via corridor without being detected any radar.

Constraints:

1. You are free to move any direction only if you stay in the corridor.

2. You are free to go through corridor borders.

3. N sensors are given as list of (x, y, r) like [(1, 3, 2), (-1, -3, 4)]. x and y are signed integers. r is a unsigned integer.

4. y1 and y2 are integers.

My solution:

1. Create an intersection graph of N sensors by comparing them each other via Euclidean distance`(x1 - x2)^2 + (y1 - y2)^2 <= (r1 + r2)^2`

2. If there is a path between y=y1 and y=y2 through intersected sensors, there do not exist any path from x=-inf to x=+inf. Otherwise, there do exist a path. So, I used BFS to search such a path.

Worst Case Complexity:

1. O(n^2)

2. O(V + E) = O(n + intersection_count)`Total: O(n^2)`

My Best Case Optimization for Intersection Graph:

- engineer06 April 29, 2018 in United States

1. For each sensor, create two events for start and end of circles vertically. y = (y1 - r) and y = (y1 + r)

2. For each sensor, register those two events into an array.

3. Use a line sweep algorithm over 2, which is O(nlogn + intersection_count) and intersection_count may be n^2 at worst case.

I wonder if I should have had a better solution with the worst case < O(n^2).| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm - 0of 0 votes

AnswersNumbers with 4 are considered to be unlucky, floor numbers are skipped with numbers with 4; for a top level n, ask how many layers there are actually; for example n=20, that is 18 levels [Remove 4, 14]

- ajay.raj April 28, 2018 in United States| Report Duplicate | Flag | PURGE

Amazon Java Developer - 0of 0 votes

AnswersI read this question here in careercup and saw no comments on it. So, I am answering it.

- mohapatrasandeep60 April 24, 2018 in United States

given a string find the sum of number of unique substring characters.

means if string is ACAX. the sub strings are A,C,A,X,AC,CA,AX,ACA,CAX,ACAX. in ACA, A occurs more than once so, its count is not considered, but C occurs once so its count is 1. Similarly in ACAX, A's count=0,C's count=1,X's count=1. In such a manner find sum of all counts for all substrings. The worst case time complexityis O(n). IF same substring occurs more than once then find its sum for that many times.| Report Duplicate | Flag | PURGE

Amazon - 0of 0 votes

AnswersInput unsorted integer array represents a list of coins,

- ajay.raj April 18, 2018 in United States

find the minimum amount of money that cannot be formed by these coins, each coin can only be used once

E.g. {1,1} -> 3, {1,2,4} -> 8| Report Duplicate | Flag | PURGE

Amazon Java Developer - 0of 0 votes

AnswersGive me a list of int, find the length of the smallest cycle. For example, 1, 2, 1, 2, the length of the cycle is 2. Then 1, 2, 1, 2, 1 has a minimum length of 2. Then the length of 1, 2, 1, 2, 3 should be 5 because the entire list is not in repeat. Then the minimum length of 1, 2, 1, 2, 1, 1, 2 is 2.

- ajay.raj April 16, 2018 in United States| Report Duplicate | Flag | PURGE

Amazon Backend Developer - 0of 0 votes

AnswersFind the kth missing element in a sorted array. For example [2,3,5,7], k = 0: return 4, k = 1: return 6

- ajay.raj April 12, 2018 in United States

expected time complexity logn| Report Duplicate | Flag | PURGE

Amazon Backend Developer - 0of 0 votes

AnswersTo an array and K, each element in the array can only move K positions to the left at most, no limit to the right, try to sort the array under the limit of K

- ajay.raj April 10, 2018 in United States

a = [5, 2, 4, 3, 1], k = 2

Return [2, 3, 1, 4, 5]| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswersGiven a function rand32() (random number range 0-2**32-1) that randomly generates a 32-bit int, design a new random function:

- ajay.raj April 09, 2018 in United States

Randn(n) generates a random distributed random number (0 - 2**n-1)

Rand3n(n) generates (0 - 3**n-1) the uniformly distributed random number| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswerTopic: There is a set of coordinates. The original format of each coordinate is (1.3, 0.5). However, the comma and decimal point are gone. Only one string is left, allowing you to restore all possible combinations. For example, 123, possible (1, 23) (1, 2.3) (12, 3) (1.2, 3)

- ajay.raj April 09, 2018 in United States| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

Answersgiven period and threshold, Assume there is a endless streaming events, each event occurs at timestamp "x". The question want you to write an API that return true if number of the events are over the threshold within the period around timestamp "x"

- ajay.raj April 08, 2018 in United States

Ex:

period = 3, threshold =2

getEvent(10) -> false

getEvent(12) -> false

getEvent(13) -> true [10,12,13]

getEvent(20) -> false

part one: event come in order

part two: event come without order| Report Duplicate | Flag | PURGE

Amazon Software Developer - 0of 0 votes

AnswersGiven vector<int> nums, and pair<int, int> range. Find out how many continuous subsequences within this vector sum up the number within the range.

- ajay.raj April 08, 2018 in United States

Input: [1, 2, 3], [3,6]

Output: (4)

because [1,2,3], [1,2], [2,3], [3]| Report Duplicate | Flag | PURGE

Amazon Software Developer - 0of 0 votes

AnswerEach have a (x,y) coordinate.

- ajay.raj April 08, 2018 in United States

Write an API that group three Googler together for lunch if they are close enough. Otherwise, throw them in un-schedule pool.

Distance formula = sqrt((x1-x2) ^2 + (y1-y2) ^2)

Given an int range;

Range: 2

Input | Output of API Un-schedule pool

0,0 -> [] [[0,0]]

1,0 -> [] [[0,0], [1,0]]

3,0 -> [] [[0,0], [1,0], [3,0]]

1,1-> [[0,0], [1,0], [1,1]] [[3,0]]| Report Duplicate | Flag | PURGE

Amazon Software Developer - 0of 0 votes

AnswersGiven an vector<int> nums and an int target, you can change any element of the vector to positive or negative. How many uniquely different vector sum up to target?

- ajay.raj April 08, 2018 in United States

Input: [1,1,1], target = 2

[-1,1,1]

[1,-1,1]

[1,1,-1]

return (3)| Report Duplicate | Flag | PURGE

Amazon Software Developer - 0of 0 votes

Answerfind max path sum in DAG, weight can be negative

- ajay.raj April 06, 2018 in United States| Report Duplicate | Flag | PURGE

Amazon Software Engineer - 0of 0 votes

AnswersImplement a method to check if a n-ary tree is unival

- ajay.raj April 04, 2018 in United States

class TreeNode {

int val;

List<TreeNode> children;

TreeNode(int val) {

this.val = val;

children = new ArrayList<>();

}

}| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswersGiven the length and width of a rectangle, how many ways can be used to go from the upper left corner to the upper right corner (each step can only go to the right, top right or bottom right):

- ajay.raj April 03, 2018 in United States

-follow up 1: If three points in the rectangle must be visited, how many ways

-follow up 2: If you are given an point H, and the path must go down below the H point, how to do it| Report Duplicate | Flag | PURGE

Amazon SDE1 - 0of 0 votes

AnswersThe thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms an n-nary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

- ajay.raj March 31, 2018 in United States

Determine the maximum amount of money the thief can rob tonight without alerting the police.

/**

* Definition for a n-ary tree node.

* public class TreeNode {

* int val;

* List<TreeNode> kids;

* }

*/

class Solution {

public int rob(TreeNode root) {

}

}| Report Duplicate | Flag | PURGE

Amazon SDE1 - 1of 1 vote

AnswerFor two string a, b, their distance is defined as the number of positions at which the corresponding character are different.

- ajay.raj March 31, 2018 in United States

Now you can swap characters at any two locations once, and ask how to swap to make the distance the smallest.| Report Duplicate | Flag | PURGE

Amazon Backend Developer - 0of 0 votes

Answerspreorder Traversing a n-ary tree without using recurrsion

- ajay.raj March 31, 2018 in United States

TreeNode<T> {

T val;

List<TreeNode> children;

}| Report Duplicate | Flag | PURGE

Amazon SDE1

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window