tausif95's blog

Help me with Google L3 Interview Question
By tausif95, history, 18 months ago, In English

Find minimum absolute difference between 2 elements in an array that are at least n indices apart.

Example 1: num = [1, 1, 1, 1, 3, 3, 3, 3, 4, 4, 4, 6, 6, 6, 11, 11, 11, 11] n = 5 The answer should be 1

Example 2: num = [24, 1400, 1900, 1200, 98, 89, 123, 27] n = 2 The answer should be 3

I got the naive solution to this problem, not sure what the optimize solution should be I was wondering whether someone else would be able to show me how to solve it.

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

Comments Comments (14)
| Write comment?
»
18 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Multiset is enough.

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it +29 Vote: I do not like it

    Why do you need a multiset? A set could be enough

    vector<int> numbers;
int n;

set<int> seen;
int p1 = 0, p2 = n;
int minDif = 1e9; // or some other bound

for (p2;p2 < numbers.size(); p1++,p2++) {
    // consider the element that's the nearest to numbers[p2]
    auto pt = seen.upper_bound(numbers[p2]);
    if (pt != seen.end()) 
        minDif = min(minDif, abs(*pt-numbers[p2]));

    if (pt != seen.begin()) {
        pt = prev(pt);
        minDif = min(minDif, abs(*pt-numbers[p2]));
    }

    seen.insert(numbers[p1]);
}
    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Is prev on set iterators O(1)? I thought iterator operations like that on set iterators could be slow in the worst case.

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

        Actually nvm, iterator operations on set iterators are linear (https://cplusplus.com/reference/iterator/prev/) but we're only moving 1 element so it's O(1). It's the same deal as when you do

        set<int> s;
for (auto it = s.begin(); it != s.end(); it++) {
}

        That it++ is O(1) each time.

        → Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i think min suffix array will work

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

Let the size of the array be len.

So, for the 0th index, it can club to all the indices from n to len-1. Maintain a multiset for that and then find the lower and upper bound of the A[i] and maintain the answer. After every iteration remove the A[i+n] element from the multiset.

Sorry for my bad English.

→ Reply
»
18 months ago, # |
  Vote: I like it -8 Vote: I do not like it

If you choose some number, then it's best pair is either the minimum element that it can pair with or the maximum. Now start from the $$$n$$$'th element. It can pair up with element $$$0$$$. Element $$$n+1$$$ can pair with $$$0$$$ and $$$1$$$, $$$n+2$$$ with $$$0$$$, $$$1$$$ and $$$2$$$, ... . Now you can just hold the minimum and maximum for that prefix and update the answer as necessary. Time complexity $$$O(N)$$$ where $$$N$$$ is the size of the array, auxilary memory $$$O(n)$$$ where $$$n$$$ is the number in the problem.

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    This doesn't always work. For example : array = [1 2 3 4 5 2], n = 3 The minimum absolute difference is abs(2-2)=0. However, when you arrive at the second 2 then the minimum value is going to be 1 and the maximum value is going to be 5.

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

      I'm sorry, I misread minimum for maximum in the problem statement.

      → Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it -29 Vote: I do not like it

[Deleted maybe my approach was wrong]

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

    Don't learn topics much higher than your CP skills. Even if you understand how it works, you won't be able to apply it correctly in real problems nearly always(unless the problem is a very standard problem).

    → Reply