# Amazon

## Interview Questions

Sergey Kharagorgiev
What to expect at Amazon?

Be able to discuss the big-O complexity of your approaches. Don't forget to brush up on your data structures like lists, arrays, hash tables, hash maps, stacks, queues, graphs, trees, heaps. Also sorts, searches, and traversals(BFS, DFS). Also review recursion and iterative approaches.
Use the programming language you're best at. It's important to write your solution correctly and in time, so use the language you are most familiar with.
Find and fix the bugs by yourself: Don't wait for the interviewer to find them for you.
Use the hints you are given: Usually, the interviewer knows the question well enough to know which hints will help you next if you get stuck.

Gas Station

There are `N` gas stations along a circular route, where the amount of gas at station `i` is `gas[i]`.

You have a car with an unlimited gas tank and it costs `cost[i]` of gas to travel from station `i` to its next station `(i+1)`. You begin the journey with an empty tank at one of the gas stations.

Return the minimum starting gas station’s index if you can travel around the circuit once, otherwise return `-1`.

You can only travel in one direction. `i to i+1, i+2, ... n-1, 0, 1, 2..`
Completing the circuit means starting at `i` and ending up at `i` again.

Example :

``````Input :
Gas :   [1, 2]
Cost :  [2, 1]

Output : 1

If you start from index 0, you can fill in gas[0] = 1 amount of gas. Now your tank has 1 unit of gas. But you need cost[0] = 2 gas to travel to station 1.
If you start from index 1, you can fill in gas[1] = 2 amount of gas. Now your tank has 2 units of gas. You need cost[1] = 1 gas to get to station 0. So, you travel to station 0 and still have 1 unit of gas left over. You fill in gas[0] = 1 unit of additional gas, making your current gas = 2. It costs you cost[0] = 2 to get to station 1, which you do and complete the circuit.

``````

Longest Increasing Subsequence

Find the longest increasing subsequence of a given sequence / array.

In other words, find a subsequence of array in which the subsequence’s elements are in strictly increasing order, and in which the subsequence is as long as possible.
This subsequence is not necessarily contiguous, or unique.
In this case, we only care about the length of the longest increasing subsequence.

Example :

``````Input : [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
Output : 6
``````

The sequence : `[0, 2, 6, 9, 13, 15]` or `[0, 4, 6, 9, 11, 15]` or `[0, 4, 6, 9, 13, 15]`

Max Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.
Return an integer corresponding to the maximum product possible.

Example :

``````Input : [2, 3, -2, 4]
Return : 6

Possible with [2, 3]
``````

Ways to Decode

A message containing letters from `A-Z `is being encoded to numbers using the following mapping:

``````'A' -> 1
'B' -> 2
...
'Z' -> 26
``````

Given an encoded message containing digits, determine the total number of ways to decode it.

Example :

Given encoded message `"12"`, it could be decoded as `"AB"` `(1 2)` or `"L"` `(12)`.

The number of ways decoding `"12"` is `2`.

Best Time to Buy and Sell Stocks II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example :

``````Input : [1 2 3]
Return : 2
``````

Best Time to Buy and Sell Stocks III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example :

``````Input : [1 2 1 2]
Output : 2

Explanation :
Day 2 : Sell
Day 4 : Sell
``````

Best Time to Buy and Sell Stocks I

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example :

``````Input : [1 2]
Return :  1
``````

Max Sum Path in Binary Tree

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

Example :

Given the below binary tree,

``````       1
/ \
2   3
``````

Return `6`.

Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example :
Given
`s = "aab"`,
Return `1` since the palindrome partitioning `["aa","b"]` could be produced using `1` cut.

Min Sum Path in Matrix

Given a `m x n` grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example :

``````Input :

[  1 3 2
4 3 1
5 6 1
]

Output : 8
1 -> 3 -> 2 -> 1 -> 1
``````