ADP Interview Question
Applications DevelopersCountry: India
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;
}
}
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;
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])
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)
- gen-y-s March 30, 2016