Algoritmo de búsqueda de unión | Conjunto 2 (Unión por rango y compresión de ruta)

En la publicación anterior , presentamos el algoritmo de búsqueda de unión y lo usamos para detectar el ciclo en un gráfico. Usamos las siguientes operaciones union() y find() para subconjuntos. C++ // Naive implementation of find int find(int parent[], int i) {     if (parent[i] == -1)         return i;     return find(parent, parent[i]); }    // … Continue reading «Algoritmo de búsqueda de unión | Conjunto 2 (Unión por rango y compresión de ruta)»

Número mínimo de bordes que se agregarán a un gráfico para satisfacer la condición dada

Dado un grafo que consta de N Nodes numerados de 0 a N – 1 y M aristas en forma de pares {a, b} , la tarea es encontrar el número mínimo de aristas que se agregarán al gráfico de manera que si existe un camino desde cualquier Node a hasta el Node b , … Continue reading «Número mínimo de bordes que se agregarán a un gráfico para satisfacer la condición dada»

Minimice el costo de conectar el gráfico conectando cualquier par de vértices que tengan un costo de al menos 0

Dado un grafo inconexo G con N vértices y M aristas y un arreglo cost[] correspondiente a cada vértice, la tarea es encontrar el costo mínimo para hacer el grafo conectando cualquier par de vértices que tengan un costo de vértices de al menos 0 y el el costo de conectar ese par de vértices … Continue reading «Minimice el costo de conectar el gráfico conectando cualquier par de vértices que tengan un costo de al menos 0»

Árbol de expansión mínimo de Kruskal usando STL en C++

Dado un gráfico ponderado, conectado y no dirigido, encuentre el árbol generador mínimo ( MST ) del gráfico utilizando el algoritmo de Kruskal . Input : Graph as an array of edges Output : Edges of MST are 6 – 7 2 – 8 5 – 6 0 – 1 2 – 5 2 – … Continue reading «Árbol de expansión mínimo de Kruskal usando STL en C++»

Encuentre la cantidad de strings que se pueden formar después de procesar las consultas Q

Dado un número N (1<=N<=2000), la tarea es encontrar las strings de números de tamaño N que se pueden obtener después de usar caracteres de ‘a’ a ‘z’ y procesando el q dado ( 1 < =q<=200000) consultas. Para cada consulta dados dos enteros L, R (0<=L<=R<=N) tales que la substring [L, R] de la … Continue reading «Encuentre la cantidad de strings que se pueden formar después de procesar las consultas Q»

El primer momento en que todos se hacen amigos

Dado un grupo de N personas, cada una con un valor de ID único de 0 a (N – 1) y una array arr[] de M elementos de la forma {U, V, tiempo} que representa que la persona U se familiarizará con la persona V en el momento dado . Digamos que la persona U … Continue reading «El primer momento en que todos se hacen amigos»

Algoritmo de ancestros comunes más bajos fuera de línea de Tarjan

Requisito previo: conceptos básicos de LCA , unión de conjuntos disjuntos por rango y compresión de ruta . Se nos da un árbol (se puede extender a un DAG) y tenemos muchas consultas de forma LCA (u, v), es decir, encontrar LCA de Nodes ‘u’ y ‘v’. Podemos realizar esas consultas en tiempo O(N + … Continue reading «Algoritmo de ancestros comunes más bajos fuera de línea de Tarjan»

Experiencia de entrevista de MakeMyTrip | Conjunto 13 (en el campus a tiempo completo)

Recientemente me entrevistaron para MakeMyTrip para el puesto de ingeniero de software a tiempo completo. Hubo en un total de 5 rondas. Primera ronda (Codificación en línea + Aptitud): En primer lugar, no espere que la interfaz en línea sea amigable. Había 3 secciones. La primera sección era aptitud, que tenía preguntas muy, muy simples, … Continue reading «Experiencia de entrevista de MakeMyTrip | Conjunto 13 (en el campus a tiempo completo)»

Estructuras de datos de conjuntos disjuntos – Part 1

Considere una situación con varias personas y las siguientes tareas que deben realizarse en ellas.  Agregue una nueva relación de amistad, es decir, una persona x se vuelve amiga de otra persona y. Averigüe si el individuo x es amigo del individuo y (amigo directo o indirecto) Ejemplo:   We are given 10 individuals say, a, … Continue reading «Estructuras de datos de conjuntos disjuntos – Part 1»

Comprobar si una string se puede convertir en otra

Dadas dos strings str y str1 , la tarea es verificar si una string se puede convertir en otra usando la siguiente operación:   Convertir toda la presencia de un personaje por un personaje diferente. Por ejemplo, si str = “abacd” y la operación es cambiar el carácter ‘a’ a ‘k’, entonces el resultado str = … Continue reading «Comprobar si una string se puede convertir en otra»