Las listas son una de las estructuras básicas para resolver problemas implementando algoritmos. A continuación un ejemplo del uso basico de una lista. #include <iostream> #include <list> int main () { int arrayInts[] = { 75, 23, 65, 42, 13 }; // crea una lista a partir del array std::list<int> milista (arrayInts, arrayInts + 5); milista.push_back(10); // aumenta el numero 10 a la milista. std::cout << "milista contiene:"; // crea un iterador para recorrer milista. std::list<int>::iterator it; // milista.begin() retorna un iterador apuntando al inicio de milista. // milista.end() retorna un iterador apuntando al final de milista. for (it = milista.begin(); it != milista.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; } El anterior código imprime como resultado en consola: milista contiene: 75 23 65 42 13 10 Por el momento no vimos ninguna diferencia entre una lista y un vector o array, pero las listas tienen una gran ventaja a la hora de insertar nuevos números en medio de la lista y también a hora de eliminar números en la lista. La complejidad para insertar un número es de $O(1)$ pero es necesario tener un iterador en el lugar donde necesitas insertar el número entonces si necesitas llegar desde el inicio de la lista buscando un numero en especial necesitarás $O(p)$ pasos utilizando un it++ para ir avanzando. Al igual que insertar para eliminar un valor es necesario un iterador ya que una lista no tiene índices al igual que un array pero si ya estas apuntando al nodo que necesitas eliminar entonces la complejidad será $O(1)$ #include <iostream> #include <list> #include <vector> int main () { std::list<int> mylist; std::list<int>::iterator it; // aca añadimos los valores iniciales for (int i=1; i<=5; ++i) mylist.push_back(i); // 1 2 3 4 5 // begin() retorna un puntero al primer valor ^ it = mylist.begin(); ++it; // "it" apunta al numero 2 ^ mylist.insert (it, 10); // 1 10 2 3 4 5 // "it" aun apunta al numero 2 ^ mylist.insert (it, 2, 20); // 1 10 20 20 2 3 4 5 --it; // "it" ahora apunta al segundo 20 ^ std::vector<int> myvector (2, 30); mylist.insert (it,myvector.begin(), myvector.end()); // 1 10 20 30 30 20 2 3 4 5 // ^ std::cout << "mylist contiene:"; for (it=mylist.begin(); it!=mylist.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; } El anterior código imprime lo siguiente en la consola: mylist contiene: 1 10 20 30 30 20 2 3 4 5 Cuando utilizo C++ y no recuerdo o necesito buscar algunas estructuras o funciones utilizó cplusplus.com y en este caso los ejemplos fueron una traducción de esta página. referencias: cplusplus list

Existen dos algoritmos básicos para recorrer un grafo o buscar un nodo en particular, la búsqueda por anchura o BFS y la búsqueda por profundidad o DFS. En este artículo explicaremos la búsqueda por profundidad (DFS). El algoritmo de la búsqueda por profundidad se puede hacer modificando el anterior (Parte 3.1 BFS) en la parte que usa una cola y usar una pila. Otra forma de implementarla es usando recursividad, a continuación se muestran ambos enfoques así como la rutina para hacer la búsqueda en grafos que no están completamente conectados. A continuación se presenta el listado con la implementación de la búsqueda por profundidad o DFS. También se ha añadido en la versión recursiva un contador que marca el orden en el que fueron visitados los nodos del grafo, dicho orden es muy útil al implementar otros algoritmos de grafos. Implementación DFS (usando una pila) int visitado[1000]; vector<list<int> > grafo(1000); void DFS(int v) { //v es el nodo de inicio del recorrido list<int> pila; //pila de nodos adyacentes list<int>::iterator nodo_actual, aux, fin; visitado[v] = 1; //marcar como visitado el nodo de inicio pila.push_back(v); while (!pila.empty()) { //mientras no se vacie la pila de adyacentes nodo_actual = pila.back(); //aqui podriamos marcar el orden en que se visitaron pila.pop_back(); aux = grafo[nodo_actual].begin(); // posicionar iteradores para // lista adyacente fin = grafo[nodo_actual].end(); while (aux != fin) { //recorrer todos los adyacente al nodo actual if (!visitado[*aux]) { //añadir a la pila solo los no visitados visitado[*aux] = 1; pila.push_back(*aux); //aqui podemos añadir código para hacer algo mientras //realizamos el recorrido } aux++; //avanzar al siguiente adyacente del nodo actual } } } Implementacion DFS (recursiva) int visitado[1000]; vector<list<int> > grafo(1000); void DFS(int v) { list<int>::iterator aux, fin; //iteradores para lista de ady visitado[v] = 1; //marcar como visitado //aqui se podria marcar el orden en que fueron visitados aux = grafo[v].begin(); //posicionar los iteradores para lista de ady fin = grafo[v].end(); while (aux != fin) { if (!visitado[*aux]) DFS(*aux); //no se necesita marcar porque *aux se convierte en v aux++; //avanzar al siguiente adyacente de v } } //esta es la version para grafos que no estan completamente conectados void DFS2() { int i; for (int i = 0; i < nvert; i++) //buscar un nuevo nodo de if (!visitado[i]) //inicio que no ha sido visitado DFS(i); } En esta implementación podrán ver que primero se visitan los nodos o vértices que fueron visitados al final, en este caso los números que se encuentran en la pila tienen como primer número al último que fue ingresado. Por ejemplo para el grafo de la figura si comenzamos la búsqueda por el nodo cero (0). 0. Inicio DFS(0) nodoActual = -1, pila = [0] 1. Sacamos el primer nodo de la pila nodoActual = 0, pila = [] 2. 0 visitara a DFS(1) y DFS(3) nodoActual = 0, pila = [1, 3] 3. Sacamos el primer nodo de la pila nodoActual = 3, pila = [1] 4. 3 visitara a DFS(2) y DFS(4) nodoActual = 3, pila = [1, 2, 4] 5. Sacamos el primer nodo de la pila nodoActual = 4, pila = [1, 2] 6. 4 no visita a ningun nodo nodoActual = 4, pila = [1, 2] 7. Sacamos el primer nodo de la pila nodoActual = 2, pila = [1] 8. 2 visitara a DFS(4) pero 4 ya fue visitado nodoActual = 2, pila = [1] 9. Sacamos el primer nodo de la pila nodoActual = 1, pila = [] 10. El algoritmo termina por la pila esta vacía En el caso de la implementación recursiva deberán hacerla correr con un ejemplo de grafo para poder analizar la pila, cuando las funciones se llaman recursivamente verán que no se llama a una sin que termine la última en ser llamada y a su vez esperará hasta que todas las funciones llamadas por la otra función sean terminadas. #include <iostream> #include <vector> #include <list> using namespace std; int visitado[1000]; vector<list<int> > grafo(1000); void DFS(int v) { list<int>::iterator aux, fin; //iteradores para lista de ady visitado[v] = 1; //marcar como visitado //aqui se podria marcar el orden en que fueron visitados cout << v << " fue visitado" << endl; aux = grafo[v].begin(); //posicionar los iteradores para lista de ady fin = grafo[v].end(); while (aux != fin) { // este ciclo extra esta para imprimir los siguientes nodos cout << '\t' << (*aux) << " sera visitado por " << v << endl; aux++; //avanzar al siguiente adyacente de v } aux = grafo[v].begin(); //posicionar los iteradores para lista de ady fin = grafo[v].end(); while (aux != fin) { if (!visitado[*aux]) DFS(*aux); //no se necesita marcar porque *aux se convierte en v aux++; //avanzar al siguiente adyacente de v } } int main() { // conectamos el grafo grafo[0].push_back(1); grafo[0].push_back(3); grafo[1].push_back(2); grafo[1].push_back(3); grafo[2].push_back(4); grafo[3].push_back(2); grafo[3].push_back(4); // llamamos a la funcion DFS DFS(0); } Para practicar con este tipo de busqueda puedes utlizar uno de los siguientes enlaces: HackerEarth Problems - Depth First Search CP3 - Chapter 4. Graph - Depth First Search

Existen dos algoritmos básicos para recorrer un grafo o buscar un nodo en particular, la búsqueda por anchura o BFS y la búsqueda por profundidad o DFS. En este articulo explicaremos la búsqueda por anchura (BFS). A continuación se muestra el algoritmo de la búsqueda por anchura en un grafo representado por medio de listas de adyacencias. En dicho algoritmo se usa una cola para almacenar los nodos adyacentes al actual y guardarlos para continuar con la búsqueda. La siguiente implementación del recorrido por anchura para un grafo completamente conectado (existe al menos un camino entre cualquier par de vértices en el grafo) y para un grafo que no lo esta. int visitado[1000]; vector<list<int> > grafo(1000); // algoritmo para grafo completamente conectado void BFS(int v) { // v es el nodo de inicio del recorrido list<int> cola; // cola de adyacentes list<int>::iterator nodo_actual, aux, fin; visitado[v] = 1; // marcamos como visitado el nodo de inicio cola.push_back(v); // metemos inicio a la cola while (!cola.empty()) { nodo_actual = cola.front(); // sacar nodo de la cola cola.pop_front(); aux = grafo[nodo_actual].begin(); //posicionar iteradores para //lista de ady fin = grafo[nodo_actual].end(); while (aux != fin) { // recorrer todos los nodos ady a nodo actual if (!visitado[*aux]) { // añadir a la cola solo los no visitados visitado[*aux] = 1; // marcarlos como visitados cola.push_back(*aux); // añadirlos a la cola // aqui podriamos añadir codigo para hacer algo mientras // recorremos el grafo } aux++; // avanzar al siguiente adyacente del nodo actual } } } // algoritmo para grafo que no esta completamente conectado void BFS2() { for (int i = 0; i < nvert; i++) if (!visitado[i]) BFS(i); } En esta implementación podrán ver que primero se visitan los nodos o vértices que fueron visitados primero. Por ejemplo para el grafo de la figura si comenzamos la búsqueda por el nodo cero (0). 0. Inicio BFS(0) nodoActual = -1, cola = [0] 1. Sacamos el primer nodo de la cola nodoActual = 0, cola = [] 2. 0 visitara a BFS(1) y BFS(3) nodoActual = 0, cola = [1, 3] 3. Sacamos el primer nodo de la cola nodoActual = 1, cola = [3] 4. 1 visitara a BFS(2) y BFS(3) pero 3 ya fue visitado nodoActual = 1, cola = [3, 2] 5. Sacamos el primer nodo de la cola nodoActual = 3, cola = [2] 6. 3 visitara a BFS(2) y BFS(4) pero 2 ya fue visitado nodoActual = 3, cola = [2, 4] 7. Sacamos el primer nodo de la cola nodoActual = 2, cola = [4] 8. 2 visitara a BFS(4) pero 4 ya fue visitado nodoActual = 2, cola = [4] 9. Sacamos el primer nodo de la cola nodoActual = 4, cola = [] 10. El algoritmo termina por la cola esta vacía Para practicar con este tipo de busqueda puedes utlizar uno de los siguientes enlaces: HackerEarth Problems - Breadth First Search CP3 - Chapter 4. Graph - Breadth First Search

Support opensource and earn a limited edition T-shirt Who Hacktoberfest is open to everyone in our global community! How Pull requests can be made in any GitHub-hosted repositories/projects. When You can sign up anytime between October 1 and October 31. Hacktoberfest 2018

Todos sabemos que en el desarrollo de Software no hay expertos con conocimientos completos, todo experto en su área dia a dia tiene que actualizarse estudiar nuevas tendencias, analizar nuevo código de otros expertos y sobre todo leer la nueva documentación del dia a dia. Lo que hace difícil esto es que después de leer la documentación, ver videos/tutoriales a veces no tienes con quien trabajar o ver y analizar código. En Algoritmos o Competencias de Programación aprendí que una vez que terminas de leer todo un area de teoría el siguiente paso viene a ser competir y resolver problemas intentando topar con ejercicios del area que buscas volverte experto. Es por eso que te presento una pagina conocida por muchos y con competencias en distintas tecnologías y lenguajes en el área de software donde encontrarás expertos del area compitiendo contra ti y te dara paso ha aprender muchas cosas nuevas. Lista de algunas sugerencias: TopCoder - NodeJS TopCoder - Python TopCoder - Java TopCoder - Angular TopCoder - ReactJS TopCoder - Android Si tu lenguaje o tecnología no esta listado puedes intentar usar la pagina de Challenges para buscar y filtrar lo que andas buscando: TopCoder - Challenges

Tal y como adelantamos en la Parte 1 ahora aprenderemos cómo representar los Grafos en código. Matriz de Adyacencias Con este método se tiene una matriz de tamaño $[n*n]$ donde n es el número de vértices o nodos en el Grafo. Una forma simple de ver la información guardada en dicha matriz es que los renglones de las mismas representan el origen y las columnas el destino de cada arista o arco en el Grafo. Si el grafo es no ponderado se acostumbra poner un cero en la [fila $i$, columna $j$] de la matriz cuando no existe dicho arco y un uno cuando dicho arco existe en el Grafo. En el caso de grafos ponderados, se acostumbra poner una bandera (normalmente el valor de infinito) en las posiciones donde no existe un arco y el peso correspondiente en las posiciones donde sí existe. Figura 1. Grafo No Ponderado y su Matriz de Adyacencias Debe notarse que para un grafo no dirigido la Matriz de Adyacencia es simétrica y que la diagonal principal contiene ceros. Esto puede llegar a aprovecharse para ahorrar tiempo en algunos algoritmos. La representación por medio de matriz se prefiere para algoritmos donde el número de arcos es grande en proporción al número de vértices. Si sucediera lo contrario se prefiere la representación por medio de Listas de Adyacencia. Figura 2. Digrafo Ponderado y su Matriz de Adyacencias Codigo en C++ de la Figura 1 #include <iostream> using namespace std; int main() { int n = 5; int G[n][n]; memset(G, 0, sizeof(G)); G[0][1] = G[1][0] = 1; G[1][2] = G[2][1] = 1; G[3][2] = G[2][3] = 1; for (int i = 0; i < n ; i++) { for (int j = i + 1; j < n ; j++) { if (G[i][j]) { cout << i << " esta conectado con " << j << endl; } } } } Listas de Adyacencias Para representar un Grafo mediante Listas de Adyacencias como su nombre lo indica se utiliza la estructura de datos de Listas enlazadas, para lo cual por cada vértice o nodo se crea una Lista donde se contiene a todos los vértices a los cuales podemos visitar a partir de este. Figura 3. Digrafo y su Listas de Adyacencias Codigo en C++ de la Figura 3 #include <iostream> #include <vector> #include <list> using namespace std; const int MAX_VERT = 5; vector<list<int> > grafo(MAX_VERT); bool visitado[MAX_VERT]; void inserta_arista(int i, int j){ grafo[i].push_back(j); } void limpia_grafo() { for (int i = 0; i < MAX_VERT; i++) { visitado[i] = 0; grafo[i].clear(); } } int main() { limpia_grafo(); inserta_arista(0, 1); inserta_arista(0, 3); inserta_arista(1, 2); inserta_arista(1, 3); inserta_arista(2, 4); inserta_arista(3, 2); inserta_arista(3, 4); list<int>::iterator it; for (it = grafo[3].begin(); it != grafo[3].end() ;it++) { cout << "3 puede visitar a " << (*it) << endl; } } Si buscamos representar un Digrafo Ponderados utilizando Listas de Adyacencia sera necesario utilizar una lista de pares del tipo $G[v_i] = [(v_0, w_0), (v_1, w_1), ..., (v_j, w_j) ]$ En C++ esta lista se representaria con el siguiente código: vector<list<pair<int, int> > > grafo(MAX_VERT);

Review Funny: Difficulty: Edge Cases: English: Data Structures: Math: Logic: Code Size: Recommended: Codility Challenges - List

Definicion Un grafo es la representación por medio de conjuntos de relaciones arbitrarias entre objetos. Existen dos tipos de grafos según la relación entre los objetos. Los primeros forman los grafos dirigidos o digrafos y los segundos los grafos no dirigidos o simplemente grafos. Grafo Dirigido Un grafo dirigido o dígrafo consiste de un conjunto de vértices $v \in V$ y un conjunto de arcos $E$. Los vértices se denominan como nodos, los arcos también se conocen como aristas o líneas dirigidas que representan que entre un par de vértices(nodos) existe una relación unívoca $(a-R-b)$ pero no $(b-R-a)$. De modo que los arcos se representan comúnmente por medio de pares ordenados $(a,b)$, donde se dice que $a$ es la cabeza y $b$ la cola del arco y a menudo se representa también por medio de una flecha, tal como se muestra en la siguiente figura. Grafo no dirigido Un grafo no dirigido o grafo propiamente dicho es un grafo $G=(V,E)$ donde $V \ne 0$. Al igual que un dígrafo consiste de un conjunto de vértices $V$ y un conjunto de arcos $E$. La diferencia consiste en que la existencia de $(a-R-b)$ presupone que $(b-R-a)$ también existe y además que son iguales. De este modo es indistinto hablar del arco $(a,b)$ o $(b,a)$, tampoco tiene sentido hablar de la cabeza o la cola del arco. Los grafos representan como lo indica la siguiente figura, donde los círculos representan los vértices y las líneas representan los arcos. Grafos Ponderados Grafos en donde los arcos tienen asociado algún valor en cuyo caso hablamos de grafos ponderados y ahora se representan los arcos como tripletas. Sigue existiendo la información de los vértices unidos por dicho arco además de la información del peso de dicho arco. Así pues el arco se representa como $a=(v_i,v_j,w)$ donde $(v_i, v_j)$ son el origen y destino y ($w$) es el peso respectivamente. Por lo general en computadora existen dos representaciones principales de grados de las cuales hablaremos en las siguientes lecciones (partes), siendo la más utilizada la representación mediante Arrays de Arrays (Matriz de Adyacencia $G[v_i,v_j] =w$). G[ v[i] ][ v[j] ] = w; Algunos Grafos Particulares Grafo nulo: aquel que no tiene vértices ni aristas. Nótese que algunas personas exigen que el conjunto de vértices no sea vacío en la definición de grafo. Grafo vacío: aquel que no tiene aristas. Grafo trivial: aquel que tiene un vértice y ninguna arista. Grafo simple: aquel que no posee bucles ni aristas paralelas. Grafo completo: grafo simple en el que cada par de vértices están unidos por una arista, es decir, contiene todas las posibles aristas. Grafo bipartito: sea $(W,X)$ una partición del conjunto de vértices $V$, es aquel donde cada arista tiene un vértice en $W$ y otro en $X$, este tipo de grafos es muy común en competencias de algoritmos, donde un conjunto de nodos esta en un grupo y el otro conjunto está en otro donde ningún nodo se conecta. Grafo bipartito completo: sea $(W,X)$ una partición del conjunto de vértices $V$, es aquel donde cada vértice en $W$ es adyacente sólo a cada vértice en $X$, y viceversa. Grafo plano: aquel que puede ser dibujado en el plano cartesiano sin cruce de aristas. Árbol: grafo conexo sin ciclos. Grafo rueda: grafo con n vértices que se forma conectando un único vértice a todos los vértices de un ciclo-(n-1). Grafos - Metodos de representación en computadora (Parte 2)

A continuacion algunos posts sobre Angular que Toptal compartio en su blog. Top 18 Most Common Mistakes that AngularJS Developers Make 12 Essential AngularJS Interview Questions Get Your Angular 2 On: Upgrading from 1.5 Building an Angular Video Player with Videogular Angular vs. React: Which Is Better for Web Development? Ngrx and Angular 2 Tutorial: Building a Reactive Application Working with Angular 4 Forms: Nesting and Input Validation Angular Change Detection and the OnPush Strategy How to Do JWT Authentication with an Angular 6 SPA Angular 6 Tutorial: New Features with New Power

Algunos enlaces con material sobre React que Toptal comparte. 13 Essential React.js Interview Questions 13 Essential React.js Interview Questions Toptal - React Blog Simple Data Flow in React Apps Using Flux and Backbone: A Tutorial with Examples Why I Switched from AngularJS to React React, Redux and Immutable.js: Ingredients for Efficient Web Applications Immutability in JavaScript using Redux Efficient React Components: A Guide to Optimizing React Performance Angular vs. React: Which Is Better for Web Development? Emulating React and JSX in Vanilla JS Unearthing ClojureScript for Front-end Development

10 Online Logical Reasoning Tests http://www.indiabix.com/online-test/logical-reasoning-test/

Este es mi implementación del algoritmo de inserción. vector<int> insertionSort(vector<int>data){ int n = data.size(), j, tmp; for (int i = 0; i < n; i++) { j = i; while (j > 0 && data[i] < data[j - 1]) j--; tmp = data[i]; for (int k = i; k > j; k--) data[k] = data[k - 1]; data[j] = tmp; } return data; } Como pueden ver este algoritmo no es muy diferente del Bubble Sort y es muy facil de implementar a continuación esta un ejemplo de la ejecución de este algoritmo: {18, 6, 9, 1, 4, 15, 12, 5, 6, 7, 11} { 6, 18, 9, 1, 4, 15, 12, 5, 6, 7, 11} { 6, 9, 18, 1, 4, 15, 12, 5, 6, 7, 11} { 1, 6, 9, 18, 4, 15, 12, 5, 6, 7, 11} { 1, 4, 6, 9, 18, 15, 12, 5, 6, 7, 11} { 1, 4, 6, 9, 15, 18, 12, 5, 6, 7, 11} { 1, 4, 6, 9, 12, 15, 18, 5, 6, 7, 11} { 1, 4, 5, 6, 9, 12, 15, 18, 6, 7, 11} { 1, 4, 5, 6, 6, 9, 12, 15, 18, 7, 11} { 1, 4, 5, 6, 6, 7, 9, 12, 15, 18, 11} { 1, 4, 5, 6, 6, 7, 9, 11, 12, 15, 18}

Este algoritmo es muy comun, por que es facil de implementar y ademas este puede ser utilizado con grandes cantidades de datos. Les dejo la implementación en C++. vector<int> quickSort(vector<int> data) { int n = data.size(), i; if (n <= 1) return data; int middle = data[n/2]; vector<int> left; vector<int> right; for (i = 0; i < n; i++) { if (i != n/2) { if (data[i] <= middle) left.PB(data[i]); else right.PB(data[i]); } } i = 0; left = quickSort(left); for (int j=0; j < left.size() ;j++) data[i++] = left[j]; data[i++] = middle; right = quickSort(right); for (int j=0; j < right.size() ;j++) data[i++] = right[j]; return data; } A continuación un ejemplo de como es la ejecución de este algoritmo. {18, 6, 9, 1, 4, 15, 12, 5, 6, 7, 11} // input, Array desordenado {6, 9, 1, 4, 12, 5, 6, 7, 11} {15} {18} // middle = {15} {6, 9, 1, 4, 5, 6, 7, 11} {12} {15} {18} // middle = {12} {1, 4} {5} {6, 9, 6, 7, 11} {12} {15} {18} // middle = {5} {1} {4} {5} {6} {6} {9, 7, 11} {12} {15} {18} // middle = {1} y {6} {1} {4} {5} {6} {6} {7} {9, 11} {12} {15} {18} // middle = {7} {1} {4} {5} {6} {6} {7} {9} {11} {12} {15} {18} // middle = {9}

Este algoritmo es muy rapido pero consume mucha memoria no sugiero usarlo si la cantidad de items que necesitas ordenar es mayo a 40000. A continuacion te dejo mi implementacion en C++. #include <time.h> #include <iostream> #include <stdio.h> #include <cmath> using namespace std; const int MAX = 40000; int data[MAX+1]; void mergeSort(int desde, int hasta) { if (hasta - desde <= 1) return; int middle = (desde + hasta) / 2; mergeSort(desde, middle); mergeSort(middle, hasta); int dPtr, lPtr, rPtr, result[hasta]; dPtr = lPtr = desde; rPtr = middle; while (dPtr < hasta) { if (lPtr == middle) result[dPtr++] = data[rPtr++]; else if (rPtr == hasta) result[dPtr++] = data[lPtr++]; else if (data[lPtr] < data[rPtr]) result[dPtr++] = data[lPtr++]; else result[dPtr++] = data[rPtr++]; } while (desde < hasta) data[desde++] = result[desde]; } int main() { int n; printf("Ingresar cuandos datos se ordenarann"); scanf("%d", &n); for (int i=0; i < n ; i++) data[i] = rand() % 1000000000; mergeSort(0, n); //aqui ordena el array de enteros for (int i=0; i < n ;i++) cout << data[i] << " "; } Como puedes ever el algoritmo es simple, separa las colecciones del Array hasta que los items quedan solos luego las une (Merge es Unir en ingles) pero al mezclarse los almacena en el orden correcto, este algoritmo no necesita comparar todos los elementos ya que las colecciones que necesitamos ordenar ya están ordenadas y la tarea solo es almacenarlas en orden. muy importante a la hora de crear los sub-arrays o sub-conjuntos para tener una velocidad aceptable es necesario solo pasar apuntadores o indices, si implementas este algoritmo creando nuevos Arrays en cada division tu algoritmo sera mas pesado. {18, 6, 9, 1, 4, 15, 12, 5, 6, 7, 11} // input / array desordenado {18, 6, 9, 1, 4} {15, 12, 5, 6, 7, 11} // split {18, 6} {9, 1, 4} {15, 12, 5} {6, 7, 11} // split {18} {6} {9} {1, 4} {15} {12, 5} {6} {7, 11} // split {18} {6} {9} {1} {4} {15} {12} {5} {6} {7} {11} // todos quedaron separados. {18} {6} {9} {1, 4} {15} {5, 12} {6} {7, 11} // merge {6, 18} {1, 4, 9} {5, 12, 15} {6, 7, 11} // merge {1, 4, 6, 9, 18} {5, 6, 7, 11, 12, 15} // merge {1, 4, 5, 6, 6, 7, 9, 11, 12, 15, 18} // resultado

You will understand better with wikipedia’s explanation XD. Sieve of Atkin in Wikipedia Here you have my implementation of Sieve of Atkin: const int max_n = 31625; vector<int> primes; // prime numbers bool sieve[max_n]; void sieveOfAtkin() { int N = sqrt(max_n); memset(sieve, 0, sizeof(sieve)); for (int x = 1; x <= N; x++) { for (int y = 1; y <= N; y++) { int n = (4*x*x)+(y*y); if (n <= max_n && (n % 12 == 1 || n % 12 == 5)) sieve[n] ^= true; n = (3*x*x)+(y*y); if (n <= max_n && n % 12 == 7) sieve[n] ^= true; n = (3*x*x)-(y*y); if (x > y && n <= max_n && n % 12 == 11) sieve[n] ^= true; } } sieve[2] = sieve[3] = true; primes.push_back(2); primes.push_back(3); int a; for (a = 5; a <= N; a+=2) { if (sieve[a]) { for (int i = a*a; i < max_n; i += a*a) sieve[i] = false; primes.push_back(a); } } for (; a < max_n; a+=2) if (sieve[a]) primes.PB(a); }

Para hallar el tiempo de ejecución de un programa, solo hace falta incluir algunas lineas de código. incluir librería: #include <time.h> función que retorna el tiempo del sistema operativo en mili-segundos: clock() #include <time.h> #include <iostream> using namespace std; int main() { double ini = clock(); // inicio de tu algoritmo int c = 0; for (int i = 0; i < 20000000 ; i++) { c++; } // final de tu algoritmo // imprime el tiempo que tu algoritmo tardo en ejecutar cout << "tiempo en segundos: " << double(clock()-ini)/1000.0 <<endl; } Con estas lineas podras comprender facilmente que los algoritmos y los codigos que haces no siempre son optimos, pueden tardar mucho si su complejidad algoritmica es muy alta.

Nota: si aun no sabes usar Arrays de Caracteres/Cadenas te invito a leer el siguiente enlace Arrays en C++ (basico) Problema: Super Reduced String (facil/easy) En este problema te dan una cadena a la cual tienes que ir eliminando todos los pares de caracteres que vayas encontrando, mientras aun tenga pares debes seguir reduciendo la cadena. Entrada: Una cadena s de caracteres en una linea. La cadena s solo contiene letras y la longitud es menor o igual que 100, $1 < |s| \leq 100$ Salida La cadena de caracteres sin ningún par de caracteres continuo. Ejemplo Si nos dan de entrada la siguiente cadena daacbbcdxyxy despues de ir eliminando los pares de caracteres seguidos como resultado tiene que imprimir xyxy. inicial: daacbbcdxyxy eliminacion 1: d(aa)c(bb)cdxyxy -> dccdxyxy eliminacion 2: d(cc)dxyxy -> ddxyxy eliminacion 3: (dd)xyxy -> xyxy resultado: xyxy Solucion En este problem lo único que necesitamos es recorrer la cadena e ir eliminando los caracteres continuos iguales. Para eliminar los caracteres simplemente iremos copiando la cadena antigua en una nueva pero saltandonos los caracteres iguales continuos. #include <cstdio> #include <iostream> #include <cstring> #include <fstream> using namespace std; char s[101]; char auxS[101]; int main() { gets(s); int n; bool hayMasCambios = true; while (hayMasCambios) { hayMasCambios = false; // si no existen cambios terminar ciclo n = strlen(s); // actual tamaño de s int itS = 0; for (int i = 0; i < n ; i++) { // recorrer s if (i + 1 < n) { if (s[i] == s[i + 1]) { i++; // saltar caracteres iguales continuos hayMasCambios = true; // aun es posible mas reduccion ? } else { auxS[itS++] = s[i]; // copiar caracter en posicion i, no pasa nada } } else { auxS[itS++] = s[i]; // copiar caracter en posicion i, no pasa nada } } auxS[itS] = '\0'; // aumentar 0 al final de la cadena limitando su tamaño strcpy(s, auxS); // copiar auxS -> s } if (n == 0) { cout << "Empty String\n"; } else { cout << s << "\n"; } return 0; } Enlace Original del problema: HackerRank - Super Reduced String (english)

Los Arrays son un tipo de estructura la cual puede almacenar una cantidad de datos y estos a su vez pueden ser accedidos y escritos en tiempo $O ( 1 )$ una vez se provee el index o posición. Declaracion En C++ un Array puede ser declarado de la siguiente manera: type name [elements]; Por ejemplo declarando un Array edades con espacio para 8 edades: int edades[8]; Como se puede ver el Array contiene elementos del tipo int. Asignacion $O (1)$ En C++ la asignación se posible utilizando los operadores [] (corchetes) y es necesario indicar el index/posición donde queremos asignar el valor. name[index] = valor; Por ejemplo si en nuestro Array edades queremos guardar la edad 5 en la posición 3: edades[2] = 5; Se puede ver que en vez del valor 3 indicamos el valor [2]esto es porque los Arrays en C++ comienzan en cero. A continuación tenemos una ilustración del actual Array edades para aclara esto. Lectura $O (1)$ En C++ la lectura igual está dada utilizando los mismos operadores [] (corchetes) y es necesario indicar el index/posición del cual queremos el valor. name[index] Por ejemplo si queremos imprimir el valor en la posición 3 necesitamos la siguiente linea: cout << edades[2] << endl; Cadena/Array de Caracteres Un Array en C++ puede ser declarado para contener caracteres a este tipo de Arrays se los conoce como cadenas de caracteres, pueden contener en muchos casos palabras o textos largos. Para declarar un Array con contenido o el texto existen dos formas: Declarar el Array y utilizando {} y comillas simples para cada caracter ' y no olvidar terminar la cadena con un '\0'. char nombre[] = { 'e', 'd', 'w', 'i', 'n', '\0' }; cout << nombre << endl; // imprime: edwin Tambien podemos declarar directamente utilizando comillas dobles ". char apellido[] = "guzman"; cout << apellido << endl; // imprime: guzman Algunas veces leeremos las cadenas desde teclado o desde un archivo y luego necesitaremos saber su tamaño o longitud para poder iterar entre sus valores para lo cual C++ nos provee strlen una función que retorna un entero representando el tamaño o longitud. cout << strlen(nombre) << endl; // imprime: 5 cout << strlen(apellido) << endl; // imprime: 6

En la siguiente pagina podrán encontrar información sobre arquitecturas actuales y software que necesita ser rápido, flexible y sobre todo poder escalar para abarcar una gran cantidad de usuarios simultáneamente conectados. High Scalability - Home Page

Preparing for interviews? Looking for practice? Codesignal - Home Page