Dynamic Programming, Easy

Question

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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

1
2
3
4

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (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.

Example 2:

1
2
3

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Backtracking, Easy

Quesion

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

1
2
3
4
5
6
7
8
9

Examples:
Input: S = "a1b2"
Output: ["a1b2", "a1B2", "A1b2", "A1B2"]
Input: S = "3z4"
Output: ["3z4", "3Z4"]
Input: S = "12345"
Output: ["12345"]

Note:

• S will be a string with length at most 12.
• S will consist only of letters or digits.

Breath-first-search

Question:

You are given a data structure of employee information, which includes the employee’s unique id, his importance value and his directsubordinates’ id.

For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct.

Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all his subordinates.

Example 1:

1
2
3
4

Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
Output: 11
Explanation:
Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3. So the total importance value of employee 1 is 5 + 3 + 3 = 11.

Note:

1. One employee has at most one direct leader and may have several subordinates.
2. The maximum number of employees won’t exceed 2000.

Question:

Write a function that takes a string as input and returns the string reversed.

Example:
Given s = “hello”, return “olleh”.

Question

卡拉兹(Callatz)猜想：

对任何一个自然数n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把(3n+1)砍掉一半。这样一直反复砍下去，最后一定在某一步得到n=1。卡拉兹在1950年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证(3n+1)，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展……

我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过1000的正整数n，简单地数一下，需要多少步（砍几下）才能得到n=1？

输入格式：每个测试输入包含1个测试用例，即给出自然数n的值。

输出格式：输出从n计算到1需要的步数。

输入样例：

1

3

输出样例：

1

5

Question:

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

Note: The merging process must start from the root nodes of both trees.

Grokking Algorithms (TURING)

Author: Aditya Bhargava

1.Binary_search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def binary_search(list, item):
    """
    list must be ordered
    time: O(logn)
    """
    low = 0
    high = len(list)-1
    while(low <= high):
        mid = (low + high)/2
        if list[mid] == item:
            return mid
        if list[mid] < item:
            low = mid+1
        else:
            high = mid-1
    return None
if __name__ == '__main__':
    print(binary_search([1,3,5,7,9],5))
    print(binary_search([1,3,4,7,8],9))

2.Selection_sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def findSmallest(arr):
    """
    input: arr
    output: smallest_index
    """
    smallest = arr[0]
    smallest_index = 0
    for i in range(len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index
def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest_index = findSmallest(arr)
        newArr.append(arr.pop(smallest_index))
    return newArr
if __name__ == '__main__':
    print(selectionSort([5, 3, 6, 2, 10]))

Question:

Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

1
2

Input: "()"
Output: true

Example 2:

1
2

Input: "()[]{}"
Output: true

Example 3:

1
2

Input: "(]"
Output: false

Example 4:

1
2

Input: "([)]"
Output: false

Example 5:

1
2

Input: "{[]}"
Output: true

Question：

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

1
2

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

1
2
3

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

Question:

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Hints:

Hint-1:

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

Hint-2:

• If I comes before V or X, subtract 1 eg: IV = 4 and IX = 9
• If X comes before L or C, subtract 10 eg: XL = 40 and XC = 90
• If C comes before D or M, subtract 100 eg: CD = 400 and CM = 900