Databases
StackOverflow2013
Postsdbo
POInterview Question... Trying to work it out, but couldn't get an efficient solution
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POInterview Question... Trying to work it out, but couldn't get an efficient solution
    primarykey
    data
    text
    <p>I am stuck in one interview question.. The question is,</p> <blockquote> <p>*given two arrays A and B. A has integers unsorted. B has the same length as A and its values are in the set {-1,0,1}</p> <p>you have to return an array C with the following processing on A. </p> <p>if B[i] has 0 then C[i] must have A[i]<br> if B[i] has -1 then A[i] must be in C within the sub array C[0] - C[i-1] ie. left subarray<br> if B[i] has 1 then A[i] must be in C within the sub array C[i+1] - C[length(A)] ie right subarray. </p> <p>if no such solution exists then printf("no solution");*</p> </blockquote> <p>I applied following logics:-</p> <pre><code>int indMinus1 = n-1; int indPlus1 = 0; //while(indPlus1 &lt; n &amp;&amp; indMinus1 &gt; 0) while(indPlus1 &lt; indMinus1) { while(b[indMinus1] != -1) { if(b[indMinus1] == 0) c[indMinus1] = a[indMinus1]; indMinus1--; } while(b[indPlus1] != +1) { if(b[indPlus1] == 0) c[indPlus1] = a[indPlus1]; indPlus1++; } c[indMinus1] = a[indPlus1]; c[indPlus1] = a[indMinus1]; b[indMinus1] = 0; b[indPlus1] = 0; indMinus1--; indPlus1++; } </code></pre> <p>But this will not going to work,, for some cases like {1,2,3} >> {1,-1,-1}... One output is possible i.e. {2,3,1};</p> <p>Please help.... does their any algorithm technique available for this problem?</p> <p><strong>Correct Solution Code</strong></p> <pre><code>int arrange(int a[], int b[], int c[], int n) { for (int i = 0; i &lt; n; ++i) { if(b[i] == 0) c[i] = a[i]; } int ci = 0; for (int i = 0; i &lt; n; ++i) { if(b[i] == -1) { while(c[ci] != 0 &amp;&amp; ci &lt; i) ci ++; if(c[ci] != 0 || ci &gt;= i) return -1; c[ci] = a[i]; ci++; } } for (int i = 0; i &lt; n; ++i) { if(b[i] == 1) { while(c[ci] != 0 &amp;&amp; ci &lt; n) ci ++; if(c[ci] != 0 || ci &lt;= i) return -1; c[ci] = a[i]; ci++; } } return 0; } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USAGeek
    1. USAGeek
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POInterview Question... Trying to work it out, but couldn't get an efficient solution
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POInterview Question... Trying to work it out, but couldn't get an efficient solution
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POInterview Question... Trying to work it out, but couldn't get an efficient solution
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWhat if you put all the possible numbers of A in each position of C, then just dfs'd those possibilities?
      singulars
      1. POInterview Question... Trying to work it out, but couldn't get an efficient solution
      1. USkevmo314
    2. COi dont get you?? can you please elaborate??
      singulars
      1. POInterview Question... Trying to work it out, but couldn't get an efficient solution
      1. USAGeek
    3. COCreate a linked list for each index of C, then loop through A/B. If B[i] = -1, then insert A[i] into the linked lists C[0..n-1] and similarly for B[i] = 1. Then what you basically have is a depth-first search problem. I'm fairly certain that this works, though there might be a simpler solution.
      singulars
      1. POInterview Question... Trying to work it out, but couldn't get an efficient solution
      1. USkevmo314
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload