Clafication
  • First, I have some questions that need clarification. / I want to ask some clarifying questions to help me understand the problem better.
  • Can the input string/array be null or empty or only have one element?
  • Can the input string contain extra characters or whitespace?
  • Can the input string contain any leading zero?
  • Is the array sorted?
  • Do I need to sort/reorder the array in-place or not?

  • Can the array/list/dict contain duplicate number/string/Integer.MIN_VALUE?

  • Can I modify the input? e.g. I want to change the char as a visited mark.

  • What's the range of the characters in the input string? e.g. only have lowercases or ASCII ['æski].

  • Do you have any requirement for the time and space complexity?

  • Do I need to write the method signature by myself? If
    (the method name and the number, type and order of its parameters, Return types and thrown exceptions are not considered to be a part of the method signature.)

  • gg的风格感觉变了，不能一上来就写题，他会要求我问一些关于这个input，output的问题，感觉这个答得不好。

  • 如果是电面，最好边打字边说；如果是onsite，最好边写边说

  • I'm not done yet. Let me work through a test case to check if there is a bug in my code.

Understanding
  • I think it is better for me to walk through an example to help me understand this problem better. e.g. Does I comprehend the question correctly?
Solution
  • Let me have a think
  • I am trying to find the pattern to solve the problem.
  • Essentially, this problem is a variation of two sum / Fibonacci sequence / Binary Tree Level Order Traversal.
  • I think this problem can be solved by DP because
  • Use an Integer variable to keep track of the max/min length

写完代码后要walk through a test case 或者 analyze the complexity，complexity优化可以从O(3n)到O(2n)，也是优化。

Recursive
  • For recursive solution, we need to find out the basic case and general case. Here, the basic case is very obvious which is that when n is 1, the function should return 1/ something else.
找规律题
  • Maybe we can find some pattern from first 20 digits.
Testcase
  • Corner Cases
  • Normal Cases
  • Extreme Cases
Complexity
  • since we only need to scan the string from left to right only once, the TC is O(n).
  • Time complexity :O(n^n). Consider the worst case where s= "\text{aaaaaaa}aaaaaaa" and every prefix ofssis present in the dictionary of words, then the recursion tree can grow up to n^n​​.
  • Space complexity :O(n). The depth of the recursion tree can go up to n.
Terms

perimeter, lexicographically, ternary operator

results matching ""

    No results matching ""