jones’s gists

jones / mergeintervals.py

Created September 3, 2015 05:14

Given a collection of intervals, merge all overlapping intervals. For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].

	# Definition for an interval.
	# class Interval(object):
	# def __init__(self, s=0, e=0):
	# self.start = s
	# self.end = e

	class Solution(object):
	def merge(self, intervals):
	"""
	:type intervals: List[Interval]

jones / groupanagrams.py

Created September 2, 2015 23:55

Given an array of strings, group anagrams together. For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], Return: [ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ] Note: For the return value, each inner list's elements must follow the lexicographic order. All inputs will be in lower-case.

	class Solution(object):
	def groupAnagrams(self, strs):
	"""
	:type strs: List[str]
	:rtype: List[List[str]]
	"""
	from itertools import groupby
	sortedAnagrams = sorted(sorted(strs), key=lambda a: sorted(a))
	return [list(v) for k,v in groupby(sortedAnagrams, key=lambda a: sorted(a))]

jones / happy.py

Created September 2, 2015 21:05

Write an algorithm to determine if a number is "happy". A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Thos…

	class Solution(object):
	def isHappy(self, n):
	"""
	:type n: int
	:rtype: bool
	"""
	seenNums = set()
	while n > 1 and (n not in seenNums):
	seenNums.add(n)
	n = sum(map(lambda x: x**2, map(int, list(str(n)))))

jones / findpeak.py

Created August 29, 2015 07:00

A peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that num[-1] = num[n] = -∞. For example, in array [1, 2, 3, 1], 3 is a peak e…

	class Solution(object):
	def findPeakElement(self, nums):
	"""
	:type nums: List[int]
	:rtype: int
	"""
	return self.findPeakRecur(nums, 0, len(nums)-1)

	def findPeakRecur(self, nums, lo, hi):
	mid = (lo + hi) // 2

jones / TurretDefense.cpp

Created April 5, 2015 18:16

"Incoming! Fire the defense turrets at these coordinates! Go go go!"

	#include <cmath>
	#include <vector>

	class TurretDefense {
	public:
	int firstMiss(std::vector <int>xs, std::vector <int>ys, std::vector <int> times) {
	int curx = 0;
	int cury = 0;
	int curtime = 0;
	for(int i = 0; i < xs.size(); i++) {

jones / mergesortedarray.cpp

Created March 3, 2015 01:23

Given two sorted integer arrays A and B, merge B into A as one sorted array. Note: You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

	class Solution {
	public:
	void merge(int A[], int m, int B[], int n) {
	int i = m - 1;
	int j = n - 1;
	int k = m + n - 1;

	while(i >= 0 && j >= 0) {
	if (A[i] > B[j]) {
	A[k--] = A[i--];

jones / longestsubstrwithoutrepeat.py

Created March 2, 2015 03:06

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

	class Solution:
	# @return an integer
	def lengthOfLongestSubstring(self, s):
	if s is None or len(s) == 0:
	return 0

	i, maxLen = 0, 0
	seenVals = set() # seen characters

	for j in range(len(s)):

jones / plusone.py

Created January 29, 2015 23:08

Given a non-negative number represented as an array of digits, plus one to the number. The digits are stored such that the most significant digit is at the head of the list.

	class Solution:
	# @param digits, a list of integer digits
	# @return a list of integer digits
	def plusOne(self, digits):
	for i in reversed(range(len(digits))):
	digits[i] = (digits[i] + 1) % 10
	if digits[i] == 0:
	continue
	return digits

jones / mfromlast.cpp

Created January 1, 2015 21:36

Given a singly-linked list, devise a time and space efficient algorithm to find the mth-to-last element of the list. Implement your algorithm, taking care to handle relevant error conditions. Define mth to last such that when m = 0, the last element of the list is returned.

	Element findMToLastElement( Element head, int m ) {
	if (!head \|\| n < 0) {
	return NULL;
	}
	Element first, second = head, head;
	for(int i = 0; i < m; i++) {
	first = first->next;
	if (!first) {
	return NULL;
	}

jones / searchinsertposition.py

Created January 1, 2015 11:18

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. Assume no duplicates in the array.

	class Solution:
	# @param A, a list of integers
	# @param target, an integer to be inserted
	# @return integer
	def searchInsert1(self, A, target):
	for i,val in enumerate(A):
	if target <= val:
	return i
	return len(A)

Tristan Jones jones