CareerCup

In case of Java HashMap, corruption is easy to occur if you use it in multi-threaded application without synchronization between threads.

The HashMap has bucket (represents a hash value) and an array representing the list of items that correspond to the given hash value.

{0} -> [x] -> [y] -> null
{1} -> [a] -> null

A common scenario of a corrupted HashMap looks like this:
{0} -> [x] -> [y]
<-

That is, [x] has [y] as its next element and [y] has [x] as its next element. This causes an infinitely loop if you traverse the list.

Suppose we could take a snapshot of the current prices across the exchanges and capture them in the following format:

public class MarketSnapshot {
		public PriceStack[] PriceStacks;
	}

	public class PriceStack {
		public int[] MaxQtys;
		public double[] Prices;
	}

Then, we construct an increasing sequence of prices points as follows:

public class PricePoint {
		public int Exchange;
		public int MaxQty;
		public double Price;
	}

	private static List<PricePoint> getSortedPricePoints(MarketSnapshot snapshot) {
		List<PricePoint> pricePoints = new ArrayList<PricePoint>();
		for(int i=0; i < snapshot.PriceStacks.length; i++) {
			PriceStack priceStack = snapshot.PricePoints[i];
			for (int j=0; j < priceStack.Prices.length; j++) {
				pricePoints.add(new PricePoint(i, priceStack.MaxQtys[j], priceStack.Prices[j]);
			}
		}
		pricePoints.sort((p1, p2) -> p1.Price.compareTo(p2.Price));
		return pricePoints;
	}

Then we simply buy starting from the left hand side of this list, until we have bought enough quantity:

private static void buyAtMarket(int qty, MarketSnapshot currentSnapshot) {
		List<PricePoint> pricePoints = getSortedPricePoints(currentSnapshot);
		int bought = 0;
		int i = 0;
		while(bought < qty && i < pricePoints.size()) {
			bought += pricePoints.get(i++);
		}
	}

Isn't this the same an object-pool (generalization of a connection pool)?

PenChief and NoOne, why do you actually need to perform the merge?
You can just run through the merge process without actually storing the results. Thus, it becomes an O(1) algo.

The following is just to give an idea. I definitely did not cover the corner cases.

int A = arr1.length;
	int B = arr2.length;
	int m = (int)(A+B)/2; // The index of the first median element in the merged array
	int n = (A+B) % 2 == 0 ? 2 : 1; // No. of median elements
	
	int i, j;
	while(i < A && j < B && (i+j) < m) {
		int a = arr1[i];
		int b = arr2[j];
		if (a < b)
			i++;
		else
			j++;
	}

	while(i < B && (i+j) < m)
		i++;

	while(j < B && (i+j) < m)
		j++;

	if (i == A) {
		return n == 1 ? arr2[j] : (arr2[j]+arr2[j+1])/2;
	} else if (j == B)
		return n == 1 ? arr1[i] : (arr1[i]+arr1[i+1])/2;
	} else {
		int x = arr1[i] < arr2[j] ? arr1[i++] : arr2[j++];
		int y = arr1[j] < arr2[j] ? arr1[i] : arr2[j];
	}

For the maximum overlapping problem, the following solution creates a sorted list of 'events' where each event is the start or the end of an interval. Think of it as a timeline of events.

Now, is a simple case of traversing the list and keep track of overlaps.

public static void solve(int[][] intervals) {
	    List<Event> events = getSortedEvents(intervals);
	    int max = 0;
	    int overlap = 0;
	    int bestPoint = 0;
	    for(Event event : events) {
	        if ("Entry".equals(event.getType()))
	          overlap++;
	        else
	          overlap--;
	        if (overlap > max) {
	            max = overlap;
	            bestPoint = event.getTime();
	        }
	    }
	    System.out.println(max + " " + bestPoint);
	}
	
	private static List<Event> getSortedEvents(int[][] intervals) {
	    List<Event> events = new ArrayList<Event>();
	    for(int i=0; i < intervals.length; i++) {
	        events.add(new Event(intervals[i][0], "Entry"));
	        events.add(new Event(intervals[i][1], "Exit"));
	    }
	    return events
	            .stream()
	            .sorted(Comparator.comparing(Event::getTime).thenComparing(Event::getType))
	            .collect(Collectors.toList());
	}
	
	private static class Event {
	    private int time;
	    private String type;
	    
	    Event(int time, String type) {
	        this.time = time;
	        this.type = type;
	    }
	    
	    int getTime() { return time; }
	    String getType() { return type; }
	}

This is a *recursive* approach:
Step 1: Pick one movie at a time and fix it's schedule.
Step 2: Recurse to schedule the rest of the movies. If can't then go back to Step 1

public class MovieScheduler {
    public static void main(String[] args) {
        Map<String, List<Integer>> movies = new HashMap<>();
        movies.put("Shining", Arrays.asList(14, 15, 16));
        movies.put("Kill Bill", Arrays.asList(14, 15));
        movies.put("Pulp Fiction", Arrays.asList(14, 15));
        List<String> movieNames = new ArrayList<>(movies.keySet());
        Map<Integer, String> schedule = new HashMap<>();
        if (schedule(movies, movieNames, 0, schedule)) {
            System.out.println("Schedule is " + schedule);
        } else {
            System.out.println("Unable to schedule!!");
        }
    }

    private static boolean schedule(Map<String, List<Integer>> movies, List<String> movieNames, int index, Map<Integer, String> schedule) {
        if (index == movieNames.size())
            return true;

        String movie = movieNames.get(index);
        List<Integer> timings = movies.get(movie);
        for(int timing : timings) {
            if (!schedule.containsKey(timing)) {
                Map<Integer, String> scheduleCopy = new HashMap<>(schedule);
                scheduleCopy.put(timing, movie);
                if (schedule(movies, movieNames, index+1, scheduleCopy)) {
                    schedule.clear();
                    schedule.putAll(scheduleCopy);
                    return true;
                }
            }
        }
        return false;
    }
}

My second attempt. This time, I managed to get O(N) time using O(logN) space by using a *Trie* data structure.

*Step 1: Build the Trie*
This is a custom Trie implementation which also keeps track of the number of potential words starting at the given character.
For example, if the dictionary has both "face" and "facebook". The node representing "f" has a word count of 2. Actually, even nodes "a", "c" and "e" have the same word count of 2. Nodes "b", "o", "o", "k" have word count of 1.

*Step 2: Find the combination of the longest possible words*
Starting at the beginning of the input, find the longest possible word that starts here. Then jump that many characters and look for the longest possible word at the next point, etc.

*Step 3: Join the words found into a sentence*
Simply join the words found to form a sentence with spaces

public class WordBreakByDictionary {
    public static void main(String[] args) {
        Trie trie = buildTrie(new String[] { "i", "like", "face", "book", "facebook" });
        System.out.println(findMinimumSentence("ilikefacebook", trie));
    }

    private static Trie buildTrie(String[] dictionary) {
        Trie root = new Trie();
        for(String word : dictionary) {
            Trie parent = root;
            for(int i=0; i < word.length(); i++) {
                int index = word.charAt(i) - 'a';
                Trie curr = parent.children[index];
                if (curr == null)
                    parent.children[index] = curr = new Trie();
                curr.wordCount++;
                if (i == word.length()-1)
                    curr.isWord = true;
                parent = curr;
            }
        }
        return root;
    }

    private static String findMinimumSentence(String input, Trie trie) {
        int index = 0;
        List<String> words = new ArrayList<>();
        while(index < input.length()) {
            String nextWord = findLongestWord(input.substring(index), trie);
            if (nextWord.length() > 0) {
                words.add(nextWord);
                index += nextWord.length();
            } else {
                return null;
            }
        }
        return String.join(" ", words);
    }

    private static String findLongestWord(String input, Trie trie) {
        Trie parent = trie;
        String longestSoFar = "";
        for(int i=0; i < input.length(); i++) {
            int index = input.charAt(i) - 'a';
            Trie curr = parent.children[index];
            if (curr == null)
                return longestSoFar;

            if (curr.isWord) {
                longestSoFar = input.substring(0, i + 1);
                if (curr.wordCount == 1)
                    return longestSoFar;
            }
            parent = curr;
        }
        return longestSoFar;
    }

    private static class Trie {
        Trie[] children = new Trie[26];
        boolean isWord;
        int wordCount;
    }
}

When I run this I get "i like face book"

This is the first iteration.

I store the dictionary as a hash set for faster lookup and use recursion to find all possible words.

public class WordBreakByDictionary {
    public static void main(String[] args) {
        Set<String> dictionary = new HashSet<>(Arrays.asList("i", "like", "face", "book", "facebook"));
        System.out.println(findMinimumWordCount("ilikefacebook", dictionary));
    }

    private static int findMinimumWordCount(String input, Set<String> dictionary) {
        if (input.length() == 0)
            return 0;

        int min = Integer.MAX_VALUE;
        for(int i=1; i <= input.length(); i++) {
            if (dictionary.contains(input.substring(0, i))) {
                int subCount = findMinimumWordCount(input.substring(i), dictionary);
                if (min > subCount+1) {
                    min = subCount + 1;
                }
            }
        }
        return min;
    }
}

However, if the problem is to include friends-of-friends as well, then we need to store all the friendships as they arrive

public class FriendshipStream {
    public static void main(String[] args) {
        List<List<Integer>> relations = new ArrayList<>();
        relations.add(Arrays.asList(1, 2));
        relations.add(Arrays.asList(2, 3));
        relations.add(Arrays.asList(1, 3));
        relations.add(Arrays.asList(2, 4));
        relations.add(Arrays.asList(5, 6));

        printFriendCircle(relations.iterator(), 1);
    }

    private static void printFriendCircle(Iterator<List<Integer>> relations, int id) {
        Map<Integer, List<Integer>> friendships = buildMap(relations);
        List<Integer> allFriends = findAllFriends(friendships, id);
        for(int friend : allFriends)
            System.out.println(friend);
    }

    private static Map<Integer, List<Integer>> buildMap(Iterator<List<Integer>> relations) {
        Map<Integer, List<Integer>> friendships = new HashMap<>();
        while(relations.hasNext()) {
            List<Integer> relation = relations.next();
            addFriendship(friendships, relation.get(0), relation.get(1));
            addFriendship(friendships, relation.get(1), relation.get(0));
        }
        return friendships;
    }

    private static void addFriendship(Map<Integer, List<Integer>> friendships, int a, int b) {
        List<Integer> friends = friendships.computeIfAbsent(a, k -> new ArrayList<>());
        friends.add(b);
    }

    private static List<Integer> findAllFriends(Map<Integer, List<Integer>> friendships, int id) {
        List<Integer> friends = new ArrayList<>();
        List<Integer> next = Collections.singletonList(id);
        while(!next.isEmpty()) {
            List<Integer> curr = new ArrayList<>();
            for(int friend : next) {
                List<Integer> friendsOfFriend = friendships.getOrDefault(friend, Collections.emptyList());
                for(int fOfF : friendsOfFriend)
                    if (!friends.contains(fOfF) && fOfF != id)
                        curr.add(fOfF);
            }
            friends.addAll(curr);
            next = curr;
        }
        return friends;
    }

}

Is the question to find *immediate* friends only? Then its trivial.

private static List<Integer> getFriends(Iterator<List<Integer>> relations, int id) {
        List<Integer> friends = new ArrayList<>();
        while(relations.hasNext()) {
            List<Integer> relation = relations.next();
            if (relation.get(0) == id)
                friends.add(relation.get(1));
            else if (relation.get(1) == id)
                friends.add(relation.get(0));
        }
        return friends;
    }


}

Chris, the original question seems to suggest *only* all possible combinations of lower case and upper case, *without* changing the order of characters.

Solution *without* recursion.

Note: this only works if the given string is less than 32 characters long.

Step 1: Calculate the number of permutations. Basically, each character can have two states, either lower case or upper case. Hence total permutations = 2^n, where n = length of given string
Step 2: Iterate through 1 to 2^n. Each of these numbers represents one possible permutation. For example, 000 means all chars are lower, abc. 010 means aBc, 001 means abC, and so on.

public static void main(String[] args) {
        String[] perms = permuteBinary("abc");
        for(String perm : perms)
            System.out.println(perm);
    }

    private static String[] permuteBinary(String given) {
        given = given.toLowerCase();
        int numPerms = 1 << given.length();
        String[] result = new String[numPerms];
        for(int i=0; i < numPerms; i++) {
            result[i] = buildPerm(given, i);
        }
        return result;
    }

    private static String buildPerm(String original, int bitPositions) {
        int k = bitPositions;
        char[] result = original.toCharArray();
        for(int i=0; i < original.length(); i++) {
            if ((k&1) == 1)
                result[i] =  Character.toUpperCase(result[i]);
            k = k >> 1;
        }
        return new String(result);
    }

My earlier solution is unnecessarily complicated. Although it is a O(n2) solution, it involves an extra O(n) iteration.

Here is a far more simple solution that is still O(n2) time and O(n) space.

1. Maintain a hash set that contains all the unique values in the given list, but start with an empty set
2. Go over each *pair* of numbers in the given list
3. For each pair, check if the sum of the two numbers has a corresponding value in the set such that (value in the set + sum of the pair = 0)
4. If found, then print out the triplet
5. If not found, the add the first item to the set

public class TripletsWithSumZero {
    public static void main(String[] args) {
        int[] given = new int[] { 0, -1, 2, -3, 1};
        findTriplets(given);
    }

    private static void findTriplets(int[] given) {
        Set<Integer> set = new HashSet<>();
        for(int i=0; i < given.length; i++) {
            for(int j=i+1; j < given.length; j++) {
                if (set.contains(-(given[i]+given[j])))
                    System.out.printf("Found a match (%d, %d, %d)\n", given[i], given[j], -(given[i]+given[j]));
                else
                    set.add(given[i]);
            }
        }
    }
}

2.

The brute force solution is O(n3) time and O(1) space.

This solution is O(n2) and O(n) space. The space is required for the hash table.

*Solution using Hash table*
Step 1: Find all the pairs of numbers and group them by the sum of the two numbers.
Step 2: For each group, store them as a hash table with key = sum and value = list of pairs
Step 3: Go over the original array once again and see if there are any pairs with sum = current number.
Step 4: To avoid duplication, make sure that the current number appears before the other two items (the pair)

public class TripletsWithSumZero {
    public static void main(String[] args) {
        int[] given = new int[] { 0, -1, 2, -3, 1};
        Map<Integer, List<Pair>> map = buildMap(given);
        findTriplets(given, map);
    }

    private static Map<Integer, List<Pair>> buildMap(int[] given) {
        Map<Integer, List<Pair>> map = new HashMap<>();
        for(int i=0; i < given.length; i++) {
            for(int j=i+1; j < given.length; j++) {
                Pair pair = new Pair(i, j);
                int sum = given[i] + given[j];
                List<Pair> pairs = map.get(sum);
                if (pairs == null) {
                    pairs = new ArrayList<>();
                    map.put(sum, pairs);
                }
                pairs.add(pair);
            }
        }
        return map;
    }

    private static void findTriplets(int[] given, Map<Integer, List<Pair>> map) {
        for (int i=0; i < given.length; i++) {
            List<Pair> matchingPairs = map.get(-given[i]);
            if (matchingPairs != null)
                for (Pair pair : matchingPairs)
                    if (i < pair.a)
                        System.out.printf("Found a match (%d, %d, %d)\n", given[i], given[pair.a], given[pair.b]);
        }
    }

    private static class Pair {
        int a, b;
        Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }
}

Solution without recursion, O(n) time and O(1) space

public static Node reverse(Node node) {
        if (node == null)
            return null;

        Node next = node.next;
        node.next = null;

        while(next != null) {
            Node temp = next.next;
            next.next = node;
            node = next;
            next = temp;
        }
        return node;
    }

1. Maintain a hash table as follows:

Key = word
    Value = array of integers of size 25
    The 26 values are
    0 => The total 24 hour count for this word
    1 => The total count for this word in the current hour
    2 => The count for this word in the previous hour
    ...
    24 => The count for this word 24th hour from now

.

2. As you process the stream of messages, for each word, do the following
(a) Look up the word in the hash table, if not found, add it
(b) Increment both the total word count (index 0) and the current hour count (index 1)
.

3. Run a batch job every hour that iterates through all the values and does the following:
(a) Subtract the 24th hour (index 24) word count from the total count (index 0)
(b) Shift the sub-array from 1-24 by one place
(c) Set value at index 1 to count=0
.

There are two advantages to this approach:
(a) Once you have processed a message, you don't need to keep the logs any more
(b) It also satisfies the follow-up question, where the message does not have a time stamp

I would ask the interviewer a few questions:
1. If a server is already processing a message, can we assign it one more? (i.e. is the server capable of queuing up messages or processing them in parallel?)
2. If No, is it OK to assign fewer messages to a slow server?

I would start with a simple round robin solution like this and improve on that based on the answers to the above:

package com.test;

public class RoundRobinDistribution {
    public static void main(String[] args) {
        String[] servers = new String[] { "S1", "S2", "S3"};
        Distributor distributor = new Distributor(servers);
        for(int i=0; i < 5; i++)
            System.out.println("Message " + i + " to " + distributor.getNextServer());
    }

    private static class Distributor {
        private String[] servers;
        private int index = -1;

        Distributor(String[] servers) {
            if (servers == null || servers.length == 0)
                throw new IllegalArgumentException("Servers list is empty");
            this.servers = servers;
        }

        public String getNextServer() {
            index = (index + 1) % servers.length;
            return servers[index];
        }
    }
}

package com.test;

import java.util.ArrayList;
import java.util.List;

public class TreeAsAMatrix {
    public static void main(String[] args) {
        boolean[][] adj = buildAdjacenyMatrix();
        TreeNode tree = buildTree(adj);
        printTree(tree);
    }

    private static boolean[][] buildAdjacenyMatrix() {
        boolean[][] matrix = new boolean[6][];
        //                                           0      1      2      3      4      5
        matrix[0] = new boolean[] { false, true , true , true , true , true  };
        matrix[1] = new boolean[] { false, false, false, false, false, false };
        matrix[2] = new boolean[] { false, false, false, false, false, false };
        matrix[3] = new boolean[] { false, false, false, false, false, false };
        matrix[4] = new boolean[] { false, false, false, false, false, false };
        matrix[5] = new boolean[] { false, false, false, false, false, false };

        return matrix;
    }

    private static TreeNode buildTree(boolean[][] adj) {
        TreeNode[] nodes = new TreeNode[adj.length];
        boolean[] hasParent = new boolean[adj.length];
        for(int i=0; i < adj.length; i++) {
            for(int j=0; j < adj.length; j++) {
                if (adj[i][j]) {
                    if (nodes[i] == null)
                        nodes[i] = new TreeNode(i);
                    if (nodes[j] == null)
                        nodes[j] = new TreeNode(j);
                    nodes[i].children.add(nodes[j]);
                    hasParent[j] = true;
                }
            }
        }

        for(int i=0; i < hasParent.length; i++)
            if(nodes[i] != null && !hasParent[i])
                return nodes[i];

        return null;
    }

    private static void printTree(TreeNode root) {
        if(root == null)
            System.out.println("Tree is empty");
        else
            printNode(root, "");
    }

    private static void printNode(TreeNode node, String prefix) {
        System.out.println(prefix + " -> " + node.data);
        for(TreeNode child : node.children)
            printNode(child, prefix + "   ");
    }

    private static class TreeNode {
        int data;
        List<TreeNode> children = new ArrayList<TreeNode>();
        TreeNode(int data) {
            this.data = data;
        }
    }

}

package com.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ShareHoldingGraph {

    public static void main(String[] args) {
        Company companyA = new Company("A");
        Company companyB = new Company("B");
        Company companyC = new Company("C");
        companyA.shares.add(new Share(companyB, 10));
        companyA.shares.add(new Share(companyC, 2));
        companyB.shares.add(new Share(companyC, 5));
        List<Company> companyList = Arrays.asList(companyA, companyB, companyC);

        System.out.println("CompanyA -> C " + companyA.getPercentage(companyC));
        clearVisisted(companyList);
        System.out.println("CompanyB -> C " + companyB.getPercentage(companyC));
        clearVisisted(companyList);
        System.out.println("CompanyA -> B " + companyA.getPercentage(companyB));
    }

    private static void clearVisisted(List<Company> companyList) {
        for(Company company : companyList)
            company.visited = false;
    }

    private static class Company {
        String name;
        List<Share> shares = new ArrayList<>();
        boolean visited;
        Company(String name) {
            this.name = name;
        }

        double getPercentage(Company company) {
            if (this == company)
                return 100;

            if (visited)
                return 0;

            this.visited = true;
            double totalShares = 0;
            for(Share share : shares) {
                if (share.company == company)
                    totalShares += share.percentage;
                else
                    totalShares += share.company.getPercentage(company) * (share.percentage/100);
            }
            return totalShares;
        }
    }

    private static class Share {
        Company company;
        double percentage;

        Share(Company company, double percentage) {
            this.company = company;
            this.percentage = percentage;
        }
    }
}

Prints:

CompanyA -> C 2.5
CompanyB -> C 5.0
CompanyA -> B 10.0

public static void main(String[] args) {
        char[] buf = new char[6];
        read(buf, 6);
        System.out.println("Read the string: " + new String(buf));
    }

    private static final int C_CHUNK_SIZE = 4;
    private static Random random = new Random();
    private static void readChunk(char[] buf) throws IOException {
        Arrays.fill(buf, 'a');
        if(random.nextBoolean())
            throw new IOException("Something went wrong");
        if(random.nextBoolean())
            buf[buf.length-1] = '\0';
    }

    private static void read(char[] buf, int length) {
        int lastIndex = 0;
        char[] temp = new char[C_CHUNK_SIZE];
        while(lastIndex < length) {
            try {
                readChunk(temp);
                for(int i=0; i < temp.length && lastIndex < length; i++) {
                    if (temp[i] == '\0')
                        return;
                    buf[lastIndex++] = temp[i];
                }
            } catch (IOException e) {
                System.out.println("There was an error reading, will try again...");
            }
        }
    }

Fixed Anon's Dynamic programming solution:

public static void main(String[] args) {
        int[] test1 = new int[] { 0 };
        System.out.println("Test 1 : " + getCountDynamic(test1));

        int[] test2 = new int[] { 1, 1, 1, 1 };
        System.out.println("Test 2 : " + getCountDynamic(test2));

        int[] test3 = new int[] { 1, 1, 0 };
        System.out.println("Test 3 : " + getCountDynamic(test3));
    }

    private static int getCountDynamic(int[] given) {
        if (given.length == 0)
            return 0;

        int counter[] = new int[given.length];
        counter[given.length-1] = (given[given.length-1] > 0 ? 1 : 0);

        for(int i=given.length-2; i >= 0; i--) {
            if (given[i] > 0 && ((given[i]*10 + given[i+1]) <=26))
                counter[i] = 1 + counter[i+1];
            else
                counter[i] = counter[i+1];
        }
        return counter[0];
    }

Test 1 : 0
Test 2 : 4
Test 3 : 2

public class GetFibonacciNumbers {
    public static void main(String[] args) {
        int[] given = new int[] {3, 6, 7, 9, 2};
        int[] output = getFibonnaciNumbers(given);
        printArray("given", given);
        printArray("output", output);
    }

    private static void printArray(String name, int[] given) {
        StringBuilder sb = new StringBuilder(name);
        sb.append(": ");
        for(int i=0; i < given.length; i++) {
            if (i > 0)
                sb.append(", ");
            sb.append(given[i]);
        }
        System.out.println(sb);
    }

    private static int[] getFibonnaciNumbers(int[] given) {
        int[] output = new int[given.length];
        int index = 0;
        for(int x : given) {
            int nearestFib = getNearestFibonacciNumber(x);
            if (x == nearestFib)
                output[index++] = x;
        }
        return output;
    }

    private static int getNearestFibonacciNumber(int given) {
        int fN = 1;
        int fNPrev = 1;
        while(fN < given) {
            int temp = fN;
            fN = fN + fNPrev;
            fNPrev = temp;
        }
        System.out.println("Neartest to " + given + " is " + fN);
        return fN;
    }
}