Adobe Online Coding Round


  • 0

    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
    

  • 0

    @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 = {}  
       
        line = sys.stdin.readline().strip()
        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:
            line = sys.stdin.readline().strip()
            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

  • 0

    @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.


  • 0

    @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?


  • 0

    @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
    3. half of your confidence

    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.)


  • 0

    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?


  • 0

    @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


  • 0

    @elmirap said in Adobe Online Coding Round:

    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.)

    @elmirap said in Adobe Online Coding Round:

    @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).


  • 0

    @elmirap said in Adobe Online Coding Round:

    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...


  • 0

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


  • 0

    @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


  • 0

    @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.


  • 0

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


  • 0

    @elmirap said in Adobe Online Coding Round:

    @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.


  • 0

    @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?


  • 0

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


  • 0

    @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!


  • 0

    @elmirap Yup. "aee" is right.


  • 0

    @StefanPochmann said in Adobe Online Coding Round:

    @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.


  • 0

    @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?


Log in to reply
 

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