Skip to content

Instantly share code, notes, and snippets.

View jones's full-sized avatar
⛄

Tristan Jones jones

⛄
  • Berkeley, CA
View GitHub Profile
@jones
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
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
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
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
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
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
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
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
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
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