Skip to content

Instantly share code, notes, and snippets.

Avatar

Raunak Ramakrishnan rrampage

View GitHub Profile
@rrampage
rrampage / check_perm.py
Last active Jul 14, 2018
Check if two strings are anagrams in O(n) time
View check_perm.py
# Check if two strings are permutations (anagrams) of each other
# For this example, using just the lowercase ASCII letters as the alphabet
# Step 1 : Generate k primes using Sieve of Erasthothenes
# Step 2 : Map characters in alphabet to prime
# Step 3 : Compare the products of the 2 strings
# Why does this work?
# - Multiplication is commutative i.e a * b * c = c * a * b
# - Fundamental theorem of arithmetic i.e every natural number can be expressed uniquely as either a prime or a product of primes (https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic)
from string import ascii_lowercase as ALPHABETS
View keybase.md

Keybase proof

I hereby claim:

  • I am rrampage on github.
  • I am raunak (https://keybase.io/raunak) on keybase.
  • I have a public key ASBUeum7e_np2neA9YXi60A7YLGFHk9yI9n3VCNsKgQSIwo

To claim this, I am signing this object:

@rrampage
rrampage / Sort by 1's.py
Last active Dec 18, 2015
Given a positive integer n, sort numbers from 1 to n with increasing number of bits set. If two numbers have same number of bits set, the lower number will come first. (From Codebunk FB Page)
View Sort by 1's.py
"""Using the implementation from Wikipedia: https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation """
def hamming_weight(n):
t1 = n - ((n>>1) & 0x55555555)
t2 = (t1 & 0x33333333) + ((t1 >> 2) & 0x33333333)
return ((((t2 + (t2 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24,n)
def hamming_sort(n):
return [x[1] for x in sorted(map(hamming_weight,xrange(1,n+1)))]