guptaji30's blog

Question from a Sprinklr interview
By guptaji30, history, 4 months ago, In English

Given an array, arr[] of integers. The task is to sort the elements of the given array in the increasing order of their modulo with 3 maintaining the order of their appearance.

Expect time complexity O(N) and the interviewer said that it can be done in only one/two traversal(s)(sorry I don't remember it clearly, it was quite sometime ago).

Expected space complexity O(1).

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

»
4 months ago, # |
← Rev. 3   Vote: I like it -22 Vote: I do not like it

https://en.wikipedia.org/wiki/Dutch_national_flag_problem

However, stability requirement is not achievable in the given constraints.

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

We can use dutch national flag as modulo with 3 will leave us with an array of 0, 1, 2. So the problem will boil down to something like this.

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

    The task is to sort the elements of the given array in the increasing order of their modulo with 3 maintaining the order of their appearance.

    How to maintain the order of their appearance in one traversal?

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

      If you push the elements in a vector, the order will be maintained.

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

        nvm

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

        Space Complexity is O(1) mate. You can't use another vector. Somehow you have to think of a way while using only swapping.

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

          You can solve it using single variables, the vecror isn't necessary, and it's indeed with swapping.

          It's basically swapping if needed, and store the first position of every kind ( 0 1 or 2 ) to be able to make the swaps efficiently

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

    In that way the original order will not be maintained.

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

Can do it in 2 traversals with no extra space. In one traversal you can get number of 0s,1s and 2s. So in the second traversal, if you encounter a number, you know its exact position (from the previous traversal). Just swap with its exact position and continue the process.

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

    can you please elaborate I had though of the same thing but wasn't sure if it will maintain the order of the elements

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

      okay, I just gave a thought and found out that the order will not be maintained. If you allow one more traversal then it is possible definitely. In the second traversal replace each value with its original position in the sorted array, this can be done using the number of 0,1,2. Finally, in the 3rd traversal, swap it i.e place everything in the positions stored. Maybe this swapping can be done in the 2nd traversal only efficiently but I guess it's tricky.

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

        Can you write the code for this ??

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

            So you are basically storing the appropriate index of the current element by multiplying it with a large number. I had said the same thing to the interviewer but he was not convinced by it.

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

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

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

.

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

I think below code will work assuming input can be modified It uses two passes one to count the number of 0,1,2's and second for modifying the input to make it sorted by starting three pointers from 0,cnt[0],cnt[0]+cnt[1].

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

    I have a doubt.... for example you are changing value of a[oneindx], but you are not storing its previous value i mean it's previous value would be diminshed?

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +7 Vote: I do not like it 
      This is very standard technique in which we can store information about two numbers using a single number.
let us say some n 
n=4
and now i want to somehow store 50 also.
So first we require some number that is bigger than both 4 and 50 so let us say 51 is one such number
so new modified number will be n=4+51*50;
now if we need to get information of both number 
so original number = n%51=(4+51*50)%51=(4%51+(50*51)%51)%51=4%51=4(original number)
if we want new number then it is equal to= n/51(integer division)=(4+51*50)/51=0+50=50(second number).
so in this we are storing information of two numbers in a single number.
      → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the use of stable_partition can surely make the code short and simple, but I am not sure about the number of traversals. Does the use of stable_partition mean traversing the array internally each time?

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

What is wrong with this solution? One traverse, no second array. Returns {0, 3, 3, 4, 10, 4, 2, 8, 5, 8}

Code
→ Reply
»
4 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it 
    int idx = 0;
    fo(i,0,n){
        if(v[i]%3==0){
            swap(v[idx++], v[i]);
        }   
    }
    fo(i,idx,n){
        if(v[i]%3==1){
            swap(v[idx++], v[i]);
        }
    }

Someone plz give an edge case for this code

PS- Forget I even asked.

→ Reply