See setup instructions, in the Code 301 Setup Guide.
Under the data-structures-and-algorithms
repository, at the top level is a folder called code-challenges
Each day, you'll add one new file to this folder to do your work for the day's assigned code challenge
This function take any list of items, and return the reverse of it.
for the chellenge it was normal but for the test I havn't made it as the first time making test until the instructor explain how to, so it's normal now also
This function take any list and value, and return the list with the value in the middle of it.
I check for length of the list to determine the index i will insert the value in, it takes me 1 hour
Write a function called BinarySearch which takes in 2 parameters: a sorted array and the search key.return the index of the array’s element that is equal to the search key, or -1 if the element does not exist.
1 : create the function with two arguments
2 : create a result by default equal to -1 and counter =0
3 : loop through the list and counter will increment 1 each time
4 : if the key inserted was zero ill return the first item and break the loop
5 : if key is bigger than zero ill continuo loop until counter reach the value of key minus one and ill break and return the item
it take me two hours
Write a clsses and some methods to create linked list and to test them
1 : create the Node class and the constructor method for it.
2 : create the Linked list class and the constructor methos, the insert method, the inclde method, and finally the str method
3 : in constructor method I set the head to none, and in the insert method 3:a I add a new node with the value argument 3:b if there are a head we will set our current pointer to the head 3:c i'll loop while there are following node to the current node 3:d when I finish I'll assign new node value as the next value for the head 3:e if there are no head and one value entered we will set it as the head
4 : in the include method ill loop in the values of the linked list and check each one
5 : in the str method ill loop also iin the linked list and store each item on pre built empty string variable and return the result string
it take me three hours
- The constructor method, to assign the head.value
- The insert method to insert a new node at the begining of linked lists
- the include method to check if a given value is included at the linked list
- str method to return result as readable string
function to get a node value with a given reverse index
-
get k as argument
-
set current to head
-
set count =0
-
check if current.next is truthy value
-
if it's assign current to the next
-
increase count by 1
-
check if k larger than count if yes raise exception
-
for i in range (count -k) set currnet into the next value
a function called zip Lists which takes two linked lists as arguments. Zip the two linked lists together into one so that the nodes alternate between the two lists and return a reference to the head of the zipped list.
-
get two linked lists as parameters
-
store the heads of each linked list as cuurent1, current2
-
check the longest linked list and make it the prime one
-
assign heads
-
loop over the first one
-
link first node to the current in the second list
-
link the second current into the first next in the first linked list
-
move the first current to the next of the first current
-
move the second current to the next of the second current
-
assign the head of the second to second current
-
return the prime linked list
Stacks are based on the LIFO principle, i.e., the element inserted at the last, is the first element to come out of the list.
Queues are based on the FIFO principle, i.e., the element inserted at the first, is the first element to come out of the list.
In this challenge I should write a combination of classes and methods which represent the stack and queues data structures and their terminologies, and then write tests to cover all the .
- I create a simple class stack that only allows pop, push, and peek operations, and a method to check the embty stack.
- In push method I check if the stack isn't embty then I take the value from the argument and make new node and assign the new node
- I assign the previuos head to the head.next
- I assign the new node to the new head
- if stack was embty I raise Exception
- In pop method
- I check if stack is embty and raise exception if yes.
- I create a new variable with name
prev
and assign the current top value to it. - I make the current top point to the node next to the current top (top.next)
- I return the
prev
- in peek method I just check if there is a top and return it's value, if there is no top, I raise Exception
- in isEmpty method I check if there is a top and return wether True or False depends on.
- I create a simple queue class that only allows dequeue, enqueue, and peek operations, and a method to check the embty queue.
- In enqueue method I check if the queue isn't embty then I take the value from the argument and make new node and assign the new node
- I assign the new node to the rear.next
- I assign the new node to the new rear
- if queue was embty I raise Exception
- In dequeue method
- I check if queue is embty and raise exception if yes.
- I create a new variable with name
prev
and assign the current front value to it. - I make the current top point to the node next to the current top (top.next)
- I return the
prev
- in peek method I just check if there is a front and return it's value, if there is no top, I raise Exception
- in isEmpty method I check if there is a front and return wether True or False depends on.
Time and Space was O(1) for all the methods, except the push method for stack was O(N)
Stack
- Push method: to add new node to the top of an previuos stack, or in embty stack.
- Pop method: to pop the node in the top and returns it's value, if there is a top.
- Peek: to print the value of the top node, witthout removing it, if there is a top.
- isEmbty: to check if a stack is empty.
Queue
- Enqueue method: to add new node either in an empty queue or not.
- Dequeue method: to remove the node in the front and returns it's value, if there is a front.
- Peek: to print the value of the front node, witthout removing it, if there is a front.
- isEmbty: to check if a queue is empty.
=======
Create a brand new PseudoQueue class. Do not use an existing Queue. Instead, this PseudoQueue class will implement our standard queue interface (the two methods listed below), but will internally only utilize 2 Stack objects. Ensure that you create your class with the following methods:
- enqueue(value)
- dequeue()
- create two stacks instances objects stack1 and stack2
- to enqueue we move all nodes in stack1 to stack2 two (pop from 1 push to 2)
- we push the new value to stack1
- then we bring back the values from 2 to 1 ( pop 2 and push to 1)
- to dequeue we return the top of stack 1
Time O(N) Space O(1)
queue = PsuedoQueue()
queue.enqueue(20)
print(queue) # 20
queue.enqueue(15)
print(queue) # 15 20
queue.enqueue(10)
print(queue) # 10 15 20
queue.enqueue(5)
print(queue) # 5 10 15 20
print(queue.dequeue()) # 20
print(queue) # 5 10 15
Create a class called AnimalShelter which holds only dogs and cats.
=====
write function that take a string as its only argument, and should return a Boolean representing whether or not the brackets in the string are balanced. {} [] ().
-
define a function take one argument which is string
-
use empty list. Each time, when an open parentheses is encountered push it in the list
-
when closed parenthesis is encountered
-
match it with the top of list and pop it.
-
If list is empty at the end, return Balanced otherwise, Unbalanced.
check balanced parentheses is to use embty list. Each time, when an open parentheses is encountered push it in the list, and when closed parenthesis is encountered, match it with the top of list and pop it. If list is empty at the end, return Balanced otherwise, Unbalanced.
Create a Node class
and a BinaryTree class
Define a method for each of the depth first traversals called preOrder, inOrder, and postOrder which returns an array of the values, ordered appropriately.
raise exceptions or errors when needed.
Create a BinarySearchTree class
and Define a method named add that accepts a value, and adds a new node with that value in the correct location in the binary search tree.
Define a method named contains that accepts a value, and returns a boolean indicating whether or not the value is in the tree at least once.
- Create a Node class with self.right and left
- Create a BinaryTree class, takes one argument root and create a node of it
- Define a method for preOrder
- Define a method for inOrder
- Define a method for post-order.
- Define a method for add in tree search
- Define a method for add in tree search
- Define a method named contains for check if element is in tree
pre-order: depth traversals root left right in-order: depth traversals root left right post-order: depth traversals root left right add: add a new node to binary search tree depend on its value contain: search for a value if it's included in a search binary tree
Find the Maximum Value in a Binary Tree
Create a method named find_max, take one arg assign root value to it and then start comparing with right and left until reach max return the max
def find_max(self):
self.value=0
def walk(current):
if current:
if current.value > self.value:
self.value = current.value
if current.right:
walk(current.right)
if current.left:
walk(current.left)
else:
return
walk(self.root)
return self.value
Find the Maximum Value in a Binary Tree
- create a mthod named breadth_first_traversal
- assigm a list with the root node to a varable called thislevel
- create a result variable list to append the results to it
- loop while thislevel is not embty
- create an empty list named next level to assign the next level nodes to it
- loop in thislevel, n times
- append the n value to result list and check if there are left and right and append them to nextlevel list
- assign the nextlevel to thislevel
- return result after finish while loop
def breadth_first_traversal(self,rootnode):
thislevel = [rootnode]
result =[]
while thislevel:
nextlevel = list()
for n in thislevel:
result.append(n.value)
if n.left: nextlevel.append(n.left)
if n.right: nextlevel.append(n.right)
print
thislevel = nextlevel
return result
Conduct “FizzBuzz” on a k-ary tree while traversing through it to create a new tree. Set the values of each of the new nodes depending on the corresponding node value in the source tree.
-
loop throght all nodes in the binary tree
-
check if:
- node capable to division by 3, replace the value with Fizz
- node capable to division by 5, replace the value with Buzz
- node capable to division by 3 and 5, replace the value with FizzBuzz
- node not capable to division by 3 or 5 , return the value
loop throght all nodes in the binary tree to check if : 1- node capable to division by 3, replace the value with Fizz 2- node capable to division by 5, replace the value with Buzz 3- node capable to division by 3 and 5, replace the value with FizzBuzz 4- node not capable to division by 3 or 5 , return the value
Write a function to sort a list in ascending order.
Time: O(n^2) The basic operation of this algorithm is comparison. This will happen n * (n-1) number of times…concluding the algorithm to be n squared. Space: O(1) No additional space is being created. This array is being sorted in place…keeping the space at constant O(1).
FOR i = 1 to arr.length
int j <-- i - 1
int temp <-- arr[i]
WHILE j >= 0 AND temp < arr[j]
arr[j + 1] <-- arr[j]
j <-- j - 1
arr[j + 1] <-- temp