The hacker, the photographer and the rival: Path Traversal

Artbit is an online social network where users can register for free and upload their own digital pictures in order to share them with the world and get popularity. To attract more visitors, the creators of the social network have launched a challenge on their platform which will reward the user who will upload the best picture. Any user can join the competition by simply … Continue reading The hacker, the photographer and the rival: Path Traversal

Playing Pacman with Multi-Agents Adversarial Search

In this post we are going to design various artificial intelligence agents to play the classic version of Pacman, including ghosts and capsules. Pacman is a famous Atari game developed back in 1979 by a nine-persons team and then released in 1980 by the former Japanese developer and publisher of arcade video games Namco. The great success the game had at the time, made it … Continue reading Playing Pacman with Multi-Agents Adversarial Search

AIs Battle Royale: The ultimate snake

In a previous post, we developed two AIs to play the game of Snake, of which, the first one implements a heuristic algorithm to select its moves while the second one consists of a deep neural network trained with a reinforcement learning algorithm (Deep Q-Learning). Afterward, in a second post, we used a genetic algorithm to create different generations of snakes where the best individuals … Continue reading AIs Battle Royale: The ultimate snake

Printing Neatly

Consider the problem of neatly printing a paragraph with a monospaced font (all characters having the same width) on a printer. The input text is a sequence of n words of lengths l1, l2,…,ln, measured in characters. We want to print this paragraph neatly on a number of lines that hold a maximum of M characters each. Our criterion of “neatness” is as follows. If a given line … Continue reading Printing Neatly

Count of Range Sums

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive. Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive. A naïve algorithm of O(n2) is trivial. You MUST do better than that. Difficulty: Very hard. Input The first line contains 3 integers separated by spaces: n, representing the length of the integer array nums. lower. upper. The second line is the integer … Continue reading Count of Range Sums

Merge Sort

Merge Sort is a “Divide and Conquer” algorithm which first divides an input array in two sub-arrays, then it calls itself for those two sub-arrays, orders them and finally merges them into the original array. Write a merge sort program to sort an integer array in ascending order. Difficulty: Easy. Input One integer representing the length of the integer array. n integers with neighboring elements separated by a space representing the … Continue reading Merge Sort

The hacker, the lover and the cheater: Geolocation

Let me introduce this post by asking you a question: is it possible to obtain someone’s location by simply asking him/her to send you a picture? You may think this is another of my nonsense questions, maybe it is, but before drawing any conclusion, you should read this story, it is a story of love, betrayal and…Computer science of course. The story of the hacker, … Continue reading The hacker, the lover and the cheater: Geolocation

Integer Partition

A partition of a positive integer n is a multiset of positive integers such that their sum is equal to n. We denote the number of partitions of n by p(n). What is the number of ways to partition n into no more than k positive integers? Difficulty: Very hard. Input There are two integers, n and k. Output Output the number of ways modulo 10^9+7 to split n into no more than k positive integers. Example Given n=5 … Continue reading Integer Partition

Lattice Paths

Going from the point (x1,y1) to the point (x2,y2) in the Cartesian graph takes at least |x1−x2|+|y1−y2| steps moving unit length along the x-axis or the y-axis at a time (taxicab geometry). We now wonder, how many ways are there, to go from (x1,y1) to (x2,y2) using least steps, and without crossing or touching the line y=x? Difficulty: Medium. Input Four integers, representing x1, y1, x2, y2, respectively. Output The number of ways modulo 10^9+7 to go from (x1,y1) to (x2,y2) using least steps, … Continue reading Lattice Paths

Visualization and analysis of web engine data

Data preprocessing and visualization are important skills of managing Internet services such as search engines and online social networks. In this post, we are going deal with two weeks of search logs from a large search engine and learn some practical techniques to analyze the data. Background and data Once you submit a query to a search engine, the search engine will log some related … Continue reading Visualization and analysis of web engine data