3905's blog

Interview Problem
By 3905, history, 9 years ago, In English

You are given N numbers and you have to determine total possible ways to arrange them such that N1 < N2 > N3 < N4 > N5 < N6 > N7....so on.N1,N2 are the numbers of the list.The interviewer didn't specify the constraints and asked instead for best possible solution.How to solve it?

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by 3905 (previous revision, new revision, compare).

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

The first obvious solution is dp: f[mask_of_used_elements][last_element], everything you need to recalc this dp is to find some not used element and try to add it in such way, that all conditions will be met. Sth like f[mask_of_used_elements | new_element][new_element] += f[mask_of_used_elements][last_element]

The answer is sum of f[2^n — 1][i] for all i.

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

    is there any better solution

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

    Why is people down-voting this? Having no constraints, this is an acceptable solution.

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

In general case, if the numbers are distinct, you don't care about the numbers, being able to normalize them. In this case, you can use a dynamic programming solution where dp[i][j] = number of permutations ending in j of i elements that respect the first i — 1 relations(through relation I mean a[1] < a[2] > a[3] ...). You can find reccurence in O(N) getting N ^ 3 time complexity, and also, using same partial sumes you can get O(N ^ 2) total time with O(1) the reccurence for an element. To be noted that this solution is a generalization which works for any given order of signs. This, being a particular case, most probably can be solved in O(N) or O(1) or something like that observing some sort of formula(using the previous dynamic) that could be inductively prove, but for getting this formula you should run the program for small values and observe certain things, I guess. One more time, this solution only works if the numbers are distinct. Otherwise, I don't think that there exist any solution with polynomial time complexity.

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

    Yes all numbers are distinct.Can you explain the recurrence for the dp solution for N^3 complexity and for N^2 complexity.

    → Reply