Coding Interview Question

Best Time to Buy and Sell Stock

Easy

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

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

Note

You cannot sell a stock before you buy one.

Example 1

Input: [7, 1, 5, 3, 6, 4]
Output: 5
Explanation: 
	Buy on day (price = 1) and sell on day 5 (price = 6), profit = 6 - 1 = 5. 
	Not 7 - 1 = 6, as selling price needs to be larger than buying price.

Best Time to Buy and Sell Stock II

You are given an array prices where prices[i] is the price of a given stock on the i^th day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e, buy one and sell one share of the stock multiple times.

Note: You may not engage in multiple transactions simultaneously (i.e, you must sell the stock before you buy again).

Example

Input: prices = [7, 1, 5, 3, 6, 4]
Output: 7
Explanatikon: Buy on day 2 (price = 1) and sell on day 3 (price = 5), prifit = 5 - 1 = 4
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6 - 3 = 3.

Two Sum

Easy

Given an array of integers, return indexes of the two numbers such that they add up to a specific target.

You may assume that each input would have Exaclty one solution and you may not use the same element twice

Example

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9
return [0, 1]

Two Sum II - Input array is soted

Easy

Given an array of integers tha is already sorted in ascending order, find two numbers such that they add up to a special target number.

The function TwoSum should return is indices of the two numbers such that they add up to the target, where index1 must me less than index2

Note

Your returned answers (both index1 and index2)
You may assume that each input would have exactly one solution and you may not use the same element twice.

Example

Input: numbers: [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: The sum of 2 and 7 is 9. Threrefor index1 = 0, index2 = 1.

Three Sum

Medium

Given an array nums of n integers, are there elements a, c, c in nums such that a + b + c = 0? Find all unique triples in the array which givens the sum of zero.

Note

The solution set must not contain duplicate triplets

Example

Give array nums = [-1, 0, 1, 2, -1, -4]
A solution set is:
[
	[-1, 0, 1],
	[-1, -1, 2]
]

House Robber

Easy

You are a profession robber plaining to rob houses along a street. Each house has as certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent house were broken into on the same night

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police

Example 1:

Inputs: nums = [1, 2, 3, 1]
Output: 4
Explanation: Rob house 1 (mony = 1) and then rob house 3 (money = 3)
	Total amount you can rob = 1 + 3 = 4

Integer to Roman

Medium

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

For example, is writen as II in Roman numeral, just two one's added together. 12 is writen as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually writen largest to smallest from left to right. However, the numeral for is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same priciple applies to the number nine, which is written as IX. There are six instances where subtraction is used.

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C(100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900

Given an integer, convert it to a roman numeral

Roman to Integer

Easy

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

For example, is writen as II in Roman numeral, just two one's added together. 12 is writen as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C(100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900

Given a roman numeral, convert it to an integer.