FAQ Database Discussion Community


What's the algorithm to assign people their most preferred value based on a list of their top choices?

algorithm,sorting,language-agnostic,ranking,choice
Let's say users input their top three (or N) preferred baseball positions: // first element of each list being most preferred userA = ["backcatcher", "center field", "short stop"]; userB = ["pitcher", "backcatcher", "center field"]; userC = ["pitcher", "center field", "short stop"]; userD = ["short stop", "backcatcher", "pitcher"]; ... users =...

What is a runtime environment for supposedly “no-overhead” systems languages?

language-agnostic,runtime
Specifically, I'm talking more about C++ and Rust than others. I don't understand how C++ has a "runtime" in the sense that Java and C# have a runtime--while Java and C# run on top of a virtual machine with its own encapsulated abstractions and such, I don't get how C++...

C - What should scripts do in programs [closed]

c,scripting,lua,language-agnostic,scripting-language
If I want to create a game in C with SDL for example, is there a reason of why I should use a scripting language like Lua with it (since alot of commercial games uses a scripting language)? I have heard that scripting languages often are faster to write and...

Where is the Balance Between Dependency Injection and Abstraction?

java,oop,design-patterns,dependency-injection,language-agnostic
Many Architects and Engineers recommend Dependency Injection and other Inversion of Control patterns as a way to improve the testability of your code. There's no denying that Dependency Injection makes code more testable, however, isn't it also a completing goal to Abstraction in general? I feel conflicted! I wrote an...

In what kind of code does it makes sense that `typeof NaN` is 'number'

javascript,language-agnostic
As far as I remember I have been aware of this peculiarity where the type of NaN is a number. Now, some people go out of their way to defend this as a 'common computer science principle', but in the end it still feels wrong to me (just because something...

Origin of inheritance in programming languages

oop,language-agnostic
What was the first language to support inheritance? Was code re-use the design intent of the feature?

How to handle exceptions during logging?

c#,exception,logging,exception-handling,language-agnostic
I thought of adding a simple logging mechanism within my application, in order to log the details of the errors that occur during operation of the application. private TextWriter m_TextWriter; private List<string> m_LogEntries; // buffered log messages // ... public void Write(string message) { m_LogEntries.Add(message); if (m_LogEntries.Count >= m_LogEntriesLimit) {...

Counting up “broadly”: Not 0,1,2,..,9,10,11,..,99 but 00, 01, 10, 11, 02, 12, 20, 21, 22, 03, .., 99

math,count,language-agnostic,numbers,sequence
When a counter is made up from a fixed number of digits (2 in the title), standard counting-up works by incrementing from the least to the most significant digit and upon overflow reset it. I want to count differently: A 4 digit number in base-10 would be counted up in...

Alternative to multiple or statements in an if block in Javascript

javascript,language-agnostic
I have to check for if(x == "An" || x == "Apple" || x == "A" || x == "Day" || x == "Keeps" || x == "The"....and so on){ return true; } else{ return false; } Is there a better way to write the if statement for large number...

How many times is x=x+1 executed in theta notation in terms of n?

algorithm,language-agnostic,time-complexity,complexity-theory,analysis
I'm taking Data Analysis and Algorithms in the Summer. The question: Find a Θ-notation in terms of n for the number of times the statement x = x + 1 is executed. for i = 1 to 526 for j = 1 to n^2(lgn)^3 for k = 1 to n...

How to find the endpoint of a vector giving its length and startpoint

math,vector,language-agnostic,geometry
I have a vector V starting at x,y with velocity dirx,diry (for example 2,3). I want to know the cooridinates of the end point of the vector if its length (i guess the norm) was equal to 40 for example. Sorry, my math knowledge it quite low, many thanks in...

gethostbyname and endianness - how are the bytes returned?

winapi,language-agnostic,winsock,endianness
On my (Intel) x86 machine, I've noticed that if I printf the results of gethostbyname for localhost, I get 100007F, even though the MSDN documentation states it should return the IP in network byte order, aka big endian. I searched a bit and found this topic. Based on the answers...

How is the following text transposed into this hex output?

text,language-agnostic,hex,translation
INPUT: 00:00:00:00 a b c d // NEWLINE separating each letter OUTPUT: Scenarist_SCC V1.0 00:00:00:00 9420 13d6 9723 6180 1376 9723 6280 94d6 9723 e380 9476 9723 6480 9420 942c 942f 00:00:01:00 942c Here is some information about the format, but I'm struggling to understand how this text transformation is...

Making a consistent API, what's less surprising?

design,architecture,language-agnostic
I have an API where there are property accessors like: int foo() Sometimes the properties can be "null". Since an int cannot be null, this is handled with a extra property to check null. bool hasFoo() What happens when people call foo() when it's null? Rather than have undefined behavior,...

Algorithm to determine an order of processing/sorting

algorithm,sorting,language-agnostic,order,priority
I've got an application that has to return 100s of user-creatable documents in a user-configurable, deterministic and consistent order. What is the best way to acheive this? I was hoping to use an enum (eg High, Medium and Low priority) as this keeps things simple and closed, but the ordering...

Calculate distance on a grid between 2 points

java,math,language-agnostic,distance
I need to calculate the distance on a grid between 2 points. The movement allowed is horizontal and vertical as well diagonal to the next neighbor (so 45 degree rotations). So Manhattan distance is not an option. Also Euclidean distance is not an option cause then it does not move...

Turn an ascii character code to a value between 0-26

algorithm,language-agnostic,ascii
Hello everyone today I have a question concerning the math involved in turning ascii code into a value between 0-26. With lowercase letters it's simply the characters code - 65. However if I run into capital letters it's no longer the case. I was wondering what would be the algorithm...

Consistency guarantee of file system regarding sequential write

io,language-agnostic,consistency,os-agnostic
My program (only 1 process and 1 thread) sequentially write n consecutive chunks of data to a file on a HDD (regular kind of HDD) using plain old write system call. It's like some kind of append-only log file. After a system crash (power failure, not HDD failure), I read...

Is Swift the only (mainstream) language with overflow checking arithmetic?

performance,swift,language-agnostic,arithmetic-expressions
I started studying Swift language today. I've leaned up to basic and advanced operators. To me, the fact that all the default arithmetic operations in Swift are checked against overflow/underflow is a little surprising. Is there any other mainstream language with this feature? Is Swift runtime's arithmetic could be sub-optimal...

How to find m in c = m^e (mod n) if c, e, n are known

language-agnostic,rsa,number-theory,modular-arithmetic
Suppose I have known java BigIntegers c, e, and n, is there a way to quickly calculate the BigInteger m, where: c = m^e (mod n) ...

Primarily Test in O(1)

language-agnostic,primality-test
We know that all prime numbers are of the form 6k+-1. To check if n is a prime number, can't we just divide n by 6, take the floor of that, then check if adding or subtracting 1 equals n? That would check if a number is prime in constant...

Hypothetical Non-Null Language - How would a Linked List be implemented?

null,linked-list,language-agnostic,programming-languages,non-nullable
Suppose you are writing in a programming language where null simply doesn't exist. It either uses empty objects or throws a ObjectNonexistentException or something similar. Now you want to implement a linked list. But: You can't point to null to end the list. If you point to an empty object...

Convert between UTF:s without intermediate encoding

algorithm,language-agnostic,utf
Is it possible to convert between UTF-8 and UTF-16 without first decoding into UCS-4 and then encode the resulting code-point, without using a large mapping table?

Bracket and brace usage in BNF?

syntax,language-agnostic,grammar,bnf,ebnf
Consider the following: A function parameter list is a sequence of zero or more parameters separated by commas and bracketed by parentheses, "(" and ")" . If I want to give the syntax of "function parameter list" assuming that the syntactic category of "parameter" has been defined, can I write:...

Prevent SQL injection when building query

sql-server,language-agnostic
I know usually how to prevent it using preparedStatements, but now I have such a method for bulding queries. For example in Java: private String buildQuery(String where) { String query = "SELECT id, name FROM someTable"; if(where.length() > 0) { query = query + " WHERE " + where; }...

Jaccard Coefficient

language-agnostic,metrics,coefficients
I have been given a formula to calculate the Jaccard Coefficient for two real vectors a and b of length n. Is this formula correct? If I calculate the coefficient for the vectors {5, 3, 1, 0, 3} and {7, 1, 3, 2, 1} I get a negative number which...

Is it good practice to use magic numbers?

html,sql,language-agnostic,coding-style
I am making a web app. In certain cases in server side I am making mysql queries where I basically say where d.id=2 meaning I hard-code a foreign key to another table. Or in client side, I have a form with a radio field, and the input field values are...

What is the cleanest way to round a value to nearest 45 degrees?

language-agnostic,rounding
I have the same question as the question here. The user asked: I just wrote this to return the nearest 45 degree angle. Like 0, 45, 90, 135... It feels like there must be a better way of doing this though. This is working fine but it looks messy. public...

Pass parameters between method name

methods,language-agnostic,parameter-passing
I was wondering if you know of any programming language in which we can pass parameters inside method name. I'm guessing this could improve the code readability. I.e. Lets say I want to multiply to integers in a method. Normally my method declaration would be something like: function multiply(int a,...

Iterator to produce unique random order?

language-agnostic,iterator,random-sample
The problem is stated as follows, we have a very large number of items which are traversed through an iterator pattern (which dynamicaly constructs or fetches) the requested item. Due to the number of items being large and thus cannot be kept in memory (as a list for example). What...

Is there any formula that maps an int on the range [0..πR²] to the (x,y) coordinates inside the circle of radius R?

algorithm,math,language-agnostic,functional-programming,formula
The formula: index(i,w,h) = (i%w, (i/w)%h) uniquely maps each integer i on the range [0..w*h] to a coordinate inside the rectangle of width w and height h. Is there any similar formula: index(i,r) = ? that uniquely maps each integer on the range [0..πR²] to a coordinate inside the circle...

How to find largest square of palindrome in a matrix

algorithm,language-agnostic,dynamic-programming
I am trying to solve a problem where I am given a nXn square matrix of characters and I want to find out size of the largest palindrome square from this? The largest palindrome square is, a square with all rows and all columns as palindrome. For eg. Input a...

Greedy algorithm: highest value first vs earliest deadline first

algorithm,language-agnostic,job-scheduling,greedy
Assume we have a set of n jobs to execute, each of which takes unit time. At any time we can serve exactly one job. Job i, 1<=i<=n earns us a profit if and only if it is executed no later than its deadline. We can a set of jobs...

How to implement multiple item selection?

javascript,language-agnostic,multipleselection
I'm working on a drawing application where the user can create and delete shapes and select them with the mouse to drag them. Should selected shapes be referenced in a "selection" array or should they each have an isSelected property? Is there any advantage to one method over the other?...

Optimal Compare Algorithm for finding string matches in List of strings C#

c#,string,algorithm,optimization,language-agnostic
Say I have a list of 100,000 words. I want to find out if a given string matches any words in that list, and I want to do it in the fastest way possible. Also I want to know if any other words, that are formed by starting with the...

Undirected, weighted graph partitioning

algorithm,language-agnostic,graph-algorithm
I need to partition a graph in such a way that node X and node Y are no longer connected. Additionally, the sum of the weights of the removed edges must be the lowest one possible. For example: 3 1 2 X ----- Z ----- W ----- Y Should become:...

Sublinear algorithm to find the maximum contiguous range with elements >= k in an array

algorithm,language-agnostic
You are given an array A of length N containing natural numbers. The question is: Give an index i and a natural number k, what is the maximum offset m such that all elements in the subarray A[i,i+m] are greater or equal to k. There is a trivial O(N) algorithm:...

Icosahedron joining edge angles

math,language-agnostic
Consider a regular icosahedron. Even with my poor math skills it is fairly easy to generate with code when you realise that the vertices of an icosahedron are the corners of three orthogonal rectangles: I would like to extend the faces but still make them join seamlessly together. Sort of...