SWE Interview preparation

https://leetcode.com/problems/powx-n/ Implement  pow( x ,  n ) , which calculates  x  raised to the power  n  (x n ). Example 1: Input: 2.00000, 10 Output: 1024.00000 Example 2: Input: 2.10000, 3 Output: 9.26100 Example 3: Input: 2.00000, -2 Output: 0.25000 Explanation: 2 -2 = 1/2 2 = 1/4 = 0.25 Note: -100.0 <  x  < 100.0 n  is a 32-bit signed integer, within the range [−2 31 , 2 31  − 1] --- Intuition if pow < 0     pow = Math.abs(pow)     base = 1.0 / base Cast power to long to prevent against integer overflow when taking Math.abs while (pow > 0) {     pow = pow / 2; } Above is log N complexity To compute power, square the number in every iteration - running calculation If power is odd, multiply answer with number one extra time --- Time - O(log N) Space - O(1) ---

https://leetcode.com/problems/angle-between-hands-of-a-clock/ Given two numbers,  hour  and  minutes . Return the smaller angle (in degrees) formed between the  hour  and the  minute  hand.   Example 1: Input: hour = 12, minutes = 30 Output: 165 Example 2: Input: hour = 3, minutes = 30 Output: 75 Example 3: Input: hour = 3, minutes = 15 Output: 7.5 Example 4: Input: hour = 4, minutes = 50 Output: 155 Example 5: Input: hour = 12, minutes = 0 Output: 0   Constraints: 1 <= hour <= 12 0 <= minutes <= 59 Answers within  10^-5  of the actual value will be accepted as correct.

https://leetcode.com/problems/count-and-say/ The count-and-say sequence is the sequence of integers with the first five terms as following: 1. 1 2. 11 3. 21 4. 1211 5. 111221 1  is read off as  "one 1"  or  11 . 11  is read off as  "two 1s"  or  21 . 21  is read off as  "one 2 , then  one 1"  or  1211 . Given an integer  n  where 1 ≤  n  ≤ 30, generate the  n th  term of the count-and-say sequence. You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit. Note: Each term of the sequence of integers will be represented as a string.   Example 1: Input: 1 Output: "1" Explanation: This is the base case. Example 2: Input: 4 Output: "1211" Explanation: For n = 3 the term was "21" in which we have two groups "2" and "1", "2" can be read as "12" which means frequency = 1 and value =

https://leetcode.com/problems/factorial-trailing-zeroes/ Given an integer  n , return the number of trailing zeroes in  n !. Example 1: Input: 3 Output: 0 Explanation:  3! = 6, no trailing zero. Example 2: Input: 5 Output: 1 Explanation:  5! = 120, one trailing zero. Note:  Your solution should be in logarithmic time complexity. --- Intuition - Count number of 5 factors in n Time - O( Log N base 5) ---

https://leetcode.com/problems/valid-triangle-number/ Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle. Example 1: Input: [2,2,3,4] Output: 3 Explanation: Valid combinations are: 2,3,4 (using the first 2) 2,3,4 (using the second 2) 2,2,3 Note: The length of the given array won't exceed 1000. The integers in the given array are in the range of [0, 1000].

https://leetcode.com/problems/evaluate-division/ Equations are given in the format  A / B = k , where  A  and  B  are variables represented as strings, and  k  is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return  -1.0 . Example: Given  a / b = 2.0, b / c = 3.0. queries are:  a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? . return  [6.0, 0.5, -1.0, 1.0, -1.0 ]. The input is:  vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries  , where  equations.size() == values.size() , and the values are positive. This represents the equations. Return  vector<double> . According to the example above: equations = [ ["a", "b"], ["b", "c"] ], values = [2.0, 3.0], queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], [&q

https://leetcode.com/problems/fraction-to-recurring-decimal/ Given two integers representing the numerator and denominator of a fraction, return the fraction in string format. If the fractional part is repeating, enclose the repeating part in parentheses. Example 1: Input: numerator = 1, denominator = 2 Output: "0.5" Example 2: Input: numerator = 2, denominator = 1 Output: "2" Example 3: Input: numerator = 2, denominator = 3 Output: "0.(6)"

https://www.lintcode.com/problem/number-of-distinct-islands-ii/description https://leetcode.com/problems/number-of-distinct-islands-ii Given a non-empty 2D array  grid  of 0's and 1's, an  island  is a group of  1 's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water. Count the number of  distinct  islands. An island is considered to be the same as another if they have the same shape, or have the same shape after  rotation  (90, 180, or 270 degrees only) or  reflection  (left/right direction or up/down direction). Example 1: 11000 10000 00001 00011 Given the above grid map, return  1 . Notice that: 11 1 and 1 11 are considered  same  island shapes. Because if we make a 180 degrees clockwise rotation on the first island, then two islands will have the same shapes. Example 2: 11100 10001 01001 01110 Given the above grid map, return  2 . Here are the two distinct islan

https://leetcode.com/problems/excel-sheet-column-number/ Given a column title as appear in an Excel sheet, return its corresponding column number. For example: A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ... Example 1: Input: "A" Output: 1 Example 2: Input: "AB" Output: 28 Example 3: Input: "ZY" Output: 701 ---

https://leetcode.com/problems/rectangle-area/ Find the total area covered by two  rectilinear  rectangles in a  2D  plane. Each rectangle is defined by its bottom left corner and top right corner as shown in the figure. Example: Input: A = -3 , B = 0 , C = 3 , D = 4 , E = 0 , F = -1 , G = 9 , H = 2 Output: 45 Note: Assume that the total area is never beyond the maximum possible value of  int . ---

https://leetcode.com/problems/rotated-digits/ X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X.  Each digit must be rotated - we cannot choose to leave it alone. A number is valid if each digit remains a digit after rotation. 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other (on this case they are rotated in a different direction, in other words 2 or 5 gets mirrored); 6 and 9 rotate to each other, and the rest of the numbers do not rotate to any other number and become invalid. Now given a positive number  N , how many numbers X from  1  to  N  are good? Example: Input: 10 Output: 4 Explanation: There are four good numbers in the range [1, 10] : 2, 5, 6, 9. Note that 1 and 10 are not good numbers, since they remain unchanged after rotating. Note: N  will be in range  [1, 10000] . ---

https://leetcode.com/problems/integer-to-roman/ 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, two is written as  II  in Roman numeral, just two one's added together. Twelve is written as,  XII , which is simply  X  +  II . The number twenty seven is written as  XXVII , which is  XX  +  V  +  II . Roman numerals are usually written largest to smallest from left to right. However, the numeral for four 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 principle 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

https://www.lintcode.com/problem/strobogrammatic-number-ii/description https://leetcode.com/problems/strobogrammatic-number-ii A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Find all strobogrammatic numbers that are of length = n. Example: Input: n = 2 Output: ["11","69","88","96"] --- Intuition All possible combinations  => DFS Fill in the string from two ends Terminate recursion when i reaches (n + 1) / 2 Skip 6, 9 for midpoint of odd length string Skip 0 for > 1 length string ---- Time - O(N) Space - O(N) --- Related problems strobogrammatic-number --- ---

https://leetcode.com/problems/find-median-from-data-stream/ Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. For example, [2,3,4] , the median is  3 [2,3] , the median is  (2 + 3) / 2 = 2.5 Design a data structure that supports the following two operations: void addNum(int num) - Add a integer number from the data stream to the data structure. double findMedian() - Return the median of all elements so far. Example: addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2 Follow up: If all integer numbers from the stream are between 0 and 100, how would you optimize it? If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it? ----