Technical Interview questions set for company W

[FredWe]

Past questions:

1. LeetCode: Merge Intervals
2. (2013) Run Length Encoding -> my solution || String Compression
3. (2013) LeetCode: Valid Parentheses
   (Other questions about parentheses to be noticed)
4. LeetCode: Find the Duplicate Number -> solution || Find duplicates in O(n) time and O(1) extra space
5. (2016) LeetCode: Contains Duplicate || Contains Duplicate II || Contains Duplicate III
   Variation: Check if there exist two indexes i and j such that a[i]=a[j] && |i - j| >= k (k is given in input). -> my solution
6. LeetCode: Power of Two
7. (2016) Maximum number of overlapping intervals || based on a custom comparator || a question example
   Finding “maximum” overlapping interval pair in O(nlog(n))
   giving lots of intervals [ai, bi], find a interval which intersect with the most number of intervals
8. (Not exactly as the following two links) Given {a -> 1, b -> 2 ...}, input a integer, output a set of letters that sum == the input integer. for e.g. 3 ==> {c} or {a, b} || Given any combination of the mapping numbers as string, return the number of ways in which the input string can be split into sub-strings and represented as character strings. || If a=1, b=2, c=3,....z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings.
9. LeetCode: ZigZag Conversion
10. Find Longest common substring between two string || related wiki
11. LeetCode: Combinations
    (Other questions about Combinations, Permutations, Subset to be noticed)
12. LeetCode: Serialize and Deserialize Binary Tree
    Variation : output List<List<>>, in level-order
13. Origami Puzzle: A origami puzzle to code for displaying the pattern as it unfolds. To find the sequence of creases in a paper which is folded n times. -> my solution
    Unfolding pattern could be represented by a pair (horizontal creases number, vertical creases number) For e.g. 0 -> (0, 0), 1 -> (0, 1), 2 -> (1, 1), 3 -> (1, 3), 4 -> (3, 3), 5 -> (3, 7), 6 -> (7, 7), 7 -> (7, 15)
14. [KMP/BM] LeetCode: Implement strStr() (KMP and BM make me dead _(:з」∠)_)
    Another application of KMP: LeetCode: Repeated Substring Pattern
15. LeetCode: Evaluate Reverse Polish Notation
    Shunting-yard algorithm
    (Other questions about Postfix notation, Expression Evaluation to be noticed)
16. LeetCode: Permutations
    Find all permutations of a string and print them in alphabetical order
    Print all the permutations of the string.
 Variation: remove duplicates, and change order such that small letters are considered before Capital letters. a->A->b->B->...->z->Z. (Not sure about it, was either this or A->a->B->b..->Z->z)  
17. LeetCode: Edit Distance
18. LeetCode: 3Sum || 3Sum Closest
19. (Quick select) Kth Largest Element in an Array
20. LeetCode: Largest Number (smallest)
21. LeetCode: Wiggle Sort
22. LeetCode: Wildcard Matching

Other questions:

• Give you some point, to choose three point to build a triangle which has the least perimeter. || Similar question
• (MDS) One-dimensional Maximum disjoint set:
  Find number of disconnect intervals from an array of intervals. For instance, (2, 4) and (3,5) can be merged to (2,5) while (1, 6) (7,9) are considered two disconnected intervals. Output how many disconnected intervals
  explanation 1 || explanation 2 || explanation 3 || explanation 4
  Details in intervals related questions
• Sort an array with minimum complexity, by adding new numbers?
• Given two numbers M and N, p is from [M,N] and q is from [1,p-1], find all irreducible fractions of p/q.
  Given 2 positive integer M, N, making 0 < a < M, M <= b <= N. Output each fractions as a / b, reducible or irreducible
  Reduce a fraction to its smallest irreducible form and arrange all such fractions in the increasing order of their value.
  Solution: [p/q for p in [M..N] for q in [1..p-1] if gcd(p,q) == 1]
  explanation 1 || explanation 2
• segregating zeros and ones in an array
• reduction of strings (consisting of a, b & c) & by replacing two chars with the third one.
  BFS solution instead of exhaustive recursion
  (DP) HackerRank: String Reduction
  tricky solution

Important Preparations List:

• (LCSubstr) Longest Common Substring (Find only first | Find all)
  • my solution only getting max length, my solution for finding all lcstr
• (LCS) Longest Common Subsequence (Find only first | Find all)
  • Variation: remove duplicates
• Longest Increasing/Decreasing Substring(contiguous subsequence) (Find only first | Find all)
  • Example Description: You will write a program to read numerical string (all the characters are digits) from keyboard, and then print the longest increasing substring.
    For example, given an input string "892478134", there are three increasing substrings, “89”, “2478” and “134”. The digits of each substring are in increasing order (781 is not an increasing string, since 1 is smaller than the first 2 digits). From these three options, “2478” is the longest substring, so we will print it as the longest increasing substring.
    Hints :
    1) Even though input consists of just digits, reading it as a String instead number is more convenient, so you can access each digit easily using the String methods. Moreover, the string input can have any length while an integer input is restricted to the size of data types.
    2) To implement this program think of:
    - How to detect increasing substrings;
    - How to keep track of the longest substring
    3) If you have more than one longest substring (equal size), print the last as output substring
• (LIS) Longest Increasing/Decreasing Subsequence (Find only first | Find all)
  • Variation: considering the fact that input-values are Hexadecimal string instead of the Decimal values.
  • Reading: Writting right binary search
• (LRS) Longest Repeated Substring (Find only first | Find all)
  • Variation: ignoring Uppercases/Lowercases
  • Longest substring appearing more than once
  • (LCP) Tool method: Longest Common Prefix
  • Suffix array: A simple application || Application in LRS || explanation
• (GCD) Greatest Common Divisor / (LCM) Least Common Multiple (for fractions related problems)
  • gcd(a, b): return b == 0 ? a : gcd(b, a % b)
• Permutations / Combinations / Subsets for Array / String
  • Limit: in sorted order.
• 0/1 Knapsack problem
  • Jiuzhang simplest explanation
  • 0-1 knapsack || complete knapsack

Currently not handled well:

• String Reduction
  • Another easier string replacement question
• Quick select
• KMP / BM