• Had an Adobe coding round today on HackerRank. 90 mins - 3 questions.

Q1. You are given an integer N and a priority array for the 26 letters of the english alphabet. Generate a string of N length using lowercase letters, such that the following function is maximised.

``````f(str) = summation [ i * priority[str[i]] ] for i = 0..(len(str)-1)
``````

If multiple such strings are possible, output the one lexicographically least.
Some sample cases:

``````Input:
1                                                               # N
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1   # priority of alphabets
Output:
a

Input:
2
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1
Output:
ae
``````

Q2: Given an array of integers (length of array is of the order `10**5`.) We need to find out if they are / can be made in ascending sorted order. However we can do only one operation of the forms:

• Swap the numbers at two indices
OR
• Reverse a contiguous segment of the array

Given the array,

• if the numbers are already in sorted form, print "yes" in a line and do no more
• If they can converted to sorted form with just one operation, print "yes" in a line
• if we are swapping, then print "swap l r" in a seperate line where the "l" and "r" are the two indexes to be swapped
• if we are reversing a segment, then print "reverse l r" on a seperate line where "l" and "r" are the two bounding indexes of the reversed segment
• if no such conversion is possible, print "no" in a line and do no more

Swapping is preferred over reversing a segment.

Some sample cases:

``````Input:
3       # the length of array
3 1 2   # the array
Output:
no

Input:
2
4 2
Output:
yes
swap 1 2  # 1 - based indices

Input:
5
1 2 3 4 5
Output:
yes

Input:
6
1 5 4 3 2 6
Output:
yes
reverse 2 5
``````

Q3: We have a cubic room of N edge length filled with unit cube sized light bulbs. Initially, some of them are ON and others are OFF. At the passing of unit time, a lightbulb can go from OFF state to ON if it's adjacent bulb is ON. Print the total time it will take for all the bulbs to become ON. If it is impossible, print -1.

The adjacent neighbours of a lightbulb at coordinates `(X, Y, Z)` are at coordinates `(X+1, Y, Z)`, `(X-1, Y, Z)`, `(X, Y+1, Z)`, `(X, Y-1, Z)`, `(X, Y, Z-1)` and `(X, Y, Z+1)`.

Input format is two integers N, M where N is edge length of room and M is the number of bulbs already ON. The next M lines have three space separated integers representing the coordinates `(X, Y, Z)`.

``````Sample Input:
5 3
1 1 1
3 3 3
2 2 2
``````

• @babhishek21
My try to solve problem 3. It is BFS from multiple sources. Most of the code is concetrated over reading an input

``````def problem3():
q = deque();
directions = [(1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, -1), (0, 0, 1)]
visited = {}

ls = line.split(" ")
n = int(ls[0])
m = int(ls[1])

if m == 0:
return -1
if m == n*n*n or n == 0:
return 0
while m > 0:
ls = line.split(" ")
tup = (int(ls[0]), int(ls[1]), int(ls[2]))
q.append(tup)
visited[tup] = True
m-=1
l = len(q)

def valid(x, y, z, cur):
return x + cur[0] <= n and x + cur[0] > 0 and y + cur[1] <= n and y + cur[1] > 0 and z + cur[2] <= n and z + cur[2] > 0

time = -1;
while l > 0:
tmp = 0;
time = time + 1
while l > 0:
cur = q.pop()
for x, y, z in directions:
if valid(x, y, z, cur):
nextBulb = (x + cur[0], y + cur[1], z + cur[2])
if nextBulb not in visited:
visited[nextBulb] = True
q.append(nextBulb)
tmp += 1
l-=1
l = tmp
return time``````

• @elmirap This isn't complete (I did the same mistake too.) Do you know why?

The directional neighbours are not exhaustive. In general, a bulb cannot reach another bulb diagonally. So you would probably need to check if all the bulbs are ON after you are done with your BFS. That would mean checking if size of `visited` is `N**3`.

• @babhishek21 ooo, yes,Thank you! I noticed that diagonally bulbs were excluded, but forgot about them later. Was this a big issue on the interview?

• @elmirap It was an online coding round on HackerRank. So if you screw up, test cases don't pass and you're left with

1. a failed solution with faily little idea of what went wrong
2. less time than you had before

I managed the first two. The third question was problematic because the judge had wrong answers. Adobe still went with giving partial credits to a wrong question. It was a big hotchpotch. I couldn't make it despite the 2/3 score (most probably because of the preceding aptitude test.)

• I see , but what percent did they give you for the third problem? I didn't take a look on the first and second problems, but which one was the hardest for you? Was difficult the aptitude test? What did they expect from it? Was it possible during the interview to review the failed tests?

• @babhishek21 after thinking for a while I doubt that it is possible to turn on less that N^3 bulbs with at least one ON bulb. Let's take a look at an example in 2D, when you don't have access to diagonal neighbours. I don't see a way to turn on less that N^2 bulbs when at least one bulb is ON. It is one connected component. It could be that I am wrong.

1------2-----3 -----4
5----- 6-----7----- 8
9-----10 - 11---- 12

• I see , but what percent did they give you for the third problem? I didn't take a look on the first and second problems, but which one was the hardest for you? Was difficult the aptitude test? What did they expect from it? Was it possible during the interview to review the failed tests?

They probably had a 1:2:3 marking ratio for the three problem, which kind of explained why my friend who managed the first and half of the third question managed to get through, when I couldn't. Aptitude tests are something that i'm never sure about. Sometimes I think I do well, and the results are off. Sometimes the reverse happens. During additional interview rounds, Adobe interviewers tend to discuss the problems of the online round (it's an additional check to see if you cheated or just got lucky.)

@babhishek21 after thinking for a while I doubt that it is possible to turn on less that N^3 bulbs with at least one ON bulb. Let's take a look at an example in 2D, when you don't have access to diagonal neighbours. I don't see a way to turn on less that N^2 bulbs when at least one bulb is ON. It is one connected component. It could be that I am wrong.

1------2-----3 -----4
5----- 6-----7----- 8
9-----10 - 11---- 12

Try visualising with a simple 3D cube where only the middle innermost element is ON. A good way to understand the difference is that the question gives you only 1 degree of freedom (along either of the orthogonal X, Y, Z axes.). To get all possible directions, we need at-least the use of 3 directions of freedom simultaneously (for example: The combination of X axis, i.e. `i` vector, Y axis, i.e. `j` vector and the Z axis, i.e. `k` vector gives an additional direction `i+j+k` vector. which is simply the direction from `(0,0,0)` to `(1,1,1)`.

• I doubt that it is possible to turn on less that N^3 bulbs with at least one ON bulb

Either I'm misunderstanding the problem, or that is obvious...

• @StefanPochmann what is obvious? I don't get the point, sorry

• @babhishek21 May I ask you a question about problem 1. You wrote there that function f should be maximized, but in the example 1, the output is 'a', which doesn't maximize the function. f("a") = 0*priority[a] =0*1 = 0. Am I wrong? Could you clear this out, please? Thank you

• @elmirap For a string of length 1, the first character is always at index 0. So the function value for such a string will always be zero.

• @babhishek21 I see, thank you. For example 2, can you explain why the output is 'ae'. Coudn't be ''ee''?

• @babhishek21 I see, thank you. For example 2, can you explain why the output is 'ae'. Coudn't be ''ee''?

At this point, I'd ask you to read the entire question again. Especially the last line.

If multiple such strings are possible, output the one lexicographically least.

• @elmirap I meant it's obvious that if we start with at least one bulb being ON, then all bulbs will end up being ON. Wasn't that what you were saying? Or do I misunderstand the problem?

• @StefanPochmann yes, it is the same what I meant!

• @babhishek21 I want just to be sure that understand the problem.
Is it right that when N = 3 and prioprities =[1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1]
output will be aee ? Thank you!

• @elmirap Yup. "aee" is right.

• @elmirap I meant it's obvious that if we start with at least one bulb being ON, then all bulbs will end up being ON. Wasn't that what you were saying? Or do I misunderstand the problem?

I still don't agree with this. I see no way to get the diagonal neighbours lit with just one ON bulb at the beginning.

• @babhishek21 thanks, is it greedy good strategy for this ;-)? I mean problem 1.
Please tell me in 2D case whether we cannot access diagonal neighbours?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.