algorithm - respuestas - que preguntar en una entrevista de trabajo como empleador
Posible pregunta de la entrevista: cómo encontrar todos los intervalos superpuestos (13)
No es una pregunta de entrevista per se , ya que me encontré con esto en mi proyecto, pero pensé que podría ser una pregunta decente para intervenir.
Tienes N pares de intervalos, digamos enteros. Se requiere que identifique todos los intervalos que se superponen entre sí en el tiempo O (N). Por ejemplo, si tiene
{1, 3} {12, 14} {2, 4} {13, 15} {5, 10}
la respuesta es {1, 3}, {12, 14}, {2, 4}, {13, 15}. Tenga en cuenta que no necesita agruparlos, por lo que el resultado puede ser en cualquier orden como en el ejemplo.
Acabo de arrojar O (N) tiempo porque el algoritmo KMP toma O (N) para la búsqueda de cadenas. :RE
Lo mejor que se me ocurrió y lo que estoy usando en este momento en el proyecto es O (N ^ 2). Sí, la fuerza bruta es bastante triste, pero nadie se queja, así que no la refacturaré. : P Aún así, tenía curiosidad si una mente más grande tiene una solución más elegante.
Coloque los puntos finales de los intervalos en una matriz, marcándolos como puntos iniciales o finales. Clasifíquelos rompiendo vínculos al colocar puntos finales antes de los puntos de inicio si los intervalos están cerrados, o al revés si están medio abiertos.
1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E
A continuación, repita la lista y realice un seguimiento de la cantidad de intervalos en los que nos encontramos (esto equivale a la cantidad de puntos de inicio procesados menos el número de puntos finales). Cada vez que alcanzamos un punto de inicio cuando ya estamos en un intervalo, esto significa que debemos tener intervalos superpuestos.
1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E
^ ^
overlap overlap
Podemos encontrar qué intervalos se superponen con el almacenamiento de datos junto a los puntos finales y el seguimiento de los intervalos en los que nos encontramos.
Esta es una solución O (N logN), siendo la clasificación el principal factor.
El enfoque estándar para los problemas de intervalos en la línea es clasificarlos según el punto de partida y luego caminar desde el principio hasta el final. O(n*logn) ( O(n) si ya está ordenado)
end = 0;
for (current in intervals) {
if current.start < end {
// there''s an intersection!
// ''current'' intersects with some interval before it
...
}
end = max(end, current.end)
}
Esta es una implementación O(N*log(N)) simple en Python:
def overlapping(intervals):
last = (-1, -1)
overlapping = set()
for curr in sorted(intervals, key=lambda p: p[0]):
if curr[0] < last[1]:
overlapping.add(curr)
overlapping.add(last)
last = max(curr, last, key=lambda p: p[1])
return list(overlapping - set((-1, -1)))
print overlapping([(1, 3), (12, 14), (2, 4), (13, 15), (5, 10)])
#=> [(1, 3), (13, 15), (2, 4), (12, 14)]
Primero, ordena los intervalos al finalizar el tiempo, que para cada intervalo compara el tiempo inicial con el mayor tiempo de finalización encontrado, y si es más pequeño significa que hay una superposición.
La parte de clasificación es la que requiere más tiempo, por lo que la complejidad final es N*log(N) .
Este problema se puede reducir al problema de exclusividad del elemento.
La unicidad del elemento tiene un límite inferior Omega (n log n) (contando el número de comparaciones), por lo que no se puede hacer nada mejor que eso.
Ha pasado bastante tiempo desde que lo utilicé, pero la solución que utilicé fue un derivado del árbol rojo-negro descrito en Introducción a los Algoritmos llamado árbol de intervalos. Es un árbol ordenado por inicio de intervalo, por lo que puede buscar rápidamente (búsqueda binaria) primero el primer nodo elegible. IIRC, los nodos fueron ordenados por una propiedad que le permite dejar de "caminar" el árbol cuando los nodos candidatos no coinciden con su intervalo. Entonces creo que fue O (m) búsqueda, donde m es el número de intervalos coincidentes.
La búsqueda encontró esta implementación .
Brett
[edit] Releyendo la pregunta, esto no es lo que preguntaste. Creo que esta es la mejor implementación cuando tiene una lista de reuniones (por ejemplo) ya programadas en las salas de conferencias (que se agregan al árbol) y desea encontrar las salas que todavía están disponibles para una reunión con un nuevo inicio y duración (el término de búsqueda). Esperemos que esta solución tenga cierta relevancia, sin embargo.
Implementación en C ++ utilizando un algoritmo de línea de barrido ( O(N log N) ):
#include <algorithm>
#include <iostream>
#include <set>
#include <tuple>
#include <vector>
struct Interval
{
double start;
double end;
};
//-----------------------------------------------------------------------------
// Enum to qualify event: Start/End of "segment-line"
enum class EIntervalState
{
Start,
End
};
//-----------------------------------------------------------------------------
// Events used for collision detection
struct Event
{
double pos;
EIntervalState state;
std::size_t id;
};
//-----------------------------------------------------------------------------
// Comparator to use if {1, 2} and {2, 3} should overlap
class LessIncludeLimit
{
public:
bool operator()(const Event& lhs, const Event& rhs) const
{
return std::tie(lhs.pos, lhs.state) < std::tie(rhs.pos, rhs.state);
}
};
//-----------------------------------------------------------------------------
// Comparator to use if {1, 2} and {2, 3} should not overlap
class LessExcludeLimit
{
public:
bool operator()(const Event& lhs, const Event& rhs) const
{
return std::tie(lhs.pos, rhs.state) < std::tie(rhs.pos, lhs.state);
}
};
//-----------------------------------------------------------------------------
std::vector<Event> MakeEvents(const std::vector<Interval>& intervals)
{
std::vector<Event> res;
std::size_t id = 0;
for (const auto& interval : intervals)
{
res.push_back({interval.start, EIntervalState::Start, id});
res.push_back({interval.end, EIntervalState::End, id});
++id;
}
return res;
}
//-----------------------------------------------------------------------------
template <typename Less>
std::vector<std::pair<std::size_t, std::size_t>>
ComputeOverlappingIntervals(std::vector<Event>&& events, Less less)
{
std::sort(events.begin(), events.end(), less);
std::set<std::size_t> activeIds;
std::vector<std::pair<std::size_t, std::size_t>> res;
for (const auto& event : events)
{
switch (event.state)
{
case EIntervalState::Start:
{
for (const auto& id : activeIds)
{
res.emplace_back(std::minmax(event.id, id));
}
activeIds.emplace(event.id);
break;
}
case EIntervalState::End:
{
activeIds.erase(event.id);
break;
}
}
}
return res;
}
Y úsala:
int main()
{
const std::vector<Interval> intervals = {
{1, 3},
{12, 14},
{2, 4},
{13, 15},
{5, 10}
};
for (const auto& p : ComputeOverlappingIntervals(MakeEvents(intervals),
LessExcludeLimit{})) {
std::cout << "intervals " << p.first << " and " << p.second << " overlap/n";
}
}
No estoy seguro acerca de O (N), pero qué pasa si primero los clasificamos por el primer número en cada tupla, y luego encontramos secuencialmente aquellos en los que el primer número de la tupla es mayor que el del mayor número visto en las tuplas anteriores, que también lo hacen no se superponen con la siguiente tupla.
Entonces, primero obtendrías:
{1, 3}, {2,4}, {5, 10}, {12, 14}, {13, 15}
ya que 4 (más grande) <5 y 10 <12, {5, 10} están aislados.
Esto implicaría que hacemos un seguimiento del número más grande que encontramos, y cada vez que encontramos una tupla cuyo número de inicio es mayor, verificamos si se superpone con el siguiente.
Esto se vuelve dependiente de la eficiencia del algoritmo de clasificación, porque el último proceso sería O (N)
Ordenar los intervalos por punto de inicio. Luego doble sobre esta lista, fusionando cada intervalo con su vecino (es decir, (1,4), (2,6) -> (1,6)) si se superponen. La lista resultante contiene esos intervalos sin socios superpuestos. Filtra estos fuera de la lista original.
Esto es lineal en el tiempo después de la operación de clasificación inicial que podría hacerse con cualquier algoritmo (n log n). No estoy seguro de cómo te las arreglarías. Incluso la operación ''filtrar duplicados'' al final es lineal si aprovecha el orden ya ordenado de la entrada y salida de la primera operación.
Aquí hay una implementación en Haskell:
-- Given a list of intervals, select those which overlap with at least one other inteval in the set.
import Data.List
type Interval = (Integer, Integer)
overlap (a1,b1)(a2,b2) | b1 < a2 = False
| b2 < a1 = False
| otherwise = True
mergeIntervals (a1,b1)(a2,b2) = (min a1 a2, max b1 b2)
sortIntervals::[Interval]->[Interval]
sortIntervals = sortBy (/(a1,b1)(a2,b2)->(compare a1 a2))
sortedDifference::[Interval]->[Interval]->[Interval]
sortedDifference [] _ = []
sortedDifference x [] = x
sortedDifference (x:xs)(y:ys) | x == y = sortedDifference xs ys
| x < y = x:(sortedDifference xs (y:ys))
| y < x = sortedDifference (x:xs) ys
groupIntervals::[Interval]->[Interval]
groupIntervals = foldr couldCombine []
where couldCombine next [] = [next]
couldCombine next (x:xs) | overlap next x = (mergeIntervals x next):xs
| otherwise = next:x:xs
findOverlapped::[Interval]->[Interval]
findOverlapped intervals = sortedDifference sorted (groupIntervals sorted)
where sorted = sortIntervals intervals
sample = [(1,3),(12,14),(2,4),(13,15),(5,10)]
Puede revisar la lista una vez y mantener una tabla hash de todos los intervalos encontrados hasta el momento. Si un intervalo de entrada es parte de algún intervalo de la tabla hash, combínelo en el intervalo de la tabla hash. Marque los intervalos no primitivos (intervalos combinados que consisten en más de un intervalo).
Luego revisa la lista por segunda vez, y para cada intervalo, compruebe en la tabla hash si está contenida en un intervalo combinado o no.
No sé si es O (N), pero es mucho mejor que O (N ^ 2).
Si N pares de intervalos son enteros, entonces podemos obtenerlo en O (n).
Ordenarlo por el primer número del par y luego el segundo número. Si todos son enteros, podemos usar el ordenamiento del cubo o la clasificación del radix para obtenerlo por O (n).
{1, 3}, {2,4}, {5, 10}, {12, 14}, {13, 15}
Luego combine uno por uno,
{1,3}
{1,4} con superposición {1,3} y {2,4}
{1,4}, {5,10}
{1,4}, {5,10}, {12,14}
{1,4}, {5,10}, {12,15} con superposición {12,14} y {13,15}
La combinación tomaría O (N) tiempo
Supongamos que la diferencia entre los puntos de inicio y final es pequeña, digamos <32. ej. 1..32. Entonces cada intervalo se puede escribir como un patrón de bits en una palabra de 32 bits. por ejemplo [1, 2] -> 001; [2, 3]-> 010; [1, 3] -> 011; [2, 3, 4] -> 110 [1, 2] -> 001; [2, 3]-> 010; [1, 3] -> 011; [2, 3, 4] -> 110 [1, 2] -> 001; [2, 3]-> 010; [1, 3] -> 011; [2, 3, 4] -> 110 . Dos intervalos, o combinaciones de intervalos, se superponen si su AND bit no es cero. p.ej. [1,2] superpone [1,3] porque 001&011 == 001 , distinto de cero. O (n) alg es mantener un funcionamiento en bits OR de intervalos vistos hasta ahora y AND cada uno nuevo:
bitsSoFar = 0
for (n=0; n < bitPatterns.length; n++)
if (bitPatterns[n] & bitsSoFar != 0)
// overlap of bitPatterns[n] with an earlier pattern
bitsSoFar |= bitPatterns[n]
A la izquierda como ejercicio:
modificar el algoritmo para identificar también la superposición de un patrón de bits con uno posterior
resolver el patrón de bits para un intervalo en O (1)
int find_no_overlapping_intervals(const vector< pair<int, int>& a)
{
// a[i].first -> X ,a[i].second->Y
// sort by start time
sort.begin(a.begin(), a.end());
// maintain <end-time, its frequency> in m
map<int, int> m; // i
// for each point, we know its a[i].X >= a[0].X. ....a[i-1].X
// there will be overlap, if for some j < i, a[j].Y >= a[i].X
// lower_bound to find this.. it can be found in O(log(n)) as we use std::map for maintaining y
int ans = 0;
for (int i=0; i < a.begin(); i++)
{
auto sit = m.lower_bound(m.begin(), m.end(), a[i].first);
auto eit = m.upper_bound(m.begin(), m.end(), a[i].first);
for (auto it = sit; it != eit; it++)
ans += it->second;
m[a[i].second]++;
}
return ans;
}
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
ArrayList<Interval> res = new ArrayList<Interval>();
if (intervals == null || intervals.isEmpty())
return res;
Comparator<Interval> comparator = new Comparator<Interval>() {
@Override
public int compare(Interval i1, Interval i2) {
if (i1.start < i2.start)
return -1;
else if (i1.start > i2.start)
return 1;
else {
if (i1.end < i2.end)
return -1;
else if (i1.end > i2.end)
return 1;
else
return 0;
}
}
};
Collections.sort(intervals, comparator);
for (int i = 0; i < intervals.size(); i++) {
Interval cur = intervals.get(i);
if (res.isEmpty()) {
res.add(cur);
} else {
Interval last = res.get(res.size() - 1);
if (last.end >= cur.start) {
last.end = Math.max(last.end, cur.end);
} else {
res.add(cur);
}
}
}
return res;
}