Altera Interview Question: An array contains some random... | Glassdoor

Interview Question

Software Engineer Interview San Jose, CA

An array contains some random positive and negative

  numbers. Arrange array elements such that all positive elements are on left side, don't care about negative elements. Number of operations allowed - O(n)
Answer

Interview Answer

3 Answers

0

This is a job for descending quicksort. Append 0 to the array and set it as the pivot and all values greater than 0 will end up on the left side after 1 iteration.

avidprog on Sep 3, 2012
0

This could be very easily done by using 2 Lists and a foreach loop. Go around adding all of the positive numbers to the first list and then adding negative numbers to the second list. Afterwards, just merge them together and voila. It only takes O(n), pretty clean and easy to understand also code describes the intention. Here is the snippet (I used C# in this case):

        class Program
    {
        private static void Main(string[] args)
        {
            IEnumerable array = PopulateArrayWithRandomValues();
            List positiveNumbers = new List();
            List negativeNumbers = new List();
            List arrangedArray = new List();

            // Actual solution with O(n) efficiency
            foreach (int item in array)
            {
                if (item > 0)
                {
                    positiveNumbers.Add(item);
                }
                else if (item PopulateArrayWithRandomValues()
        {
            int[] array = new int[100]; // We will say 100 random items for the sake of this example

            Random randomNumber = new Random();

            for (int i=0; i arrangedArray)
        {
            foreach (var item in arrangedArray)
            {
                System.Diagnostics.Debug.WriteLine(item);
            }
        }
    }

Avetis Ghukasyan on Apr 16, 2015
1

We can use a similar logic as Quick sort but without tampering with the original dataset (Like adding a 0).
Declare 2 int variables:

        int i = 0;
        int negIndex = a.length-1;

        while (i = 0){
                i++;
            }
            else{
                int temp = a[i];
                a[i] = a[negIndex];
                a[negIndex] = temp;
                negIndex--;
            }
        }

Akash on Apr 25, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.