algorithm

Why Time complexity of permutation function is O(n!)

by

Consider following code. public class Permutations { static int count=0; static void permutations(String str, String prefix){ if(str.length()==0){ System.out.println(prefix); } else{ for(int i=0;i<str.length();i++){ count++; String rem = str.substring(0,i) + str.substring(i+1); permutations(rem, prefix+str.charAt(i)); } } } public static void main(String[] args) { permutations(“abc”, “”); System.out.println(count); } } here the logic, that i think is followed is- it … Read more

Shortest path (fewest nodes) for unweighted graph

by

I’m trying build a method which returns the shortest path from one node to another in an unweighted graph. I considered the use of Dijkstra’s but this seems a bit overkill since I only want one pair. Instead I have implemented a breadth-first search, but the trouble is that my returning list contains some of … Read more

Check if any item in a list matches any item in another list

by

A coleague asked me to write a one-liner to replace the following method: public static bool IsResourceAvailableToUser(IEnumerable<string> resourceRoles, IEnumerable<string> userRoles) { foreach (var userRole in userRoles) foreach (var resourceRole in resourceRoles) if (resourceRole == userRole) return true; return false; } Resharper and I came up with this: public static bool IsResourceAvailableToUser(IEnumerable<string> resourceRoles, IEnumerable<string> userRoles) { … Read more

A fast array shift implementation in C#?

by

I need to shift to the right and to the left an array by N places. The items that pop out on the side where i shift to must get back into on the other side. Shift right by 13: [0,1,2,3,4,5,6,7,8,9] -> [7,8,9,0,1,2,3,4,5,6] Shift left by 15: [0,1,2,3,4,5,6,7,8,9] -> [5,6,7,8,9,0,1,2,3,4] This operation will happen millions … Read more

Artificial Intelligence Methods to Detect Cheating in Games [closed]

by

Closed. This question needs to be more focused. It is not currently accepting answers. Want to improve this question? Update the question so it focuses on one problem only by editing this post. Closed 1 year ago. Improve this question My day job is for an online browser based game, one that is small, with … Read more

In Big-O notation for tree structures: Why do some sources refer to O(logN) and some to O(h)?

by

In researching complexity for any algorithm that traverses a binary search tree, I see two different ways to express the same thing: Version #1: The traversal algorithm at worst case compares once per height of the tree; therefore complexity is O(h). Version #2: The traversal algorithm at worst case compares once per height of the … Read more