Yes, you are right. The concept of MST allows weights of an arbitrary sign. The two most popular algorithms for finding MST (Kruskal&#39;s and Prim&#39;s) work fine with negative edges.

Actually, you can just add a big positive constant to all the edges of your graph, making all the edges positive. The MST (as a subset of edges) will remain the same.

Yes, you are right because if you see the algorithm for shortest path like dijkstera it will check if the present distance of vertex v is greater than sum of present value + edge weight then it will change the value of distance of vertex v from s by the sum value and if the edge weight is negative  then it will give some problems.

But in the MST problem there are algorithms like prims,kruskal which take only the minimum weight edge so that make the negative edge qualify for MST.

Yes,you are right 
Prim&#39;s algorithm works like dijkstra&#39;s algorithm but in prim&#39;s algorithm it should not compute shortest path from i to j having negative edges . So, their is an another algorithm is their i.e Bellman-Ford algorithm for compute shortest path from i to j with negative edge.

Therefore prim&#39;s and Kruskal&#39;s algorithm is not fear for negative edges. 

I am reading a book for Java that I am trying to learn, and I have a question. I can&#39;t understand what is the difference between the variable type `char` and `String`. For example, there is a difference between `int` and `short`, the bytes at the memory and the area of numbers that they have.

But what is the difference between `char` and `String`? except that `char` use (&#39;) and &quot;String&quot; (&quot;).

PS: It is my first &quot;real&quot; programming language. (At school I learned a fake-language for the purpose of the programming lesson.)


Difference between &quot;char&quot; and &quot;String&quot; in Java

I am using:

    driver.manage().timeouts().implicitlyWait(180, TimeUnit.SECONDS);

But it still fails continuously for the below element 

		driver.findElement(By.id(&quot;name&quot;)).clear();
		driver.findElement(By.id(&quot;name&quot;)).sendKeys(&quot;Create_title_01&quot;);

I have added wait code:

    for (int second = 0;; second++) {
			if (second &gt;= 120) fail(&quot;timeout&quot;);
			try { if (isElementPresent(By.id(&quot;name&quot;))) break; } catch (Exception e) {}
			Thread.sleep(1000);
		}

Shouldn&#39;t implicit wait take care of waiting till an element is found?
Also would it be better if I use Explicit wait instead of the code I have added that has `Thread.sleep()`?



When to use explicit wait vs implicit wait in Selenium Webdriver?

This is a follow-up question of https://stackoverflow.com/questions/10381474/graph-why-most-graph-algorithms-do-not-adapt-so-easily-to-negative-numbers.

I think Shortest Path (SP) has problem with negative weights, because it adds up all weights along the paths and tries to find the minimum one.

But I don&#39;t think Minimum Spanning Tree (MST) has problems with negative weights, because it just takes the single minimum weight edge without caring about the overall total weights.

Am I right?

Is Minimum Spanning Tree afraid of negative weights?

This is a follow-up question of <a href="https://stackoverflow.com/questions/10381474/graph-why-most-graph-algorithms-do-not-adapt-so-easily-to-negative-numbers" target="_blank" rel="noopener noreferrer">https://stackoverflow.com/questions/10381474/graph-why-most-graph-algorithms-do-not-adapt-so-easily-to-negative-numbers</a>.
I think Shortest Path (SP) has problem with negative weights, because it adds up all weights along the paths and tries to find the minimum one.
But I don't think Minimum Spanning Tree (MST) has problems with negative weights, because it just takes the single minimum weight edge without caring about the overall total weights.
Am I right?

Is anybody able to give a &#39;plain english&#39; intuitive, yet formal, explanation of what makes QuickSort n log n? From my understanding it has to make a pass over n items, and it does this log n times...Im not sure how to put it into words why it does this log n times.



Intuitive explanation for why QuickSort is n log n?

After spending about 6-8 hours trying to digest the Manacher&#39;s algorithm, I am ready to throw in the towel. But before I do, here is one last shot in the dark: can anyone explain it? I don&#39;t care about the code. I want somebody to explain the **ALGORITHM**.

Here seems to be a place that others seemed to enjoy in explaining the algorithm:
http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

I understand why you would want to transform the string, say, &#39;abba&#39; to #a#b#b#a#
After than I&#39;m lost. For example, the author of the previously mentioned website says the key part of the algorithm is: 

                          if P[ i&#39; ] ≤ R – i,
                          then P[ i ] ← P[ i&#39; ]
                          else P[ i ] ≥ P[ i&#39; ]. (Which we have to expand past 
                          the right edge (R) to find P[ i ])

This seems wrong, because he/she says at one point that P[i] equals 5 when P[i&#39;] = 7 and P[i] is not less or equal to R - i. 

If you are not familiar with the algorithm, here are some more links: http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html (I&#39;ve tried this one, but the terminology is awful and confusing. First, some things are not defined. Also, too many variables. You need a checklist to recall what variable is referring to what.)

Another is: http://www.akalin.cx/longest-palindrome-linear-time (good luck)

The basic gist of the algorithm is to find the longest palindrome in linear time. It can be done in O(n^2) with a minimum to medium amount of effort. This algorithm is supposed to be quite &quot;clever&quot; to get it down to O(n). 






Manacher&#39;s algorithm (algorithm to find longest palindrome substring in linear time)

I am looking for a JavaScript function that can compare two strings and return the likeliness that they are alike. I have looked at soundex but that&#39;s not really great for multi-word strings or non-names. I am looking for a function like:
```js
    function compare(strA,strB){
    
    }
    
    compare(&quot;Apples&quot;,&quot;apple&quot;) = Some X Percentage.
```
The function would work with all types of strings, including numbers, multi-word values, and names. Perhaps there&#39;s a simple algorithm I could use?

Ultimately none of these served my purpose so I used this:
```js
     function compare(c, u) {
            var incept = false;
            var ca = c.split(&quot;,&quot;);
            u = clean(u);
            //ca = correct answer array (Collection of all correct answer)
            //caa = a single correct answer word array (collection of words of a single correct answer)
            //u = array of user answer words cleaned using custom clean function
            for (var z = 0; z &lt; ca.length; z++) {
                caa = $.trim(ca[z]).split(&quot; &quot;);
                var pc = 0;
                for (var x = 0; x &lt; caa.length; x++) {
                    for (var y = 0; y &lt; u.length; y++) {
                        if (soundex(u[y]) != null &amp;&amp; soundex(caa[x]) != null) {
                            if (soundex(u[y]) == soundex(caa[x])) {
                                pc = pc + 1;
                            }
                        }
                        else {
                            if (u[y].indexOf(caa[x]) &gt; -1) {
                                pc = pc + 1;
                            }
                        }
                    }
                }
                if ((pc / caa.length) &gt; 0.5) {
                    return true;
                }
            }
            return false;
        }
        
        // create object listing the SOUNDEX values for each letter
        // -1 indicates that the letter is not coded, but is used for coding
        //  0 indicates that the letter is omitted for modern census archives
        //                              but acts like -1 for older census archives
        //  1 is for BFPV
        //  2 is for CGJKQSXZ
        //  3 is for DT
        //  4 is for L
        //  5 is for MN my home state
        //  6 is for R
        function makesoundex() {
            this.a = -1
            this.b = 1
            this.c = 2
            this.d = 3
            this.e = -1
            this.f = 1
            this.g = 2
            this.h = 0
            this.i = -1
            this.j = 2
            this.k = 2
            this.l = 4
            this.m = 5
            this.n = 5
            this.o = -1
            this.p = 1
            this.q = 2
            this.r = 6
            this.s = 2
            this.t = 3
            this.u = -1
            this.v = 1
            this.w = 0
            this.x = 2
            this.y = -1
            this.z = 2
        }
        
        var sndx = new makesoundex()
        
        // check to see that the input is valid
        function isSurname(name) {
            if (name == &quot;&quot; || name == null) {
                return false
            } else {
                for (var i = 0; i &lt; name.length; i++) {
                    var letter = name.charAt(i)
                    if (!(letter &gt;= &#39;a&#39; &amp;&amp; letter &lt;= &#39;z&#39; || letter &gt;= &#39;A&#39; &amp;&amp; letter &lt;= &#39;Z&#39;)) {
                        return false
                    }
                }
            }
            return true
        }
        
        // Collapse out directly adjacent sounds
        // 1. Assume that surname.length&gt;=1
        // 2. Assume that surname contains only lowercase letters
        function collapse(surname) {
            if (surname.length == 1) {
                return surname
            }
            var right = collapse(surname.substring(1, surname.length))
            if (sndx[surname.charAt(0)] == sndx[right.charAt(0)]) {
                return surname.charAt(0) + right.substring(1, right.length)
            }
            return surname.charAt(0) + right
        }
        
        // Collapse out directly adjacent sounds using the new National Archives method
        // 1. Assume that surname.length&gt;=1
        // 2. Assume that surname contains only lowercase letters
        // 3. H and W are completely ignored
        function omit(surname) {
            if (surname.length == 1) {
                return surname
            }
            var right = omit(surname.substring(1, surname.length))
            if (!sndx[right.charAt(0)]) {
                return surname.charAt(0) + right.substring(1, right.length)
            }
            return surname.charAt(0) + right
        }
        
        // Output the coded sequence
        function output_sequence(seq) {
            var output = seq.charAt(0).toUpperCase() // Retain first letter
            output += &quot;-&quot; // Separate letter with a dash
            var stage2 = seq.substring(1, seq.length)
            var count = 0
            for (var i = 0; i &lt; stage2.length &amp;&amp; count &lt; 3; i++) {
                if (sndx[stage2.charAt(i)] &gt; 0) {
                    output += sndx[stage2.charAt(i)]
                    count++
                }
            }
            for (; count &lt; 3; count++) {
                output += &quot;0&quot;
            }
            return output
        }
        
        // Compute the SOUNDEX code for the surname
        function soundex(value) {
            if (!isSurname(value)) {
                return null
            }
            var stage1 = collapse(value.toLowerCase())
            //form.result.value=output_sequence(stage1);
        
            var stage1 = omit(value.toLowerCase())
            var stage2 = collapse(stage1)
            return output_sequence(stage2);
        
        }
        
        function clean(u) {
            var u = u.replace(/\,/g, &quot;&quot;);
            u = u.toLowerCase().split(&quot; &quot;);
            var cw = [&quot;ARRAY OF WORDS TO BE EXCLUDED FROM COMPARISON&quot;];
            var n = [];
            for (var y = 0; y &lt; u.length; y++) {
                var test = false;
                for (var z = 0; z &lt; cw.length; z++) {
                    if (u[y] != &quot;&quot; &amp;&amp; u[y] != cw[z]) {
                        test = true;
                        break;
                    }
                }
                if (test) {
        //Don&#39;t use &amp; or $ in comparison
                    var val = u[y].replace(&quot;$&quot;, &quot;&quot;).replace(&quot;&amp;&quot;, &quot;&quot;);
                    n.push(val);
                }
            }
            return n;
        }
```

Compare Strings Javascript Return %of Likely

&gt; **Possible Duplicate:**  
&gt; [Rolling median algorithm in C](https://stackoverflow.com/questions/1309263/rolling-median-algorithm-in-c)  

&lt;!-- End of automatically inserted text --&gt;

&gt; Given that integers are read from a data stream. Find median of elements read so far in efficient way. 

Solution I have read: We can use a max heap on left side to represent elements that are less than the effective median, and a min heap on right side to represent elements that are greater than the effective median.

After processing an incoming element, the number of elements in heaps differ at most by 1 element. When both heaps contain the same number of elements, we find the average of heap&#39;s root data as effective median. When the heaps are not balanced, we select the effective median from the root of heap containing more elements.

But how would we construct a max heap and min heap i.e. how would we know the effective median here? I think that we would insert 1 element in max-heap and then the next 1 element in min-heap, and so on for all the elements. Correct me If I am wrong here.

Find running median from a stream of integers

To find the median of an unsorted array, we can make a min-heap in O(nlogn) time for n elements, and then we can extract one by one n/2 elements to get the median. But this approach would take O(nlogn) time.

Can we do the same by some method in O(n) time? If we can, then please tell or suggest some method.

Finding the median of an unsorted array

I have a Hashmap in Java like this:

    private Map&lt;String, Integer&gt; team1 = new HashMap&lt;String, Integer&gt;();

Then I fill it like this:

    team1.put(&quot;United&quot;, 5);

How can I get the keys?  Something like: `team1.getKey()` to return &quot;United&quot;.

 

Get keys from HashMap in Java

Any help on this problem will be greatly appreciated.

So basically I want to run a query to my SQL database and store the returned data as Pandas data structure.

I have attached code for query.

I am reading the documentation on Pandas, but I have problem to identify the return type of my query.

I tried to print the query result, but it doesn&#39;t give any useful information.

Thanks!!!! 

```python
from sqlalchemy import create_engine

engine2 = create_engine(&#39;mysql://THE DATABASE I AM ACCESSING&#39;)
connection2 = engine2.connect()
dataid = 1022
resoverall = connection2.execute(&quot;
    SELECT 
       sum(BLABLA) AS BLA,
       sum(BLABLABLA2) AS BLABLABLA2,
       sum(SOME_INT) AS SOME_INT,
       sum(SOME_INT2) AS SOME_INT2,
       100*sum(SOME_INT2)/sum(SOME_INT) AS ctr,
       sum(SOME_INT2)/sum(SOME_INT) AS cpc
    FROM daily_report_cooked
    WHERE campaign_id = &#39;%s&#39;&quot;,
    %dataid
)
```

So I sort of want to understand what&#39;s the format/datatype of my variable &quot;resoverall&quot; and how to put it with PANDAS data structure.

How to convert SQL Query result to PANDAS Data Structure?

I&#39;ve been learning about different algorithms in my spare time recently, and one that I came across which appears to be very interesting is called the HyperLogLog algorithm - which estimates how many unique items are in a list.

This was particularly interesting to me because it brought me back to my MySQL days when I saw that &quot;Cardinality&quot; value (which I always assumed until recently that it was calculated not estimated).

So I know how to write an algorithm in *O*(*n*) that will calculate how many unique items are in an array. I wrote this in JavaScript:

    function countUniqueAlgo1(arr) {
        var Table = {};
        var numUnique = 0;
        var numDataPoints = arr.length;
        for (var j = 0; j &lt; numDataPoints; j++) {
            var val = arr[j];
            if (Table[val] != null) {
                continue;
            }
            Table[val] = 1;
            numUnique++;
        }
        return numUnique;
    }

But the problem is that my algorithm, while *O*(*n*), uses a lot of memory (storing values in `Table`).

I&#39;ve been reading [this paper][1] about how to count duplicates in a list in *O*(*n*) time and using minimal memory.


It explains that by hashing and counting bits or something one can estimate within a certain probability (assuming the list is evenly distributed) the number of unique items in a list.

I&#39;ve read the paper, but I can&#39;t seem to understand it. Can someone give a more layperson&#39;s explanation? I know what hashes are, but I don&#39;t understand how they are used in this HyperLogLog algorithm.


  [1]: http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf

How does the HyperLogLog algorithm work?

I am confused about the terminology of the below trees, I have been studying the Tree, and I am unable to distinguish between these trees:
 
 **a) Complete Binary Tree**

 **b) Strict Binary Tree**

 **c) Full Binary Tree** 

Please help me to differentiate among these trees.
When and where these trees are used in Data Structure?

Difference between &quot;Complete binary tree&quot;, &quot;strict binary tree&quot;,&quot;full binary Tree&quot;?

I need a `Stack` data structure for my use case. I should be able to push items into the data structure and I only want to retrieve the last item from the Stack. The [JavaDoc for Stack][1] says :

&gt; A more complete and consistent set of LIFO stack operations is
&gt; provided by the Deque interface and its implementations, which should
&gt; be used in preference to this class. For example:

   

    Deque&lt;Integer&gt; stack = new ArrayDeque&lt;&gt;();

I definitely do not want synchronized behavior here as I will be using this datastructure local to a method . Apart from this why should I prefer `Deque` over `Stack` here ?

P.S: The javadoc from Deque says :

&gt; Deques can also be used as LIFO (Last-In-First-Out) stacks. This
&gt; interface should be used in preference to the legacy Stack class.

[1]:http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/Stack.java#Stack

Why should I use Deque over Stack?

I have a list of dates, each date in it can occur more than once. I want to count the number of times each date occurs (histogram) and display it in a graph (with the Y axis being the number of times the date occurs and the X axis being the date itself)?

Sample list:

    19/05/2012
    19/05/2012
    19/05/2012
    17/05/2012
    17/05/2012
    16/05/2012
    16/05/2012
    16/05/2012
    16/05/2012
    15/05/2012
    15/05/2012
    15/05/2012
    15/05/2012
    12/05/2012
    12/05/2012
    12/05/2012
    7/05/2012

I clicked every menu option over the past few years and never did I find anything specific to this. Would this be a case for using PivotTables somehow?

Count number of times a date occurs and make a graph out of it

So i have a page already which draws a force directed graph, like the one shown [here][1].

And that works fine. I&#39;m using the JS from [here][2], with a few tweaks to spread out the nodes slightly nicer.

These are more or less the only differences:

    d3.json(&quot;force.json&quot;, function(json) {
      var force = d3.layout.force()
          .gravity(0.1)
          .charge(-2000)
          .linkDistance(1)
          .linkStrength(0.1)
          .nodes(json.nodes)
          .links(json.links)
          .size([w, h])
          .start();

Where reducing the link strength seems to make the links more like springs, so it becomes similar to the [Fruchterman &amp; Reingold][3] technique often used. This works reasonably well, but only for fairly small graphs. With larger graphs the number of crossings just goes up - as one would expect, but the solution it lands on is normally far from optimal. I&#39;m not looking for a method to get the optimal solution, I know that&#39;s very difficult. I would just like it to have some crude addition that tries to force the lines apart as well as the nodes.

**Is there a way to add a repulsion between in links, as well as between the nodes?** I&#39;m not familiar with the way D3 force works, and i can&#39;t seem to find anything that says this is possible...


  [1]: http://networkx.lanl.gov/
  [2]: http://mbostock.github.com/d3/ex/force.html
  [3]: http://en.wikipedia.org/wiki/Force-based_algorithms_%28graph_drawing%29

D3.js force directed graph, reduce edge crossings by making edges repel each other

I need a working algorithm for finding all simple cycles in an undirected graph. I know the cost can be exponential and the problem is NP-complete, but I am going to use it in a small graph (up to 20-30 vertices) and the cycles are small in number.

After a long research (mainly here) I still don&#39;t have a working approach. Here is a summary of my search:

https://stackoverflow.com/questions/5068086/finding-all-cycles-in-an-undirected-graph

https://stackoverflow.com/questions/526331/cycles-in-an-undirected-graph -&gt; detects only whether there is a cycle or not

https://stackoverflow.com/questions/9804127/finding-polygons-within-an-undirected-graph -&gt; very nice description, but no solution

https://stackoverflow.com/questions/546655/finding-all-cycles-in-graph/549402#549402 -&gt; finds cycles only in directed graphs

https://stackoverflow.com/questions/9626249/detect-cycles-in-undirected-graph-using-boost-graph-library

The only answer I found, which approaches my problem, is this one:

https://stackoverflow.com/questions/2839908/find-all-cycles-in-graph-redux

It seems that finding a basic set of cycles and XOR-ing them could do the trick. Finding a basic set of cycles is easy, but I don&#39;t understand how to combine them in order to obtain all cycles in the graph...

Finding all cycles in undirected graphs

I read it is ideal to represent sparse graphs by adjacency lists and dense graphs by an adjacency matrix. But I would like to understand the main difference between sparse and dense graphs. 

What is the distinction between sparse and dense graphs?

I was wondering what&#39;s the difference between _uniform-cost search_ and _Dijkstra&#39;s algorithm_. They seem to be the same algorithm.

What&#39;s the difference between uniform-cost search and Dijkstra&#39;s algorithm?

What  is the exact difference between Dijkstra&#39;s and Prim&#39;s algorithms? I know Prim&#39;s will give a MST but the tree generated by Dijkstra will also be a MST. Then what is the exact difference?

Content Type	Original Author	Original Content on Stackoverflow
Question	Jackson Tale	View Question on Stackoverflow
Solution 1 - Algorithm	Skiminok	View Answer on Stackoverflow
Solution 2 - Algorithm	Rahul Dhawan	View Answer on Stackoverflow
Solution 3 - Algorithm	REVANASIDDA	View Answer on Stackoverflow

Is Minimum Spanning Tree afraid of negative weights?

Algorithm Problem Overview

Algorithm Solutions

Solution 1 - Algorithm

Solution 2 - Algorithm

Solution 3 - Algorithm

When to use explicit wait vs implicit wait in Selenium Webdriver?

Difference between "char" and "String" in Java

Attributions