# Questions tagged [lists]

The tag has no usage guidance.

79 questions
Filter by
Sorted by
Tagged with
30 views

### Need help with beginner python [closed]

Here is the question 5.2 Write a program that repeatedly prompts a user for integer numbers until the user enters 'done'. Once 'done' is entered, print out the largest and smallest of the numbers. If ...
96 views

### Design a data-structure $BankAccount$ that supports the following operations in constant time complexity

Problem: Design a data-structure $BankAccount$ that supports the following operations in $\underline{\text{constant time complexity}}$. Meaning $O(1)$. $Init()$ - initializes bank account $L$ with ...
• 233
1 vote
36 views

### Why doesn't this implementation of Skip List simply return the current node when its key is equal to the query key?

I was studying Skip Lists in section 3.10 of Advanced Data Structures by Peter Brass and was confused about a detail of how the search algorithm in implemented. (This is self-study, not homework). The ...
25 views

### Good sources that treat "sliding window" whiteboarding-style problems?

This is a reference request for algorithms textbooks that address the common "sliding window" problems that come up in whiteboarding. If not textbooks per se, I'm looking for a more ...
• 115
1 vote
24 views

### Finding max values at a point given a list of ranges

In coding competitions I usually see problems that involve dealing with values in given ranges. A typical example is, given a list of 3-tuples defined as so ...
• 111
191 views

### Is there another type of list than arraylist and linked-list?

My question is not about how arraylists or linked-lists work, but why there aren't other types of lists. From my understanding, memory is accessed linearly by adresses. Thus, you have the choice to ...
• 187
1 vote
36 views

I am reading Data Structures and Algorithms by Alfred Aho, Jeffrey Ullman, et al. In the section about lists it's said: We should note that a position in a linked-list implementation of a list ...
• 113
156 views

### What do you call a data structure containing multiple lists?

I was thinking about a data structure to make concatenation of lists easier, something that contains multiple lists (in a sequence) internally, but can be treated as a single contiguous list. I know ...
• 103
1 vote
55 views

### A silly doubt on Computer Science Objects: Arrays, Lists, Strings, and Vectors, are they the same concept?

First of all I'm a Physics Student and I've been arguing with my brother concerning the usage and the fundamental meaning of a vector on Computer Science (CS). I) Vectors A vector have a axiomatic ...
• 141
1k views

### What is the difference between python list and c++ vector?

I read about the similarities between the python list and c++ vector and it looks as if the only difference is python list is heterogeneous. Are there any other differences? How are they both ...
• 125
1 vote
46 views

### What is the theoretical result of flattening a list containing only itself?

Consider the following python code X = [None] X[0] = X This has many fun properties such as X[0] == X and ...
20 views

### Generate slice that contains element

Suppose I have the array: [2, 3, 4, 5, 6, 7, 8, 9] Now based on few parameters: current_item - currently selected item. <...
• 123
1 vote
57 views

### What is the name of the data structure that is a tree on the backend but has a list like API?

I'm looking for the name of a data structure. It is organized like a balanced tree. The elements need not be comparable. Instead of asking if the tree contains a thing (like you would with a ...
• 486
1 vote
66 views

### Historical examples of bad security policies/mechanisms that we got stuck with through switching costs?

The following process seems to be a recurring one: Initial design. Commercial organisations invent and implement a design that seems at the time to work. Problem discovered, new design suggested. Due ...
• 3,474
1 vote
459 views

### Sorting a large list of test scores

You have a large list (say N > 10000) of test scores which you would like to sort. The test scores are between 1 and 100. What is quickest way to sort the list? First thought. We have a O(N log N) ...
• 143
1 vote
379 views

### Difference between a skiplist and an Indexable skiplist

Can someone please help me understand the main differences between a simple skiplist and an indexable skiplist? How does an indexable skiplist work in comparison to a normal skiplist (maybe a little ...
• 11
159 views

48 views

### Abstract Data Type

I have been studying data structures. In that I have come across topics like Array being defined as Power set of cross product of set of objects and set of natural number and list being defined as ...
1 vote
36 views

### Abstract Data Types and their Implementation [closed]

I wanted to know if there is good resource to learn about the ADTs like set ADT, list, array, boolean etc and their implementation.
1 vote
46 views

### Terminology Questions: Data-structure consisting of lists without repetitions

I've google around and have been unsuccessful in finding a name for a data-structure consisting of a list whose elements are unique. I've seen "unique sorted lists", but I'm looking into the more ...
392 views

### Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?

Context, I have a geometric algorithm that is sensitive to collinear points and receives as input a list of points in 2D generated randomly. Suppose that I have a Boolean function nonCollinear(x,y,z) ...
• 265
832 views

### Fastest way to search a word in a word list?

I have a word list like "English Open Word List" used to create word games. The list is in txt file with space between words, like; aa aah aahed .........and so on. I want to search it while typing ...
42 views

### create distance (ment is high difference between values) between Vertexes in a list

Given are some vertexes, arranged in a list (so there every vertex is connected with two others and there are no circles in the graph). Every Vertex contains one number. Now you can lower the Number ...
174 views

### Big O Notation for Return List is it O(N)?

what is the Big O for Returning List? aka return list (e.g. list=[1,2,...]) is it o(1) or o(n) and is there a good website for average big o for different operations including sorting for simple ...
• 101
14k views

### Time complexity to check if there is an edge between two nodes in an adjacency list

I know that the time required to check if there exists an edge between two nodes in an adjacency matrix is $O(1)$ because we can access it directly (i.e: $M[i][j]$). However, I didn't really get why ...
• 103
1 vote
42 views

### How would I go about determining popularity and relevance among articles and use it to improve my search algorithm

Disclaimer: First of all I've had a lot of trouble finding the right stack exchange site for this question and I don't know if it's correct here either. The Problem: I'm working on a search algorithm ...
• 123
290 views

### Remove duplicates of first elements of pairs

A list of pairs is given using Python. I want to remove duplicate occurrences of the first element of the pair leaving only one occurrence of each first element paired with the highest second element ...
• 33
201 views

### List of scheduling problems and their statuses

As of 1993, there are 4536 scheduling problems, 3821 were proven to be $NP$-hard, 417 polynomially solvable, and 298 still open. Where can I find the most up-to-date list of scheduling problems and ...
• 152
1 vote
64 views

### Is there a name for the "tree" aproach to listing things?

I've only been studying computer science for a few weeks, so I apologize if this is a silly or naive question. Suppose we're trying to list all elements of the set C(r) = \{(x,y,z) \in \mathbb{N}^3 ...
• 134
1 vote
120 views

### Partial intersection of 10 sorted lists of integers

Suppose I want to find the numbers that appear in at least 3 of the 10 sorted lists, is there an efficient way to do it apart from iterating over all 10 of them in parallel?
• 171
39k views

### When are adjacency lists or matrices the better choice?

I was told that we would use a list if the graph is sparse and a matrix if the graph is dense. For me, it's just a raw definition. I don't see much beyond it. Can you clarify when would it be the ...
• 341
70 views

### General name for linked lists based on hashes

I am thinking of a particular datastructure, but don't know the name of it. A sequence of elements may be modeled by a collection of some X, where each X consists of: The element, serialized as a ...
79 views

### Expected Time for LookUpSkipList

A skip list Let C(k) = the expected length of the path that raises k levels backwards. Thus C(0) = 0 For any node P in the path, with k levels higher to go, there are two cases: P is a node of ...
• 123
105 views

### Gauss-Jordan using stacks and list

I have a homework assignment in which I need to write an implementation of Gauss-Jordan with complete pivoting. Complete pivoting is a modification to the basic Gauss-Jordan algorithm in which rows ...
508 views

### How to use structural induction to prove law on lists

I want to prove that the following equation holds using structural induction on (finite) lists ...
2k views

### Why does linear search have $\frac{n}{2}$ comparisons on average?

I'm reading the Wikipedia page on Linear Search and it is mentioned that there are on average $\frac{n}{2}$ comparisons. I tried working this out on my own. First I considered the number of cases. ...
• 155
4k views

### What's the fastest way to find the Kth smallest value in an unsorted list without sorting?

My initial algorithm: Compare element 0 with every other element, keeping track of how many elements are less than it. Repeat for each element until an element that is greater than exactly (k-1) ...
• 213
206 views

### Efficiently finding duplicates in lists of numbers

I decided to try my hand at solving the knapsack problem. My idea involved generating $i$ tables, where $i: 1 \le i \lt n$, and each cell of an $i$ table contains one of the possible sums of the ...
• 1,587
2k views

### Lambda calculus lists construction explanation

I have the following notes that introduce how lambda calculus handles lists. They go as follows: A list is something we can match on and deconstruct if it is not empty: ...
• 2,220
56 views

### Description of lists with functions in LISP

I have been given the following implementation of basic list functions in LISP: ...
• 2,220
1 vote