Questions tagged [c++]
Programming questions are off-topic here. Do not ask questions about how to write code in C++. However, conceptual questions about computer science are more appropriate. See our help center for the scope of this site.
86
questions
0
votes
1
answer
31
views
time complexity of loops
what is the time complexity of:
for (i = 1; i <= n; i = 2*i)
for (j = 0; j < i; j++)
sum++;
?
I thought it is O(nlogn) since the otter loop ...
0
votes
0
answers
24
views
How to Think About Physical Design of Libraries in C++ When Considering the Deliverable's API?
Since design ideas, and even the concept of Physical Design (exactly where you put your files), are such a broad topic, may I give a definite example and ask for feedback on the example?
Suppose you ...
- 1
0
votes
0
answers
30
views
How to handle parentheis in Operator Precedence Parser?
I wrote this c++ code for a operator precedence parser.
it works perfectly for expressions without parentheis.
Eg: i*i+i is accepted
...
0
votes
1
answer
63
views
Constructing a Container for the Given Situation
I need to make a container in which I can store (x,y) as pairs, and for a given number 'a', I have to find a pair (p, q) such that p<=a and q is maximum possible.
Note the constraints: x>=1 and ...
- 13
3
votes
4
answers
118
views
Is there an elegant algorithm for applying multiple simultaneous search-and-replace operations to a string?
The operation I'm interested in is a slight twist on your standard search-and-replace operation, in that instead of a single pair of arguments (replaceme and ...
- 267
2
votes
4
answers
143
views
Best C++ STL container to store bodies in an N-body simulation?
I am writing an N-body simulation in C++ that has to be able to deal with large N ($N \le 10^6$).
Everything has been going well so far, but now that I have started to code in collisions between ...
6
votes
4
answers
3k
views
How does the linker know where to look for a function implementation in C++?
I am currently learning about how the compilation and linking works in C++. I think I kinda get how the compiler works, and that for a file to fully compile you don't need to have function ...
- 163
-1
votes
1
answer
43
views
Determining a faster/better approach for finding the pairs with minimum difference in an array
Wondering which approach is faster in terms of time complexity. In short, is having a single loop that clears out the vector every time there's a difference lesser than the minimum so far faster than ...
- 127
-1
votes
1
answer
135
views
Does the Posix read() system call for FILE* have an internal buffer in the kernel?
Does the answer depend on the number of bytes requested? If it is forced to keep a buffer due to some unknown device/diver, can it optimize and skip the buffer if it's going to be a disk read? I'm ...
- 1
0
votes
1
answer
104
views
Finding whether a point lies on the boundary of an geometrical object or not?
Suppose I have the mesh of an geometrical object (Interval in 1d, Region in 2d, Volume in 3d). How can I find out whether a point lies on its boundary or not?
I am looking for algorithms with ...
- 111
0
votes
2
answers
79
views
Retreive farthest value to the right of element
I reached a subproblem where I have an array of numbers (0 to n) un-sorted and I want to retrieve, for each element, the index of the farthest value from it to the RIGHT of that element.
Like
...
- 123
0
votes
1
answer
42
views
Why dont I need to memoize maxHeight in the problem below
I see this occasionally when solving Dynamic programming questions. I like to solve dp questions using recursion, then Memoize it based on the number of parameters I pass to the recursive function.
...
- 65
0
votes
0
answers
56
views
Best way to sort two arrays in correspondence in a manner that coordination between them does not change
Let me put it this way. I have two arrays A and B. Array A contains manufacturing dates of cars, and Array B contains corresponding car model names. A and B are in correspondence. Now I want to sort ...
2
votes
1
answer
114
views
Looking for a proof on why my algorithm in codeforces works
I'm trying prove the correctness of my algorithm.
This is the problem in codeforces: https://codeforces.com/contest/1428/problem/C
Here's my code in C++ which was accepted:
...
1
vote
1
answer
391
views
Algorithmn for SIMD matrix multiplication
I've been trying to implement a program for matrix multiplication of multiple of 4 (ex: 4x4, 8x8, 16x16, etc.) and while I my program works for 4x4 matrix, it only fills the first 4 row of every ...
1
vote
1
answer
55
views
How are pointers interpreted differently to variables in a control flow graph (CFG)?
I have been working with control flow graphs and believe I understand how they function when describing dependencies between variables. For example, given the operations:
...
- 113
1
vote
0
answers
62
views
Completely clueless on computer science assignments [closed]
This question isn't very technical, but I'm in desperate need of help and I thought this would be the best place to post this question. I'm in an computer science course, data structures and ...
- 11
1
vote
0
answers
71
views
finding max element in a min-max heap structure
I am trying to implement min-max heap structure
A min-max heap is a data structure that is identical to a binary heap, but the heap-order property is that for any node, X,
at even depth, the element ...
2
votes
3
answers
183
views
Why doesn't the compiler typecast the pointer and remove the error? (C++ Programming)
int *numPtr;
double num;
numPtr = #
This code shows an error as pointer points to data of different datatype. But why does it show the error? Why doesn't ...
- 21
0
votes
0
answers
42
views
Solving course scheduling with prerequisite problem
How should one go about this kind of problems? I'm supposed to use a graph structure for this.
Say I have a file containing a couple of courses with their prerequisites.
I have to organize the ...
- 1
0
votes
0
answers
116
views
Bin packing problem using bit masking
We have n box and an array of weights, where weight of ith box is given by arr[i]. We have a container which can carry a maximum weight of w. Now we have to find minimum number of containers required ...
- 31
1
vote
0
answers
1k
views
Minimum no of swaps to be done in an array such that, no two adjacent elements are same
Given an array of size n, find minimum number of swaps required, so that no two adjacent elements are equal. For ex-
n = 6, a[] = {1, 1, 5, 2, 5, 5}, answer = 1, ( swap a[0] with a[4] or
a[5] )
n = 8,...
- 31
6
votes
1
answer
1k
views
How are extremely large integers stored and implemented in programming languages?
We have data types like int and long etc. which can store just a few bytes of integers.
But when we are implementing ...
- 139
3
votes
0
answers
36
views
Subtype Check with Type DAG
Trying to understand how compiler/static-type-checker checks for subtyping, I run into 2 problems.
1. Reachability in DAG
Since both Python/C++ support multiple inheriatnce, the types can be ...
- 131
1
vote
1
answer
409
views
Find non common numbers in two arrays
Given two arrays of integers, please write a function that returns all elements present in one of the two arrays but not both. E.g. f([ 1, 3, 5 ], [ 1, 2, 4, 5 ]) -> [ 2, 3, 4 ]
I know I can do ...
- 11
1
vote
2
answers
248
views
Fast computing of a matrix power for large integer values in C++
I'm working with squared matrices that can be quite large, for instance, a M = 50 x 50 matrix.
My objective is to compute the power of the squared matrix ...
- 113
3
votes
0
answers
120
views
How to detect when to use radix sort in runtime
I'm implementing a stable integer sorting algorithm, I've chosen radix sort. I've tested LSD vs MSD implementation, wrote MSD/LSD hybrid implementation to reduce bandwidth pressure. The repo is here: ...
- 131
1
vote
1
answer
99
views
virtual machine based programming languages vs low level
I took programming lecture it was about C/java and how to build compilers, so I wanted to know.
As far I see, languages like Java/C# are developing their virtual machine CLR/JVM with good base and are ...
- 197
0
votes
1
answer
612
views
In C++ how does "sizeof(array)/sizeof(array[0])" give the number of elements in an array? Why isn't it affected by the length of each element?
I'm playing around with C++ and was looking at how to loop through an array of unknown length. The following code was suggested and works perfectly from the little testing I've done:
...
1
vote
2
answers
1k
views
Which goes first stl or data structures and algorithms?
So I'm a newbie to c++. I know the basic concepts of c++ as I have already learnt c language. For competitive programming DSA is very important. But I don't know any STL functions.
Is it possible to ...
- 11
0
votes
1
answer
200
views
Combinations (repetition not allowed & order not important)
How to compute a table of numbers (all possibilities), where repetition is not allowed and order is not important.
Example:
I have a set of prime numbers. In this example I have four: {3,5,7,11}, but ...
3
votes
1
answer
145
views
Why is the address-of operator in C/C++ represented with the "&" symbol?
I've started learning C++, and I know a little bit of C. Something that always struck me as somewhat off was that the address-of operator is represented with the seemingly random ampersand (&) ...
- 31
1
vote
2
answers
71
views
Practice of setting parallelism as the default behaviour
This is a soft, and probably also an opinion based question.
Suppose I am writing a library in C++ for the purposes of working with financial data. My goals are:
Since I work with big data, I want to ...
- 113
1
vote
1
answer
58
views
Reason behind declaring iteration variables on a method level
Lately, I have been in touch with some C++ snippets, and I have a very strange observation on the tiny detail:
Most of the times, I see, that people declare iteration variables outside of the for/...
1
vote
1
answer
64
views
How to remove an ordering requirement from a board game simulation?
The Problem:
I'm trying to simulate part of the game tantrix which is a board game played with hexagonal tiles. Each tile has 3 lines of different colors that each start at one side of the hexagon ...
- 123
-1
votes
1
answer
58
views
Time complexity of similar-looking functions
What is the time complexity of the following functions, and why?
...
- 15
1
vote
1
answer
229
views
What is the minimum number of parts required to split the sequence S to in order to obtain sequence T?
Suppose a person has a sequence (S) consisting of integer numbers and would like to split the sequence into a
number (possibly one) of continuous parts. For each part independently, I then choose any ...
0
votes
1
answer
91
views
The probability that a person succeeds to pick the longest stick from a randomly ordered n sticks of distinct lengths following the optimal strategy?
To begin with, consider two persons(Px and Py) are playing a game. Px is the organiser of the game who has n sticks of distinct lengths and displaying them one by one to Py in a random order, with ...
2
votes
1
answer
47
views
printf("%d",~5); prints out -6 why is that?
I was reading the book "Computer systems: A programmer's perspective" and saw that the operator, "~", is a NOT operator. When I use it to NOT positive integers, it returns the ...
1
vote
1
answer
319
views
Time complexity of the travelling salesman problem (Recursive formulation)
According to this recursion formula for dynamic programming (Held–Karp algorithm), the minimum cost can be found. I entered this code in C ++ and this was achieved (...
- 21
0
votes
1
answer
292
views
Calculate the sum of all sub-arrays with given indices
I am new to Algorithms and Competitive Coding. I have a problem as follow:
For this problem, the time limit is 1 second so brute force is not a good way to solve. The only way I think must be Dynamic ...
- 111
1
vote
1
answer
942
views
Unordered data structure with fast insertion, deletion, and iteration
So, I need a data structure that would support the following operations:
Add an element to the structure and get some "handle" for that element
Retrieve an element by a handle
Remove an ...
- 121
0
votes
0
answers
31
views
What is meant by the statement "Data is inactive but information is active"?
I came across the statement "data is inactive but information is active" while reading differences between data and information. What is meant by this statement?
1
vote
1
answer
269
views
Is C++ considered a language with high or low orthogonality?
I'm looking to make a comparison of regularity in languages - specifically orthogonality.
If I were to say Java is weak in terms of orthogonality and Haskell stronger, where would C++ sit and why?
- 113
-1
votes
1
answer
54
views
doubts on cin and scanf [closed]
i spent literally 5hrs trying to figure out, why the value of n is 1 for my second test case ( which begins at line 12 ) , but i am unable to, could you help me with that?
...
0
votes
2
answers
440
views
Intuition behind the Reversal Algorithm [ Rotation of Array ]
I know that the below program uses Reversal algorithm to rotate an array's elements to k positions to the right. But how does the Reversal algorithm works? It seems kinda magic to see. Can somebody ...
- 1
0
votes
1
answer
283
views
How to Sort 2D array with out 1D array
Hello I am a new Computer Science student
Ok, so I am trying to sort the 2D array I know you can actually sort a 2D array by copying it into a 1D array sort it using any Algorithm, and then place ...
1
vote
1
answer
102
views
Cancellation in C++
I am trying to figure out what the problem with the following expression in C++ is:
y=std::log(std::cosh(x));
My first intention was that there might occure a ...
- 58
2
votes
1
answer
118
views
Math behind leetcode problem 47 permutations II
Please tell me why the expression i>0 && nums[i] == nums[i-1] && !used[i-1] works on getting unique permutations. And what is the math behind it?
...
- 23
2
votes
4
answers
128
views
How do compilers assure stability?
Suppose you need a c compiler. It would be preferable to write that compiler in a c-like language, given the complexity of a compiler of that degree. At best, the c compiler would be written in c, but ...
user123355