jones’s gists

jones / longestcommonprefix.py

Created December 31, 2014 06:25

Write a function to find the longest common prefix string amongst an array of strings.

	class Solution:
	# @return a string
	def longestCommonPrefix(self, strs):
	# computes the LCP of the stringlist strs
	if strs is None or len(strs) == 0:
	return ""

	return reduce(self.lcp, strs)

	def lcp(self, str1, str2):

jones / pow.py

Created January 1, 2015 05:59

Implement pow(x, n).

	class Solution:
	# @param x, a float
	# @param n, a integer
	# @return a float
	def pow(self, x, n):
	if x == 0.0:
	return 0.0
	if n < 0:
	# Avoids arithmetic underflow
	return 1.0/self.pow(x, -n)

jones / linkedlistintersect.cpp

Created January 1, 2015 10:06

Write a program to find the node at which the intersection of two singly linked lists begins.

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:

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)

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 / 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 / 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 / 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 / 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 / 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

Tristan Jones jones