zklib's People
zklib's Issues
Make all lists an opaque structure for API users and only expose opaque pointers
The intent of this change is to:
- Simplify the API. The user does not need to know or care about internal data.
- The struct definition can change without impacting any of the using code.
- It prevents misuse of internal struct data.
Remove duplicates from an unsorted linked list/array
Remove Duplicates From an Unsorted Linked List/Array
The problem of removing duplicates from an unsorted linked list or array involves eliminating any duplicate elements while maintaining the order of the remaining elements.
Problem Description
Given an unsorted linked list or array, the task is to remove any duplicate elements from it. The resulting linked list or array should only contain the unique elements in their original order.
For example, consider the following input:
Input: [2, 4, 1, 3, 2, 4]
Output: [2, 4, 1, 3]
In this example, the input list/array contains duplicate elements (2 and 4) that need to be removed. The resulting list/array should only include the unique elements (2, 4, 1, 3) in their original order.
Requirements
The requirement is to implement a function that takes an unsorted linked list or array as input and removes any duplicate elements from it while preserving the order of the remaining elements.
Applications
The problem of removing duplicates from an unsorted linked list or array has applications in various scenarios, including:
- Data Preprocessing: Before performing analysis or computations on data, it is often necessary to remove duplicate entries to ensure data accuracy and consistency.
- Data Cleaning: Removing duplicates is a common step in data cleaning pipelines, where duplicate records can skew analysis or cause data quality issues.
- Algorithmic Challenges: The problem serves as a common coding challenge to test a candidate's understanding of data structures, algorithms, and problem-solving skills.
These are some examples of how the "Remove Duplicates From an Unsorted Linked List/Array" problem can be applied in practical scenarios. The specific application may vary depending on the requirements and context of the data processing or algorithmic problem.
Implement a function that find the intersection between two list.
This function could have the following prototype:
zk_slist_t * zk_slist_intersection(,zk_slist_t * list1, zk_slist_t * list2);
It should return the node where the intersection starts. If no intersection is found, NULL is returned.
In order to make sure both lists have an intersection, one can call zk_slist_has_intersection()
Merge K sorted Lists
Given an array of k linked-lists lists, each linked list is sorted in ascending order.
A function shall be created to merge all the linked-lists into one sorted linked-list and return it.
Bellow some ideas for the prototype:
zk_slist * zk_slist_merge( zk_vector * lists);
zk_dlist * zk_slist_merge( zk_vector * lists);
zk_c_slist * zk_slist_merge( zk_vector * lists);
zk_d_slist * zk_slist_merge( zk_vector * lists);
Example:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
Palindrome kinked list and array
Given the head of a linked list/array, return true
if it is a palindrome or false
otherwise.
Example
Input : [1,2,3,3,2,1]
Output: true
Input: [2,1]
Output: false
Possible functions signature:
bool zk_slist_is_palindrome(zk_slist* list);
bool zk_dlist_is_palindrome(zk_dlist* list);
bool zk_c_slist_is_palindrome(zk_c_slist* list);
bool zk_c_dlist_is_palindrome(zk_c_dlist* list);
bool zk_vector_is_palindrome(zk_vector* vec);
Smallest range covering elements from K Lists/Arrays
Given K sorted lists/arrays, implement a function that finds the smallest range containing at least one element from each list/array. The resulting range should have the smallest span between the maximum and minimum values among all possible ranges.
Here is an example to illustrate the problem:
Input:
K = 3
List 1: [4, 10, 15, 24]
List 2: [0, 9, 12, 20]
List 3: [5, 18, 22, 30]
Output: [20, 24]
In this example, the smallest range that covers at least one element from each of the three lists is [20, 24]. It includes the elements 24, 20, and 22 from List 1, List 2, and List 3 respectively.
zk_vector * zk_slist_smallest_range(zk_vector * lists);
zk_vector * zk_dlist_smallest_range(zk_vector * lists);
zk_vector * zk_c_slist_smallest_range(zk_vector * lists);
zk_vector * zk_c_dlist_smallest_range(zk_vector * lists);
zk_vector * zk_vector_smallest_range(zk_vector * lists);
Rotate List/Array
Rotate List/Array
The "Rotate List/Array" problem involves rotating a given list or array by a specified number of positions. The goal is to shift the elements of the list/array to the right or left by the given number of positions.
Example
Input: [1, 2, 3, 4, 5], k = 2
Output: [4, 5, 1, 2, 3]
In this example, the input list/array is rotated by 2 positions to the right. The last two elements (4 and 5) move to the beginning of the list/array, while the remaining elements shift to the right.
Requirements
Given a list or array and a number k, implement a function that rotates the list/array by k positions. The resulting list/array should have the elements shifted to the right or left by the given number of positions, preserving the relative order of the elements.
Applications
- Data Transformations: Rotating a list/array can be useful in transforming data representations or preparing data for further processing or analysis.
- Array Manipulation: The problem provides a way to manipulate the order of elements in an array, which can be useful in various array-based algorithms or operations.
- Data Encryption: In cryptography or data security, rotating elements in a list/array can be part of encryption or decryption algorithms to achieve data scrambling.
- Algorithmic Challenges: The problem serves as a common algorithmic challenge to test a candidate's understanding of list/array operations and problem-solving skills.
These are some examples of how the "Rotate List/Array" problem can be applied in practical scenarios. The specific application may vary depending on the requirements and context of the software development or problem-solving task.
Add commit-lint to repository and pipeline
Run format lint on CI
Swap nodes in a list
Given the head of a list and two integers i
, j
the function should swap both nodes
in the list. The function returns the head of the new list with nodes swapped.
Example
Input: 1->2->3->4->5 , i=2, j=5
Output: 1->5->3->4->2
Note: nodes and not the only the data need to be swapped
Possible functions signature:
zk_slist* zk_slist_swap( zk_slist* list, size_t i, size_t j);
zk_dlist* zk_dlist_swap( zk_dlist* list, size_t i, size_t j);
zk_c_slist* zk_c_slist_swap( zk_c_slist* list, size_t i, size_t j);
zk_c_dlist* zk_c_dlist_swap( zk_c_dlist* list, size_t i, size_t j);
Implement a function to check if two list has intersections
The function could have the following prototype:
bool zk_slist_has_intersection( zk_slist_t* list1, zk_slist_t* list1);
It should return true
if the lists have any node in common (an intersection) otherwise false
.
Find the middle of the linked list
Given the head of a linked list, return the middle node of the linked list. In case there are 2 middle nodes (the list has an even number of nodes) then return the second middle node.
Examples
-
Input: 1->2->3
-
Output: 2->3
-
Input: 1->2->3->4
-
Output: 3->4
Possible functions signautes:
zk_slist* zk_slist_middle(zk_slist* list);
zk_dlist* zk_dlist_middle(zk_dlist* list);
zk_c_slist* zk_c_dlist_middle(zk_c_slist* list);
zk_c_dlist* zk_c_dlist_middle(zk_c_dlist* list);
Implement a functions push_front, push_back, pop_front, pop_back.
The functions should be generic and have the following prototypes:
T* zk_push_front( T* list, void * data); // Prepends the given element data to the beginning of the container.
T* zk_pop_front( T* list); // Removes the first element of the container.
T* zk_push_back( T* list, void * data); // Appends the given element data to the end of the container.
T* zk_pop_back( T* list); // Removes the last element of the container.
Where T
could be the following type:
zk_slist
- single linked listzk_dlist
- double linked listzk_c_slist
- circular single linked listzk_c_dlist
- circular double linked list
Implement a function to sort a single linked list.
This function could have the following prototype:
zk_slist_t *zk_slist_sort(zk_slist_t *list, zk_compare_t func, void *user_data);
It should sort a zk_slist_t using the given comparison function.
The user should provide a comparison function which is passed the data from 2 elements of the zk_slist_t
and the user_data
. This function should return 0 if the 2 elements of the zk_slist_t
equal, a negative value if the first element comes before the second, or a positive value if the first element comes after the second.
Function to detect if there is cycle in lists
Implement a function that can detect the presence of a cycle within a linked list.
Given the head of a linked list, return the node
where the cycle begins. If there is no cycle, return null
.
zk_slist * zk_slist_has_cycle(zk_slist * list);
zk_dlist * zk_dlist_has_cycle(zk_dlist * list);
Note: could be implemented using the technic of the slow and fast pointer.
Split linked list and vector in parts
Given a linked list/vector and a number k
, implement a function that splits the linked list/vector into k
parts, ensuring that each part has a balanced distribution of nodes
. The resulting parts should be stored and returned as an array or any appropriate data structure.
Here is an example to illustrate the problem:
- Input: 1 → 2 → 3 → 4 → 5, k = 3
- Output: [1 → 2], [3 → 4], [5]
Application:
The application of the "Split Linked List/Vector in Parts" problem can be found in scenarios where there is a need to divide a linked list/vector into smaller, manageable chunks. This can be useful for parallel processing, distributed systems, or situations where processing or analysis of large linked lists/vectors needs to be performed in a distributed or parallel manner.
Possible functions prototype:
zk_vector * zk_slist_split(zk_slist* list, size_t k);
zk_vector * zk_dlist_split(zk_dlist* list, size_t k);
zk_vector * zk_c_slist_split(zk_c_slist* list, size_t k);
zk_vector * zk_c_dlist_split(zk_c_dlist* list, size_t k);
zk_vector * zk_vector_split(zk_vector* list, size_t k);
Change function API to return execution status when appropriated
The current API does not report any hint to the user in case of error occurred during function execution which does not allow the user of the API to know where an error occurred or to recover from it. This issue aims to define the error type which could be an enum
with error codes to be used as functions return when appropriated.
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.