Google Interview Report
- 0of 0 votes
AnswerThe topic is to design a data structure to store employee relationships.
- ajay.raj December 01, 2017 in United States
For example, A is B's direct manager, there is an operation is "" set_manager "," A "," B ">.
For example, B is a colleague of C <"set_peer", "B", "C">
At this point, we do this with <query_manager "," A "," B "> and we get True, which means that A is B's manager (either direct or indirect).
This is true if we have <"query_manager", "A", "C">, because C is a coworker for B, so A is also C's manager. That is, there is a transitive relationship between colleagues.
Follow up, such as query <"query_manager", "A", "D"> (D this person has not been initialized), what to do. Conflict how to do
For example, A is a direct manager of B, E is a direct manager of C, which is set_peer (B, C), there will be conflicts, B and C direct manager should be the same person,
E and A are two people, there are contradictions here.| Report Duplicate | Flag | PURGE
Google Java Developer - 0of 0 votes
Answergiven a dictionary, output the longest List <String>. The result of a String is the previous String add a character at any position.
- ajay.raj December 01, 2017 in United States
example: {i, in, ing, sing, sting, string}| Report Duplicate | Flag | PURGE
Google Java Developer - 0of 0 votes
AnswersFind a “local minimum” in a binary tree
- ajay.raj December 01, 2017 in United States
a local min is a node whose value is smaller than that of any other nodes that are connected to it| Report Duplicate | Flag | PURGE
Google Java Developer - 0of 0 votes
Answers1. merge intervals with value
- ajay.raj December 01, 2017 in United States
PD: there are a series of continuous intervals, and each interval has a value. Initially, the ith
interval is (i - 1, i - 1), merge these intervals and return the result.
Merge Rule:
a. We can only merge the ith interval with i-1 th or i + 1 interval. The value of new interval is the
mean of these two original intervals.
b. Define cost as absolute difference of two neighboring intervals,
every time merge two intervals with the smallest cost.
c. If the smallest cost exceeds a threshold t, then stop.
d. There may be multiple valid result, just return one.
for example:
value: 3 7 6 5 1
intervals: (0,0) (1,1) (2,2) (3,3) (4,4)
threshold: t = 2
first iteration:
min cost = |7 - 6| = 1, notice that |6 - 5| is also okay.
after merging:
value: 3 6.5 5 1
intervals: (0,0) (1,2) (3,3) (4,4)
second iteration:
min cost = |6.5 - 5| = 0.5
after merging:
value: 3 5.75 1
intervals: (0,0) (1,3) (4,4)
second iteration:
min cost = |3 - 5.75| = 2.75 > t = 2, stop
return [(0,0), (1,3), (4,4)]| Report Duplicate | Flag | PURGE
Google Java Developer