Bueno, suponga que le dan el siguiente problema:

Tiene una lista desordenada de números de tamaño N; Cada elemento puede estar entre 0 y N. Le preguntan cual es la forma más rápida de saber si dicha lista tiene elementos duplicados, utilizando la menor cantidad de memoria posible y en un tiempo constante.

¿Como lo resolvería usted?

Usted podría comenzar resolviendo este problema contando cuantas ocurrencias de cada número aparecen en la lista. Para ello podría guardarlas en un arreglo asociativo (HashMap) el cual tiene tiempo de accesso constante. Pero el problema es que si usted tiene muchisimos números repetidos, entonces va a gastar memoria que jode…

Bueno, si alguna vez usted vió corrimiento de bits ala izquierda y mascaras de bits (en la ULA yo lo aprendí a hacer en una materia que se llama sistemas lógicos ) entonces vera que el algoritmo se puede simplificar bastante simplemente dandole una mascara distinta a cada número, guardandolos a todos en una variable entera. Si recuerda bien, cada vez que corremos un bit a la izquierda es como si estuvieramos elevando a la n dicho número, donde n es la cantidad de bits que corremos a la izquierda.

¿Fumado? Si, pero el concepto es muy arrecho

OK, no siga leyendo, pienselo un rato y vaya al frente de su computadora.

¿Ya terminó?, Veamos entonces el código en Java:

   1:/**   2: * You are given a list of numbers from 0..N; Each element on the array has   3: * a number that goes from 0..N. Find if the array has any duplicates on it.   4: * Well, for this problem I'm going to assume that CPU power is not an issue   5: * but storage space. Also will try to keep access to the list to the minimun.   6: *   7: * @author Jose V Nunez Zuleta   8: * @version 0.1 - 02/28/2005   9: * License: GPL  10: * Blog: El Angel Negro - http://elangelnegro.blogspot.com  11: */  12:public class ArrayDuplicate {  13:      14:        /**  15:         * So the idea is to count how many ocurrences of the number appears.  16:         * We have to scan the whole list in order to find duplicates, so the  17:         * worst case is log(n). We will use the fact that each number can be  18:         * stored as a mask of bits, and based on the position from 0 to N we   19:         * can have each number as f(n)=2^(n-1). We are only interested to see   20:         * if there is a duplicate, so we don't really care about the real number  21:         * of duplicates.  22:         *  23:         * @param args - List of unsorted numbers  24:         * @throws Exception if the numbers are invalid  25:         * @since 0.1  26:         */  27:        public static void main(String [] args) throws Exception {  28:                if (args == null) {  29:                        throw new  30:                                IllegalArgumentException("Provide some numbers");  31:                }  32:              33:                if (args.length == 0) {  34:                        throw new  35:                                IllegalArgumentException("Provide some numbers");  36:                }  37:                int len = args.length;  38:              39:                int num = 0;  40:                int checksum = 0;  41:                for (int i = 0; i < len; i++) {  42:                        num = Integer.parseInt(args[i]);  43:                        int mask = numMask(num);  44:                        // This number is not on the list, so add it!  45:                        if ( (checksum & mask) == 0 ) {  46:                                checksum |= mask;  47:                        } else {  48:                                System.out.println("Found first duplicate: "  49:                                        + num);  50:                                        break;  51:                        }  52:                }  53:        }  54:      55:        /**  56:         * f(n)=2^(n-1)  57:         * @param number  58:         * @return int  59:         */  60:        public static int numMask(int number) {  61:                return 1 << number;  62:        }  63:      64:}

Una corrida de ejemplo:

[josevnz@localhost Arrays]$ javac ArrayDuplicate.java -d .
[josevnz@localhost Arrays]$ java ArrayDuplicate 2 3 5 8 7 8 90
Found first duplicate: 8
[josevnz@localhost Arrays]$ java ArrayDuplicate 2 3 5 100 7 8 90 2
Found first duplicate: 2
[josevnz@localhost Arrays]$ java ArrayDuplicate 2 3 5 100 7 8 90 0
[josevnz@localhost Arrays]$

Puede bajarse el código desde acá.

¿Se le ocurre otra idea de como ver si hay duplicados?

Sin categoría

Les tengo un problemita: Suponga que a usted le dan una secuencia desordenada de números (un arreglo de enteros), desde el 1 hasta el 1000, con uno de ellos perdido en la secuencia. Le piden (si, siempre alguien le pide algo ) que diga que número está perdido. Obviamente puede utilizar la computadora, pero tiene una restricción: No puede crear estructura de datos adicionales, como por ejemplo la lista de números ordenada para buscar el número perdido.

¿Piensa que es inútil?. Pienselo otra vez, esto lo preguntan en entrevistas de vez en cuando y no es tan dificil de resolver.

Una pista: Una forma de resolverlo sería marcar que números están en la secuencia, para luego volver a revisar (esta vez contando desde 1 hasta 1000) y así ver quien falta. Sin embargo esto es muy ineficiente ya que hay que contar dos veces, además de hay que almacenar que números fueron visitados.
Pista dos: Empiece con una lista más pequeña, a ver si logra obtener un algoritmo.

No siga leyendo, pienselo un poco más…

OK, ya se rindio. Que chimbo . Bueno, la solución es simple: Usted puede saber cual es la suma teorica de todos los números de 1 hasta 1000, y si usted suma la secuencia que le dieron y resta ambas sumas entonces allí está su número. Para optimizar más el algoritmo, usted puede calcular la suma de una secuencia conocida con la siguente formula:

suma = n(n+1)/2, donde n es el número más grande de la secuencia.

Así, para n=1000 tenemos que suma = 500000.

Aqui le dejo un pedazo de código en Java (la lógica es la misma en cualquier lenguaje):

   1:/**   2: * This program shows how to find a missing number on a sequence of numbers   3: * @author Jose V Nunez   4: * @version 0.1 - 02/27/2005   5: * License: GPL   6: * Blog: El Angel Negro - http://elangelnegro.blogspot.com   7: */   8:   9:import java.util.Random;  10:import java.util.ArrayList;  11:  12:public class FindNumber {  13:      14:        public static final int MAX_NUMBERS = 1000;  15:  16:        /**  17:         * Command line processing  18:         * @param args - ignored  19:         * @throw Throwable  20:         */  21:        public static final void main(String [] args) throws Throwable {  22:              23:                Random ran = new Random();  24:                Integer [] numbers = null;  25:                ArrayList list = new java.util.ArrayList(MAX_NUMBERS);  26:                // Get a list of unique random numbers  27:                for (int i=0; i < MAX_NUMBERS - 1; i++) {  28:                        while (true) {  29:                                Integer num = new Integer(  30:                                        ran.nextInt(MAX_NUMBERS) + 1);  31:                                if (! list.contains(num)) {  32:                                        list.add(num);  33:                                        break;  34:                                }  35:                        }  36:                }  37:                System.out.println(list);  38:                long teorSum = (MAX_NUMBERS * (MAX_NUMBERS + 1)) / 2;  39:                long realSum = 0;  40:                numbers = (Integer []) list.toArray(new Integer[0]);  41:                // Now get the sum of the real sequence  42:                int len = numbers.length;  43:                for (int i = 0; i < len ; i++) {  44:                        realSum += numbers[i].intValue();  45:                }  46:                System.out.println("The missing number is: " +  47:                        (teorSum - realSum) );  48:      49:        }  50:}

Por ejemplo, para revizar una lista de 10 números:

[josevnz@localhost test]$ javac FindNumber.java -d .
[josevnz@localhost test]$ java FindNumber
[1, 5, 10, 6, 9, 7, 4, 2, 8]
The missing number is: 3
[josevnz@localhost test]$

Y puede bajarse el código de aqui.

Sin categoría

Bueno, creo que logré arrechar a la comunidad PHP de Venezuela . El pana Topocho se declaró mi nemesis y FastOnion ya contrato un par de sicarios expertos en Gentoo para liquidarme, así que he decidido mostrarles más información de lo bueno que se puede hacer en PHP como una muestra de buena voluntad (y para salvar el pellejo ).

Para empezar, hay muchisimos recursos en la web, por ejemplo IBM está dandole muchisimo soporte a PHP, el sitio de Oreilly ONLAMP tiene tutoriales que da miedo con un enfoque pragmático. Yo (y lo admito sin culpa) he sido usuario de buenas aplicaciones escritas en PHP como Tutos en la compañia en la cual trabajo.

Así que bueno, al final no importa como se haga el trabajo, lo importante es que se haga y sobre todo que se aprenda en el proceso. Creo que ahora puedo moverme a otro tópico como echarle tierra a otras distribuciones de Linux, como Gentoo

Sin categoría

Si, todos lo sentimos,…. una fuerte conmoción en la fuerza, miles de gritos en dolor y luego…, silencio.

Sólo que esta vez no fué la estrella de la muerte la que lo ocasiono, sino miles de desarrolladores de Java arrechos por los comentarios de IBM acerca de su desilusión con Java y su soporte hacia PHP.

Leyendo los posts de el sitio web “theserverside”, me encontré con un post bastante provocador que decía lo siguiente:

PHP vs JSP
Posted by: Nikolay Kolev on February 25, 2005 in response to Message #158728 5 replies in this thread
For simple projects, PHP is way more productive… if you don’t take into account the conversion of PHP to J2EE/.NET later, if you want a truly scalable platform. Truly scalable from not only from an operational, but primarily from a development point of view.

My personal opinion is that PHP is so attractive, because:
- hosting is cheap;
- it’s easy to learn;
- PHP talent is much cheaper;
- integration w/ MySQL is easy;
- there are huge libraries of standard functions for virtually everything a web app might need;
- out of the box PHP has much more stuff already built-in, compared to Tomcat, for example;
- even if PHP is a scripting language, the libraries are compiled native code, which helps the performance and also makes it much easier to integrate with legacy C/C++;
- there is so much more sample code online compared to Java;
- there are numerous advantages of a pure scripting weakly-typed language versus a compiled one;

There could be other advantages, these are just few of the ones that came to my mind.

I’m personally a big fan of Java and will always recommend it, but honestly it’s hard to convince people that Java is better even for small and mid-size projects.

I remember a few months ago Sun saying that they will integrate PHP into the Java platform, if I’m not wrong. I personally can’t see this happening soon though, because PHP’s value is not in it’s scripting engine, it is in its libraries. From a pure scripting language, I don’t think that PHP is better than JavaScript (especially compared to the new JavaScript versions).

According to the live edits of JSP – it is possible with Java, yes. I am personally using it and Java IDEs such as JBuilder make it effortless.

Como siempre es un problema de percepción, en particular creo que si Sun ofreciera un traductor de PHP -> Java quizas esa impedancia podría ser vencida; Pero en mi opinión es más un problema de percepción que de implementación en como Java maneja la construcción de aplicaciones web.

Yo les voy a dejar una anecdota de cuando yo trabajé en un sitio al que llamaré ‘la empresa‘, y de como fué nuestra experiencia con Perl, ColdFusion y luego Java.

Cuando me uní a la ‘empresa’ ya habia algo de código en Perl pero casi todo se desarrollaba en Cold Fusion (un producto de Allaire, hoy en dia Macromedia). Una monstrusidad de proceso: corría sólo en Solaris, se comia el sólo como 400MB de RAM y se caia (bajo carga fuerte) más comunmente de lo que queriamos. El concepto de “reuso” de los desarrolladores que trabajaban allí: plantillas (templates) los cuales eran importados en cada una de las páginas. Por supuesto el código era modificado por los diseñadores gráficos, los cuales eran instruidos de no tocar ciertas etiquetas de HTML.

Nos tocó hacer un nuevo proyecto y por razones de desempeño no pidíamos correrlo en la misma máquina en donde estaba el motor de ColdFusion (ya dos sitios web corrían allí). También queriamos reusar unos pequeños modulos escritos en Perl, así que el sitio se hizo en CGI usando el módulo de CGI y DBD::Oracle. El código era elegante y… una pesadilla para mantener ya que la presentación estaba dentro de el script (los desarrolladores fueron forzados a cortar y pegar HTML dentro de código en Perl). Luego vinieron los problemas de desempeño: Cuando el sitio llegaba a tener cierno nivel de usuarios, simplemente los tiempos de respuesta subian hasta el infinito. Oracle se quejaba de no poder abrir más conexiones.

Al final el motor de búsqueda fué reescrito en ColdFusion, el cual si tenía una piscina de conexiones. Perl fracasó en la tarea y nunca más lo usamos para otra cosa que herramientas internas de la compañia.

Otro nuevo projecto apareció en el mapa; Ya el grupo contaba con un par de desarrolladores con experiencia en Java y de verdad queríamos movernos a un lenguaje que nos permitiera cambiar de motor de servlets en el futuro, mientras manteniamos el código (ya estabamos ladillados de ColdFusion con todos sus peos, además de que estabamos casados con Allaire). Tomcat estaba aún en beta, así que decidimos usar JRUN de Allaire (ironicamente).

La migración no fué fácil: La mayoría de los desarrolladores no estaban acostumbrados al paradigma de objetos, además de que ahora habia que compilar ciertas partes de el proyecto (servlets) y sintaxis nueva con los JSP. Tuvimos problemas de escalabilidad con las conexiones de base de datos (hasta que aprendimos como usar un ‘connection pool’ con JNDI, después de desechar nuestra propia implementación, peos de concurrencia y un bug maldito de JRUN el cual clavava al servidor después de una hora. Pero al tiempo todo el mundo se acostumbro a la nueva forma de trabajar, aunque no hubo tiempo de probar otras cosas como ‘tag libraries’ o unit testing con ‘junit’.

Como puede ver, sólo cambie el nombre de ‘ColdFusion‘ por PHP y se hará una idea de lo que quiero decir. Si bien todos los cambios de paradigmas duelen, al final traen buenos resultados.

Sin categoría

Uno de mis compañeros de trabajo de la oficina (el pana Balaji) de Madras, India, me trajo unos suculentos dulces enviados por otro de los administradores (Sadiq). Simplemente muy buenos, y una faena de trabajo ya que el pana los cargo consigo por 17 horas (eso es lo que se toma desde la India Madras hasta USA en NY).

Para darles un poco de envidia, aqui la foto, antes de sean devorados sin misericordia por este humilde servidor:

(Dulces Indues)

Sin categoría

IBM ha declarado que está decepcionado de como Java es muy dificil de usar y que ahora va a soportar a PHP en sus productos; Si bien estas son muy buenas noticias para todos los desarrolladores de PHP, eso significa también que Sun debe pensar mucho má seriamente en como simplificar sus herramientas de programación, tal y como lo ha hecho PHP.

Ojo, esto no significa que haya cambiado mi postura con respecto a PHP; Aún pienso que mezclar lógica con presentación es un error pero por otro lado quizas JSP podría ser un poco más amigable, al menos para las tareas más básicas a las que programadores casuales están más acostumbrados.

A la final como decía el pana FastOnion, “cada programador hace de su código un chiquero“…

Sin categoría

¿Como intercambiar el contenido de dos variables enteras, si usar una variable intermedia? Bueno, este es más un rompecabezas de programación que un problema real.

Usando una variable intermedia, usted haría algo así:

x=99
y=20
aux=x
x=y
y=aux

Le doy una pista: Usted está sólo hablando de intercambiar dos números, así que no se ponga a pensar en ‘punteros’ en C o referencias en Perl o en algo similar.

No sea perezoso, pienselo por 5 minutos, no es tan difícil (bueno, asi se ven todos los problemas una vez resueltos ).

Esta es la solución, implementada en JAVA:

   1:/**   2: * This program shows how to swap to integers without using a temp variable.   3: * It doesn't consider overflows.   4: * @author Jose V Nunez Z   5: * Blog: El Angel Negro: http://elangelnegro.blogspot.com   6: * License: GPL   7: */   8:public class SwapInt {   9:        /**  10:         * Swap two integer variables without using an intermediate variable  11:         * @param arg The integers. Two are expected  12:         * @throws Exception If the paramaters are wrong or missing  13:         */  14:        public static void main(String [] args) throws Exception {  15:                if (! ((args != null) && (args.length == 2)) ) {  16:                        throw new  17:                                IllegalArgumentException("Requires 2 numbers");  18:                }  19:                int x = Integer.parseInt(args[0]);  20:                int y = Integer.parseInt(args[1]);  21:                System.out.println("x = " + x + ", y = " + y);  22:                x = x + y;  23:                y = x - y;  24:                x = x - y;  25:                System.out.println("x = " + x + ", y = " + y);  26:        }  27:}

Como puede ver, el truco es sumar y restar a las variables originales. Obviamente el código tiene un problema, ya que no considera el caso de números muy grandes, lo cual puede ocasionar que la suma se salga de el rango de los números enteros (en Java siempre de 32 bits).

Una sálida de el programa:

[josevnz@XXX josevnz]$ javac SwapInt.java -d .
[josevnz@XXX josevnz]$ java SwapInt 5 3
x = 5, y = 3
x = 3, y = 5
[josevnz@XXX josevnz]$ java SwapInt -5 3
x = -5, y = 3
x = 3, y = -5
[josevnz@XXX josevnz]$ java SwapInt -5 -3
x = -5, y = -3
x = -3, y = -5
[josevnz@XXX josevnz]$

Espero le haya gustado

Sin categoría

¿Como probar que un arreglo cuadrado tiene una columna o fila llena de ceros?. Bueno, este es un problema de entrevistas, y requiere que usted quizas dibuje en papel un pequeño arreglo y lo recorra. Trate de hacerlo usando la mínima cantidad de comparaciones, y evitando crear estructura de datos adicionales.

No siga leyendo, piense un poco la solución.

Le voy a dar varias pistas:

• Las dimensiones de el arreglo son iguales (largo, ancho)
• Si la suma de una fila o columna es cero, entonces el arreglo satisface la condición.

¿Trancado aún?, bueno aqui tiene el ćodigo, la clave es moverse en una dirección constante y al mismo tiempo ir sumando las filas y columnas. Es mucho más fácil en este caso probar que hay una fila o columna con ceros que ninguna:

   1:/*   2: * This program tests if a square double array has any row or column   3: * full of zeroes   4: * @author Jose V Nunez   5: * license: GPL   6: * Blog: El Angel Negro - http://elangelnegro   7: */   8:public class SquareMatrix {   9:     10:        /**  11:         * Command line test  12:         * @param args  13:         */  14:        public static void main(String [] args) {  15:                int [][] hasZeros = {  16:                        {0, 8, 0, 3, 0},  17:                        {0, 1, 2, 0, 0},  18:                        {0, 0, 3, 0, 2},  19:                        {1, 5, 0, 6, 0},  20:                        {0, 0, 0, 0, 0}  21:                };  22:             23:                int [][] noZeros = {  24:                        {0, 8, 0, 3, 0},  25:                        {0, 1, 2, 0, 0},  26:                        {4, 0, 3, 0, 2},  27:                        {0, 5, 0, 6, 0},  28:                        {0, 0, 1, 0, 0}  29:                };  30:             31:                if (hasZero(hasZeros)) {  32:                        System.out.println("Has zeros");  33:                }  34:                if (! hasZero(noZeros)) {  35:                        System.out.println("Has no zeros");  36:                }  37:        }  38:     39:        /**  40:         * Detect if a square array has a file or row full of zeroes  41:         * @param a The double array to check  42:         * @return boolean  43:         */  44:        public static boolean hasZero(int [][] a) {  45:                boolean status = false;  46:                int rowLength = a.length;  47:                int colLength = rowLength;  48:                for (int i = 0; i < rowLength; i++) {  49:                        int colCount = 0;  50:                        int rowCount = 0;  51:                        for (int j = 0; j < colLength; j++) {  52:                                colCount += a[i][j];  53:                                rowCount += a[j][i];  54:                        }  55:                        // Count at the end of the row  56:                        if (colCount == 0 || rowCount == 0) {  57:                                status = true;  58:                                return status;  59:                        }  60:                }  61:                return status;  62:        }  63:}

Si usted lo corre, verá algo como esto:

[josevnz@localhost test]$ javac SquareMatrix.java -d .
[josevnz@localhost test]$ java SquareMatrix
Has zeros
Has no zeros
[josevnz@localhost test]$

¿Sabe de alguna manera de hacer este proceso más rápido?

Puede bajarse el código de aquí.

Sin categoría

Quise colocar unas fotos en Flicker y cual será mi sorpresa:

Sin categoría

Bueno, no me dejan de llover este tipo de correos; Ya antes en otro post anterior había tocado el punto de los problemas de seguridad relacionados con PHP. Así que ya (para pasar a otra cosa), les dejo una perla que me llegó esta tarde por correo electrónico.

Por cierto, dejando de un lado el lio de la vulnerabilidad, miren las maravillas que se pueden hacer con CURL para emular el uso de formas (se me vinieron un par de ideas a la cabeza):

Sin categoría