This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#1.1 Implement an algorithm to determine if a string has all unique characters. Whatif you cannot use additional data structures? | |
test =[0 for i in range(255)] | |
re = 0 | |
s= raw_input('Input:') | |
if s.strip() =='': | |
print'This is empty string' | |
else: |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#1.3 Given two strings, write a method to decide is one is a permutation of the other. | |
def permutation(s1, s2): | |
#write string into list | |
list1 = list(s1) | |
list2 = list(s2) | |
#compare the length, if not the same re turn false | |
if len(list1) != len(list2): | |
return False | |
else: |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def replaceS(s): | |
replist = list(s) | |
for i in range (0, len(s)): | |
if ord(replist[i]) == 32: | |
replist[i] = '20%' | |
newlist = ''.join(replist) | |
return newlist | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# cc1.5 Implement a method to perform string compression using counts of repeated characters. If the compressed string is not smaller than the ooriginal string, return the original one. | |
def compression(s): | |
list1 = list(s) | |
list2 = [] | |
c = 1 | |
j = 0 | |
for i in range(1, len(list1)): |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#cc 1.6 Given an image represented by an N*N matrix, where each pixel in the image is 4 bytes. write a method to rotate the image by 90 degrees | |
#Assume clockwise rotation | |
def rotate(matrix): | |
n = len(matrix) | |
for layer in range(0, n/2): | |
first = layer | |
last = n-layer-1 | |
for i in range(first, last): |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0. | |
# deal matrix as a list | |
def listIndex(x, y, n): | |
return y + x * n | |
def toList(matrix, m, n): | |
global listm |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#cc 1.8 Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (e.g.,"waterbottle"is a rotation of"erbottlewat"). | |
def isRotation(s1, s2): | |
if (len(s1) == len(s2) and len(s1) > 0): | |
s = s1 + s1 | |
return isSubstring(s, s2) | |
else: | |
return False |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Node: | |
def __init__(self, data): | |
self.data = data | |
self.next = None | |
class LinkedList: |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#2.2 Implement an algorithm to find the kth to last element of a singly linked list. | |
# supose that the length of the link is unknown | |
from LinkedList import Node, LinkedList | |
def nthtolast(head, k): | |
if head is None: | |
return | |
p1 = head |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#2.3 Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node. | |
from LinkedList import LinkedList, Node | |
def deleteNode(node): | |
if node is None or node.next is None: | |
return False | |
node.data = node.next.data | |
node.next = node.next.next | |
return True |
OlderNewer