kbex07
BAN USER- 5of 5 votes
AnswersAs input, you are given two sets:
- kbex07 in United States
1) set R of n1 non-overlapping rectangles, whose sides are parallel to the x- and y-axes (ie: not rotated rectangles). Each rectangle denoted by bottom left & top right corner coordinates.
2) set P of n2 points
- let n = n1 + n2
For each point 'p' in set P, find the rectangle 'r_p' in set R that contains 'p'. If 'p' is not enclosed by any rectangle, then 'r_p' is undefined. Otherwise, 'r_p' is unique because of the non-overlapping set.
Goal: come up with a divide-and-conquer pseudocode to solve the general problem in O(n(logn)^2) time.
Asked about points that are on the edge of the rectangle, and they said it was up to me whether to include those or not, just a matter of "<" vs "<=", etc. comparisons. Because it's just pseudocode they were looking for, they were not too concerned with the actual structure of the return value, just that the D&C algorithm showed the logic.
Struggled with it for awhile and they simplified the problem to a ~special case with the constraint where all rectangles of R intersected a horizontal line 'L', and instead give a O(nlogn) algorithm to solve the same problem. I suspect this would've been a subproblem/subroutine of the more general case, but again got a bit lost.| Report Duplicate | Flag | PURGE
Facebook Algorithm - 0of 0 votes
AnswersWith a set 'S' of 'n' numbers {a(1), ... , a(n) } , determine if S contains a 4-term arithmetic sequence with:
- kbex07 in United States
a(k) = a(i) + 2(a(j) - a(i)) and a(l) = a(i) + 3(a(j) - a(i)) ; a(i) != a(j)
where the four terms are {a(i), a(j), a(k), a(l) }.
Output boolean.
Example:
Input: 31, 8, 2, 9, 5, 6, 12, 11, 20
Output: True - because {2,5,8,11}
Recruiter tried to lead me in the direction of adapting the 3SUM alg'm to get a runtime of O(n^2(logn)).| Report Duplicate | Flag | PURGE
Intern Algorithm
While technically you could use either BFS or DFS, predominantly, DFS is used to find cycles in graphs.
DFS is more memory efficient than BFS as you can backtrack sooner, and it's also easier to implement. Once DFS finds a cycle, the stack will contain the nodes forming the cycle. The same is not true for BFS, so you need to do extra work if you want to print the cycle that was found.
Another characteristic to take into account is if the graph is directed or undirected. If you're dealing with a directed graph, then you have to not just remember if you have visited a node or not, but also how you got there. Otherwise you might think you have found a cycle but in reality all you have is two separate paths A->B, but that ~doesn't mean there is a path B->A. With a DFS you can mark nodes as you descend and unmark them as you backtrack.
Some interesting Twitter lectures are on the UC Berkeley iSchool site and one titled "Detecting Twitter Trends" is one of them - an overview of the mixture of statistics and data structures that goes into computing trending topics.
- kbex07 February 11, 2013blogs*ischool*berkeley*edu/i290-abdt-s12/