Skip to content

Instantly share code, notes, and snippets.

View jesuyedavid's full-sized avatar

Jesuye David jesuyedavid

1 follower · 12 following
View GitHub Profile
@jesuyedavid
jesuyedavid / ShortestReachGraph.py
Created May 9, 2018 22:27
Consider an undirected graph consisting of nodes where each node is labeled from to and the edge between any two nodes is always of length .
'''
algorithm:
1. Find shortest path between start and goal nodes
and multiply distance with 6.
2. If distance does not exist in graph that means
replace it with -1 because it is not connected to start node
'''
from collections import defaultdict
@jesuyedavid
jesuyedavid / onegiantoverlap.py
Created May 8, 2018 02:43
Derive one giant overlap
def mergeIntervals(arr):
sorted(arr)
index=0
for i in range(len(arr)):
if(index!=0 and arr[index-1][0]<=arr[i][1]):
while(index!=0 and arr[index-1][0]<arr[i][1]):
arr[index-1][1]=max(arr[index-1][1], arr[i][1])
arr[index-1][0]=min(arr[index-1][0], arr[i][0])
index-=1
else:
@jesuyedavid
jesuyedavid / davisStairCase.py
Created May 4, 2018 01:18
Davis has s staircases in his house and he likes to climb each staircase 1,2, or 3 steps at a time. Being a very precocious child, he wonders how many ways there are to reach the top of the staircase. Given the respective heights for each of the s staircases in his house, find and print the number of ways he can climb each staircase on a new lin…
countStaircase={}
def countSteps(n):
if n in countStaircase:
return countStaircase[n]
elif n==0:
return 1
elif n<0:
return 0
else:
@jesuyedavid
jesuyedavid / printKFromBack.py
Created May 1, 2018 21:56
Given k, print the kth element from the end of a linked list
class Node:
def __init__(self, data):
self.data=data
self.nex=None
def prkte(cur, k):
if(cur.nex==None):
if(k-1==0):
print(cur.data)
return k-1
@jesuyedavid
jesuyedavid / dfsGraph.py
Last active April 26, 2018 21:00
Detect whether the graph has a cycle, and find the longest cycle.
from collections import defaultdict
class Graph:
def __init__(self):
self.graph=defaultdict(list)
self.V=len(self.graph)
def addEdge(self, u, v):
self.graph[u].append(v)
self.V=len(self.graph)
@jesuyedavid
jesuyedavid / salesperson.cpp
Last active May 4, 2018 00:23
For each used car a salesperson sells, the commission is paid as follows: $20 plus 30% of the selling price in excess of the cost of the car. Typically, the minimum selling price of the car is the cost of the car plus $200 and the maximum selling price of the car is the cost of the car and $2,000. Write a program that prompts the user to enter t…
#include <iostream>
#include <string>
#include <assert.h>
using namespace std;
struct result{
double maxiSelPrice;
double miniSelPrice;
double comRangeL;
@jesuyedavid
jesuyedavid / revList.py
Last active April 24, 2018 18:11
Reverse a linked list using iteration.
class Node:
def __init__(self, data):
self.data=data
self.nex=None
def revList(head):
trail=head
cur=head.nex
temp=cur.nex
trail.nex=None
@jesuyedavid
jesuyedavid / maxFish.py
Created April 21, 2018 21:16
A fisherman is in a rectangular sea. The value of the fish at point (i, j) in the sea is specified by an n × m 2D array A. Write a program that computes the maximum value of fish a fisherman can catch on a path from the upper leftmost point to the lower rightmost point. The fisherman can only move down or right
def maxFish(grid):
nc=grid[0]
for i in range(len(nc)):
if(i!=0):
nc[i]+=grid[0][i-1]
for i in range(1,len(grid)):
for j in range(len(grid[0])):
if (j!=0):
nc[j]=max(grid[i][j]+nc[j], nc[j-1]+grid[i][j])
@jesuyedavid
jesuyedavid / numWays.py
Created April 21, 2018 15:29
Find the number ways to traverse an mXn grid in O(min(m,n)) space.
def numWays(n, m):
num=[1]*min(n, m)
for i in range(max(n,m)-1):
for j in range(min(n,m)):
if j!=0:
num[j]+=num[j-1]
return(num[n-1])
print(numWays(2,5))
@jesuyedavid
jesuyedavid / recRev.py
Created April 19, 2018 13:58
Reverse print a digit using recursion
def recRev(x, y):
if(x>0):
y+=x%10
return (recRev(x/10, y*10))
else:
return (y/10)