CareerCup

The leftmost employee is the shortest employee with a value of zero taller employees on his left. So we find him first, and then reduce by one the count of all shorter employees. To find the next employee, we repeat the same steps - find the shortest employee with count of 0, and reduce the count of shorter employees. Repeat this N times.Complexity O(n^2)

1. declare an array height[n] with all elements value as 0.
2. For each employee's height i, from 1 to n, (say i)
- get the number of taller person from given n (say j = Input_arr[i-1])
- check if height[j] is zero, set it to i,
- if height[j] is already set to non-zero , then increase j and set height[j] = i in next available position (use a for loop)


code can be like this: n =4
height[4] = {0,0,0,0}
for(i = 1; i< = 4; ++i)
{
j = input_arr[i-1];
for( ; j<n; ++j )
{
if(height[j] == 0)
height[j] = i;
else
continue;
}
}

vector<int> emp(n);

for(int i = 1; i <= n; ++i)
{
   int j = arr[i - 1]; //arr is the input array
   for (; j < n; ++j)
   {
      if (emp[j] == 0)
      {
         emp[j] = i;
         break;
      }
   }
}

With segment trees time complexity will be O(n(log(n)), space complexity O(n)

I think question is copied from Code Gladiator coding context
Please try it on own because next round is tough

I question is copied from Code Gladiator coding context
Please try it on own because next round is tough.

int left, current;
    static int arr[4] = {0};
    int i      = 0;

    for(i=0;i<input1;i++)
    {
        current = input2[i];
        left    = 0;

        if(current > 0)
            left    = arr[(current-1)];

        if(left == 0 && arr[current] == 0)
        {
            arr[current] = input1-current;
        }
        else
        {
            for(int j=(i+1);j<input1;j++)
            {
                if(arr[j] == 0)
                {
                    left = arr[(j-1)];
                    arr[j] = left - 1;
                }
            }
        }
    }


    return arr;

[plplp

In the above example, why order 4-3-2-1 is wrong?
We can say that height sequence is:

4>2>1>3; 4 being the tallest?

unable to understand the question. Can anybody tell the meaning of line

you are given a int[], the ith element of which represents the number of taller employees to the left of the employee with height i (where i is a 1-based index)

Here is my code goes in Python

# input1 n = no. of employees 4
# input2 array of n elements  {2, 1, 1, 0}
# Output [4, 2, 1, 3]
# 0 [2, 1, 1, 0] [4, 2, 1, 3]
# 1 [2, 1, 1, 0] [4, 2, 1, 3]
# 2 [2, 1, 1, 0] [4, 2, 1, 3]
# 3 [2, 1, 1, 0] [4, 2, 1, 3]

import copy


def findLogic(temp, input2):
    for i, (k, v) in enumerate(zip(temp, input2)):
        count = 0
        if i == 0:
            countList = []
        j = i + 1
        #print(i, temp, input2)
        if j in input2:
            #print(i, temp, input2, input2.index(j))
            for l in range(input2.index(j), -1, -1):
                if l >= 0 and j <= (len(input2)-1):
                    if j < input2[l]:
                        count += 1
            countList.append(count)
            if countList == temp:
                #print(input2)
                print("{", end="")
                for i in input2:
                    print(i, end="")
                    if input2.index(i) != len(input2) - 1:
                        print(",", end="")
                print("}", end="")
                return 1

def PlaceNumbs(input2, l, r, temp):
    if l == r:
        if findLogic(temp, input2):
            return
    for i in range(l, r):
        input2[l], input2[i] = input2[i], input2[l]
        PlaceNumbs(input2, l + 1, r, temp)
        input2[l], input2[i] = input2[i], input2[l]

#def FinalOrder(n, input2):
def uniqueValue(input1,input2):
    n = input1
    temp = copy.deepcopy(input2)
    input3 = []
    for i in range(1, n+1):
        input3.append(int(i))
    PlaceNumbs(input3, 0, n, temp)

uniqueValue(4, [2, 1, 1, 0])
print("\n")
uniqueValue(8, [1, 2, 1, 1, 1, 1, 0, 0])