Algorithm

I took Google’s online campus hiring written test yesterday. Skip algorithms for a day and your skills slide right back down. Problem A. Password Attacker Description How many passwords of length M can be formed from N distinct characters, such that every password uses all N characters at least once? Solution 1: Brute Force For each solution to the equation below, add the number of distinct permutations. If one solution is X1, …, Xn, that group contributes M!...

After grinding LeetCode for several days, I finally finished. Code is here. Reverse Words in a String Simulation on strings Evaluate Reverse Polish Notation Simulation — evaluate postfix expressions Max Points on a Line Given N points in the plane, find a line that passes through the most points. Enumerate each point as the origin, compute relative coordinates, then compute y/x and use a hash table to count duplicates and find the maximum....

Zookeeper hardly needs an introduction — it is a distributed coordination service. A few questions I was curious about: How does ZooKeeper implement asynchronous watcher callbacks? (code-level details) How does ZooKeeper implement distributed locks? How do Queue, barrier, and similar recipes work? I read the Python client kazoo and got the general picture. A simple client example #!/usr/bin/python import logging from time import sleep from kazoo.client import KazooClient # print log to console logging....

Source code and related articles are available here. This article discusses the K-th largest or K-th smallest element in a sequence. Since the K-th largest can be reduced to finding the (N−K+1)-th smallest (where N is the sequence length), we focus on the K-th smallest element. Problems covered in this article: Given an integer sequence, find the K-th smallest element. Given an integer sequence that supports dynamic updates, answer queries for the K-th smallest element....

Hash Table A hash table is an array of size buckets, table[0...size-1]. Hashing an object yields an index; we store the object in table[value]. When a bucket holds multiple objects, they are chained into a linked list. This collision strategy is called separate chaining. Load Factor If a hash table has size buckets and used stored elements, used / size is the load factor. When loadFactor <= 1, expected lookup cost is O(1)....

Abstract: Plane sweep is widely used in computational geometry, computer graphics, grid computing, and related areas. Many classic algorithms use plane sweep to greatly reduce time complexity — e.g. segment intersection, union of axis-aligned rectangle perimeters, rectangle intersection, spatial collision detection, Voronoi diagram construction, closest pair of points, and more. This article introduces several plane sweep algorithms commonly used in ACM programming contests. By purpose, they fall into: Data aggregation; Detecting geometric positional relationships; Closest pair of points....