Блог пользователя tausif95

Help me with Google L3 Interview Question
Автор tausif95, история, 17 месяцев назад, По-английски

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.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
17 месяцев назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Multiset is enough.

→ Ответить
  • »
    »
    17 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

    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]);
}
    → Ответить
    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

      → Ответить
»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i think min suffix array will work

→ Ответить
»
17 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.

→ Ответить
»
17 месяцев назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    17 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    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.

    → Ответить
»
17 месяцев назад, # |
← Rev. 2   Проголосовать: нравится -29 Проголосовать: не нравится

[Deleted maybe my approach was wrong]

→ Ответить
  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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).

    → Ответить