Databases
StackOverflow2013
Postsdbo
POGiven an array [a1b2c3d4] convert to [abcd1234]
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POGiven an array [a1b2c3d4] convert to [abcd1234]
    primarykey
    data
    text
    <p><strong>Constraints :</strong></p> <ol> <li>O(1) space </li> <li>O(n) Time</li> </ol> <p>It is not a homework question just a interesting question I came across.</p> <p>Here are some solutions I could think of but nothing that does it in given constraints.</p> <p><strong>Method 1</strong></p> <p>*With O(n) memory *</p> <ul> <li>Divide the array in two parts recursively. ( keep dividing till the size &lt;=2 for each sub problem )</li> <li>Sort each sub problem with array first and numbers at end.</li> <li>Merge the sub problem arrays</li> </ul> <p><strong>Method 2</strong></p> <p><em>In O(n log n) time</em> </p> <ul> <li>Sort the array based Lexicographical order it becomes 1234abcd</li> <li>Reverse both halves of array 4321dcba</li> <li>Reverse the whole string abcd1234</li> </ul> <p><strong>Method 3</strong> </p> <p><em>If range of numbers was defined</em></p> <p>Also if the case was that numbers are in a specific range then I can initialize a int say track= 0; And set the appropriate bit when I come across a number in array eg (1 &lt;&lt; a[2] ) . 1. Swap alphabets to first half of array 2. Mark numbers in track variable 3. later use track to fill in second half of array.</p> <p><strong>Method 4</strong> We can use Method 3 with HashMap if we want to remove the constraint of range of integers but then it will need more memory.</p> <p>Cannot think of a better way to solve the generic problem in O(1) time and O(n) space.</p> <p>Generic Problem here refers to:</p> <p>Given a sequence x1y1x2y2x3y3....xnyn where x1 , x2 are alphabets x1 &lt; x2 &lt;.... &lt; xn and y1y2...yn are integers . y1 &lt; y2 &lt;.... &lt; yn Arrange the output as x1x2...xny1y2...yn</p> <p>Any suggestions ?</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USamit modi
    1. USamit modi
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POGiven an array [a1b2c3d4] convert to [abcd1234]
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POGiven an array [a1b2c3d4] convert to [abcd1234]
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POGiven an array [a1b2c3d4] convert to [abcd1234]
      1. This table or related slice is empty.
      1. VTUpMod
    1. COYou need to figure out how to rearrange 6 characters with no more than 8 actions. (But the "actions" can each be multiple swaps, if need be, and still maintain order N.) (And note that the problem, as you stated it, says nothing about sorting, just rearranging 8 characters into a defined sequence.)
      singulars
      1. POGiven an array [a1b2c3d4] convert to [abcd1234]
      1. USHot Licks
    2. CO@Hot Licks: I tried actually thinking on these lines but ended up with a solution that was not generic. 1.Swap center elements of first half eg ."1b" so we get ab12c3d4. 2. Swap center elements of second half ab12cd34. 3. Swap center 2 element of complete array abcd1234. BUT this technique only works if the size of array is in multiple of 8.
      singulars
      1. POGiven an array [a1b2c3d4] convert to [abcd1234]
      1. USamit modi
    3. CODefine "generic" -- you've not stated a generic problem. You've given an example but no hint as to how that generalizes.
      singulars
      1. POGiven an array [a1b2c3d4] convert to [abcd1234]
      1. USHot Licks
 

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