Barry Fruitman
BAN USER- 2of 2 votes
AnswersDesign the Facebook newsfeed for an Android app. The actual design would be very complex so you may limit your solution to only status updates and photo posts. Keep your answer broad rather than deep since it would need to fit in a 45-minute interview.
- Barry Fruitman in United States
Normally you would need to ask the interviewer a lot of questions but since that is not possible here, state your assumptions.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Android - 2of 2 votes
AnswersWrite a function that takes a string and returns true if the entire string is a palindrome, otherwise return false. The function should be case-insensitive and ignore any whitespace or punctuation.
- Barry Fruitman in United States
For example, return true for:
"A man, a plan, a canal: Panama."| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 1of 1 vote
AnswersImplement this Java function:
- Barry Fruitman in United States
int findNeedleInHaystack(String haystack, String needle)
If needle is a substring of haystack, it should return the index of needle.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm
- 4 Answers Phone screen vs. face-to-face
Hi,
- Barry Fruitman March 16, 2013
It would be nice if sample questions could be tagged as phone screen or face-to-face interview. There is considerable difference between the two so it would make easier to prepare for the type of interview we are facing.
Thanks,
Barry| Flag | PURGE
@stevenh47 Your solution may work but it will more complex than O(n*m) unless m is very large. Also, sorting a string list takes longer than O(n log n) because string comparisons take longer than O(1) .
- Barry Fruitman April 03, 2013It is better to check if a character is NOT a letter than to check if it IS whitespace or punctuation.
- Barry Fruitman March 21, 2013@showell30 Absolutely right. I had the same solution as you except I accidentally placed the punctuation check outside the main loop.
- Barry Fruitman March 21, 2013I like your answer a lot, except you can simplify even further:
int findSubstring(String haystack, String needle)
{
return haystack.indexOf(needle);
}
Honestly, I thought the face-to-face problems were supposed to be harder than the phone screen problems. However in my recent experience I've found them to be more-or-less the same.
- Barry Fruitman March 19, 2013@jay You're right. Sequential locking is the way to go.
- Barry Fruitman March 18, 2013@showell30@yahoo.com Thanks for the upvote.
I thought your summing method was just a clever shortcut but now I suspect it is actually the layer of DP this problem needed. It is a table that stores the results of the overlapping subproblems, i.e. the sums of all the overlapping ranges of numbers. In other words it meets all the requirements of DP. Or at least I think it does, I'm still new to this.
BTW I'm interviewing with some big companies this week and it would mean a lot if you wished me good luck! :)
I got it to work recursively and with showell30's clever summing shortcut. Runtime is somewhat slow (3-4 seconds) on the second test case.
There must be a DP solution since there are overlapping subproblems but I'd need a 3D whiteboard to figure it out.
My Java code:
public class FindMatchingSums {
private static int S[];
private static int n;
public static void main(String args[]) {
String s1 = "123231";
initializeS(s1);
int sum1 = comparehalves(0, s1.length()-1);
System.out.println("sum1=" + sum1);
String s2 = "986561517416921217551395112859219257312";
initializeS(s2);
int sum2 = comparehalves(0, s2.length()-1);
System.out.println("sum2=" + sum2);
}
private static void initializeS(String number) {
// Precompute sums (thanks, showell30)
n = number.length();
S = new int[n];
S[0] = Integer.parseInt(number.substring(0,1));
for(int i = 1; i < n; i++)
S[i] = S[i-1] + Integer.parseInt(number.substring(i,i+1));
}
private static int comparehalves(int i, int j) {
// compare the sums of the two halves of the range of numbers from i to j
// i.e. split the range of numbers from i to j into two equal subranges, sum each and compare the sums
// if they are equal, return the length of the whole range, otherwise return 0
if(i < 0)
return 0;
if(j >= n)
return 0;
if(i >= j)
return 0;
if(((i - j + 1) & 1) == 1) {
// Can't split an odd length string in half
int max = 0;
int s1 = comparehalves(i+1,j);
int s2 = comparehalves(i,j-1);
return Math.max(s1, s2);
}
// Compare halves of this range
int end_of_first_half = ((j-i+1)/2)+i-1;
if(sum_of_range(i, end_of_first_half) == sum_of_range(end_of_first_half+1, j))
return j - i + 1;
// Compare even length substrings
int max = 0;
int s1 = comparehalves(i+2, j);
int s2 = comparehalves(i+1, j-1);
int s3 = comparehalves(i, j-2);
return Math.max(s1, Math.max(s2, s3));
}
private static int sum_of_range(int k, int l) {
int sum = S[l] - (k > 0 ? S[k-1] : 0);
return sum;
}
}
@showell30@yahoo.com Your solution is extremely robust but I think they were looking for a fix to the given Java class rather than the design for a large distributed banking system, don't you?
- Barry Fruitman March 17, 2013@jay Good point. However in this particular case I might still lock the critical block because the code within is extremely fast.
- Barry Fruitman March 17, 2013Good point. I was confusing this "remove" problem with an "insert" problem which would require moving all the chars every time.
- Barry Fruitman March 17, 2013@eugene.yaravoi Excellent point. It is important to understand the difference between a "find all" and "count all" problem. The former usually has higher complexity.
- Barry Fruitman March 17, 2013I got a similar question on my Google interview... and blew it. I wish I had spent more time solving this problem. Ironically, I figured out the optimal solution the next day while walking my dog. It uses DP and goes like this:
1. Sort the discs by top
2. Keep a "meta-disc" in memory and initialize it to the first disc in the sorted list. The meta-disc represents the preceding series of discs that overlap.
3. Iterate through the sorted list, from disc 2 to disc n.
4. If the top of disc i is below the bottom of the meta disc (i.e. we found a gap) re-initialize the meta-disc to disc i and proceed to the next disc.
5. However if the top of disc i is within the meta-disc, it must overlap with one of the preceding discs and we increment the overlap count.
6. Also, if the bottom of disc i is below the bottom of the meta-disc, enlarge the meta-disc by setting it's bottom to the bottom of disc i.
The meta-disc is our DP subproblem-holder. It saves us from checking every disc or searching for particular discs.
The complexity is O(n log n) due to the sort. The iterations take O(n) and don't require a binary search so each iteration takes O(1).
DJ!!! ALWAYS... ASK... QUESTIONS
Good luck on your next job interview.
Is the complexity of this solution O(N^2 x n) ? We are calculating an NxN matrix n times. Please correct me if I'm wrong.
- Barry Fruitman March 17, 2013We only need to compare the word against the beginning of each item in the list, keeping track of the longest match. The result is max + 1, unless the entire prefix matched some word, in which case we can exit early and there is no solution (return null).
The prefix "" can never be a result since it matches everything.
Complexity is O(N*m) since we iterate through the list once, comparing m characters (m is the length of word). This is the best we can do since we must compare the prefix against every word.
public class ShortestPrefix {
private static String shortestPrefix(String[] list, String word) {
int max = 0;
// Iterate through the word list once
for(String item : list) {
if(item.length() < word.length())
// Skip this item, it's shorter than word
continue;
int i = 0;
for(i = 0; i < word.length(); i++) {
// Compare char-by-char until there isn't a match
if(item.charAt(i) != word.charAt(i))
break;
}
if(i > max)
// Update max to the longest prefix that matched at least one word
max = i;
if(max == word.length())
// The entire prefix matched at least one word. Therefore there is
// no prefix that isn't a prefix of any word
return null;
}
// Return the length of the longest prefix that matched, plus 1
return word.substring(0, max+1);
}
public static void main(String[] args) {
// Test cases
String list[] = new String[] {"alpha", "beta", "cotton", "delta", "camera"};
// String list[] = new String[] {"alpha", "beta", "cotton", "delta"};
// String list[] = new String[] {"alpha", "beta", "delta"};
// String list[] = new String[] {"catalog", "category", "catacomb"};
String word = "cat";
String result = shortestPrefix(list, word);
}
}
The in-place solution has complexity of O(N^2) because you have to move the characters following a space after it's removed. (N characters moved N times).
By copying the string we don't have to move any characters so the solution is O(N). Only one pass is necessary if we can return the copied string, otherwise a second pass is necessary to copy it back to the original. Either way it's still O(N).
@Venkat the problem with synchronizing on the accounts is one caller may be transferring from account A to B while another is transferring from B to A. In this case they will be locking in reverse order and a deadlock can occur.
Unlocking and circling back can just cause the same problem to happen over and over.
Don't synchronize the entire method, just the critical block:
Public void TransferAccount(AccountID id1, AccountID id2){
Account a1 = id1.GetAccount();
Account a2 = id2.GetAccount();
//Swap amounts.
synchronized (this) {
// This section should execute very quickly and affect performance very little
Temp = a1.Balance;
a1.Balance = a2.Balance;
a2.Balance = Temp;
}
}
A method marked synchronized is synchronized on an instance of the containing class. Only one thread at a time can call that method per instance.
e.g. if m1 and m2 are instances of MyClass, and MyClass.syncedMethod() is synchronized, m1.syncedMethod() and m2.syncedMethod() can be called at the same time by two threads, but if a third thread tries to call either, it will be blocked.
A method marked static synchronized is synchronized on the class. Only one thread at a time can call that method, period.
I believe he was looking for the paranoid response. Many security breaches leave traces that can appear perfectly normal (e.g. a light bulb removed by an intruder can be mistaken for a burnt-out bulb, and usually is). A person in charge of security must never overlook these signs.
Awesome question, BTW.
My solution in Java. The time complexity is O(n^m) where n is the number of variable positions (in this case 2, f and b) and m is the number of possible values (in this case 3 for each, the letter + its substitutes).
The complexity is exponential but I don't believe we can improve on it since we are required to generate n^m output strings.
import java.util.HashMap;
import java.util.ArrayList;
public class Substitutes {
private static HashMap<String,ArrayList<String>> substitutesMap = new HashMap<String,ArrayList<String>>();
private static void permute(String permutation, String input, int pos) {
if(pos == input.length()) {
System.out.println(permutation);
return;
}
String letter = input.substring(pos,pos+1);
ArrayList<String> substitutes = new ArrayList<String>();
substitutes.add(letter);
if(substitutesMap.get(letter) != null)
substitutes.addAll(substitutesMap.get(letter));
for(String substitute : substitutes)
permute(permutation + substitute, input, pos+1);
}
/*
* TEST HARNESS
*/
static {
ArrayList<String> f = new ArrayList<String>();
f.add("F");
f.add("4");
ArrayList<String> b = new ArrayList<String>();
b.add("B");
b.add("8");
substitutesMap.put("f", f);
substitutesMap.put("b", b);
};
public static void main(String args[]) {
permute("", "fab", 0);
}
}
Does anybody know the time complexity of this problem if "f" and "b" had a different number of substitutes?
- Barry Fruitman March 16, 2013@goutham Time complexity is always expressed in terms of input size. If we express a problem like this in terms of output it's always linear and doesn't tell us much.
This is a string/sequence problem. So in this problem, ignoring letters that aren't in the hash map (since they don't change), there are n^m combinations of possible words, where n is the number of variable positions and m is the number of possible values for each. In other words the complexity is O(n^m), which is the expected complexity of generating all sequences of length m from n items. In this case it's 2^3 = 8 words.
However if the number of possible values is different for each position (e.g if "f" had m1 substitutes and "b" had m2), I think the complexity is O(n^(max(m1,m2))) but I'm not 100% certain.
My bad. I see it now when I drill down to the question. I was looking for it on the main list.
- Barry Fruitman March 16, 2013showell30@yahoo.com We can eliminate both A and B at the same time if they don't know each other. Since they cannot both be celebs, and neither is known, they must both be non-celebs. I'm not sure if you considered this but it isn't in your original description.
This reduces the runtime but not the complexity.
(Sweet solution BTW)
I love this one. It does in one line of code what my recursive algorithm does in 9.
- Barry Fruitman March 15, 2013Thanks for the upvote.
Since all three solutions are semantically equivalent, as you pointed out, I chose #2 because a node is the ultimate return value so it made sense to implement it as such. As well, in my view k is a parameter so I made it one. I guess my solution is asymmetric because the two pertinent values are asymmetric.
I originally implemented solution #1 (but didn't post it) and viewed it as more-or-less equivalent to #3, the only difference being how the two values are returned to the caller (mutation vs. return value). I also defined a class similar to your search_result but changed it because I saw no need to combine the two values in one data structure. I believe the difference between our approaches is a matter of preference, not correctness.
I agree my K class is a little strange but I really liked the C solutions that passed a pointer to k and wanted my solution to work the same way.
My solution in Java. I created a class K to hold k since an int will not work with recursion.
Like the solutions above, it performs a reverse in-order traversal.
public class FindKthLargest {
Node kthLargest(Node root, int ik) {
// Create a new "K"
K k = new K(ik);
// Traverse the tree from largest to smallest
return reverseIOT(root, k);
}
/**
* Traverse a subtree in reverse in-order (right,node,left)
* @param node The subtree to traverse
* @param k Exit with k.k == 0
* @return The kth largest node
*/
private Node reverseIOT(Node node, K k) {
if(node == null)
return null;
Node n = reverseIOT(node.right, k);
if(n != null)
return n;
if(--k.k == 0)
return node;
return reverseIOT(node.left, k);
}
/**
* Node class as defined by problem
*/
private static class Node {
private Node(int value) {
this.value = value;
}
private final int value;
private Node left;
private Node right;
public String toString() {
return String.valueOf(value);
}
}
/**
* This class holds a mutable integer
*/
private class K {
private int k;
private K(int k) {
this.k = k;
}
}
/**
* Test harness
* @param args Ignored
*/
public static void main(String args[]) {
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
Node node7 = new Node(7);
node4.left = node2;
node4.right = node6;
node2.left = node1;
node2.right = node3;
node6.left = node5;
node6.right = node7;
FindKthLargest app = new FindKthLargest();
System.out.println(app.kthLargest(node4, 5));
}
}
@Frank is your code in Java? I don't think it will work because after traversing the right subtree k will still be equal to the value before the traversal since decrementing k in the recursion doesn't affect the caller's k. The C code equivalent works because you can pass a pointer to an int, but not in Java.
There are two ways around this in Java:
1. Make k a member of the class instead of a parameter. (worse)
2. Create a new inner class K { int k; } and pass that instead. (better)
Check out my code. It is similar to yours but uses the K structure.
Here is my Java code. DFS search, storing visiting nodes in a HashMap. Nodes must be labeled for the hash to work.
Complexity is O(|V| + |E|)
Usage:
// Build your graph. "root" is the root of the graph to be copied.
GraphClone cloner = new GraphClone(root);
Node newRoot = cloner.cloneGraph();
import java.util.HashMap;
import java.util.Map;
public class GraphClone {
private Map<String, Node> visited = new HashMap<String,Node>();
private final Node root;
public GraphClone(Node root) {
this.root = root;
}
public Node cloneGraph() {
return cloneGraph(root);
}
private Node cloneGraph(Node node) {
Node clone = visited.get(node.label);
if(clone != null)
return clone;
clone = new Node(node);
visited.put(node.label, clone);
for(int i = 0; i < node.children.length; i++) {
Node child = node.children[i];
Node childClone = cloneGraph(child);
clone.children[i] = childClone;
}
return clone;
}
public static class Node {
String label;
Node[] children;
private Node(String label) {
this.label = label;
}
private Node(Node orig) {
label = orig.label;
children = new Node[orig.children.length];
}
}
}
Nice solution but re-initializing the second array after every word will result in complexity is O(N * k), where N is the length of the dictionary and k is the length of the letter list.
However if you reinitialize by working backward through the word you just examined and incrementing (essentially reversing the decrements you just did), the complexity is only O(N).
I like your solution a lot. It's very elegant.
- Barry Fruitman March 14, 2013I believe the complexity of your solution is O(M + k) (where k is the number of letters in the original letter list) because k is not constrained to 26 since it may contain unlimited duplicates. The +k is the cost of building V[] at the beginning.
- Barry Fruitman March 14, 2013BTW the complexity is O(n + m).
- Barry Fruitman March 14, 2013Divide-and-conquer algorithms don't need to divide the problem in half each time. From chapter 4 (Divide-and-Conquer) of CLR:
"Subproblems are not necessarily constrained to being a constant fraction of the original problem size. For example, a recursive version of linear search would create just one subproblem containing only one element fewer than the original problem."
This divide-and-conquer algorithm simply pops the smaller value off the head of one of the lists and recurses on the rest of the problem.
Pseudocode:
merge_sorted_lists(list1, list2)
if(list1 and list2 are empty)
return empty list
if(list1 is empty)
return list2
else if(list2 is empty)
return list1
else if(head of list1 < head of list2)
smaller = pop head of list1
else if(head of list2 < head of list1)
smaller = pop head of list2
return smaller + merge_sorted_lists(list1, list2)
Java:
import java.util.ArrayList;
public class MaidenMerge {
public static void main(String args[]) {
// TEST HARNESS
int[] array1 = new int[] {1, 3, 5, 7, 9};
int[] array2 = new int[] {2, 4, 6, 8, 10};
ArrayList<Integer> list1 = new ArrayList<Integer>();
ArrayList<Integer> list2 = new ArrayList<Integer>();
for(int i = 0; i < array1.length; i++)
list1.add(new Integer(array1[i]));
for(int i = 0; i < array2.length; i++)
list2.add(new Integer(array2[i]));
ArrayList<Integer> merged = maiden(list1, list2);
System.out.println(merged.toString());
}
// RECURSIVE METHOD
private static ArrayList<Integer> maiden(ArrayList<Integer> list1, ArrayList<Integer> list2) {
ArrayList<Integer> result = new ArrayList<Integer>();
int smaller;
if(list1.size() == 0 && list2.size() == 0)
// Both lists are empty. This is our base case.
return result;
// Set "smaller" to the lesser of the heads of list 1 or list 2
if(list2.size() == 0) {
// List 2 is empty
return list1;
} else if(list1.size() == 0) {
// List 1 is empty
return list2;
} else if(list1.get(0) < list2.get(0)) {
// The head of list 1 is smaller than the head of list 2
smaller = list1.get(0);
list1.remove(0);
} else {
// The head of list 2 is smaller than the head of list 1
smaller = list2.get(0);
list2.remove(0);
}
// result = smaller + the recursive result of the sublists
result.add(new Integer(smaller));
result.addAll(maiden(list1, list2));
return result;
}
}
- Barry Fruitman March 14, 2013I wouldn't use a hash table because it would be difficult to get a list of appointments for a particular day, which is an important and common function of a calendar. You would have to lookup every possible hash value (there 1440 minutes in a day) which is incredibly inefficient.
Also, how would you find collisions with a hash table? You need to know the start and end of an appointment to detect collisions, and a hash table could only key on one or the other. Even if you could key on both (somehow), the start and/or end times would have to line up exactly. A hash lookup would miss a collision between a 1pm-2pm appointment and a 1:30pm-2:30pm appointment.
I've been thinking about it, and I don't think any solution that uses a binary search to find the tops and/or bottoms of discs will guarantee a worst-case complexity of O(N log N). The problem is that a binary search has a complexity of O(N) in the case where all the tops (or bottoms) overlap. Multiply this by the iteration and we have a worst-case complexity of O(N^2) for any solution that uses this approach. :(
I'm starting to think that interval trees (see below) are the way to go.
http://en.wikipedia.org/wiki/Interval_tree
@Alva0930 Can you please explain how this equals the number of overlapping discs?
int index = Arrays.binarySearch(begin, e + 0.5);
int insert = -(index + 1);
sum += (insert - i - 1);
Thanks
- Barry Fruitman March 03, 2013I agree the location of the center of the disc is irrelevant to determining overlap, but it's a useful way to index the discs for the purposes of iteration because it guarantees we can iterate in precisely O(N) time. Plus we receive the data this way.
Keeping the original list does require more space, but that is allowed by the problem.
It's possible my explanation is incorrect because it's hard to tell what the original poster was saying, but my solution is still correct. I think there is more than one correct way to iterate over of the discs...
@gen-y-s The way I read it, he's iterating on the original list sorted by center, not the new list sorted by starting point. As he goes along the first list, he searches for intersecting discs in the second list. This process should take O(N log N).
Please look below for the elaboration I wrote yesterday, based on what I think he is saying.
@Zythum42 Hash map operations only guarantee constant time with a perfect hash function and a big enough table. Worst-case is not constant, for example, if all the entries are identical.
However that is not an issue in this case (which is why I re-scratched my original argument).
I think we are making the same point, though. :)
I believe his answer implied that we only consider discs that start below the current disc (which can be determined in constant time). Considering discs above would count each intersection twice.
- Barry Fruitman February 28, 2013Re-scratch that. :) I see you're using the center as your hash key. Looks good to me.
One nitpick: Arrays.sort() uses quicksort which has a worst-case complexity of O(N^2). Replacing it with mergesort or heapsort would fix that.
Unscratch that. If you're mapping on the start or end (not the center), they can all overlap.
- Barry Fruitman February 28, 2013Scratch that. They can't ALL be overlapping since they're evenly spaced.
- Barry Fruitman February 28, 2013Unfortunately looking up discs in a hash map while iterating through the list will have worst-case time of O(N^2 log N). Consider the case where ALL the discs are overlapping: they will all be in the same bucket so each lookup will take O(N)..
I do believe your algorithm has AVERAGE performance of O(N log N), though.
You mean "works in O(n log n)" , not "O(log n)", right?
- Barry Fruitman February 28, 2013I like zyfo2's answer but it's a little terse so I'll offer my elaboration:
1. We are given a list of discs already sorted by the location of the center of disc. Create a second list of discs that is sorted by the location of the top of the disc. If we use mergesort, this operation will take O(N log N) in the worst case and O(N) space complexity in the worst case.
2. Iterate through the entire given list of discs. For every disc i, search the second list (sorted by top of disc) for the first disc whose top is located at or below the center of disc i. This is the first intersecting disk.
3. Then search for the last disc whose top is located at or above the bottom of disc i (computed as i+A[i]). This is the last intersecting disc. Both searches take O(log N) so we haven't increased the complexity.
4. The difference between the first and last disc (plus one) is the number of discs intersecting with disc i. Add this to a running total.
When we reach the end of the list, the running total will contain the solution. Note that since we are only looking for discs below disc i, we'll never count the same intersection twice.
Menlo Park (near Palo Alto)
- Barry Fruitman April 05, 2013