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.
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]
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]
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
.
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
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 1 : Buy
Day 2 : Sell
Day 3 : Buy
Day 4 : Sell
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
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
.
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.
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