Archivo de la categoría: Java

#DailyCodingProblem: El producto de todos los elementos en el arreglo menos el elemento actual

https://www.dailycodingproblem.com/

Good morning! Here’s your coding interview problem for today.

This problem was asked by Uber.

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Follow-up: what if you can’t use division?

Si ignoramos la restricción este problema es muy sencillo de resolver.

  • Iteramos el arreglo y calculamos el producto total de todos los elementos: 1 x 2 x 3 x 4 x 5 = 120
  • Iteramos nuevamente dividiendo el total entre cada uno de los elementos y guardamos esos resultados en nuevo arreglo: 120/1, 120/2, 120/3, 120/4, 120/5

La complejidad de esta solución seria O(2n) o simplemente O(n), pero debido a que el problema dice que no podemos usar la división las cosas se complican un poco mas.

Solución cuadrática

Sin usar la división la solución mas obvia es una solución cuadrática, iteramos el arreglo y por cada elemento vamos a ir acumulando el producto de esos valores menos el elemento i actual.

    int[] calculateProduct(int[] numbers) {
        int[] result = new int[numbers.length];
        // ...
        // ... logica para inicializar todos los valores de result en 1
        // ...
        for (int i = 0; i < numbers.length; i += 1) {
            for (int j = 0; j < numbers.length; j += 1) {
                if (i != j) {
                    result[j] *= numbers[i];
                }
            }
        }
        return result;
    }

Esta solución es muy fácil de entender pero no es para nada eficiente, O(n2), en la publicación anterior ya analizábamos otra solución cuadrática y veíamos que era un problema con inputs de datos muy grandes, por ejemplo un arreglo de 1000 elementos (1 millón de operaciones).

Solución en tiempo lineal con programación dinámica

Después de pensar un rato en este problema, haciendo algunas anotaciones y viendo la relación entre los indices y el producto parcial de cada uno de ellos llegue a la siguiente solución.

La primera fila son los valores del arreglo, después como si estuviéramos iterando, el valor actual es marcado en color amarillo, si pudiéramos obtener el producto acumulado de izquierda y derecha de cada uno de los elementos entonces podríamos resolver el problema multiplicándolos entre si 🙂

Ejemplo: para el obtener el resultado del 3 tendríamos que multiplicar sus valores de la izquierda que son 2 y sus valores de la derecha que son 20 dando como resultado 40.

Vamos a recorrer el arreglo por la izquierda y por la derecha guardando el producto de sus elementos, para eso necesitaremos 2 arreglos mas, left y right, podemos hacer esos recorridos en una sola iteración, después iteramos nuevamente multiplicando los valores de izquierdo y derecho de result[i].

    public static int[] calculateProduct(int[] numbers) {
        int[] result = new int[numbers.length];
        int[] left = new int[numbers.length];
        int[] right = new int[numbers.length];
        int totalLeft = 1;
        int totalRight = 1;
        int size = numbers.length - 1;
        for (int i = 0; i <= size; i += 1) {
            totalLeft *= numbers[i];
            totalRight *= numbers[size - i];
            left[i] = totalLeft;
            right[size - i] = totalRight;

        }
        for (int i = 0; i < numbers.length; i += 1) {
            if (i == 0) {
                result[i] = right[i + 1];
            } else if (i == numbers.length - 1) {
                result[i] = left[i - 1];
            } else {
                result[i] = left[i - 1] * right[i + 1];
            }
        }
        return result;
    }

La complejidad en tiempo de esta solución es O(2n) o O(n).
La complejidad en espacio de esta solución es O(3n) o O(n), (tomando en cuenta solamente los 3 nuevos arreglos que necesitamos, todas las demás variables son espacio constante).

Happy hacking 🙂

#DailyCodingProblem: Encontrar si dos números dentro de un arreglo suman K

https://www.dailycodingproblem.com/

Good morning! Here’s your coding interview problem for today.

This problem was recently asked by Google.

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

Bonus: Can you do this in one pass?

Como el problema lo indica, debemos crear una función que reciba 2 parámetros, un arreglo de números y un numero entero k, debemos buscar dentro de ese arreglo si dos elementos sumados entre si son iguales al numero k.

La solución naive para este problema seria iterar sobre los elementos del arreglo y por cada uno de ellos iterar nuevamente para ver si la suma de numbers[i] + numbers[j] da como resultado el numero k

   for (int i = 0; i < numbers.length; i += 1) {
        for (int j = 0; j < numbers.length; j += 1) {
            // evitamos la comparación de un elemento consigo mismo
            if (i != j && (numbers[i] + numbers[j]) == k) {
                return true;
            }
        }
    }

Esta solución no es muy buena ya que por cada elemento en el arreglo vamos a iterar nuevamente los datos, resultando en una complejidad O(n2) donde n es el tamaño del arreglo, imagina un arreglo de 1000 elementos, tendríamos que realizar 1 millón de operaciones.

Solución lineal para encontrar si dos números suman K

Vamos a iterar el arreglo, pero esta vez vamos a usar un HashSet para guardar información, por cada elemento:

  • Calculamos el numero que falta para completar el total k
  • Revisamos si el numero que nos falta existe en el HashSet, si es así devolvemos true (buscar elementos en un HashSet se hace en tiempo constante)
  • Si el numero que buscamos no existe entonces registramos el numero actual como “observado” en el HashSet

Si terminamos de recorrer el arreglo significa que no hay números que sumados nos den como resultado k y por lo tanto devolvemos false.

    public static boolean findSum(int[] numbers, int k) {
        HashSet<Integer> seenNumbers = new HashSet<>();
        for (int i = 0; i < numbers.length; i += 1) {
            int missing = k - numbers[i];
            if (seenNumbers.contains(missing)) {
                return true;
            }
            seenNumbers.add(numbers[i]);
        }
        return false;
    }

La complejidad en tiempo de esta solución es O(n), ya que el numero de operaciones a realizar depende directamente del tamaño del arreglo n.

La complejidad en espacio de esta solución también es O(n), el espacio o la memoria a utilizar depende directamente de lo que reciba la función, en este caso un arreglo de n elementos, utilizamos un HashSet para almacenar máximo el mismo numero de elementos y no realizamos otras operaciones que sean significativas con la memoria.

Happy hacking 🙂

Tutorial Material Design en Android #5

Crear un RecyclerView para Android

Hola lectores, ha pasado un tiempo desde que publique la última entrega del tutorial de Material Design en Android en donde aprendimos a crear un Navigation Drawer, continuamos con los tutoriales y en esta ocasión les enseñare a crear un RecyclerView.

Pero antes, ¿Que es un RecyclerView?, seguramente muchos lo abran visto ya en acción, este tipo de componente es cada vez más y más popular y ha venido remplazando a las antiguas ListViews, se trata de un componente que nos permite crear listas de contenedores que a su vez pueden tener dentro otros componentes (TextView, EditText, ImageView, etc.). El RecyclerView tiene la particularidad de haber sido diseñado con la eficiencia en mente, como su nombre lo indica los objetos que son visible en la pantalla son los que se dibujan en pantalla y una vez que desaparecen (el usuario hace scroll) estos remplazan su contenido (se reciclan) para mostrar otro tipo de información.

Imaginemos una lista de 100 contactos, en la pantalla de nuestro teléfono solo podemos renderizar 5 contactos a la vez, en lugar de renderizar los 100 desde un inicio solo vamos remplazando la información en las filas de nuestro RecyclerView conforme lo vamos necesitando, cabe decir que este es un proceso automático.

list_mail

Pero el RecyclerView es mucho más que eso, a diferencia de su predecesor con este nuevo componente podemos crear listas con diferentes tipos de layouts

20150415193645985

images

EAF-MD3

Retomamos nuestro proyecto, como les comentaba en la publicación pasada he subido el código realizado hasta el momento en el siguiente repositorio https://github.com/Alevsk/Material-design-en-Android.

Lo primero que vamos a hacer sera agregar la dependencia a nuestro proyecto en el archivo de gradle, abrimos el archivo build.gradle que se encuentra en MaterialdesignApp (proyecto)> app > build.gradle y en la parte de abajo en el apartado de dependencias agregaremos
compile ‘com.android.support:recyclerview-v7:+’ quedando de la siguiente forma

dependencies {
    compile fileTree(dir: 'libs', include: ['*.jar'])
    compile 'com.android.support:appcompat-v7:22.2.0'
    compile 'com.android.support:recyclerview-v7:22.2.0'
}

Sincronizamos gradle para descargar las dependencias (o también podemos dar re build al proyecto) y una vez tenemos la dependencia vamos a comenzar a utilizar el componente, vamos a nuestro archivo fragment_navigation_drawer.xml (aquí vamos a crear el menú), si no recuerdan donde está el archivo se encuentra en MaterialdesignApp > app > src > main > res > layout > fragment_navigation_drawer.xml

Por el momento tenemos esto, un simple texto ¿bastante simple cierto?

Capture

drawer_navigation

Al final de nuestro tutorial vamos aprender a crear algo como esto :), pues manos a la obra, o mejor dicho al codigo XD

16170261501_9b7ce86ca7_b

En nuestro archivo XML (fragment_navigation_drawer.xml) vamos a crear nuestro RecyclerView con el siguiente código, si se fijan elimine el TextView que teníamos porque ya no lo necesitamos.

<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:background="@color/grayPanel"
    tools:context="com.alevsk.materialdesignapp.fragments.NavigationDrawerFragment">

    <android.support.v7.widget.RecyclerView
        android:id="@+id/drawerList"
        android:layout_width="match_parent"
        android:layout_height="wrap_content">
    </android.support.v7.widget.RecyclerView>

</RelativeLayout>

Una vez añadido el componente en nuestra vista xml vamos a nuestro controller NavigationDrawerFragment.java (MaterialdesignApp > app > src > main > java > com.alevsk.materialdesignapp > fragments > NavigationDrawerFragment.java) y definimos una nueva variable tipo RecyclerView como propiedad de la clase

public class NavigationDrawerFragment extends Fragment {

    private RecyclerView mRecyclerView;
    private ActionBarDrawerToggle mDrawerToggle;
    private DrawerLayout mDrawerLayout;
    private Toolbar mToolbar;
    ....
    ..

Una vez creado nuestro RecyclerView vamos a agregar la referencia hacia su objeto xml, para eso en el método onCreateView, vamos a modificar un poco el código, actualmente tenemos algo como esto

Capture

Lo remplazamos por esto, sencillo, a estas alturas del tutorial ya deberían saber que estamos obteniendo el elemento mediante el id (layout.findViewById(R.id.drawerList)) que definimos, estamos haciendo un cast (RecyclerView) y lo estamos asignando a la variable mRecyclerView, por ultimo retornamos el layout (View) que es con el que trabajara la aplicacion.

    @Override
    public View onCreateView(LayoutInflater inflater, ViewGroup container,
                             Bundle savedInstanceState) {
        // Inflate the layout for this fragment
        View layout = inflater.inflate(R.layout.fragment_navigation_drawer, container, false);
        mRecyclerView = (RecyclerView) layout.findViewById(R.id.drawerList);
        return layout;
    }

Pero no tan rápido, antes de correr nuestra aplicación nos falta crear un par de componentes más, un Adapter (un manejador lógico para los elementos de nuestra lista), ViewHolders y un modelo (representación de un elemento en la lista)

Pero antes, para tener todo más organizado, vamos a crear dos nuevos Package en nuestro proyecto, uno llamado adapters y otro models

Capture

Vamos a comenzar a pensar en MVC (Model View Controller), si bien no existe un estándar totalmente definido para utilizar MVC en Android podemos tomar el concepto y definir lo siguiente:

  • Model: Qué vamos a renderizar en la aplicación (objetos principales utilizados en los controladores)
  • View: Como lo vamos a renderizar (xml)
  • Controller: Eventos del ciclo de vida de las pantallas, manejar las entradas de usuario, definición de componentes de Android como el RecyclerView, etc.

Creando un Modelo en Android

Teniendo lo anterior como premisa al momento de definir nuestro menú lo que necesitamos es una imagen que sirva como icono y un texto que sirva como título, procedemos a crear nuestra clase Menu.java en el Package models que definimos previamente

Quicktip: en nuestra clase primero definimos las propiedades de nuestro objeto (int icon, String title) y después para generar nuestros gets y sets usamos el shortcut “alt + insert” lo que desplegara un menú en donde elegimos getters and settters y marcamos todas las propiedades (variables) de nuestra clase.

Capture

public class Menu {
    private int icon;
    private String title;

    public int getIcon() {
        return icon;
    }

    public void setIcon(int icon) {
        this.icon = icon;
    }

    public String getTitle() {
        return title;
    }

    public void setTitle(String title) {
        this.title = title;
    }
}

Creando un Adapter personalizado para el RecyclerView

Ahora en el Package adapters creamos una clase llamada MenuAdapter que extenderá o heredara sus metodos de RecyclerView.Adapter, el código inicialmente queda así.

package com.alevsk.materialdesignapp.adapters;

import android.support.v7.widget.RecyclerView;
import android.view.ViewGroup;

/**
 * Created by Alevskey on 23/01/2016.
 */
public class MenuAdapter extends RecyclerView.Adapter {
    @Override
    public RecyclerView.ViewHolder onCreateViewHolder(ViewGroup parent, int viewType) {
        return null;
    }

    @Override
    public void onBindViewHolder(RecyclerView.ViewHolder holder, int position) {

    }

    @Override
    public int getItemCount() {
        return 0;
    }
}

Creando un ViewHolder personalizado

Ademas de eso también vamos a crear un ViewHolder, podemos definir la clase como una subclase de nuestro MenuAdapter, como siempre aquí tienen más documentación respecto a lo que vamos a utilizar http://developer.android.com/reference/android/support/v7/widget/RecyclerView.ViewHolder.html

Quedando el codigo final de la siguiente forma

Capture

Continuamos, Si leyeron la documentación acerca del comportamiento de los Adapter sabrán que por default manejan el tipo de objeto ViewHolder, pero nosotros acabamos de definir uno llamado MenuViewHolder que será el encargado de “contener” elementos como TextView, ImageView y todo lo que necesitemos para personalizar nuestro elemento de menú, sabiendo eso necesitamos realizar algunos cambios en nuestra clase, para empezar en la definición de nuestra clase vamos a definir (valga la redundancia) explícitamente que queremos utilizar MenuViewHolder

public class MenuAdapter extends RecyclerView.Adapter<MenuAdapter.MenuViewHolder> {
...
..
.

Ahora tenemos un montón de errores en la clase y esto es porque tenemos que modificar el tipo de objeto que retorna la función onCreateViewHolder de RecyclerView.ViewHolder a MenuViewHolder, también deberemos definir otra función llamada OnBindViewHolder, una vez realizados los cambios tenemos lo siguiente.

public class MenuAdapter extends RecyclerView.Adapter<MenuAdapter.MenuViewHolder> {
    @Override
    public MenuViewHolder onCreateViewHolder(ViewGroup parent, int viewType) {
        return null;
    }

    @Override
    public void onBindViewHolder(MenuViewHolder holder, int position) {

    }

    @Override
    public int getItemCount() {
        return 0;
    }

    class MenuViewHolder extends RecyclerView.ViewHolder {

        public MenuViewHolder(View itemView) {
            super(itemView);
        }
    }
}

Ahora vamos a crear la vista xml de nuestro item de Menu, en la carpeta layout creamos un archivo llamado viewholder_menu.xml que contendrá dos cosas, un ImageView y un TextView

<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:orientation="horizontal">

    <ImageView
        android:id="@+id/listIcon"
        android:layout_width="50dp"
        android:layout_height="50dp"
        android:padding="8dp"
        android:layout_gravity="center_vertical"
        android:src="@drawable/dummy" />

    <TextView
        android:id="@+id/listText"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:padding="8dp"
        android:layout_gravity="center_vertical"
        android:text="@string/dummy_text" />

</LinearLayout>

La imagen @drawable/dummy es una imagen de ejemplo que yo utilice, ustedes pueden usar la que más les guste.

Regresamos a nuestro MenuAdapter.java y vamos a comenzar a utilizar los métodos que creamos anteriormente, primero vamos a crear un constructor para nuestro adapter, el cual recibirá un Context que nos servirá para hacer el binding de los elementos xml en nuestro ViewHolder, y una lista (de objetos Menu) que será la información con la cual llenaremos el RecyclerView después de eso vamos a realizar ese binding en el método onCreateView, tambien modificamos la función getItemCount para retornar el tamaño actual de la lista.

    private LayoutInflater mInflater;
    private List<Menu> data = Collections.emptyList();

    public MenuAdapter(Context context, List<Menu> data) {
        mInflater = LayoutInflater.from(context);
        this.data = data;
    }

    @Override
    public MenuViewHolder onCreateViewHolder(ViewGroup parent, int viewType) {
        View view = mInflater.inflate(R.layout.viewholder_menu, parent, false);
        MenuViewHolder holder = new MenuViewHolder(view);
        return holder;
    }

    @Override
    public int getItemCount() {
        return data.size();
    }

Ahora en la subclase MenuViewHolder vamos a definir el ImageView y TextView

    class MenuViewHolder extends RecyclerView.ViewHolder {
        ImageView icon;
        TextView title;
        public MenuViewHolder(View itemView) {
            super(itemView);
            title = (TextView) itemView.findViewById(R.id.listText);
            icon = (ImageView) itemView.findViewById(R.id.listIcon);
        }
    }

Ahora en el método onBindViewHolder es donde se realiza la acción de asignar los valores a las variables del MenuHolder (imágenes, textos, etc).

    public void onBindViewHolder(MenuViewHolder holder, int position) {
        holder.title.setText(data.get(position).getTitle());
        holder.icon.setImageResource(data.get(position).getIcon());
    }

Lo que hace nuestro método es recibir un holder, y una posición int, entonces con esa información de nuestra Lista de objetos Menu extraemos el titulo y el id de recurso de imagen que contiene el objeto Menu en la posición indicada de la lista, por ultimo hacemos set de esa información al TextView e ImageView del holder.

Venga ya falta poco, casi terminamos!!!

Me di cuenta que aún no hemos definido el tema de la app, lo he estado pensando y me gustaría enfocarla a un pequeño catálogo de anime que consuma la api opensource de hummingbird, desarrollando un catálogo les poder enseñar a utilizar muchos más componentes que el ecosistema de Android nos ofrece, así como a consumir Apis e interactuar con las mismas, algo muy común en la industria de desarrollo de aplicaciones hoy en día.

Teniendo claro lo anterior las opciones de nuestro menú serán:

  • Buscar (buscador de anime)
  • Lo que estoy viendo (anime que el usuario ve actualmente)
  • Para más tarde (anime que el usuario tiene en la categoría de plan-to-watch)
  • Completado (series que el usuario ha terminado de ver)
  • Mi cuenta (información del usuario y anime favorito)

De ahí hay 3 opciones que solo pueden ser utilizados una vez el usuario haya sido autenticado en nuestra aplicación, pero eso lo dejaremos para más tarde, por ahora nos centraremos en desarrollar el menú.

Primero vamos a nuestro archivo strings.xml que se encuentra en MaterialdesignApp > app > src > main > res > values > strings.xml y ahi vamos a crear una lista de items que contendrá los elementos del menú

    <string-array name="menu_list">
        <item>Buscar</item>
        <item>Lo que estoy viendo</item>
        <item>Para mas tarde</item>
        <item>Mi cuenta</item>
    </string-array>

Buscamos en Internet algún set de iconos gratuitos y los incluimos a los recursos de nuestro proyecto en la carpeta res > drawable pues los necesitamos para el menu

    <array name="menu_icons">
        <item>@drawable/ic_search</item>
        <item>@drawable/ic_eye</item>
        <item>@drawable/ic_ticket</item>
        <item>@drawable/ic_account</item>
    </array>

Cargando los datos al RecyclerView

En nuestro archivo NavigationDrawerFragment.java vamos a crear una nueva función llamada getData(), esta función será la encargada de leer la información estática que definimos en nuestro archivo strings.xml

    public List<Menu> getData() {
        List<Menu> menu = new ArrayList<Menu>();
        TypedArray icons = getResources().obtainTypedArray(R.array.menu_icons);
        String[] labels = getResources().getStringArray(R.array.menu_list);

        for(int i = 0; i < labels.length; i++) {
            Menu item = new Menu();
            item.setTitle(labels[i]);
            item.setIcon(icons.getResourceId(i,-1));
            menu.add(item);
        }

        return menu;
    }

Lo que estamos haciendo en nuestra función es leer los títulos e imágenes (ids de recurso) y con ello estamos instanciando objetos Menu que a su vez agregamos a una lista que será devuelta por el método.

Finalmente en nuestra función onCreateView vamos a crear una nueva instancia de nuestro Adapter personalizado y se lo vamos a pasar al RecyclerView, también definiremos un objeto llamado LayoutManager para nuestro RecyclerView (asegúrate de definir el Adapter como una propiedad de tu clase)

    @Override
    public View onCreateView(LayoutInflater inflater, ViewGroup container,
                             Bundle savedInstanceState) {
        // Inflate the layout for this fragment
        View layout = inflater.inflate(R.layout.fragment_navigation_drawer, container, false);
        mRecyclerView = (RecyclerView) layout.findViewById(R.id.drawerList);
        mAdapter = new MenuAdapter(getActivity(),getData());
        mRecyclerView.setAdapter(mAdapter);
        mRecyclerView.setLayoutManager(new LinearLayoutManager(getActivity()));

        return layout;
    }

Corremos la aplicación en nuestro emulador o teléfono físico, abrimos el NavigationDrawer y vemos nuestro menú 🙂

recyclerview

Eso es todo por ahora lectores, en el siguiente tutorial aprenderemos a aplicar color a los iconos utilizando filtros y a definir las acciones una vez que el usuario da Tap en un elemento del menú. Recuerden que el código de lo trabajado durante este tutorial lo pueden encontrar en el repositorio https://github.com/Alevsk/Material-design-en-Android
salu2

50% de descuento para Campus Party 2014!

cover2

Uno de los eventos más importantes de Tecnología y ambiente tecnológico del mundo se celebrará en nuestro país en Zapopan, hablamos de CPMX5 y hoy te mostraremos la oportunidad de como obtener tus entradas con el 50 de descuento.

  • Deben registrarse como campusero en www.campus-party.com.mx.
  • Si ya tienes usuario solo debes hacer login.
  • Una vez hecho login en el panel de usuario deben seleccionar la opción «Comprar entrada». (http://www.campus-party.com.mx/webapp/fichaUsuario/pago)
  • Elegir la opción «Comprar con descuento».
  • En el proceso deben usar el siguiente código de descuento: CD501ihw35hi (copia y pega).
  • Una vez elegido el tipo de entrada se procede al pago de la cantidad vía PayPal.

¡Y listo! solo faltaría esperar a que llegue el día de comienzo de #CPMX5 para disfrutar de una semana de contenidos para los fans de la tecnología y lo que esto implica.

Lista de ganadores de entradas para Campus Party 2013

Muchas gracias a todos los que participaron el sorteo de 3 entradas gratis para asistir a Campus Party México 2013, las personas listadas a continuación ganaron una entrada con puesto en sala para el evento :), muchas felicidades.

  • Braicot Espinoza
  • Rocio Barragan
  • Jose Vazquez Quezada

Si no resultaste ganador no te desanimes, todavía puedes conseguir tu entrada con un 20% de descuento :)!

¿Como? Muy fácil, tan solo pídela utilizando nuestra sección de contacto y con mucho gusto te enviare un código promocional para que puedas adquirir tu entrada!.

Ya falta poco, nos vemos en Campus Party México 2013

salu2