I am tutoring students in Java II this semester and one of the programming assignments is to determine if a number is prime number, and if it is not a prime number, to determine all the factors of the given number. A prime number is any number, N, that only has factors of 1 and N. For example, 11 is a prime number, because it only has factors of 1 and 11. The number 6 is not a prime number, because it has factors of 1, 2, 3, and 6.
Reversing a linked list is a popular technical interview question and one I see a lot on popular programming challenge websites. The programming challenge typically has a custom LinkedList Class with a Reverse Method that the developer needs to complete to properly reverse a linked list. A Node Class is provided that represents each node in the linked list, and the LinkedList Class has a pointer to the head node. Let's solve this programming challenge in Python so we can solve it for our next technical job interview.
We've looked at using linear search to find a node in a linked list, inserting nodes in linked list to maintain a sorted list of values, and even created Stack and Queue abstract data structures using linked list as the underlying data structure. Now let's turn our attention to a very popular programming challenge using linked lists - detecting a cycle in a linked list.
In the previous tutorial I discussed how to code a Stack Abstract Data Type using a linked list as the underlying data structure. In this tutorial I will create a Queue Abstract Data Type using a linked list. The queue will implement the two most common operations of enqueue and dequeue to add and remove an item from the queue. Although a linked list will maintain the state of the queue, the software developer will not interact with the linked list directly. The details of the algorithm and data structures used to perform dequeue and enqueue are encapsulated by the custom Python
In recent tutorials I have been discussing linked lists. Linked lists are a fundamental data structure in computer science and a popular topic in technical interviews and programming challenges. In the first tutorial I discussed using linear search to find a value in a linked list, and in the second tutorial I discussed inserting a new node in a linked list.
Earlier I demonstrated how to search a linked list using linear search, which is a popular technical interview question and programming challenge to test one's knowledge of computer science data structures and algorithms. Another popular coding challenge is to insert a new value in a linked list, which is what I would like to demonstrate in this tutorial. However, let's add a twist. Let's insert integer values so that the linked list maintains the list of integers in ascending numerical value.
A linked list is a fundamental data structure in computer science and a common subject of technical job interview questions and programming challenges. One of the simplest challenges, and a great starting point for learning linked lists, is to search a linked list to see if it contains a given value.
Shell sort is a sorting algorithm based on insertion sort. Insertion sort uses a fixed distance of 1 when it compares values during the sorting process. Insertion sort moves from left-to-right and picks the next value in the unsorted portion of the list and inserts it into its proper position in the sorted portion of the list. Shellsort uses a similar algorithm, but compares values over greater distances, called gaps. The benefit of comparing values over larger distances is that shell sort can quickly move small and large values to the front and end of the list, reducing the overall number of exchanges done by insertion sort. The final pass or gap used by shell sort is 1, which is insertion sort.
Cocktail sort is a sorting algorithm, like comb sort, that attempts to improve the performance of bubble sort by eliminating turtles. Turtles are small numbers at the end of the unsorted list that slowly move to the front of the list one position at a time using bubble sort. Turtles greatly reduce the performance of bubble sort by increasing the number of passes bubble sort must make through the list. Although cocktail sort, comb sort, and bubble sort are considered impractical for use in real-world applications, there is a lot to gain from understanding them algorithmically in a computer science classroom.