# Amazon Interview Experience for Fresher SDE - 1, Jan 2019

## PROFILE

## Preparation

Do lot of hard work and practice of Data Structures and Algorithms based questions. I personally recommend you Coding Ninjas and Geeks For Geeks for interview preparation.

## Application Process

Make your resume short and try to make it of one page only and do mention all your skills which you are confident of in your resume.

## Interview Process

### Round 1

Given a “2 x n” board and tiles of size “2 x 1”, count the number of ways to tile the given board using the 2 x 1 tiles. A tile can either be placed horizontally i.e., as a 1 x 2 tile or vertically i.e., as 2 x 1 tile.

Examples:

Input n = 3

Output: 3

Explanation:

We need 3 tiles to tile the board of size 2 x 3.

We can tile the board ...

Given an encoded string where repetitions of substrings are represented as substring followed by count of substrings. For example, if encrypted string is “ab2cd2” and k=4 , so output will be ‘b’ because decrypted string is “ababcdcd” and 4th character is ‘b’.

Note: Frequency of encrypted substring can be of more than one digit. For example, in “ab12c3”, ab is repeated 12 time...

### Round 2

Given an array of positive and negative integers, print x if +x and -x are present in the array.

### Round 3

At the beginning of this round, the interviewer asked me about the data structures I knew. Linked lists, trees, graphs, arrays etc. was my answer. He asked me how well I knew Dynamic Programming. I said I wasn’t strong in that and he said that he would ask me a question on dynamic programming for sure.

Given a generic tree, find the count of all special nodes. A node is a special node if there is a path from root to that node with all distinct elements. The input was not a pointer to a tree. He’d give me an adjacency list and an array of values where the value of ith node in the adjacency list is the ith element in the values array. He asked me not a create a tree out of the given information...

Given an integer array, find the longest subsequence with adjacent numbers having a digit in common. Eg: 1 12 44 29 33 96 89 . The longest subsequence here is { 1 12 29 96 89} and the answer is 5.

### Round 4

The interviewer asked me if I was comfortable with the interview process so far and how the previous interviews were. I said it was good and he gave me the first problem to solve.

Given a binary tree, modify the tree satisfying the following constrains :

Value at root must be the sum of left child and right child (not subtrees).

You can’t reduce the value at any node. You can only increase it.

Value of root node must be minimum

Given an array A of size N containing 0s, 1s, and 2s; you need to sort the array in ascending order. You can scan the array only once.

### Round 5

The interviewer asked me some Computer Science fundamentals in this round as well as some behavioural questions.

Implement a Trie data structure and write functions to insert and search for a few words in it.

Given two strings a and b consisting of lowercase characters. The task is to check whether two given strings are anagram of each other or not. An anagram of a string is another string that contains same characters, only the order of characters can be different. For example, “act” and “tac” are anagram of each other.

*Comment Removed*

Thank You So much. For the splitwise question DP something like subset sum will work.

*Comment Removed*

great