funk
BAN USER- 1of 1 vote
AnswersConsider an implementation of Strings consisting of an array where the first element of the array indicates the length of the String and the next elements represent the value of the ASCII characters in the String. Implement String concatenation and discuss shortcomings of this operation under this implementation of Strings.
- funk in United States for Infrastructure| Report Duplicate | Flag | PURGE
Facebook Software Developer - 0of 0 votes
AnswersSuppose that there exists a service to fetch Facebook posts through an interface defined by you, design the Facebook wall feed.
- funk in United States for Infrastructure| Report Duplicate | Flag | PURGE
Facebook Software Developer - 2of 2 votes
AnswersGiven an array of ints and a value X, find wether there are 3 elements in the array such that their sum is X (return true/false).
- funk in United States for Infrastructure| Report Duplicate | Flag | PURGE
Facebook Software Developer - 0of 0 votes
AnswersGiven two vectors that might be sparse, calculate their Dot product. You can assume any data structure to represent the vectors.
- funk in United States for Infrastructure| Report Duplicate | Flag | PURGE
Facebook Software Developer - 0of 0 votes
AnswersGiven a matrix of characters where '_' represents an empty space, 'T' is a tree and 'H' is a house and a coordinate of that matrix, find the sum of the minimum distances from that coordinate to each house when considering that you can move through empty spaces and houses but not through trees.
- funk in United States for Infrastructure| Report Duplicate | Flag | PURGE
Facebook Software Developer - 0of 0 votes
AnswersReverse a linked list.
- funk in United States for Infrastructure| Report Duplicate | Flag | PURGE
Facebook Software Developer - 0of 0 votes
AnswerGiven two tree nodes and the root of a tree, find the distance between both nodes in the tree.
- funk in United States for Infrastructure| Report Duplicate | Flag | PURGE
Facebook Software Developer - 0of 0 votes
AnswersGiven a String that contains parenthesis, remove the least amount of parenthesis from it such that it becomes balanced.
- funk in United States for Infrastructure| Report Duplicate | Flag | PURGE
Facebook Software Developer
Assuming the tasks need to be run in the order given, as per the example, we can keep a map to remember the last time slot where a task was executed and advance the time slot until we can execute the current task in the list. Below is the Java code for this solution.
However, there's no need to keep remembering the last time slot for a task after it's farther away than the cooldown from the current time slot, so in order to save memory and avoid collisions in the map, an alternative solution would make use of a PriorityQueue to detect when it's no longer necesary to remember a time slot and remove it from the map.
public static int timeSlots(List<Integer> tasks, int cooldown) {
if ( cooldown <= 0 ) { return tasks.size(); }
Map<Integer, Integer> lastTimeSlot = new HashMap<>();
int result = 0;
int taskIndex = 0;
while ( taskIndex < tasks.size() ) {
Integer task = tasks.get(taskIndex);
Integer last = lastTimeSlot.get(task);
if ( last == null || result - last > cooldown ) {
lastTimeSlot.put(task, result);
taskIndex++;
}
result++;
}
return result;
}
@ChrisK, you forgot to add the message to the msgQueue, other than that I think you nailed it.
Here's the Java code for the same solution.
public static void checkFast(Message[] messages) {
Map<Long, Message> msgByUserId = new HashMap<>();
Queue<Message> pq = new LinkedList<>();
for ( Message m : messages ) {
Message found = msgByUserId.get(m.getUserId());
if ( found != null && found.getTimestamp() >= (m.getTimestamp()-1000) ) {
too_fast(found, m);
}
while ( !pq.isEmpty() && pq.peek().getTimestamp() < (m.getTimestamp()-1000) ) {
Message popped = pq.poll();
/* make sure we don't remove from the map a message with same userId but different timestamp */
if ( msgByUserId.get(popped.getUserId()).equals(popped) ) {
msgByUserId.remove(popped.getUserId());
}
}
pq.offer(m);
msgByUserId.put(m.getUserId(), m);
}
}
Here's a java solution using a little bit of dynamic programming by computing a set of all the possible sums that I can find if I start in the current node and continue through any of its children. For this we add a BST in each node that will keep those values, so in the end the result will be true if 100 is in the root node's BST.
This solution assumes that a branch will be composed of a path between the root node and a leaf and doesn't need the tree to be a pyramid to find the result, that is to say that it doesn't expect every node to have the same height with it's siblings and cousins.
public static class SumNode<T> {
public T val;
public SumNode<T> left;
public SumNode<T> right;
public TreeSet<Integer> possibleSums;
public SumNode(T val) {
this.val = val;
this.possibleSums = new TreeSet<>();
}
}
private static void calcPossibleSums(SumNode<? extends Integer> node) {
if ( node != null && node.possibleSums.isEmpty() ) {
if ( node.left == null && node.right == null ) {
node.possibleSums.add(node.val);
} else {
if (node.left != null) {
calcPossibleSums(node.left);
for (Integer i : node.left.possibleSums) {
node.possibleSums.add(i + node.val);
}
}
if (node.right != null) {
calcPossibleSums(node.right);
for (Integer i : node.right.possibleSums) {
node.possibleSums.add(i + node.val);
}
}
}
}
}
public static boolean canSumTo(SumNode<? extends Integer> root, Integer sum) {
calcPossibleSums(root);
return root.possibleSums.contains(sum);
}
@ChrisK I think the only thing missing from your algorithm to be optimal would be to identify when two friends have equal positive and negative net cash flow in which case you would have them transact with each other and prevent them from going into the heaps in order to ensure that their debt would settle in a single transaction. I believe it's NP as well.
Here's my solution that does the same idea but without heaps. It appears to also not be optimal.
/**
* @param n total number of friends
* @param transactions array of 3-tuples {from, to, value}
*/
public static List<int[]> shuffleDebt(int n, int[][] transactions) {
int[][] sum = new int[n][2];
for ( int i = 0; i < n; ++i ) { sum[i][0] = i; } // identify the friends for later use
for (int[] transaction : transactions) {
int from = transaction[0];
int to = transaction[1];
int val = transaction[2];
sum[from][1] -= val;
sum[to][1] += val;
}
Arrays.sort(sum, (sum1, sum2) -> Integer.compare(sum1[1],sum2[1]));
ArrayList<int[]> result = new ArrayList<>();
int begin = 0, end = n-1;
while ( begin < end ) {
if ( sum[begin][1] == 0 ) { begin++; }
else if ( sum[end][1] == 0 ) { end--; }
else {
int val = sum[end][1] >= -sum[begin][1] ? -sum[begin][1] : sum[end][1];
result.add(new int[] {sum[begin][0], sum[end][0], val});
sum[begin][1] += val;
sum[end][1] -= val;
}
}
return result;
}
@NoOne hey, what programming language is that? I'm trying to understand the algorithm and what you're saying. If your solution is greedy then it might not be optimal, right? i.e. it might not yield the smallest set of drinks needed, but it gives a good enough solution.
Also how did you realize it was an instance of the Bin packing problem? I spent so long trying to think of a solution before realizing that I could only come up with inefficient or non-optimal algorithms; good thing you pointed it out.
This solution is O(kn) where k is the number of sets in the list and n is the size of those sets.
public static boolean isContained(Set<Integer> test, Set<Integer>[] sets) {
int total = test.size();
Map<Integer, Boolean> testMap = new HashMap<>(total);
for ( Integer i : test ) { testMap.put(i, true); }
for ( Set<Integer> s : sets ) {
int counter = 0;
for ( Integer k : s ) {
if ( testMap.get(k) != null ) {
counter++;
if ( counter >= total ) { return true; }
}
}
}
return false;
}
Here's a solution using a priority queue. Sort the input by start times, then iterate through them with the following idea: Whenever someone new joins the conference room, check who has left by now and remove them from the priority queue, then compare the size of the queue to the max value found until now.
public static int maxConcurrent(int[][] ranges) {
int res = 0;
Arrays.sort(ranges, (range1, range2) -> Integer.compare(range1[0],range2[0]));
PriorityQueue<Integer> currently = new PriorityQueue<>();
for ( int i = 0; i < ranges.length; ++i ) {
int t = ranges[i][0];
currently.offer(ranges[i][1]);
while ( !currently.isEmpty() && currently.peek() <= t ) {
currently.poll();
}
res = Math.max(res, currently.size());
}
return res;
}
Here's my Java solution, it makes a BFS going through all the discovered coordinates that are accessible remembering how many steps have been taken to get there.
public static int minDistancesSumToHouses(char[][] map, int x, int y) {
int n = map.length;
int[][] distances = new int[n][n]; // hold the min distance from (x,y) to each coordinate
for ( int i = 0; i < n; ++i ) {
for (int j = 0; j < n; ++j) {
distances[i][j] = -1; // initialize them as unreachable with distance -1
}
}
List<Coord> toVisit = new LinkedList<>(); // list of coordinates I will be visiting next iteration
toVisit.add(new Coord(x, y)); // start with the starting position (x,y)
distances[x][y] = 0; // distance to itself is 0
int level = 0; // how many steps have I walked up to this point
int result = 0; // sum of all the min distances to each house
while ( !toVisit.isEmpty() ) { // stop when there are no more points available to visit
List<Coord> newToVisit = new LinkedList<>(); // discovered coordinates that we will visit next
for ( Coord visited : toVisit ) {
int i = visited.x;
int j = visited.y;
if ( distances[i][j] < 0 ) { distances[i][j] = level; } // non visited coordinate
else { distances[i][j] = Math.min(distances[i][j], level); }
if ( 'H' == map[i][j] ) { result += distances[i][j]; } // found a house, add its distance to the result
map[i][j] = '*'; // mark the coordinate as visited
Coord left = toLeft(visited);
Coord right = toRight(visited);
Coord up = toUp(visited);
Coord down = toDown(visited);
if ( canMoveTo(map, left) ) { newToVisit.add(left); }
if ( canMoveTo(map, right) ) { newToVisit.add(right); }
if ( canMoveTo(map, up) ) { newToVisit.add(up); }
if ( canMoveTo(map, down) ) { newToVisit.add(down); }
}
level++; // at the next iteration we will have taken one more step
toVisit = newToVisit;
}
return result;
}
// can I move to the target coordinate in the map
private static boolean canMoveTo(char[][] map, Coord target) {
int n = map.length;
int x = target.x;
int y = target.y;
if ( x < 0 || x >= n || y < 0 || y >= n ) {
return false;
}
return map[x][y] != 'T' && map[x][y] != '*';
}
// move from src 1 space in a certain direction
private static Coord toLeft(Coord src) { return new Coord(src.x-1, src.y); }
private static Coord toRight(Coord src) { return new Coord(src.x+1, src.y); }
private static Coord toUp(Coord src) { return new Coord(src.x, src.y-1); }
private static Coord toDown(Coord src) { return new Coord(src.x, src.y+1); }
// convenience class to hold values x and y
private static class Coord { int x; int y; Coord(int x, int y) {this.x = x; this.y = y;}
}
- funk July 17, 2017The distance from a node to all it's adjacent nodes is always 1, dijkistra does solve the problem but all it does is a BFS search through all the nodes. If you were to program a solution using dijkistra I'd recommend skipping the algorithm to select the next node and just select any node within reach.
- funk July 17, 2017Here's the solution using binary search
/**
* a[i][0]: i-element's position in the vector
* a[i][1]: i-element's value
*/
public static int dotProduct(int[][] a, int[][] b) {
int result = 0, i = 0, j = 0;
while ( i < a.length && j < b.length ) {
if ( a[i][0] == b[j][0] ) {
result += a[i][1] * b[j][1];
i++; j++;
} else if ( a[i][0] > b[j][0] ) {
j = bsearch(b, a[i][0], j+1, b.length);
} else {
i = bsearch(a, b[j][0], i+1, a.length);
}
}
return result;
}
private static int bsearch(int[][] v, int pos, int from, int to) {
if ( to-from <= 1 ) { return from; }
int mid = (to-from)/2 + from;
if ( v[mid][0] == pos ) { return mid; }
else if ( v[mid][0] > pos ) { return bsearch(v, pos, from, mid); }
else { return bsearch(v, pos, mid+1, to); }
}
In this particular interview they didn't. I was being considered for a role at the Enterprise team and was interviewed by someone from the Infrastructure team. I collected from his feedback afterwards that he was interested in more technical details related to infrastructure rather than the responses I gave him.
I wish I could provide you more insight but I felt like I learnt little from that interview.
@sagartiwari230, yea I thought of that too, but interviewer told me I was not supposed to mess with the construction phase of the vectors because it wouldn't be reusable.
What she wanted me to arrive to (which I didn't at the time) was to use the representation that @ChrisK mentioned and then to use binary search to find the next element on each vector to multiply with each other.
@sagartiwari230 yea, that's the one. That's the solution the interviewer wanted me to reach.
When I look at that solution now I think there should be a way in which at the first step when you're sorting the array, you can also look for the three numbers at the same time that you sort, it would duplicate the number of comparisons during the sort process, but chances are you will find the answer during the sort process and if not then you can continue with steps 2 and 3 that you wrote. Thoughts?
@sagartiwari230 I like your solution a lot, which isn't among the ones that I proposed to the interviewer, however I thought you might like to know that the interviewer asked me insistently to consider a representation of the vectors where for each element you store it's position and it's value like this:
class VectorElement{ int pos; int value; }
and then to represent each vector as an array of these elements and optimize the dot product accordingly.
- funk July 05, 2017
@ChrisK, for part 2 I think that custom implementation of a binary heap with pointers to bubble up elements when rank changes would be the most efficient way of handling it, although I definitely don't think this would've been able to be implemented over a 30 mins phone interview.
- funk July 29, 2017I can also think of a solution using a Treap instead of a binary heap where you would use the entry key as the node's key and the entry's rank as the node's priority, which would allow us to do all the same operations as the heap but it would take O(2ln(n)) to update the rank of an entry by looking up a node by key and removing it, and then reinserting it with a new rank.