Adobe | SSE | Interview Experience | [waiting]

Anonymous User

6117

Adobe Onsite India Interview Senior Level

Hi Guys,
Would like to share my interview experience with Adobe.

Interview Date: Aug 2019
Location: India
Type: Onsite
Experience : 6+ Year [Java-Backend & Spark ]

How day went
There were 4 onsite face to face round, with 30 min break after 2 round for lunch. All rounds were knock out round.

Face to Face

Round 1 : Data structure and Algo

General introduction
K Distance away node from a given node [https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/]
Difference between mutax and semaphore [https://www.geeksforgeeks.org/mutex-vs-semaphore/]
Design custom thread safe HashMap.

Interviewer was very nice and we had really good discussion in 3rd question. I manage to touch 10's aspect to break my design and give him a possible solution to make it really optimize and concurrent.

Round 2 : Engineering Manager

Most challenging work & project deep dive
Design a Thread Safe cache that support both LFU and LRU; both should use same data structure. Type of eviction policy will be pass in constructor while creating of cache.
[https://leetcode.com/problems/lru-cache/ , https://leetcode.com/problems/lfu-cache/ ]
{I'll share the code later}

Interviewer was kind a rude person. He was not letting me to finish most of the statement and keep forgetting what I’ve already explained earlier.
He is also not was quite sure about the second question {Like seems he really don't know how LFU works , thread safety come in play only when multiple threads trying to access shared resource. }

Lunch break

Round 3 : Data structure and Algo

Given houses in circular manner, a robber need to rob maximum money from houses, conditioned that he cannot theft from adjacent houses. [https://leetcode.com/problems/house-robber-ii/]
Given an array of numbers where every element appears 3 times but only one number appears 1’s. Find that number which appeared 1’s [https://leetcode.com/problems/single-number-ii]
Design a data structure that support Top 10 words from Stream based on frequency. [https://leetcode.com/problems/top-k-frequent-words/]

This interviewer was one of the best. We really had good discussion in problems. Specially in first problem.
He was really impressed with me for second question.

Round 4: Technical architect; High Level and Api design

Design High level elevator system that should be configurable with ‘m’ floors{could be divided in chunks} and ’n’ lifts {could be divided in chunks}
{could be divided in chunks} Means a lift can operate only on some sub-set of floors from m floors {1…m)
[Idea from : https://medium.com/system-designing-interviews/design-a-elevator-system-fc5832ca0b8b]
Design a chat application service apis & its security aspect.

Interviewer was decent and humble, he was in company about 12 years. I managed to ask him question regarding actual system design implications, career advices.

Round 5: Video conferencing {this round happen after 2 days of onsite interview }

Given a function f(), don’t have any arguments and return nothing.

void f(){
   f(); 
 }

a) What happens when u excuse the above program {stack overflow / memory exhaustion }
b) Given 8GB RAM, 2.5 GHz quad core processor. How much time it takes to tell you about the memory exhaustion
C) what happen when

void f(){
   while(true); 
 }

same questions ‘what happen’, ‘how much time’

Given an array of 1000 numbers, your method multiply all the numbers and takes ‘x ms’ time.
2.1 Found the value of x, with above configuration
2.2 How do you optimise it {parallel , how many threes etc }
2.3 Time in which you solution works in ‘ms’
Design your own garbage collector
Questions on databases [ based on resume ]
Cassandra vs mysql [why, how, what… performance, use-cases, why did u choose one of them, what happen if you replace one with another etc ]
3-tier arch
How do you test 3 tier arch for performance bottleneck {various questions around it; nearly 10 }
Scalability

Solutions
Round 1:

K Distance away


/**
 * O(n)
 * Runtime: 1 ms, faster than 100.00% of Java online submissions for All Nodes Distance K in Binary Tree.
 * Memory Usage: 37.4 MB, less than 73.68% of Java online submissions for All Nodes Distance K in Binary Tree.
 */
class KDistanceAwayFromNodeSolution {

    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        List<Integer> output = new ArrayList<>();
        distanceK(root, target, K, output);
        return output;

    }

    private void distanceKInSubTrees(TreeNode root, int k, List<Integer> output) {

        if (root == null || k < 0)
            return;

        if (k == 0) {
            output.add(root.val);
            return;
        } else {
            distanceKInSubTrees(root.left, k - 1, output);
            distanceKInSubTrees(root.right, k - 1, output);

        }


    }

    private int distanceK(TreeNode root, TreeNode target, int k, List<Integer> output) {
        if (null == root)
            return -1;

        //Print the subtree of target node
        if (root == target) {
            distanceKInSubTrees(target, k, output);
            return 0; // as this node is 0 distance away from target node
        }

        //Search in left subtree
        int distanceFromLeft = distanceK(root.left, target, k, output);

        //means we had found the target node in left subtree
        if (distanceFromLeft != -1) {


            //check does this node is k distance away from target;
            if (distanceFromLeft == k - 1) //(since target to this node is 1 distance away(1 edge), as root is parent of target)
                output.add(root.val);

                //otherwise, we need to find all the node which is rooted this root node
                // we need to go right side of this tree rooted at this root, as we already cover left in above calls
                // The right node would be 2 edges away from the current node
            else
                distanceKInSubTrees(root.right, k - distanceFromLeft - 2, output);


            //return the distance of this node to target node;
            return distanceFromLeft + 1;

        }


        //Search in right subtree
        int distanceFromRight = distanceK(root.right, target, k, output);

        //means we had found the target node in left subtree already
        if (distanceFromRight != -1) {


            //check does this node is k distance away from target;
            if (distanceFromRight == k - 1) //(since target to this node is 1 distance away(1 edge), as root is parent of target)
                output.add(root.val);

                //now, we need to find all the node which is rooted this root node
                // we need to go left side of this tree rooted at this root, as we already cover right in above calls
                // The left node would be 2 edges away from the current node
            else
                distanceKInSubTrees(root.left, k - distanceFromRight - 2, output);


            //return the distance of this node to target node;
            return distanceFromRight + 1;

        }

        // if both left and right says they did not found, then we did not found it
        return -1;


    }
}


/**
 * Runtime: 1 ms, faster than 100.00% of Java online submissions for All Nodes Distance K in Binary Tree.
 * Memory Usage: 37.1 MB, less than 94.74% of Java online submissions for All Nodes Distance K in Binary Tree.
 */
class KDistanceAwayFromNodeSolutionCleaner {
    /*
     class Pair<K, V> {
        private K key;

        public K getKey() {
            return key;
        }

        private V value;

        public V getValue() {
            return value;
        }

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
     */

    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        List<Integer> output = new ArrayList<>();
        distanceK(root, target, K, output);
        return output;

    }

    private void distanceKInSubTrees(TreeNode root, int k, List<Integer> output) {

        if (root == null || k < 0)
            return;

        if (k == 0) {
            output.add(root.val);
            return;
        } else {
            distanceKInSubTrees(root.left, k - 1, output);
            distanceKInSubTrees(root.right, k - 1, output);

        }

    }


    private Pair<Integer, TreeNode> distanceK(TreeNode root, TreeNode target, int k, List<Integer> output) {
        if (null == root)
            return null;

        //Print the subtree of target node
        if (root == target) {
            distanceKInSubTrees(target, k, output);
            return new Pair<>(0, root);// as this node is 0 distance away from target node
        }

        Pair<Integer, TreeNode> distance;

        //means we had found the target node in left subtree already
        if (((distance = distanceK(root.left, target, k, output)) != null
                || ((distance = distanceK(root.right, target, k, output)) != null))) {


            //check does this node is k distance away from target;
            if (distance.getKey() == k - 1) {
                output.add(root.val);
                return null;
            }


            //now, we need to find all the node which is rooted this root node of k-1 distance away
            // (since target to this node is 1 distance away, as root is parent of target)

            // we need to go left/right side of this tree rooted at this root,
            //The left/right node would be 2 edges away from the current node
            if (root.left == distance.getValue()) {
                distanceKInSubTrees(root.right, k - distance.getKey() - 2, output);
            } else {
                distanceKInSubTrees(root.left, k - distance.getKey() - 2, output);
            }

            //return the 'distance' of this 'node' to target node;
            return new Pair<>(distance.getKey() + 1, root);
        }


        // if both left and right says they did not found, then we did not found it
        return null;

    }
}

Round 3:
Given houses in circular manner: Various solution, given few of them below

Solution 1: O(n)/O(n)

 /**
     * Apply the same logic as {@link MaximumSumNoTwoElementsAreAdjacent} and build two
     * array
     * 1. Left to Right {dpLR}
     * 2. Right to left {dpRL}
     * <p>
     * Then take the maximum of dpLR[n-2] {skipping nums[n-1]} and dpRL[1]{skipping nums[0]}
     *
     * @param nums
     * @return
     */
    public static int maximumSumNoTwoAdjCircularArrayTwoArrayDp(int nums[]) {

        if (nums == null || nums.length == 0)
            return 0;


        if (nums.length == 1)
            return nums[0];

        if (nums.length == 2)
            return Math.max(nums[0], nums[1]);


        int n = nums.length;
        int dpLR[] = new int[n];
        int dpRL[] = new int[n];

        dpLR[0] = nums[0];
        dpLR[1] = Math.max(nums[0], nums[1]);

        dpRL[n - 1] = nums[n - 1];
        dpRL[n - 2] = Math.max(nums[n - 1], nums[n - 2]);

        for (int i = 2, j = n - 3; i < nums.length; i++, j--) {

            //Build dpLR -> dp[i] = Max ( dp[i-2] + nums[i] , dp[i-1] )
            dpLR[i] = Math.max(dpLR[i - 2] + nums[i], dpLR[i - 1]);

            //Build dpRL -> dp[j] = Max ( dp[j+2] + nums[j] , dp[j+1] )
            dpRL[j] = Math.max(dpRL[j + 2] + nums[j], dpRL[j + 1]);
        }

        return Math.max(dpLR[n - 2], dpRL[1]);
    }

Solution 2: O(n)/O(1)

 public static int maximumSumNoTwoAdjCircularArrayTwoArrayLinearSingleScan(int nums[]) {

        if (nums == null || nums.length == 0)
            return 0;

        if (nums.length == 1)
            return nums[0];

        if (nums.length == 2)
            return Math.max(nums[0], nums[1]);

        //build dpLR [0..n-2] & build dpRL [1...n-1]

        int n = nums.length;

        int includingLR = nums[0];
        int excludingLR = 0;

        int includingRL = nums[1];
        int excludingRL = 0;
        int maxLR;
        int maxRL;


        int i = 1;
        int j = 2;

        for (; i < n - 1 && j < n; i++, j++) {

            maxLR = Math.max(includingLR, excludingLR);
            includingLR = excludingLR + nums[i]; //dp[i-2] + nums[i]
            excludingLR = maxLR; //dp[i-1]


            maxRL = Math.max(includingRL, excludingRL);
            includingRL = excludingRL + nums[j]; //dp[i-2] + nums[i]
            excludingRL = maxRL; //dp[i-1]

        }

        return Math.max(Math.max(includingLR, excludingLR), Math.max(includingRL, excludingRL));


    }

You can do above in two scan also to simplfy the code [i did first two scan, then in one scan ]

number which appeared 1’s

  private static int numberOccurringOnce(int[] arr, int n) {

        int result = 0;
        int sum ;

        for (int i = 0; i < 32; i++) {

            sum = 0;
            int x = 1 << i;
            for (int j = 0; j < arr.length; j++) {

                if ((arr[j] & x) != 0)
                    sum++;

            }
            sum = sum % n;
            if (sum != 0)
                result = result | x;
        }

        return result;
    }

    private static int  numberOccurringOnceFaster(int[] arr, int n){

        int occurringOnce = 0;
        int occurringTwice = 0;

        for (int i = 0; i<arr.length; i++){

            occurringOnce = occurringOnce^arr[i] & ~occurringTwice;
            occurringTwice = occurringTwice^arr[i] & ~occurringOnce;

        }
        return occurringOnce;
    }

Comments (3)