CODEWITHSUNDEEP
arrayslinked-list
JOSI
JOSI

Reputation: 63

basic thing from a job interview - using linked list,arrays

I got this question on a job interview, and i could't solve it.
i think i was just really nervous because it doesn't look this hard.

Arr is a given integer array, size n. Sol is a given empty array, size n.

for each i (i goes from 0 to n-1 ) you have to put in Sol[i] the index in Arr of the closest elemnt appears on the left side, that is smaller than Arr[i]. meaning: Sol[i]=max{ j | j < i; Arr[j] < Arr[i] }. if the is no such index, put -1.

for example: Arr is [5,7,9,2,8,11,16,10,12] Sol is [-1,0,1,-1,3,4,5,4,7]

time complexity: o(n) space complexity: o(n)

I tried to scan the array from the end to the start, but I didn't know how to continue.

I was asked to use only array and linked list. I had 10 minutes to solve it, so guess it is not that hard.

thanks a lot!!

Upvotes: 0

Views: 59

Answers (2)

Michael Burr
Michael Burr

Reputation: 340366

Note that for Arr[] with length < 2 there are trivial solutions. This pseudo code assumes that Arr[] has a length >= 2.

int Arr[] = {5,7,9,2,8,11,16,10,12};
int Sol[] = new int[9];

Stack<int> undecided;   // or a stack implemented using a linked list

Sol[0] = -1;    // this is a given

for(int i = Arr.length() - 1; i != 0; --i) {
    undecided.push(i); // we haven't found a smaller value for this Arr[i] item yet
                       // note that all the items already on the stack (if any)
                       // are smaller than the value of Arr[i] or they would have
                       // been popped off in a previous iteration of the loop
                       // below

    while (!undecided.empty() && (Arr[i-1] < Arr[undecided.peek()])) {
        // the value for the item on the undecided stack is
        //  larger than Arr[i-1], so that's the index for 
        //  the item on the undecided stack
        Sol[undecided.peek()] = i-1;
        undecided.pop();
    }
}

// We've filled in Sol[] for all the items have lesser values to
//  the left of them.  Whatever is still on the undecided stack
//  needs to be set to -1 in Sol

while (!undecided.empty()) {
    Sol[undecided.peek()] = -1;
    undecided.pop();
}

To be honest, I'm not sure I would have come up with this in an interview situation given a 10 minute time limit.

A C++ version of this can be found on ideone.com: https://ideone.com/VXC0yq

Upvotes: 1

jonhid
jonhid

Reputation: 2135

    int Arr[] = {5,7,9,2,8,11,16,10,12};
    int Sol[] = new int[9];

    for(int i = 0; i < Arr.length; i++) {
        int element = Arr[i];

        int tmp = -1;
        for(int j = 0 ;j < i; j++) {
            int other = Arr[j];
            if (other < element) {
                tmp = j;                    
            }
        }

        Sol[i] = tmp;           
    }

Upvotes: 0

Related Questions