calmdown_69's blog

Google coding interview question
By calmdown_69, history, 4 years ago, In English

Hello everyone.

Reference: here

problem statement:

An array is good if all subarrays have atleast 1 element in them whose frequency is 1.

Good : 1,2,1
Good: 1,2,5,2,4,3,4
Bad: 1,2,3,1,2,3

O(N^2) solution is easy but can anyone share a better approach for this question.
Thank you.

  • Vote: I like it
  • +34
  • Vote: I do not like it

Comments Comments (29)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

Wrong Approach ! Thanks @ScoobyDoobyDoo

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    [3 2 4 2 4 3 2 4 2 4] Subarray of size 5 is good, size 4 is not

    → Reply
»
4 years ago, # |
  Vote: I like it +53 Vote: I do not like it

By good subarray I mean that it contains at least one unique element. The whole array needs to be good, so it has to contain an unique element. Find this element, now each subarray containing it is good, so we can just recursively repeat our algorithm for the elements to the left and to the right. This is pretty easy to do in $$$O(n \log n)$$$ complexity.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    but won't be it quadratic if unique element is not in the middle like quick select worst case is O(n^2) if good pivot is not chosen

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -26 Vote: I do not like it

      I think that it would not be possible to get guranteed time complexity of NlogN. And also in that reference link there is clearly said that expected time complexity so may be this could referred to time complex.. of randomized algorithms. Still I didn't have think too much about it so it can possible to get guranteed lower bound of NlogN.
      So for time being this quick sort type solution would do better.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +70 Vote: I do not like it

      Yes, but there is quite well known trick to search simultaneously from the left border and the right border, so we make O(smaller part) so it will sum up to $$$O(n \log n)$$$.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hi Anadi, We can maintain a min array and a right bound array (Lets say mn[n] , R[n]) While checking the ith index, we find its previous element with same value and next with same value (Lets say Prev[i] , Next[i] in O(nlog(n))) Then we update all elements in the range — [Prev[i], i] with max(R[j],Next[i] — 1) for each j in the range. In the min array we maintain the left most index with R[j] = i => mn[i] = j So, while checking the ith element, Prev[i] should be less than or equal to mn[i — 1] otherwise subarray — [mn[i — 1] , i] would not have any unique element. We can iteratively do the process in O(nlog(n)) time. I would love for you to check this approach.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          I am not sure, probably don’t understand your approach. I cannot see why your approach wouldn’t fail on some easy test like $$$2$$$, $$$3$$$, $$$2$$$, $$$3$$$.

          → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it -6 Vote: I do not like it

      Not sure, but it seems a good implementation can guaranteed O(n logn) solution .

      If there exist multiple unique elements, select one which is closest to middle index.

      Otherwise, let suppose if there is only 1 unique element which is at leftmost index, then it is obvious that we get result just after one recursion as we can't find any unique element in next recursive call.

      In general we can guaranteed, that if such unique element is find at kth index, recursion depth will not exceed k. so if k < logn, then complexity is obviously O(nlogn).

      I know this seems quite abstract, but may be there is some mathematical proof of it.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Here's a counterexample where the recursion depth is $$$n/2$$$:

        2 1 3 2 4 3 5 4 6 5 7 6 7

        After each step, there's a unique value at the second index.

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +94 Vote: I do not like it

      Expanding a little bit more on the following statement:

      Yes, but there is quite well known trick to search simultaneously from the left border and the right border, so we make O(smaller part) so it will sum up to $$$O(n \log n)$$$.

      Argument:

      You start looking for a unique element from both ends simultaneously: $$$1, n, 2, n - 1, 3, n - 2...$$$.

      Suppose you spot the unique element at position $$$i$$$. At this step you did $$$2 \cdot min(i, n - i)$$$ operations to check for each element if it is unique on this interval or not.

      Then you run the algorithm recursively to the left and to the right. Notice that: $$$ min(i, n - i) \leq min(|left|, |right|)$$$ so basically the cost of each step is proportional to the smallest resulting interval.

      Now to compute the complexity, suppose that every time you inspect an element you add a coin on it if it belongs to the minimal interval in that iteration. The number of check operations you will do in the end is proportional to the number of coins (in particular close to twice the number of coins).

      Each time a coin is added on top of an element, it means the interval where this element was located was merged with a bigger interval, then its size increased in at least twice. So the number of coins $$$k$$$ must satisfy that $$$2^k \leq n$$$, then $$$k \leq \log_2 n$$$. Then in total the number of coins is $$$O(n \cdot \log n)$$$ which is indeed the complexity of this algorithm.

      Notice that this analysis is pretty much the same as the technique of merging smaller to larger (usually on trees), just backwards.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Suppose you spot the unique element at position i. At this step you did 2⋅min(i,n−i) operations to check for each element if it is unique on this interval or not.

        Can somebody explain this part? Till now what I have understood (maybe wrong) is we are searching from the left border and right border i.e checking first i elements and last i elements, but how can we check element at position i is unique in complete array if we have only traversed first i and last i elements.

        Can somebody please clear my doubt?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

          You can for instance precompute for each element the indices of its previous and next identical elements. Then to check that an element is unique in a subrange, it suffices to check that the precomputed indices fall outside of that subrange.

          → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Not getting this!

        "So the number of coins k must satisfy that 2^k ≤ n, then k ≤ log2n."

        Shouldn't it be:

        every time a coin is added, we have atleast 1 mirror element in larger interval

        then k coins imply 2*k <= n, which is k <= n/2

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Your reasoning is not wrong, but doesn't provide a good upper bound. You can do better.

          Suppose an element has $$$k$$$ coins. It means it belonged $$$k$$$ times to the smallest side. The last time you added a coin to it the length of the interval containing it was $$$a_k$$$ and the length of the other side was $$$b_k \geq a_k$$$, but then it implies that in the previous step all $$$a_k + b_k$$$ elements were in one side, so when we add the previous coin the size of the interval was $$$a_{k -1} \geq a_k + b_k \geq 2\cdot a_k$$$. So we know the size of the intervals when we add a coin as we move backwards at least increased twice. This argument is enough to proof that the maximum number of coins added to an element is $$$O(\log_2 n)$$$

          → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the constraint on Array elements? I mean what is the range of A[i]?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Whatever they may be but we can use coordinate compression and bring them in the range [1, n].

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No that's not my point. I mean suppose N is in order of 10^5 and A[I] is in the range [1,100], then we can get some idea about how many elements are repeated and all.

      → Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

might be useful: cs stackexchange answer
similar to one of the mentioned solutions.

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

Create an array of next occurrence of each element then using segment tree descent we can find first unique element in l-r in logn. Now recurrence will be T(n)=T(n-1)+O(logn) which will be O(nlogn)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can there be any O(N) solutions?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Checking for the existence of a unique element itself would probably take $$$O(n \log n)$$$, or at least $$$\omega(n)$$$ time (deterministically), so if you want to avoid randomized solutions (including hash tables), the answer is probably no.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah I'm having a problem similar to this, I tried the O(NlogN) way but it turns out to be TLE

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        link to question
        Very well explained editorial

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        You might be finding the frequency each time (for checking if an element is unique), which would give TLE, since you do $$$O(n)$$$ work instead of $$$O(\min(i, n - i))$$$ work. As pointed out in one of the above comments, you'll need to maintain the indices of the previous equal element and the next equal element.

        It might also be the case that you're not performing constant factor optimizations (or inadvertently doing too many unnecessary memory accesses — for instance, while using map).

        Code
        → Reply