Pages

Sunday, June 23, 2013

Unsorted Array Converted To "E1 < E2 > E3 < E4..." Format

I had a question once where given an unsorted array of integers, you have to produce an array in the "E1 < E2 > E3 < E4..." format. For example {3, 2, 6, 4, 9, 7, 1, 10, 8, 5} would produce {2, 6, 3, 9, 4, 7, 1, 10, 5, 8} and this is because 2 < 6 > 3 < 9 > 4 < 7 > 1 < 10 > 5 < 8. 

This is a tricky question where if asked by an interviewer you have to ask follow-up questions! I'm saying this out of my experience, my first solutions that I had in mind when I first had this question asked were involving sorting or priority queues, thus at least O(n log n) running time and involving additional space. But when I asked about the desired running time I was told that it should be faster, so I revisited my thoughts. It is in fact a very simple problem where you have to traverse the array just once resulting in O(n) running time. Note that you also have to ask about how to handle duplicates, in this case I considered an array of unique numbers.

The idea is that while traversing the array, you maintain a flag that indicates whether a "less than" or a "greater than" comparison should succeed. If it does not succeed you swap the previous index with the current index. 

This will be easier to understand through an example. Let's say we have the above array {3, 2, 6, 4, 9, 7, 1, 10, 8, 5}. We traverse the array starting at the second element (2), since we'll be comparing the current with the previous element. We also have to maintain the above mentioned flag, say a flag named lessThan which will be defaulted to true since our format definition indicates that we have to start from a less than sign. So we have our element "2" and previous element "3". Is element "3" less than element "2" ? No, then we swap the elements which results in the array {2, 3, 6, 4, 9, 7, 1, 10, 8, 5}. We also have to switch the lessThan flag and then go to the next index. Now the flag tells us that we have to use the "greater than" sign. Is element "3" greater than element "6" ? No, then swap the numbers. But wait, what happens to the previous comparison ? The second index has to stay greater than the first one, but note that this did get verified by the condition that we just imposed by comparing "6" with "3". "6" is greater than "3", which is greater than "2" - this means "6" is greater than "2", thus it's safe swapping "6" with "3". This results in {2, 6, 3, 4, 9, 7, 1, 10, 8, 5}. This goes on until the end of the array. Here's a table that may add more sense to how the algorithm works:


Iteration Array LessThan flag Swapped
0 2, 3, 6, 4, 9, 7, 1, 10, 8, 5 true true
1 2, 6, 3, 4, 9, 7, 1, 10, 8, 5 false true
2 2, 6, 3, 4, 9, 7, 1, 10, 8, 5 true false
3 2, 6, 3, 9, 4, 7, 1, 10, 8, 5 false true
4 2, 6, 3, 9, 4, 7, 1, 10, 8, 5 true false
5 2, 6, 3, 9, 4, 7, 1, 10, 8, 5 false false
6 2, 6, 3, 9, 4, 7, 1, 10, 8, 5 true false
6 2, 6, 3, 9, 4, 7, 1, 10, 8, 5 false false
7 2, 6, 3, 9, 4, 7, 1, 10, 5, 8 true true



The code is pretty simple. See it below:
Note:
- The swap function is trivial and it may look like in the code below.

6 comments:

  1. can you write my paper for me? If you do it successfully, I will pay you. Any one can say you. So get ready.

    ReplyDelete
  2. Thanks for sharing this information with us, your website is really awesome. Oginsta music maniac z4root

    ReplyDelete
  3. There are a stunning variety of corporations and organizations presently invested within the house, be it via pre-fabricated fashions, kits or open-source, downloadable plans. We pulled together a listing of {some of the|a few of the|a variety of the} most distinguished, which you'll be able to|which you'll} a glance at|try} after the break. To mix separate bodies, click on “Insertion,” then “Functions,” hit “Combine,” then hit the “Add” possibility till you've have} a single strong mannequin. In “Cut” view, {you can|you'll be able to|you probably can} verify that your fashions have merged when you see a shiny blue flash between the two fashions with no spaces. If there Funnel Plungers Toilet Brush is a house within the blue, then use the “Combine” perform to merge them absolutely.

    ReplyDelete