Skip to content

Latest commit

 

History

History
92 lines (85 loc) · 2.57 KB

week6.md

File metadata and controls

92 lines (85 loc) · 2.57 KB

Week 6: “Random Week”

1) Palindrome

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward. Determine whether an string is a palindrome. An integer is a palindrome when it reads the same backward as forward. https://leetcode.com/problems/palindrome-number/

Input: x = 121
Output: true

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

2) RPN

Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Input: ["10", "6", "9", "3", "+", "11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation:
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Time Complexity: O(n)
Space Complexity: O(k) k where k is the number of digits

3) Compute the Levenshtein Distance

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a character https://leetcode.com/problems/edit-distance/

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Time Complexity: O(log (m+n))
Space Complexity:

3) Test Collatz Conjecture

Collatz Conjecture: take any natural number, if it is odd, triple it and add 1, if even, halve it. Repeat the process indefinitely and no matter what number, the sequence will always end with 1. Given an long n, test the Collatz Conjecture for the first n integers. If all the integers pass the Collatz Conjecture, return true. Otherwise return false.

Example sequence: 11 -> 11,34,17,52,26,13,40,20,10,5,16,8,4,2,1

input: 3
output: true