[Leetcode] Random pick with weight

 class Solution {

    private int[] prefixSums;

    private int totalSum;

    public Solution(int[] w) {

        this.prefixSums = new int[w.length];

        int prefixSum = 0;

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

            prefixSum += w[i];

            this.prefixSums[i] = prefixSum;

        }

        this.totalSum = prefixSum;

    }

    public int pickIndex() {

        double target = this.totalSum * Math.random();

        int i = 0;

        // run a linear search to find the target zone

        for (; i < this.prefixSums.length; ++i) {

            if (target < this.prefixSums[i])

                return i;

        }

        // to have a return statement, though this should never happen.

        return i - 1;

  }

} 

[Leetcode] Accounts Merge

Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Solution 1:

Find the connected components in the graph

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> emailToName = new HashMap();
        Map<String, ArrayList<String>> graph = new HashMap();
        for (List<String> account: accounts) {
            String name = "";
            for (String email: account) {

                // the first word is the email
                if (name == "") {
                    name = email;
                    continue;
                }

                // every email is getting connected with an edge to the first email in that list
                graph.computeIfAbsent(email, x-> new ArrayList<String>()).add(account.get(1));

                // the first email is also getting connected by an edge to all the other emails in the list
                graph.computeIfAbsent(account.get(1), x-> new ArrayList<String>()).add(email);
                emailToName.put(email, name);
            }
        }

        Set<String> seen = new HashSet();
        List<List<String>> ans = new ArrayList();
        for (String email: graph.keySet()) {
            if (!seen.contains(email)) {
                seen.add(email);
                Stack<String> stack = new Stack();
                stack.push(email);
                List<String> connectedComponent = new ArrayList();
                while (!stack.empty()) {

                    // once all the nodes in a connectedComponent are looked at, the stack becomes empty
                    String node = stack.pop();
                    connectedComponent.add(node);
                    for (String nei: graph.get(node)) {
                        if (!seen.contains(nei)) {
                            seen.add(nei);
                            stack.push(nei);
                        }
                    }
                }
                Collections.sort(connectedComponent);
                connectedComponent.add(0, emailToName.get(email));

                // add the name to the first element in the connectedComponents list
                ans.add(connectedComponent);
            }
        }
        return ans;
    }
}

Adobe Interview Questions - Java

Interview I :
1) Binary search in a shifted array
2) N teams are playing. Finding a sequence on length N so that the left team has lost to the right team.

Interview 2:
1) I am flipping cards from a deck of 26 cards. Design a game stratregy so that you can guess which card is red. Proof of your strategy by induction.
2) Find two numbers whose sum is k in a bst
3) A number as sum of 1s and 2s. Permutations and Combinations
4)

Interview 3:
1) Implement a LRU cache
2) Implement threadpool in Java
3) Implement a blocking queue in Java
Added question : How to implement connection pool in java.

Interview 4:
1) XML questions on Xpath and search
2) Producer Consumer problem

Adobe Interview Experience (Jan - 2008)

First Interview

1. 4 persons with different speeds attempt to cross a bridge in the night. There is only one torch and only two people can cross the bridge together and the joint speed is that of the slower of the two. Find the minimum time required to get everyone across.


Time taken by person 1 : 1 minute
Time taken by person 2 : 2 minutes
Time taken by person 3 : 5 minutes
Time taken by person 4 : 10 minutes

2. There are 2 cans - can 'A' contains a red liquid and can 'B' contains blue liquid. We take one unit of liquid from A and mix it with B. Then we take one unit from B and mix it with A. What's the proportion of red:blue in A and blue:red in B now? 

3. Write a non recursive function to reverse a linked list

4. There are a lot of events emanating from user input (mouse movement, keyboard key punches, mouse clicks etc). In the event processing code - there is a single giant switch case that handles these. How do we organize the switch statement to minimize the number of case checks. 


Second Interview 

1. Array A has size M+N and contains M integers in sorted order. Array B has size N and contains N integers in sorted order. How can we merge A and B without using a third array?

2. Find one pair of elements in a sorted array whose sum equals a given value. If the array is unsorted but contains only positive integers, how would you still solve it in O(n) ? 

3. Given 2 sorted arrays, how will you find the median of numbers contained in both of them in logarithmic time?

4. You have a program a.c that is compiled into a.exe and another b.c that is compiled into b.exe . b.exe appends a file 1.dat to a.exe and creates the file out.exe. Now assuming that out.exe is a valid executable, how would you write code in a.c so that data is read from the data file that is appended to the executable? 

5. What are the differences between new and malloc? You said you could overload new operator - what else must be done so that I can write my own memory management library? Do you know what name hiding is? Do you know what name mangling is - why is it required? 


Third Interview

1. Given n integers from the range 50...100 such that no integer repeats. The integers are stored on the disk - Now you're required to sort them in linear time. You are given only 7 bytes of storage apart from the few variables you will invariably need for writing the code. How will you sort if I gave you even less memory? (The code involved creating a bitmap using the 7 element array and setting the bit corresponding to the integers that was found and later printing out the map - I'd to write the code in all its glory and run it on a few cases) 

2. There are 3W and 2B hats in a basket. Persons labelled 1, 2, 3 are made to stand in a row such that 2 can see the hat 1 is wearing and 3 can see the color of the hats 1 and 2 are wearing. Now 3 remarks, "I've no idea about the color of my hat". Then 2 remarks, "I've no idea about the color of my hat either!". Then 1 correctly deduces the color of his hat - what reasoning did A use and what is the color of his hat? 


Fourth Interview

1. A pre order traversal of a complete binary tree is given in an array - then you need to print all the elements at a specified level.
2. You're given the following program:

-------------------------------- 
int main()
{
printf("TWO\n");
return 0;
}
---------------------------------

Add any code above or below the lines so that the output is 

ONE
TWO
THREE

Give me 10 different ways to do this and which of them are specific to C++? 

3. There's a gold bar 100 units in length. You need to pay a worker 2 units everyday for his work. What's the minimum number of cuts that you need to make and where will you make them?
4. What's the difference between an abstract class and a virtual class? ... from the standpoint of multiple inheritance? 
5.There are 50 famillies in a village each consisting of a husband and a wife. Each woman knows all the men who are thieves except her husband. Now the king announces that there is at least one thief in the village. What happens then?