Code Says – Page 3 – C code. C code run. Run code run… please!

Solution to Minimum Size Subarray Sum by LeetCode

1 Jan

Question: https://leetcode.com/problems/minimum-size-subarray-sum/ Question Name: Minimum Size Subarray Sum This question is very similar with Longest Substring Without Repeating Characters and Minimum Window Substring.

class Solution(object):

def minSubArrayLen(self, s, nums):

"""

:type s: int

:type nums: List[int]

:rtype: int

"""

begin = 0 # Inclusive

end = 0 # Exclusive. It is always different from "begin"

# after the first move.

window_sum = 0

result = 0

# Find candidate windows, whose sum is >= s.

while end < len(nums):

# Prepare for this window.

window_sum += nums[end]

end += 1

# Extend the window by moving the "end".

# For the first window, it may be extended by multiple steps.

# Otherwise, it is always extended by one step.

while end < len(nums) and window_sum < s:

window_sum += nums[end]

end += 1

if window_sum < s: break

# Shrink the window by moving the "begin".

while window_sum - nums[begin] >= s:

window_sum -= nums[begin]

begin += 1

# Update the result if this window is shorter.

if result == 0 or end - begin < result:

result = end - begin

return result

Solution to Implement Trie (Prefix Tree) by LeetCode

1 Jan

Question: https://leetcode.com/problems/implement-trie-prefix-tree/ Question Name: Implement Trie (Prefix Tree) Not a full implementation. The delete function is not required.

class TrieNode(object):

def __init__(self):

"""

Initialize your data structure here.

"""

self.isWord = False

self.sons = {}

class Trie(object):

def __init__(self):

self.root = TrieNode()

def insert(self, word):

"""

Inserts a word into the trie.

:type word: str

:rtype: void

"""

current = self.root

for letter in word:

if letter not in current.sons:

current.sons[letter] = TrieNode()

current = current.sons[letter]

current.isWord = True

def search(self, word):

"""

Returns if the word is in the trie.

:type word: str

:rtype: bool

"""

current = self.root

for letter in word:

if letter not in current.sons:

return False

else:

current = current.sons[letter]

return current.isWord

def startsWith(self, prefix):

"""

Returns if there is any word in the trie

that starts with the given prefix.

:type prefix: str

:rtype: bool

"""

current = self.root

for letter in prefix:

if letter not in current.sons:

return False

else:

current = current.sons[letter]

return True

# Your Trie object will be instantiated and called as such:

# trie = Trie()

# trie.insert("somestring")

# trie.search("key")

Solution to Course Schedule by LeetCode

22 Dec

Question: https://leetcode.com/problems/course-schedule/ Question Name: Course Schedule

class Solution(object):

def _hasLoop(self, courseID, adjacencySet, reachableNodes, currentPath):

"""

:type numCourses: int

:type adjacencySet: List[set(int)]

:type: reachableNodes: mutable, set(int)

:type: current_path: mutalbe, set(int)

:rtype: bool

"""

if courseID in currentPath:

return True

currentPath.add(courseID)

reachableNodes.add(courseID)

for prerequisite in adjacencySet[courseID]:

if self._hasLoop(prerequisite, adjacencySet, reachableNodes, currentPath):

return True

currentPath.remove(courseID)

return False

def _buildAdjacencySet(self, numCourses, prerequisites):

"""

:type numCourses: int

:type prerequisites: List[List[int]]

:rtype: List[set(int)]

"""

adj_set = [set() for _ in xrange(numCourses)]

for prerequisite in prerequisites:

adj_set[prerequisite[0]].add(prerequisite[1])

return adj_set

def canFinish(self, numCourses, prerequisites):

"""

:type numCourses: int

:type prerequisites: List[List[int]]

:rtype: bool

"""

# Find out the courses, which are not prerequisite of others.

is_prerequisite = [False for _ in xrange(numCourses)]

for prerequisite in prerequisites:

is_prerequisite[prerequisite[1]] = True

adjacency_set = self._buildAdjacencySet(numCourses, prerequisites)

is_doable = [False for _ in xrange(numCourses)]

for courseID in xrange(numCourses):

if is_prerequisite[courseID]:

continue

# Check whether it is possible to finish this course.

# If it is, all its direct/indirect prerequisites are also doable.

reachable_nodes = set()

current_path = set()

if self._hasLoop(courseID, adjacency_set, reachable_nodes, current_path):

return False

for courseID in reachable_nodes:

is_doable[courseID] = True

return all(is_doable)

Solution to Polygon-Concavity-Index by codility

18 Oct

Question: https://codility.com/demo/take-sample-test/polygon_concavity_index/ Question Name: Polygon-Concavity-Index or PolygonConcavityIndex Thanks to Robert Sedgewick, the Youtube video (Algorithms, Part I – Convex Hull) tells everything about this problem.

def _IsClockwise(point_A, point_B, point_C):

''' Return the direction from points A -> B -> C.

'''

result = (point_B.x - point_A.x) * (point_C.y - point_A.y) -

(point_B.y - point_A.y) * (point_C.x - point_A.x)

# The direction of a->b->c is:

if result > 0: return 1 # counter-clockwise

elif result < 0: return -1 # clockwise

else: return 0 # a staight line

def solution(A):

''' The solution refers to:

https://www.youtube.com/watch?v=0HZaRu5IupM

'''

# Find the lowest point(s) in y-axis.

lowest_y = A[0].y

lowest_y_index = []

for i in xrange(len(A)):

if A[i].y < lowest_y:

lowest_y = A[i].y

lowest_y_index = [i]

elif A[i].y == lowest_y:

lowest_y_index.append(i)

else:

continue

# Find a point, which is not the lowest in y-axis and immediately

# after a lowest-in-y-axis point.

start_point = lowest_y_index[0]

lowest_y_array = [False] * len(A)

for i in lowest_y_index: lowest_y_array[i] = True

while lowest_y_array[start_point] == True:

start_point = (start_point + 1) % len(A)

start_point = (start_point - 1 + len(A)) % len(A)

# Re-organize the points so that, it is easier to check every three

# consecutive points in one loop (without module operation %).

rotated_A = A[start_point : ] + A[ : start_point]

# We find the start point such that, the direction is non-zero.

direction = _IsClockwise(rotated_A[-1], rotated_A[0], rotated_A[1])

extened_A = rotated_A + rotated_A[:2]

for i in xrange(len(A)):

temp = _IsClockwise(extened_A[i], extened_A[i+1], extened_A[i+2])

if temp * direction < 0:

# Compute the original index and return

return (i + 1 + start_point)%len(A)

# Every point is on the convex hull.

return -1

Solution to Odd-Occurrences-In-Array by codility

18 Sep

Question: https://codility.com/programmers/task/odd_occurrences_in_array Question Name: Odd-Occurrences-In-Array or OddOccurrencesInArray This question is completely the same as the Perm-Missing-Elem by codility. The comment from Kim is very helpful.

def solution(A):

result = 0

for number in A:

result ^= number

return result

Solution to Number-Solitaire by codility

6 Sep

Question: https://codility.com/demo/take-sample-test/number_solitaire/ Question Name: Number-Solitaire or NumberSolitaire The key point is: to achieve the position i, we can only come from the positions i-6, i-5, i-4, i-3, i-2, and i-1.

def solution(A):

# The first six items are used for padding only, so that we can have

# a unified for loop, no matter how many squares are there in input.

# The first item is never accessed.

max_so_far = [A[0]] * (len(A) + 6)

for index in xrange(1, len(A)):

# Because we have a fixed length of window as 6, the time

# complexity of max(max_so_far[index : index + 6]) is O(1).

max_so_far[index + 6] = max(max_so_far[index : index + 6]) +

A[index]

return max_so_far[-1]

Solution to Max-Nonoverlapping-Segments by Codility

4 Sep

Question: https://codility.com/demo/take-sample-test/max_nonoverlapping_segments/ Question Name: Max-Nonoverlapping-Segments or MaxNonoverlappingSegments It is an easy solution, but a bit hard to prove it. Let’s scan from left to right, according to the end points. Since the input has already been sorted with the end … Read More »

Solution to Reverse Linked List by LeetCode

3 Sep

Question: https://leetcode.com/problems/reverse-linked-list/ Question Name: Reverse Linked List

# Definition for singly-linked list.

# class ListNode(object):

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution(object):

def reverseList(self, head):

"""

:type head: ListNode

:rtype: ListNode

"""

if head == None:

return None

# Store the nodes from head to end.

stack = []

while head != None:

stack.append(head)

head = head.next

# Rebuild the list from end to head.

for index in xrange(len(stack)-1, 0, -1):

stack[index].next = stack[index-1]

stack[0].next = None

return stack[-1]

Solution to Isomorphic Strings by LeetCode

1 Sep

Question: https://leetcode.com/problems/isomorphic-strings/ Question Name: Isomorphic Strings The key point is to avoid 2+ characters map to the same character.

class Solution(object):

def isIsomorphic(self, s, t):

"""

:type s: str

:type t: str

:rtype: bool

"""

mapping = {}

for index in xrange(len(s)):

if not s[index] in mapping:

# New mapping is found.

mapping[s[index]] = t[index]

elif mapping[s[index]] != t[index]:

# No 2+ characters may map to the same character.

return False

# Make sure that no 2+ characters may map to the same character.

if len(set(mapping.keys())) != len(set(mapping.values())):

return False

return True

Solution to Count Primes by LeetCode

29 Aug

Question: https://leetcode.com/problems/count-primes/ Question Name: Count Primes

class Solution(object):

def countPrimes(self, n):

"""

:type n: int

:rtype: int

"""

# The first and second elements are never used. Otherwise,

# primesRecord[i] is for interger i.

primesRecord = [False] * n

primesCount = 0

for number in xrange(2, n):

if primesRecord[number] == False:

# Cannot be divided by any smaller integer. This is

# a prime nubmer.

primesCount += 1

current = number

while current < n:

# This is a composite number.

primesRecord[current] = True

current += number

return primesCount

tl;dr: Please put your code into a <pre>YOUR CODE</pre> section.

Hello everyone!

If you want to ask a question about the solution. DO READ the post and comments firstly.

If you had some troubles in debugging your solution, please try to ask for help on StackOverflow, instead of here.

If you want to post some comments with code or symbol, here is the guidline.

1. To post your code, please add the code inside a <pre> </pre> section (preferred), or <code> </code>. And inside the pre or code section, you do not need to escape < > and &, e.g. no need to use < instead of <.

2. To use special symbols < and > outside the pre block, please use "<" and ">" instead.

3. If you have a comment with lots of < and >, you could add the major part of your comment into a <pre class="decode:true crayon-inline "> YOUR COMMENTS </pre> section.

Finally, if you are posting the first comment here, it usually needs moderation. Please be patient and stay tuned. Thanks!

CodeSays.com Admin

Ovi February 12, 2024 at 11:14 pm on Solution to Min-Perimeter-Rectangle by codilityExactly my question too. I tried something very similar to Sheng's solution, importing the math module and using sqrt(). Codility marked it only as 80%,...
Doron Ben Ari February 11, 2024 at 4:10 am on Solution to Min-Avg-Two-Slice by codilityInspired by Sheng's great solution, I wrote the following proof: Assume you found the slice with minimal average. Assume the first two consecutive elements of...
Ovi February 4, 2024 at 9:03 am on Solution to sigma2012 (Stone-Wall) by codility def solution(H): heights = H # geometric logic: the blocks need to be cuboid, all sides are rectagular. Nothing fancy, means that the angles...
Ovidiu Oprea February 2, 2024 at 11:06 am on Solution to Fish by codilityIt's the reason why it took me 2 weeks to finish this task (in the context of adult life with non-dev job). I was trying...
Ovi January 15, 2024 at 2:40 pm on Solution to Brackets by codilityThanks for this blog post! I was banging my head against the wall thinking this is a simple / short solution, where you just build...
parikshit verma July 5, 2023 at 8:26 am on Solution to Missing-Integer by codility def missingnum(a): st=min(a) en=max(a) b=set(range(1,en+2)) if (en<1 or st>1) : return 1 else: return min(b-set(a))
Pavankumar Nandeshwar June 26, 2023 at 8:07 am on Solution to Dwarfs-Rafting by codilityOk fixed it. gives 100%: int solution(int N, string &S, string &T) { int q = N / 2 * N / 2; int lf...
Pavankumar Nandeshwar June 26, 2023 at 5:23 am on Solution to Dwarfs-Rafting by codilityCan someone explain what is wrong with my solution in C++ ? int solution(int N, string &S, string &T) { int q = N /...
Pavankumar Nandeshwar June 23, 2023 at 10:25 pm on Solution to Flood-Depth by codilityMy C++ Solution. O(N) #include <climits> int solution(vector<int> &A) { int max_depth {}; int max_lvl = {}; int min_lvl = INT_MAX; for (unsigned int i...