[Oracle面经】Coding Question Oracle OA 开发岗 数据岗

喵贵妃 2020-7-27 567

Input: An array of characters, example: [a,a,b,b,b,a,c] Ouput: Smallest length reduced form after removing duplicates step by step: [c]

[a,a,b,b,b,a,c] ---remove all b---> [a,a,a,c] ---remove all a---> [c] [a,b,c,c,b,a,a] ---remove all c---> [a,b,b,a,a] ---remove all b---> [a,a,a] --> []

Does anyone know if it's similar to an existing leetcode question? I couldn't find the solution, but interviewer hinted that it's about using a stack.

最新回复 (1)
  • Crusader 7月前
    0 引用 2
    #-*- coding:utf-8 -*-
    When you see 'duplicates' related questions you should immediately
    hint yourself with the most powerful set of data structures that solve
    this type of problem. Taking Java as an example, typical data structures
    are HashMap and HashSet which are normally used to count or mark presense of
    In Python, there are also set() and dict() (i.e., '{}') for you to use.
    In C, there are bitmap and lookup table. Highly recommend you to understand
    the principles before you jump to a solution.
    In this problem, no matter how you reduce the form of the array of characters,
    you are always removing characters that appear more than once. Since you did not
    mention clearly if the interviewer wants the reduced array or the list of
    reduction steps, I assume it's the reduced array.
    As you listed in your examples:
    Input: [a,a,b,b,b,a,c] Output: [c]
    Input: [a,b,c,c,b,a,a] Output: []
    On the other hand, you should also ask the interviewer if the original "Array"
    is mutable or immutable and if extra memory is allowed to allocate to solve
    this problem.
    From the hint, it seems a stack solution is possible but not necessary. Stack is used
    often if the order of something makes a difference to your output.
    Here the order of the removal steps don't really affect the output.
    I.e., you can remove all 'a' first or all 'b' first, the output is always
    [c] in the first example. You can remove all 'a' first, or all 'c' first, or all 'b' first,
    the output in always [] in the second example.
    A dict/HashMap solution is way more intutitive.
       This solution gives you worst case
       O(n) time complexity if 'n' is length of the array.
       Worst case is that all characters are unique in array.
       This solution allocates O(n) worst case extra memory due to use of dict.
       Worst case is that all characters are unique in array.
    def reduce_duplicates_dict(arr):
       # initialize a dict
       s = {}
       for i in xrange(0, len(arr)):
           if arr[i] not in s:
               s[arr[i]] = 1
               s[arr[i]] += 1
       result = []
       for key, value in s.iteritems():
           if value < 2:
       return result
    if __name__ == "__main__":
       # using dict
       print(reduce_duplicates_dict(['a', 'a', 'b', 'b', 'b', 'c']))