tag:blogger.com,1999:blog-30986389250899933152024-03-14T01:53:57.373+05:30KodeKnightData structures, Algorithms, Coding, Technical Interview Questions and much more. (Still work in progress)Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.comBlogger1055125tag:blogger.com,1999:blog-3098638925089993315.post-31641579973332943272016-03-30T10:02:00.000+05:302016-03-30T10:02:44.611+05:30Convert String to ZigZag Bottom Up<div dir="ltr" style="text-align: left;" trbidi="on">
<h4 style="text-align: left;">
<b>Problem</b></h4>
<div style="-webkit-text-stroke-width: 0px; background-color: white; color: #333333; font-family: 'Helvetica Neue Light', HelveticaNeue-Light, 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 19.6px; margin: 0px; orphans: auto; outline: none; padding: 0px; text-align: left; text-indent: 0px; text-transform: none; white-space: normal; widows: 1; word-spacing: 0px;">
The string <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Monaco, Menlo, Consolas, 'Courier New', monospace; font-size: 12.2222px; padding: 2px 4px; white-space: nowrap;">"PAYPALISHIRING"</code> is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)</div>
<br class="Apple-interchange-newline" />
<h4 style="text-align: left;">
Example</h4>
<br />
<div style="-webkit-text-stroke-width: 0px; background-color: white; color: #333333; font-family: 'Helvetica Neue Light', HelveticaNeue-Light, 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 19.6px; margin: 0px; orphans: auto; outline: none; padding: 0px; text-align: left; text-indent: 0px; text-transform: none; white-space: normal; widows: 1; word-spacing: 0px;">
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; font-family: Monaco, Menlo, Consolas, 'Courier New', monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; padding: 9.5px; white-space: pre-wrap; word-break: break-all; word-wrap: break-word;">P A H N
A P L S I I G
Y I R
</pre>
And then read line by line: <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Monaco, Menlo, Consolas, 'Courier New', monospace; font-size: 12.2222px; padding: 2px 4px; white-space: nowrap;">"PAHNAPLSIIGYIR"</code><br />
<div style="box-sizing: border-box; margin: 0px 0px 10px; outline: none; padding: 0px;">
Write the code that will take a string and make this conversion given a number of rows:</div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; font-family: Monaco, Menlo, Consolas, 'Courier New', monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; padding: 9.5px; white-space: pre-wrap; word-break: break-all; word-wrap: break-word;">string convert(string text, int nRows);</pre>
<code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Monaco, Menlo, Consolas, 'Courier New', monospace; font-size: 12.2222px; padding: 2px 4px; white-space: nowrap;">convert("PAYPALISHIRING", 3)</code> should return <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Monaco, Menlo, Consolas, 'Courier New', monospace; font-size: 12.2222px; padding: 2px 4px; white-space: nowrap;">"PAHNAPLSIIGYIR"</code>.</div>
<br />
<br class="Apple-interchange-newline" />
<h3 style="text-align: left;">
Solution</h3>
<h4>
Method 1 - Use list to save the substrings</h4>
<br />
A straightforward solution is to actually build up the zigzag character matrix and read the matrix into a string.
<br />
Here is the basic algo:
<br />
<ul style="text-align: left;">
<li>Maintain down boolean which tells whether you are going up or down in zig zag order.
</li>
<li>As soon as rows = 0 means you need to go down now and as soon as rows = nRows - 1 you need to go up now
</li>
<li>Just keep on doing this until whole string is exhausted
</li>
<li>Using StringBuilder list/array to store elements in zig zag order and in the end just append all characters from each StringBuilder to return output.
</li>
</ul>
Here is the code in java:
<br />
<pre class="brush:java">import java.util.ArrayList;
public class Solution {
public String convert(String s, int nRows) {
if(s == null || s.length() <= 1 || nRows <= 1){
return s;
}
ArrayList<StringBuilder> list = new ArrayList<StringBuilder>();
for(int i = 0; i < nRows; i++){
list.add(new StringBuilder());
}
int i = 0;
boolean down = false;
int row = 0;
while(i < s.length()){
list.get(row).append(s.charAt(i));
if(row == 0){
down = true;
}else if(row == nRows - 1){
down = false;
}
if(down){
row++;
}else{
row--;
}
i++;
}
i = 0;
StringBuilder output = new StringBuilder();
while( i < list.size()){
output.append(list.get(i).toString());
i++;
}
return output.toString();
}
}
</pre>
<br />
Though time complexity is good O(n), but the space is complexity is O(nRows*Max_column_in_a_row) = O(n)
<br />
<br />
<h4 style="text-align: left;">
Method 2 - Append the character on the fly
</h4>
Another way is to calculate the corresponding index on the fly and append the character into a string.
<br />
Take <code>convert("PAYPALISHIRING", 4)</code> as an example. The matrix will look as follows :
<br />
<pre class="brush:java">P I N
A L S I G
Y A H R
P I
</pre>
<br />
which can be expended as below (You will see why we rewrite like this soon.).<br />
<pre class="brush:java">P I N
A S G
Y H
P I
A R
L I
</pre>
<br />
Some useful properties:
<br />
<ul style="text-align: left;">
<li>For any full columns, the odd ones have nRows characters, even ones have (nRows - 2) characters.
</li>
<li>For the first and last rows, we read one single character from each expended column;
</li>
<li>For the rest of rows, we read two characters, one from top part and one from bottom part, from each expended column.
</li>
<li>One edge case is that nRows = 1, where (nRows*2 - 2) becomes 0. In this case, we should simply return the original string.
</li>
</ul>
<pre class="brush:java">public String convert(String s, int nRows) {
if (nRows == 1) return s;
StringBuilder ss = new StringBuilder();
int n = nRows + nRows - 2;
// rest rows
for (int i = 0; i < nRows; ++i) {
int cur = i;
while (cur < s.length()) {
ss.append(s.charAt(cur));
cur += n;
if (i > 0 && i < nRows - 1 && (cur - i - i) < s.length()) {
ss.append(s.charAt(cur - i - i));
}
}
}
return ss.toString();
}
</pre>
<br />
Thanks.<br />
<b>Reference</b><br />
<a href="http://www.params.me/2014/04/leetcode-zigzag-conversion-in-java.html">http://www.params.me/2014/04/leetcode-zigzag-conversion-in-java.html</a><br />
<a href="http://n00tc0d3r.blogspot.in/2013/06/zigzag-conversion.html">http://n00tc0d3r.blogspot.in/2013/06/zigzag-conversion.html</a>
<br />
<a href="https://leetcode.com/problems/zigzag-conversion/">https://leetcode.com/problems/zigzag-conversion/</a>
</div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-44929752060861667532016-03-11T10:24:00.002+05:302016-07-13T02:18:29.395+05:30Growth Rate - The Importance of Asymptotics<div dir="ltr" style="text-align: left;" trbidi="on">
It really is true that if algorithm A is o(algorithm B) then for
large problems A will take <b>much</b> less time than B.<br />
<br />
<b>Definition</b>: If (the number of operations in)
algorithm A is o(algorithm B), we call A
<b>asymptotically faster</b> than B.<br />
<br />
<b>Example:</b>: The following sequence of functions are
ordered by <b>growth rate</b>, i.e., each function is
little-oh of the subsequent function.
<br />
log(log(n)), log(n), (log(n))<sup>2</sup>, n<sup>1/3</sup>,
n<sup>1/2</sup>, n, nlog(n), n<sup>2</sup>/(log(n)), n<sup>2</sup>,
n<sup>3</sup>, 2<sup>n</sup>, 4n, n!<br />
<br />
One way to compare 2 functions, is using L'Hospital rule. Here is good explanation:<br />
<a href="https://www.youtube.com/watch?v=6IjVGfbhe9w">Growth Rates of Functions and L'Hospital's Rule</a><br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen="" class="YOUTUBE-iframe-video" data-thumbnail-src="https://i.ytimg.com/vi/6IjVGfbhe9w/0.jpg" frameborder="0" height="266" src="https://www.youtube.com/embed/6IjVGfbhe9w?feature=player_embedded" width="320"></iframe></div>
<br />
Here is the snapshot of how the growth looks in increasing order<br />
<table border="0" style="width: 520px;"><tbody>
<tr align="right"><td width="70">1</td>
<td width="70">loglog<i><b>n</b></i></td>
<td width="70">log<i><b>n</b></i></td>
<td width="60"><b><i>n</i></b></td>
<td width="80"><b><i>n</i></b>log<b><i>n</i></b></td>
<td width="60"><b><span style="color: black;"><i>n<sup>2</sup></i></span></b></td>
<td width="60"><b><span style="color: black;"><i>2<sup>n</sup></i></span></b></td>
<td width="60"><b><span style="color: black;"><i>n</i>!</span></b></td>
<td width="60"><b><span style="color: black;"><i>n<sup>n</sup></i></span></b></td></tr>
</tbody></table>
<br />
<b>Reference</b><br />
<a href="https://cs.nyu.edu/courses/fall02/V22.0310-002/class-notes.html">https://cs.nyu.edu/courses/fall02/V22.0310-002/class-notes.html</a><br />
<br />
<a href="http://www.cs.odu.edu/~cs381/cs381content/function/growth.html">http://www.cs.odu.edu/~cs381/cs381content/function/growth.html</a><br />
<br />
<br /></div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-65272967933745846752016-03-11T10:24:00.001+05:302016-07-13T02:18:29.406+05:30Asymptotic Notation<div dir="ltr" style="text-align: left;" trbidi="on">
Its been a while, since I have blogged. To start with I am posting a basics of asymptotic analysis of algorithm, which we study at the start of the course.<br />
Now we are going to be less precise and worry only about approximate
answers for large inputs.
<br />
<h3>
The <q>Big-Oh</q> Notation</h3>
<b>Definition</b>: Let f(n) and g(n) be real-valued
functions of a single non-negative integer argument.
We write <tt>f(n)</tt> is <tt>O(g(n))</tt> if there is a positive real
number <tt>c</tt> and a positive integer <tt>n<sub>0</sub></tt>
such that <tt>f(n)≤cg(n)</tt> for all <tt>n≥n<sub>0</sub></tt>.
<br />
What does this mean?
<br />
For large inputs (<tt>n≤n<sub>0</sub></tt>), <tt>f</tt> is not much
bigger than <tt>g</tt> (<tt>f(n)≤cg(n)</tt>).
<br />
Examples to do on the board
<br />
<ol>
<li><tt>3n-6</tt> is <tt>O(n)</tt>. So, what f(n) = 3n-6<tt> <= c*n. For example, c=4.</tt> Some less common ways of
saying the same thing follow.
</li>
<li><tt>3x-6</tt> is <tt>O(x)</tt>.
</li>
<li>If <tt>f(y)=3y-6</tt> and <tt>id(y)=y</tt>,
then <tt>f(y)</tt> is <tt>O(id(y))</tt>.
</li>
<li><tt>3n-6</tt> is <tt>O(2n)</tt>
</li>
<li><tt>9n<sup>4</sup>+12n<sup>2</sup>+1234</tt> is
<tt>O(n<sup>4</sup>)</tt>.
</li>
<li><tt>innerProduct</tt> is <tt>O(n)</tt>
</li>
<li><tt>innerProductBetter</tt> is <tt>O(n)</tt>
</li>
<li><tt>innerProductFixed</tt> is <tt>O(n)</tt>
</li>
<li><tt>countPositives</tt> is <tt>O(n)</tt>
</li>
<li><tt>n+log(n)</tt> is <tt>O(n)</tt>.
</li>
<li><tt>log(n)+5log(log(n))</tt> is <tt>O(log(n))</tt>.
</li>
<li><tt>12345<sup>54321</sup></tt> is <tt>O(1)</tt>.
</li>
<li><tt>3/n</tt> is <tt>O(1)</tt>. True but not the best.
</li>
<li><tt>3/n</tt> is <tt>O(1/n)</tt>. Much better.
</li>
<li><tt>innerProduct</tt> is <tt>O(100n+log(n)+34.5)</tt>. True, but
awful.
</li>
</ol>
A few theorems give us rules that make calculating big-Oh easier.<br />
<br />
<b>Theorem (arithmetic)</b>: Let <tt>d(n)</tt>,
<tt>e(n)</tt>, <tt>f(n)</tt>, and <tt>g(n)</tt> be nonnegative
real-valued functions of a nonnegative integer argument and assume
<tt>d(n)</tt> is <tt>O(f(n))</tt> and <tt>e(n)</tt> is
<tt>O(g(n))</tt>. Then
<br />
<ol>
<li><tt>ad(n)</tt> is <tt>O(f(n))</tt> for any nonnegative a
</li>
<li><tt>d(n)+e(n)</tt> is <tt>O(f(n)+g(n))</tt>
</li>
<li><tt>d(n)e(n)</tt> is <tt>O(f(n)g(n))</tt>
</li>
</ol>
<b>Theorem (transitivity)</b>: Let <tt>d(n)</tt>,
<tt>f(n)</tt>, and <tt>g(n)</tt> be nonnegative real-valued functions
of a nonnegative integer argument and assume <tt>d(n)</tt> is
<tt>O(f(n))</tt> and <tt>f(n)</tt> is <tt>O(g(n))</tt>. Then
<tt>d(n)</tt> is <tt>O(g(n))</tt>.
<br />
<b>Theorem</b> (special functions): (Only <tt>n</tt> varies)
<br />
<ol>
<li>If <tt>f(n)</tt> is a polynomial of degree d, then
<tt>f(n)</tt> is <tt>O(n<sup>d</sup>)</tt>.
</li>
<li><tt>n<sup>x</sup></tt> is <tt>O(a<sup>n</sup>)</tt> for any
<tt>x>0</tt> <tt>and a>1</tt>.
</li>
<li><tt>log(n<sup>x</sup>)</tt> is <tt>O(log(n))</tt> for any <tt>x>0</tt>
</li>
<li><tt>(log(n))<sup>x</sup></tt> is <tt>O(n<sup>y</sup>)</tt> for any
<tt>x>0</tt> and <tt>y>0</tt>.
</li>
</ol>
<br />
<b>Definitions</b>: (Common names)
<br />
<ol>
<li>If a function is <tt>O(log(n))</tt> we call it <b>logarithmic</b>.
</li>
<li>If a function is <tt>O(n)</tt> we call it <b>linear</b>.
</li>
<li>If a function is <tt>O(n<sup>2</sup>)</tt> we call it
<b>quadratic</b>.
</li>
<li>If a function is <tt>O(n<sup>k</sup></tt>) with <tt>k≥1</tt>, we call it
<b>polynomial</b>.
</li>
<li>If a function is <tt>O(a<sup>n</sup>)</tt> with <tt>a>1</tt>,
we call it <b>exponential</b>.
</li>
</ol>
<b>Remark</b>: The last definitions would be better with a
relative of big-Oh, namely big-Theta, since, for example <tt>3log(n)</tt> is
<tt>O(n<sup>2</sup>)</tt>, but we do <i>not</i> call
<tt>3log(n)</tt> quadratic.<br />
<h3>
1.2.2 <q>Relatives</q> of the Big-Oh</h3>
<h4>
Big-Omega and Big-Theta</h4>
Recall that f(n) is O(g(n)) if for large n, f is not much bigger
than g. That is g is some sort of <b>upper</b> bound on f.
How about a definition for the case when g is (in the same sense) a
<b>lower</b> bound for f?
<br />
<b>Definition</b>: Let f(n) and g(n) be real valued
functions of an integer value. Then <b>f(n) is
Ω(g(n))</b> if g(n) is O(f(n)).
<br />
<b>Remarks</b>:
<br />
<ol>
<li>We pronounce f(n) is Ω(g(n)) as "f(n) is big-Omega of g(n)".
</li>
<li>What the last definition says is that we say f(n) is not much smaller
than g(n) if g(n) is not much bigger than f(n), which sounds
reasonable to me.
</li>
<li>What if f(n) and g(n) are about equal, i.e., neither is much
bigger than the other?
</li>
</ol>
<b>Definition</b>: We write
<b>f(n) is Θ(g(n))</b> if <b>both</b>
f(n) is O(g(n)) <b>and</b> f(n) is Ω(g(n)).
<br />
<b>Remarks</b>
We pronounce f(n) is Θ(g(n)) as "f(n) is big-Theta of g(n)"
<br />
Examples to do on the board.
<br />
<ol>
<li>2x<sup>2</sup>+3x is θ(x<sup>2</sup>).
</li>
<li>2x<sup>3</sup>+3x is <b>not</b> θ(x<sup>2</sup>).
</li>
<li>2x<sup>3</sup>+3x is Ω(x<sup>2</sup>).
</li>
<li>innerProductRecutsive is Θ(n).
</li>
<li>binarySearch is Θ(log(n)). Unofficial for now.
</li>
<li>If f(n) is Θ(g(n)), the f(n) is &Omega(g(n)).
</li>
<li>If f(n) is Θ(g(n)), then f(n) is O(g(n)).
</li>
</ol>
<h4>
Little-Oh and Little-Omega</h4>
Recall that big-Oh captures the idea that for large n, f(n) is not
much bigger than g(n). Now we want to capture the idea that, for
large n, f(n) is tiny compared to g(n).
<br />
If you remember limits from calculus, what we want is that
f(n)/g(n)→0 as n→∞. However, the definition we give
does not use limits (it essentially has the definition of a limit
built in).<br />
<br />
<b>Definition</b>: Let f(n) and g(n) be real valued
functions of an integer variable. We say
<b>f(n) is o(g(n))</b>
if for <b>any</b> c>0,
there is an n<sub>0</sub> such that
f(n)≤g(n) for all n>n<sub>0</sub>.
This is pronounced as "f(n) is little-oh of g(n)".<br />
<br />
<b>Definition</b>: Let f(n) and g(n) be real valued
functions of an integer variable. We say
<b>f(n) is ω(g(n)</b> if
g(n) is o(f(n)). This is pronounced as "f(n) is little-omega of g(n)".
<br />
<b>Examples</b>: log(n) is o(n) and x<sup>2</sup> is
ω(nlog(n)).
<br />
<br />
<div style="text-align: left;">
<br /></div>
<h3 style="text-align: left;">
Properties of Notations</h3>
<div style="text-align: left;">
</div>
<br />
<div style="direction: ltr;">
<table border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse; border-color: #A3A3A3; border-style: solid; border-width: 1pt; direction: ltr;" valign="top">
<tbody>
<tr>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: .9145in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
<span style="font-weight: bold;">Notations</span></div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 1.2555in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
<span style="font-weight: bold;">Reflexive</span></div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 2.0451in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
<span style="font-weight: bold;">Transitive</span></div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 1.0909in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
<span style="font-weight: bold;">Symmetric</span></div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 2.293in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
<span style="font-weight: bold;">Transpose Symmetric</span></div>
</td>
</tr>
<tr>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: .8958in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
<span style="font-weight: bold;">O</span></div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 1.2555in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
Yes</div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 2.0451in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
Yes</div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 1.0798in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
No</div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 2.3013in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
No</div>
</td>
</tr>
<tr>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: .8958in;">
<div lang="el-GR" style="font-family: "times new roman"; font-size: 10.0pt; margin: 0in;">
<span style="font-weight: bold;">Ω</span></div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 1.2555in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
Yes</div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 2.0451in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
Yes</div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 1.0798in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
No</div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 2.5819in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
Yes<br />
</div>
<div style="margin: 0in;">
<span lang="en-US" style="font-family: Helvetica; font-size: 12.0pt;">Yes i.e. f(n) = O(g(n)), iff<span style="mso-spacerun: yes;">
</span>g(n) = </span><span lang="el-GR" style="font-family: "times new roman"; font-size: 10.0pt;">Ω</span><span lang="en-US" style="font-family: Helvetica; font-size: 12.0pt;">(f(n))</span></div>
</td>
</tr>
<tr>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: .8958in;">
<div lang="el-GR" style="font-family: "times new roman"; font-size: 12.0pt; margin: 0in;">
<span style="font-weight: bold;">Θ</span></div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 1.2555in;">
<div style="font-size: 12.0pt; margin: 0in;">
<span lang="en-US" style="font-family: Helvetica;">Yes<br />
i.e.f(n) = </span><span lang="el-GR" style="font-family: "times new roman";">Θ</span><span lang="en-US" style="font-family: "times new roman";">
(f(n))</span></div>
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
<br /></div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 2.0451in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
Yes</div>
<div style="font-size: 12.0pt; margin: 0in;">
<span lang="en-US" style="font-family: Helvetica;">f(n)=</span><span lang="el-GR" style="font-family: "times new roman";">Θ</span><span lang="en-US" style="font-family: Helvetica;">(g(n)) and
g(n)=</span><span lang="el-GR" style="font-family: "times new roman";">Θ</span><span lang="en-US" style="font-family: Helvetica;">(h(n))<br />
<span style="mso-spacerun: yes;"> </span>implies f(n) = </span><span lang="el-GR" style="font-family: "times new roman";">Θ</span><span lang="en-US" style="font-family: Helvetica;">(h(n))</span></div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 1.0798in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
Yes</div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 2.3013in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
No</div>
</td>
</tr>
<tr>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: .8958in;">
<div style="font-family: arial; font-size: 10.0pt; margin: 0in;">
<span style="font-weight: bold;">o</span></div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 1.2555in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
No</div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 2.0451in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
Yes</div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 1.0798in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
No</div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 2.3013in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
No</div>
</td>
</tr>
<tr>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: .8958in;">
<div lang="el-GR" style="font-family: "times new roman"; font-size: 10.0pt; margin: 0in;">
<span style="font-weight: bold;">ω</span></div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 1.2555in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
No</div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 2.0451in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
Yes</div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 1.0798in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
No</div>
</td>
<td style="border-color: #A3A3A3; border-style: solid; border-width: 1pt; padding: 4pt 4pt 4pt 4pt; vertical-align: top; width: 2.3013in;">
<div lang="en-US" style="font-family: Helvetica; font-size: 12.0pt; margin: 0in;">
No</div>
</td>
</tr>
</tbody></table>
</div>
<br />
<br />
<br />
<b>Source</b><br />
<a href="https://cs.nyu.edu/courses/fall02/V22.0310-002/class-notes.html">https://cs.nyu.edu/courses/fall02/V22.0310-002/class-notes.html</a></div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-53348125501946159952015-09-04T06:24:00.000+05:302015-09-04T06:25:13.841+05:30Given a BST with 2 nodes swapped, fix it<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
Problem</h3>
Given a BST with 2 nodes swapped fix it.<br />
<br />
<b>Example</b><br />
Consider the BST:<br />
<pre class="brush:java">Following is the correct BST
10
/ \
5 20
/ \
2 8</pre>
<br />
<br />
Now we swap 8 and 20, and BST is changed.<br />
<br />
<pre class="brush:java">Input Tree:
10
/ \
5 8
/ \
2 20
In the above tree, nodes 20 and 8 must be swapped to fix the tree.
</pre>
In the <a href="http://k2code.blogspot.in/2015/09/given-binary-search-tree-with-2-nodes.html">previous post</a>, we saw how many pairs in the input tree violate the BST property. Here we will fix it.<br />
<br />
<b>1.</b> The swapped nodes are not adjacent in the inorder traversal of the BST.
<br />
<pre> For example, Nodes 5 and 25 are swapped in {3 5 7 8 10 15 20 25}.
The inorder traversal of the given tree is 3 25 7 8 10 15 20 5
</pre>
If we observe carefully, during inorder traversal, we find node 7 is
smaller than the previous visited node 25. Here save the context of
node 25 (previous node). Again, we find that node 5 is smaller than the
previous node 20. This time, we save the context of node 5 ( current
node ). Finally swap the two node’s values.<br />
<b>2.</b> The swapped nodes are adjacent in the inorder traversal of BST.
<br />
<pre> For example, Nodes 7 and 8 are swapped in {3 5 7 8 10 15 20 25}.
The inorder traversal of the given tree is 3 5 8 7 10 15 20 25 </pre>
Unlike case #1, here only one point exists where a node value is
smaller than previous node value. e.g. node 7 is smaller than node 8.<br />
<br />
<b>How to Solve?</b> <i>We will maintain three pointers,
first, middle and last. When we find the first point where current node
value is smaller than previous node value, we update the first with the
previous node & middle with the current node. When we find the
second point where current node value is smaller than previous node
value, we update the last with the current node. In case #2, we will
never find the second point. So, last pointer will not be updated. After
processing, if the last node value is null, then two swapped nodes of
BST are adjacent</i>.<br />
<br />
code:<br />
<pre class="brush:java"> private void swap(Node a, Node b) {
if (n1 == null || n2 == null) return;
int tmp = a.val;
a.val = b.val;
b.val = tmp;
}
public void recoverTree(Node root) {
Node cur = root, pre = null, first = null, second = null;
// in order travesal should return a sorted list
Stack<node> stack = new Stack<node>();
while (cur != null) { // find the left most child
stack.push(cur);
cur = cur.left;
}
while (!stack.isEmpty()) {
cur = stack.pop();
// is it wrong?
if (pre != null && cur.val < pre.val) {
if (first == null) {
// the first wrong item should be the bigger one
first = pre;
second = cur; // there is a chance that the two were swapped
} else {
// the second wrong item should be the smaller one
second = cur;
break;
}
}
// go to right child and repeat
pre = cur;
cur = cur.right;
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
}
swap(first, second);
}
</node></node></pre>
<br />
<br />
<b>References</b><br />
<ul style="text-align: left;">
<li><a href="http://www.geeksforgeeks.org/fix-two-swapped-nodes-of-bst/">http://www.geeksforgeeks.org/fix-two-swapped-nodes-of-bst/</a> </li>
</ul>
</div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-31072654649146684042015-09-04T05:44:00.003+05:302015-09-04T06:29:23.032+05:30Given a binary search tree with 2 nodes swapped find number of pairs not following BST properties<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
Problem</h3>
Given a binary search tree with 2 nodes swapped, give the number of nodes not following bst property. Follow up - Fix the BST, in the <a href="http://k2code.blogspot.in/2015/09/given-bst-with-2-nodes-swapped-fix-it.html">next post</a>.<br />
<br />
<b>Example</b><br />
Consider the BST:<br />
<pre class="brush:java">Following is the correct BST
10
/ \
5 20
/ \
2 8</pre>
<br />
<br />
Now we swap 8 and 20, and BST is changed.<br />
<br />
<pre class="brush:java">Input Tree:
10
/ \
5 8
/ \
2 20
In the above tree, nodes 20 and 8 must be swapped to fix the tree.
</pre>
Now number of pairs not following BST property are 3. The reason is :<br />
<ul style="text-align: left;">
<li>10-20</li>
<li>10-8</li>
<li>20-8</li>
</ul>
<h3 style="text-align: left;">
Solution</h3>
<b>Method 1 - Using in-order traversal</b><br />
We can have following solution:<br />
<ol style="text-align: left;">
<li>Find the inorder traversal of the input tree. Example - 2, 5, 20, 10, 8</li>
<li>Find the number of <a href="http://k2code.blogspot.in/2013/08/inversions.html">inversions</a> in the inorder traversal. That is the answer. Here the inversions are 20-10, 20-8, and 10-8. </li>
</ol>
Time complexity - O(n logn) as O(n) time for inorder traversal and O(nlogn) for number of inversions in the sorted array.<br />
<br /></div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-62375082244515127242015-09-04T05:12:00.001+05:302015-09-04T05:12:41.760+05:30For a Given node of a binary tree, print the K distance nodes.<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem</b><br />
<div class="post-text" itemprop="text">
You are given a function printKDistanceNodes which takes in a root
node of a binary tree, a start node and an integer K. Complete the
function to print the value of all the nodes (one-per-line) which are a K
distance from the given start node in sorted order. Distance can be
upwards or downwards.<br />
<br />
<b>Example</b><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEglnI7FqXdZew88Hggfxr1HTtayMu_2FEbvyWiFQDjVJlrSZ893RxK15GsP9zYvKANXC5RYHpHgFBvwlYRSV9UTPQ-KTZJnWELBjxPEoKbJxCB64gSfP8di6VB_vFDCtKt3RoQpl27HTamV/s1600/bst-remove-case-2-1_1child.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="267" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEglnI7FqXdZew88Hggfxr1HTtayMu_2FEbvyWiFQDjVJlrSZ893RxK15GsP9zYvKANXC5RYHpHgFBvwlYRSV9UTPQ-KTZJnWELBjxPEoKbJxCB64gSfP8di6VB_vFDCtKt3RoQpl27HTamV/s320/bst-remove-case-2-1_1child.png" width="320" /></a></div>
start node = 18, k = 2 , then output = 2, 19, 25</div>
<div class="post-text" itemprop="text">
start node = 18, k = 3, then output = -4, 3<br />
<br /></div>
<h3 style="text-align: left;">
Solution </h3>
We have already seen a similar problem, where we have to find <a href="http://k2code.blogspot.in/2014/01/print-nodes-at-k-distance-from-root.html">k distance from the root</a> and <a href="http://k2code.blogspot.in/2015/09/print-all-nodes-that-are-at-distance-k.html" target="_blank">k distance from the leaf</a>. Find the distance from root is easy. In the second case of printing from bottom to top (k distance from leaves), we know the direction, i.e. we have to go up. But here we have to find the k elements even going upwards.<br />
<br />
Note :- Parent pointer is not given.<br />
<br />
<b>Method 1 - Using the recursion</b> <br />
<br />
(Printing nodes at a disance of K downwards is easy). Its a simple
recursive function.So moving to nodes which are in upwards direction.<br />
<br />
There are two types of nodes to be considered.<br />
<b>1)</b> Nodes in the subtree rooted with target node. For example if the target node is 18 and k is 2, then such nodes are 19 and 25.<br />
<b>2) </b>Other nodes, may be an ancestor of target, or a node
in some other subtree. For target node 18 and k is 2, the node 2 comes
in this category.<br />
<br />
Finding the first type of nodes is easy to implement. Just traverse
subtrees rooted with the target node and decrement k in recursive call.
When the k becomes 0, print the node currently being traversed (See <a href="http://k2code.blogspot.in/2014/01/print-nodes-at-k-distance-from-root.html" target="_blank">this </a>for more details). Here we call the function as <i>printkdistanceNodeDown()</i>.<br />
<br />
How to find nodes of second type? For the output nodes not lying in
the subtree with the target node as the root, we must go through all
ancestors. For every ancestor, we find its distance from target node,
let the distance be d, now we go to other subtree (if target was found
in left subtree, then we go to right subtree and vice versa) of the
ancestor and find all nodes at k-d distance from the ancestor.<br />
<pre class="brush:java">// Recursive function to print all the nodes at distance k in the
// tree (or subtree) rooted with given root. See
void printkdistanceNodeDown(Node root, int k)
{
// Base Case
if (root == null || k < 0) return;
// If we reach a k distant node, print it
if (k==0)
{
System.out.println(root.data);
return;
}
// Recur for left and right subtrees
printkdistanceNodeDown(root.left, k-1);
printkdistanceNodeDown(root.right, k-1);
}
// Prints all nodes at distance k from a given target node.
// The k distant nodes may be upward or downward. This function
// Returns distance of root from target node, it returns -1 if target
// node is not present in tree rooted with root.
int printkdistanceNode(Node root, Node target , int k)
{
// Base Case 1: If tree is empty, return -1
if (root == null) return -1;
// If target is same as root. Use the downward function
// to print all nodes at distance k in subtree rooted with
// target or root
if (root == target)
{
printkdistanceNodeDown(root, k);
return 0;
}
// Recur for left subtree
int dl = printkdistanceNode(root.left, target, k);
// Check if target node was found in left subtree
if (dl != -1)
{
// If root is at distance k from target, print root
// Note that dl is Distance of root's left child from target
if (dl + 1 == k)
System.out.println(root.data) endl;
// Else go to right subtree and print all k-dl-2 distant nodes
// Note that the right child is 2 edges away from left child
else
printkdistanceNodeDown(root.right, k-dl-2);
// Add 1 to the distance and return value for parent calls
return 1 + dl;
}
// MIRROR OF ABOVE CODE FOR RIGHT SUBTREE
// Note that we reach here only when node was not found in left subtree
int dr = printkdistanceNode(root.right, target, k);
if (dr != -1)
{
if (dr + 1 == k)
System.out.println(root.data) endl;
else
printkdistanceNodeDown(root.left, k-dr-2);
return 1 + dr;
}
// If target was neither present in left nor in right subtree
return -1;
}
</pre>
<br />
<br />
<b>Method 2 - Using the queue </b><br />
<br />
Use a queue of size K to store the root to node path.<br />
Now since, the queue is of size K.As soon as we find the NODE in tree,
the node at front of queue is at a distance K from NODE. It can be the
case that the front node is less than K distant from NODE.<br />
So, maintain a counter.<br />
<br />
Now start popping a node from queue which is at distant i from NODE,
and print all downwards nodes at distance K-i in its other subtree.We
only need to print the nodes in other subtree to avoid Error.<br />
<br />
Note :- Since we need to print the nodes in sorted order, we can
maintain a priority queue to store the nodes and after processing the
nodes, we can print it.<br />
<br />
<b>References</b><br />
<ul style="text-align: left;">
<li><a href="http://www.geeksforgeeks.org/print-nodes-distance-k-given-node-binary-tree/">http://www.geeksforgeeks.org/print-nodes-distance-k-given-node-binary-tree/</a></li>
<li><a href="http://stackoverflow.com/questions/7865055/nodes-at-a-distance-k-in-binary-tree">stackoverflow.com/questions/7865055/nodes-at-a-distance-k-in-binary-tree</a></li>
<li><a href="http://stackoverflow.com/questions/27813998/how-to-find-nodes-at-a-distance-k-from-the-given-node-in-binary-tree">http://stackoverflow.com/questions/27813998/how-to-find-nodes-at-a-distance-k-from-the-given-node-in-binary-tree</a></li>
</ul>
</div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-10782104516376441272015-09-04T04:12:00.000+05:302015-09-04T04:33:44.468+05:30 Print all nodes that are at distance k from a leaf node<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
Problem </h3>
Given a Binary Tree and a positive integer k, print all nodes that are distance k from a leaf node.<br />
<br />
Here the meaning of distance is different from <a href="http://k2code.blogspot.in/2015/09/find-distance-between-2-nodes-in-binary.html" target="_blank">previous post</a>.
Here k distance from a leaf means k levels higher than a leaf node.
For example if k is more than height of Binary Tree, then nothing should
be printed. Expected time complexity is O(n) where n is the number
nodes in the given Binary Tree.<br />
<br />
<br />
<br />
<br />
<b>Example</b><br />
(<i>Please ignore the empty node, and consider it null</i>) <br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgzyhC4QnWmXMDw-lcaZ9dVTcRkgJo_j6zROk9vrsQuZfX7UbJ5FTmOfRviogvORG7jfvz722w-5C7JYyIy6UgkZFqeTMH_1Wo3PP8dAs_NtSFa_HcyDymCNb98ThexF9_Qv1jF-PPLkycU/s1600/bst-remove-case-3-6.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="174" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgzyhC4QnWmXMDw-lcaZ9dVTcRkgJo_j6zROk9vrsQuZfX7UbJ5FTmOfRviogvORG7jfvz722w-5C7JYyIy6UgkZFqeTMH_1Wo3PP8dAs_NtSFa_HcyDymCNb98ThexF9_Qv1jF-PPLkycU/s320/bst-remove-case-3-6.png" width="320" /></a></div>
<br />
k = 1, Answer = 2, 19 , 21<br />
k = 2, Answer = 5, 18 , 19<br />
<br />
<h3 style="text-align: left;">
Solution</h3>
The idea is to traverse the tree. Keep storing all ancestors till we
hit a leaf node. When we reach a leaf node, we print the ancestor at
distance k. We also need to keep track of nodes that are already
printed as output. For that we use a boolean array visited[].<br />
<br />
<pre class="brush:java">// This function prints all nodes that are distance k from a leaf node
// path[] - Store ancestors of a node
// visited[] - Stores true if a node is printed as output. A node may be k
// distance away from many leaves, we want to print it once
void kDistantFromLeafUtil(Node node, int path[], bool visited[],
int pathLen, int k)
{
// Base case
if (node==null) return;
// append this Node to the path array
path[pathLen] = node.data;
visited[pathLen] = false;
pathLen++;
// it's a leaf, so print the ancestor at distance k only
// if the ancestor is not already printed
if (node.left == null && node.right == null &&
pathLen-k-1 >= 0 && visited[pathLen-k-1] == false)
{
System.out.print(path[pathLen-k-1] + " ");
visited[pathLen-k-1] = true;
return;
}
// If not leaf node, recur for left and right subtrees
kDistantFromLeafUtil(node.left, path, visited, pathLen, k);
kDistantFromLeafUtil(node.right, path, visited, pathLen, k);
}
// Given a binary tree and a nuber k, print all nodes that are k
// distant from a leaf
void printKDistantfromLeaf(Node node, int k)
{
int[] path = new int[MAX_HEIGHT];
boolean[] visited = new boolean[MAX_HEIGHT];
//all the elements false in visited
Arrays.fill(visited, false);
kDistantFromLeafUtil(node, path, visited, 0, k);
}
</pre>
<br />
<br />
<b>References</b><br />
<ul style="text-align: left;">
<li><a href="http://www.geeksforgeeks.org/print-nodes-distance-k-leaf-node/">http://www.geeksforgeeks.org/print-nodes-distance-k-leaf-node/</a></li>
</ul>
</div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-60314923431752046782015-09-04T03:45:00.001+05:302016-03-10T15:15:41.330+05:30Find the distance between 2 nodes in Binary Tree<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
Problem</h3>
Find the distance between two keys in a binary tree, no parent pointers are given. <span id="more-127078"></span>Distance between two nodes is the minimum number of edges to be traversed to reach one node from other.<br />
<br />
<b>Example</b><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgdk1rCBRXopXkKY5242OAdOPEUlC7LjY8xyKRhqHXb9s1nmMgFyKmrLwLIsboREsOSAxXLb_rYd6n-Xhq-Y_-c4wXFQYjDdmzXch2U_vnB7r7bPQeNgR94W5kvZWa9SrPf46Vx-UZsi2tg/s1600/bst-remove-case-2-3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgdk1rCBRXopXkKY5242OAdOPEUlC7LjY8xyKRhqHXb9s1nmMgFyKmrLwLIsboREsOSAxXLb_rYd6n-Xhq-Y_-c4wXFQYjDdmzXch2U_vnB7r7bPQeNgR94W5kvZWa9SrPf46Vx-UZsi2tg/s1600/bst-remove-case-2-3.png" /></a></div>
Dist(-4,3) = 2,<br />
Dist (-4,19) = 4<br />
Dist(21,-4) = 3<br />
Dist(2,-4) = 1<br />
<h3 style="text-align: left;">
Solution</h3>
The distance between two nodes can be obtained in terms of <a href="http://k2code.blogspot.in/2009/12/find-closest-ancestor-of-two-nodes-in.html" target="_blank">lowest common ancestor</a>. Following is the formula.<br />
<br />
<pre class="brush:java">Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2*Dist(root, lca)
'n1' and 'n2' are the two given keys
'root' is root of given Binary Tree.
'lca' is lowest common ancestor of n1 and n2
Dist(n1, n2) is the distance between n1 and n2.
</pre>
<br />
Example take the case of Dist(-4,3)<br />
LCA(-4,3) = 2<br />
Dist(-4,3) = Dist(5,-4)+Dist(5,3) - 2 * (5,2) = 3 + 3 - 2 * 2 = 2<br />
<br />
Now lets do the coding.<br />
<br />
<b>Code</b> <br />
<br />
<pre class="brush:java">// Returns level of key k if it is present in tree, otherwise returns -1
int findLevel(Node root, int k, int level)
{
// Base Case
if (root == null)
return -1;
// If key is present at root, or in left subtree or right subtree,
// return true;
if (root.key == k)
return level;
int l = findLevel(root.left, k, level+1);
return (l != -1)? l : findLevel(root.right, k, level+1);
}
// This function returns pointer to LCA of two given values n1 and n2.
// It also sets d1, d2 and dist if one key is not ancestor of other
// Note that we set the value in findDistUtil for d1,d2 and dist
// d1 -. To store distance of n1 from root
// d2 -. To store distance of n2 from root
// lvl -. Level (or distance from root) of current node
// dist -. To store distance between n1 and n2
Node findDistUtil(Node root, int n1, int n2, Integer d1, Integer d2,
Integer dist, int lvl)
{
// Base case
if (root == null) return null;
// If either n1 or n2 matches with root's key, report
// the presence by returning root (Note that if a key is
// ancestor of other, then the ancestor key becomes LCA
if (root.key == n1)
{
d1 = lvl;
return root;
}
if (root.key == n2)
{
d2 = lvl;
return root;
}
// Look for n1 and n2 in left and right subtrees
Node left_lca = findDistUtil(root.left, n1, n2, d1, d2, dist, lvl+1);
Node right_lca = findDistUtil(root.right, n1, n2, d1, d2, dist, lvl+1);
// If both of the above calls return Non-null, then one key
// is present in once subtree and other is present in other,
// So this node is the LCA
if (left_lca!=null && right_lca!=null)
{
dist = d1 + d2 - 2*lvl;
return root;
}
// Otherwise check if left subtree or right subtree is LCA
return (left_lca != null)? left_lca: right_lca;
}
// The main function that returns distance between n1 and n2
// This function returns -1 if either n1 or n2 is not present in
// Binary Tree.
int findDistance(Node root, int n1, int n2)
{
// Initialize d1 (distance of n1 from root), d2 (distance of n2
// from root) and dist(distance between n1 and n2)
Integer d1 = -1, d2 = -1, dist;
Node lca = findDistUtil(root, n1, n2, d1, d2, dist, 1);
// If both n1 and n2 were present in Binary Tree, return dist
if (d1 != -1 && d2 != -1)
return dist;
// If n1 is ancestor of n2, consider n1 as root and find level
// of n2 in subtree rooted with n1
if (d1 != -1)
{
dist = findLevel(lca, n2, 0);
return dist;
}
// If n2 is ancestor of n1, consider n2 as root and find level
// of n1 in subtree rooted with n2
if (d2 != -1)
{
dist = findLevel(lca, n1, 0);
return dist;
}
return -1;
}
</pre>
<br />
findDistance() is the main function which calculates the distance, which calls findDistUtil which calculates distance as well as find the LCA in case n1 is not the ancestor of n2 or vice versa.<br />
If n1 is ancestor of n2 or vice versa, we use findLevel to simply find the difference between 2 levels.<br />
<br />
Time Complexity - O(n) as we do single traversal on the tree<br />
<br />
Note that in java we dont have out parameters in function, like we have in c#. Hence I have used Integer Object, so that I can set the value in d1,d2 and dist as we have pass by value for primitive types in java, but we needed pass by reference.<br />
<br />
<b>References</b><br />
<ul style="text-align: left;">
<li><a href="http://www.geeksforgeeks.org/find-distance-two-given-nodes/">http://www.geeksforgeeks.org/find-distance-two-given-nodes/</a> </li>
</ul>
</div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com2tag:blogger.com,1999:blog-3098638925089993315.post-17367336868072807582015-09-04T03:06:00.003+05:302015-09-04T03:06:56.884+05:30Program to count leaf nodes in a binary tree<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
Problem</h3>
Count leaf nodes in a binary tree<br />
<br />
<h3 style="text-align: left;">
Solution</h3>
<b>Method 1 - Recursive</b><br />
Here is the logic:<br />
<ol style="text-align: left;">
<li>If node is NULL then return 0.</li>
<li>Else If left and right child nodes are NULL return 1.</li>
<li>Else recursively calculate leaf count of the tree using below formula.<br />Leaf count of a tree = Leaf count of left subtree + Leaf count of right subtree</li>
</ol>
<br />
Here is the recursive solution:<br />
<pre class="brush:java">int countLeaves(Node node){
if( node == null )
return 0;
if( node.left == null && node.right == null ) {
return 1;
} else {
return countLeaves(node.left) + countLeaves(node.right);
}
}
</pre>
<br />
Time complexity - O(n)<br />
<br />
<b>Method 2 - Iterative</b><br />
Here we can use Queue. Idea is to use Level Order traversal.<br />
<br />
<pre class="brush:java">int countLeaves(Node root)
{
int count=0;
if(root==null)
return 0;
Queue<Node> myqueue = new Queue<Node>();
myqueue.push(root);
while(!myqueue.empty())
{
Node temp;
temp=myqueue.pop();//take the top element from the queue
if(temp.left==null && temp.right==null)
count++;
if(temp.left!=null)
myqueue.push(temp.left);
if(temp.right!=null)
myqueue.push(temp.right);
}
return count;
}
</pre>
<br />
Time complexity - O(n)<br />
Space Complexity - O(n) for queue<br />
<br />
<b>Referenes</b><br />
<ul style="text-align: left;">
<li><a href="http://www.geeksforgeeks.org/write-a-c-program-to-get-count-of-leaf-nodes-in-a-binary-tree/">http://www.geeksforgeeks.org/write-a-c-program-to-get-count-of-leaf-nodes-in-a-binary-tree/</a></li>
<li><a href="http://stackoverflow.com/questions/5949882/counting-number-of-leaf-nodes-in-binary-tree">http://stackoverflow.com/questions/5949882/counting-number-of-leaf-nodes-in-binary-tree</a> </li>
</ul>
</div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-42664544859157023792015-06-26T22:28:00.002+05:302015-06-26T22:28:25.176+05:30Friend Circle - Hackerrank<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
Problem Reference - <a href="https://www.hackerrank.com/contests/juniper-hackathon/challenges/friend-circles">Hackerrank</a></h3>
<br />
<h3 style="text-align: left;">
Problem</h3>
There are <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-1-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-1" style="display: inline-block; width: 0.903em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 0.723em;"><span style="clip: rect(1.741em, 1000em, 2.68em, -0.427em); left: 0em; position: absolute; top: -2.529em;"><span class="mrow" id="MathJax-Span-2"><span class="mi" id="MathJax-Span-3" style="font-family: STIXGeneral; font-style: italic;">N<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.06em;"></span></span></span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 0.933em; overflow: hidden; vertical-align: -0.074em; width: 0px;"></span></span></nobr></span> students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature, i.e., if <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-2-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-4" style="display: inline-block; width: 0.792em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 0.632em;"><span style="clip: rect(1.726em, 1000em, 2.665em, -0.458em); left: 0em; position: absolute; top: -2.529em;"><span class="mrow" id="MathJax-Span-5"><span class="mi" id="MathJax-Span-6" style="font-family: STIXGeneral; font-style: italic;">A</span></span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 0.933em; overflow: hidden; vertical-align: -0.056em; width: 0px;"></span></span></nobr></span> is friend of <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-3-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-7" style="display: inline-block; width: 0.792em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 0.632em;"><span style="clip: rect(1.741em, 1000em, 2.665em, -0.415em); left: 0em; position: absolute; top: -2.529em;"><span class="mrow" id="MathJax-Span-8"><span class="mi" id="MathJax-Span-9" style="font-family: STIXGeneral; font-style: italic;">B</span></span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 0.914em; overflow: hidden; vertical-align: -0.056em; width: 0px;"></span></span></nobr></span> and <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-4-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-10" style="display: inline-block; width: 0.792em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 0.632em;"><span style="clip: rect(1.741em, 1000em, 2.665em, -0.415em); left: 0em; position: absolute; top: -2.529em;"><span class="mrow" id="MathJax-Span-11"><span class="mi" id="MathJax-Span-12" style="font-family: STIXGeneral; font-style: italic;">B</span></span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 0.914em; overflow: hidden; vertical-align: -0.056em; width: 0px;"></span></span></nobr></span> is friend of <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-5-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-13" style="display: inline-block; width: 0.847em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 0.678em;"><span style="clip: rect(1.728em, 1000em, 2.683em, -0.341em); left: 0em; position: absolute; top: -2.529em;"><span class="mrow" id="MathJax-Span-14"><span class="mi" id="MathJax-Span-15" style="font-family: STIXGeneral; font-style: italic;">C<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.022em;"></span></span></span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 0.952em; overflow: hidden; vertical-align: -0.078em; width: 0px;"></span></span></nobr></span>, then <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-6-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-16" style="display: inline-block; width: 0.792em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 0.632em;"><span style="clip: rect(1.726em, 1000em, 2.665em, -0.458em); left: 0em; position: absolute; top: -2.529em;"><span class="mrow" id="MathJax-Span-17"><span class="mi" id="MathJax-Span-18" style="font-family: STIXGeneral; font-style: italic;">A</span></span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 0.933em; overflow: hidden; vertical-align: -0.056em; width: 0px;"></span></span></nobr></span> is also friend of <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-7-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-19" style="display: inline-block; width: 0.847em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 0.678em;"><span style="clip: rect(1.728em, 1000em, 2.683em, -0.341em); left: 0em; position: absolute; top: -2.529em;"><span class="mrow" id="MathJax-Span-20"><span class="mi" id="MathJax-Span-21" style="font-family: STIXGeneral; font-style: italic;">C<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.022em;"></span></span></span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 0.952em; overflow: hidden; vertical-align: -0.078em; width: 0px;"></span></span></nobr></span>. A friend circle is a group of students who are directly or indirectly friends. <br />
You are given a <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-8-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-22" style="display: inline-block; width: 7.903em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 6.414em;"><span style="clip: rect(1.74em, 1000em, 2.69em, -0.427em); left: 0em; position: absolute; top: -2.529em;"><span class="mrow" id="MathJax-Span-23"><span class="mi" id="MathJax-Span-24" style="font-family: STIXGeneral; font-style: italic;">N<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.06em;"></span></span><span class="mo" id="MathJax-Span-25" style="font-family: STIXGeneral; padding-left: 0.25em;">×</span><span class="mi" id="MathJax-Span-26" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.25em;">N<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.06em;"></span></span><span class="mo" id="MathJax-Span-27" style="font-family: STIXGeneral; padding-left: 0.25em;">−</span><span class="mi" id="MathJax-Span-28" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.25em;">m</span><span class="mi" id="MathJax-Span-29" style="font-family: STIXGeneral; font-style: italic;">a</span><span class="mi" id="MathJax-Span-30" style="font-family: STIXGeneral; font-style: italic;">t<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.018em;"></span></span><span class="mi" id="MathJax-Span-31" style="font-family: STIXGeneral; font-style: italic;">r<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.023em;"></span></span><span class="mi" id="MathJax-Span-32" style="font-family: STIXGeneral; font-style: italic;">i</span><span class="mi" id="MathJax-Span-33" style="font-family: STIXGeneral; font-style: italic;">x<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.003em;"></span></span></span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 0.946em; overflow: hidden; vertical-align: -0.086em; width: 0px;"></span></span></nobr></span> <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-9-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-34" style="display: inline-block; width: 1.069em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 0.858em;"><span style="clip: rect(1.741em, 1000em, 2.665em, -0.425em); left: 0em; position: absolute; top: -2.529em;"><span class="mrow" id="MathJax-Span-35"><span class="mi" id="MathJax-Span-36" style="font-family: STIXGeneral; font-style: italic;">M<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.039em;"></span></span></span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 0.914em; overflow: hidden; vertical-align: -0.056em; width: 0px;"></span></span></nobr></span> which consists of characters <code>Y</code> or <code>N</code>. If <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-10-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-37" style="display: inline-block; width: 5.792em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 4.697em;"><span style="clip: rect(1.732em, 1000em, 2.872em, -0.425em); left: 0em; position: absolute; top: -2.529em;"><span class="mrow" id="MathJax-Span-38"><span class="mi" id="MathJax-Span-39" style="font-family: STIXGeneral; font-style: italic;">M<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.039em;"></span></span><span class="mo" id="MathJax-Span-40" style="font-family: STIXGeneral;">[</span><span class="mi" id="MathJax-Span-41" style="font-family: STIXGeneral; font-style: italic;">i</span><span class="mo" id="MathJax-Span-42" style="font-family: STIXGeneral;">]</span><span class="mo" id="MathJax-Span-43" style="font-family: STIXGeneral;">[</span><span class="mi" id="MathJax-Span-44" style="font-family: STIXGeneral; font-style: italic;">j<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.001em;"></span></span><span class="mo" id="MathJax-Span-45" style="font-family: STIXGeneral;">]</span><span class="mo" id="MathJax-Span-46" style="font-family: STIXGeneral; padding-left: 0.313em;">=</span><span class="mi" id="MathJax-Span-47" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.313em;">Y<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.077em;"></span></span></span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.18em; overflow: hidden; vertical-align: -0.31em; width: 0px;"></span></span></nobr></span>, then <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-11-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-48" style="display: inline-block; width: 1.125em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 0.903em;"><span style="clip: rect(1.214em, 1000em, 2.36em, -0.358em); left: 0em; position: absolute; top: -2.213em;"><span class="mrow" id="MathJax-Span-49"><span class="msubsup" id="MathJax-Span-50"><span style="display: inline-block; height: 0px; position: relative; width: 0.888em;"><span style="clip: rect(1.74em, 1000em, 2.676em, -0.358em); left: 0em; position: absolute; top: -2.529em;"><span class="mi" id="MathJax-Span-51" style="font-family: STIXGeneral; font-style: italic;">i</span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span><span style="left: 0.271em; position: absolute; top: -2.685em;"><span class="texatom" id="MathJax-Span-52"><span class="mrow" id="MathJax-Span-53"><span class="mi" id="MathJax-Span-54" style="font-family: STIXGeneral; font-size: 70.7%; font-style: italic;">t<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.013em;"></span></span><span class="mi" id="MathJax-Span-55" style="font-family: STIXGeneral; font-size: 70.7%; font-style: italic;">h</span></span></span><span style="display: inline-block; height: 2.304em; width: 0px;"></span></span></span></span></span><span style="display: inline-block; height: 2.213em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.187em; overflow: hidden; vertical-align: -0.069em; width: 0px;"></span></span></nobr></span> and <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-12-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-56" style="display: inline-block; width: 1.181em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 0.949em;"><span style="clip: rect(1.216em, 1000em, 2.556em, -0.531em); left: 0em; position: absolute; top: -2.213em;"><span class="mrow" id="MathJax-Span-57"><span class="msubsup" id="MathJax-Span-58"><span style="display: inline-block; height: 0px; position: relative; width: 0.938em;"><span style="clip: rect(1.742em, 1000em, 2.872em, -0.531em); left: 0em; position: absolute; top: -2.529em;"><span class="mi" id="MathJax-Span-59" style="font-family: STIXGeneral; font-style: italic;">j<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.001em;"></span></span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span><span style="left: 0.321em; position: absolute; top: -2.683em;"><span class="texatom" id="MathJax-Span-60"><span class="mrow" id="MathJax-Span-61"><span class="mi" id="MathJax-Span-62" style="font-family: STIXGeneral; font-size: 70.7%; font-style: italic;">t<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.013em;"></span></span><span class="mi" id="MathJax-Span-63" style="font-family: STIXGeneral; font-size: 70.7%; font-style: italic;">h</span></span></span><span style="display: inline-block; height: 2.304em; width: 0px;"></span></span></span></span></span><span style="display: inline-block; height: 2.213em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.426em; overflow: hidden; vertical-align: -0.31em; width: 0px;"></span></span></nobr></span> students are friends with each other, otherwise not. You have to print the total number of friend circles in the class. <br />
<b>Input Format</b> <br />
First line of the input contains an integer <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-13-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-64" style="display: inline-block; width: 0.903em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 0.723em;"><span style="clip: rect(1.741em, 1000em, 2.68em, -0.427em); left: 0em; position: absolute; top: -2.529em;"><span class="mrow" id="MathJax-Span-65"><span class="mi" id="MathJax-Span-66" style="font-family: STIXGeneral; font-style: italic;">N<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.06em;"></span></span></span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 0.933em; overflow: hidden; vertical-align: -0.074em; width: 0px;"></span></span></nobr></span> - (size of the matrix), followed by N lines each having N characters. <br />
<b>Output Format</b> <br />
Print the maximum number of friend circles. <br />
<b>Constraints</b> <br />
<span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-14-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-67" style="display: inline-block; width: 6.569em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 5.33em;"><span style="clip: rect(1.718em, 1000em, 2.768em, -0.296em); left: 0em; position: absolute; top: -2.529em;"><span class="mrow" id="MathJax-Span-68"><span class="mn" id="MathJax-Span-69" style="font-family: STIXGeneral;">1</span><span class="mo" id="MathJax-Span-70" style="font-family: STIXGeneral; padding-left: 0.313em;">≤</span><span class="mi" id="MathJax-Span-71" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.313em;">N<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.06em;"></span></span><span class="mo" id="MathJax-Span-72" style="font-family: STIXGeneral; padding-left: 0.313em;">≤</span><span class="mn" id="MathJax-Span-73" style="font-family: STIXGeneral; padding-left: 0.313em;">300</span></span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.069em; overflow: hidden; vertical-align: -0.182em; width: 0px;"></span></span></nobr></span> <br />
Each element of matrix friends will be <code>Y</code> or <code>N</code>. <br />
Number of rows and columns will be equal in the matrix. <br />
<span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-15-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-74" style="display: inline-block; width: 5.792em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 4.697em;"><span style="clip: rect(1.732em, 1000em, 2.821em, -0.425em); left: 0em; position: absolute; top: -2.529em;"><span class="mrow" id="MathJax-Span-75"><span class="mi" id="MathJax-Span-76" style="font-family: STIXGeneral; font-style: italic;">M<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.039em;"></span></span><span class="mo" id="MathJax-Span-77" style="font-family: STIXGeneral;">[</span><span class="mi" id="MathJax-Span-78" style="font-family: STIXGeneral; font-style: italic;">i</span><span class="mo" id="MathJax-Span-79" style="font-family: STIXGeneral;">]</span><span class="mo" id="MathJax-Span-80" style="font-family: STIXGeneral;">[</span><span class="mi" id="MathJax-Span-81" style="font-family: STIXGeneral; font-style: italic;">i</span><span class="mo" id="MathJax-Span-82" style="font-family: STIXGeneral;">]</span><span class="mo" id="MathJax-Span-83" style="font-family: STIXGeneral; padding-left: 0.313em;">=</span><span class="mi" id="MathJax-Span-84" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.313em;">Y<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.077em;"></span></span></span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.117em; overflow: hidden; vertical-align: -0.247em; width: 0px;"></span></span></nobr></span>, where <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-16-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-85" style="display: inline-block; width: 5.069em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 4.11em;"><span style="clip: rect(1.718em, 1000em, 2.768em, -0.383em); left: 0em; position: absolute; top: -2.529em;"><span class="mrow" id="MathJax-Span-86"><span class="mn" id="MathJax-Span-87" style="font-family: STIXGeneral;">0</span><span class="mo" id="MathJax-Span-88" style="font-family: STIXGeneral; padding-left: 0.313em;">≤</span><span class="mi" id="MathJax-Span-89" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.313em;">i</span><span class="mo" id="MathJax-Span-90" style="font-family: STIXGeneral; padding-left: 0.313em;"><</span><span class="mi" id="MathJax-Span-91" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.313em;">N<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.06em;"></span></span></span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.069em; overflow: hidden; vertical-align: -0.182em; width: 0px;"></span></span></nobr></span> <br />
<span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-17-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-92" style="display: inline-block; width: 3.403em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 2.755em;"><span style="clip: rect(1.732em, 1000em, 2.872em, -0.425em); left: 0em; position: absolute; top: -2.529em;"><span class="mrow" id="MathJax-Span-93"><span class="mi" id="MathJax-Span-94" style="font-family: STIXGeneral; font-style: italic;">M<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.039em;"></span></span><span class="mo" id="MathJax-Span-95" style="font-family: STIXGeneral;">[</span><span class="mi" id="MathJax-Span-96" style="font-family: STIXGeneral; font-style: italic;">i</span><span class="mo" id="MathJax-Span-97" style="font-family: STIXGeneral;">]</span><span class="mo" id="MathJax-Span-98" style="font-family: STIXGeneral;">[</span><span class="mi" id="MathJax-Span-99" style="font-family: STIXGeneral; font-style: italic;">j<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.001em;"></span></span><span class="mo" id="MathJax-Span-100" style="font-family: STIXGeneral;">]</span></span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.18em; overflow: hidden; vertical-align: -0.31em; width: 0px;"></span></span></nobr></span> = <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-18-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-101" style="display: inline-block; width: 3.403em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 2.755em;"><span style="clip: rect(1.732em, 1000em, 2.872em, -0.425em); left: 0em; position: absolute; top: -2.529em;"><span class="mrow" id="MathJax-Span-102"><span class="mi" id="MathJax-Span-103" style="font-family: STIXGeneral; font-style: italic;">M<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.039em;"></span></span><span class="mo" id="MathJax-Span-104" style="font-family: STIXGeneral;">[</span><span class="mi" id="MathJax-Span-105" style="font-family: STIXGeneral; font-style: italic;">j<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.001em;"></span></span><span class="mo" id="MathJax-Span-106" style="font-family: STIXGeneral;">]</span><span class="mo" id="MathJax-Span-107" style="font-family: STIXGeneral;">[</span><span class="mi" id="MathJax-Span-108" style="font-family: STIXGeneral; font-style: italic;">i</span><span class="mo" id="MathJax-Span-109" style="font-family: STIXGeneral;">]</span></span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.18em; overflow: hidden; vertical-align: -0.31em; width: 0px;"></span></span></nobr></span>, where <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-19-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-110" style="display: inline-block; width: 7.069em;"><span style="display: inline-block; font-size: 123%; height: 0px; position: relative; width: 5.736em;"><span style="clip: rect(1.718em, 1000em, 2.872em, -0.383em); left: 0em; position: absolute; top: -2.529em;"><span class="mrow" id="MathJax-Span-111"><span class="mn" id="MathJax-Span-112" style="font-family: STIXGeneral;">0</span><span class="mo" id="MathJax-Span-113" style="font-family: STIXGeneral; padding-left: 0.313em;">≤</span><span class="mi" id="MathJax-Span-114" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.313em;">i</span><span class="mo" id="MathJax-Span-115" style="font-family: STIXGeneral; padding-left: 0.313em;"><</span><span class="mi" id="MathJax-Span-116" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.313em;">j<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.001em;"></span></span><span class="mo" id="MathJax-Span-117" style="font-family: STIXGeneral; padding-left: 0.313em;"><</span><span class="mi" id="MathJax-Span-118" style="font-family: STIXGeneral; font-style: italic; padding-left: 0.313em;">N<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.06em;"></span></span></span><span style="display: inline-block; height: 2.529em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.197em; overflow: hidden; vertical-align: -0.31em; width: 0px;"></span></span></nobr></span><br />
<br />
Here is the code<br />
<script src="https://gist.github.com/kinshuk4/fd93f7898b3120dcc065.js"></script><br />
Thanks
</div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-65273444770882867192015-06-10T10:54:00.001+05:302015-06-14T23:26:00.510+05:30Lazy Caterer's sequence<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem </b><br />
Given a circular (or regular polygon) cake and a knife by which you can only cut vertically, find the maximum number of pieces of cake you can get by making n cuts. Write a program to do that.<br />
<br />
<div style="text-align: left;">
<span style="font-size: large;">Solution</span></div>
The solution to this is very simple, if you know mathematics. :P<br />
<br />
Number of pieces p<br />
<pre class="brush:java">p = ( n^2+n+2)/2
p = C(n+1,2) + 1
</pre>
<br />
More on wikipedia - <a href="http://en.wikipedia.org/wiki/Lazy_caterer%27s_sequence">http://en.wikipedia.org/wiki/Lazy_caterer%27s_sequence</a>.<br />
<br />
<span style="font-size: large;">Proof</span><br />
When a circle is cut <i>n</i> times to produce the maximum number of pieces, represented as <i>p</i> = <i>ƒ</i>(<i>n</i>), the <i>n</i>th cut must be considered; the number of pieces before the last cut is <i>ƒ</i>(<i>n</i> − 1), while the number of pieces added by the last cut is <i>n</i>.<br />
To obtain the maximum number of pieces, the <i>n</i>th cut line
should cross all the other previous cut lines inside the circle, but not
cross any intersection of previous cut lines. Thus, the <i>n</i>th line itself is cut in <i>n</i> − 1 places, and into <i>n</i> line segments. Each segment divides one piece of the (<i>n</i> − 1)-cut pancake into 2 parts, adding exactly <i>n</i>
to the number of pieces. The new line can't have any more segments
since it can only cross each previous line once. A cut line can always
cross over all previous cut lines, as rotating the knife at a small
angle around a point that is not an existing intersection will, if the
angle is small enough, intersect all the previous lines including the
last one added.<br />
Thus, the total number of pieces after <i>n</i> cuts is<br />
<br />
f(n) = n + f(n-1) <br />
<dl><dd></dd></dl>
This <a href="http://en.wikipedia.org/wiki/Recurrence_relation" title="Recurrence relation">recurrence relation</a> can be solved. If <i>ƒ</i>(<i>n</i> − 1) is expanded one term the relation becomes<br />
f(n) = n + n-1 + f(n-2) <br />
<dl><dd></dd></dl>
Expansion of the term <i>ƒ</i>(<i>n</i> − 2) can continue until the last term is reduced to <i>ƒ</i>(0), thus,<br />
f(n) = n + n-1 + n-2 ..... + 1 + f(0) <br />
<dl><dd></dd></dl>
But f(0) = 1 , because there is one piece before any cuts are made, this can be rewritten as<br />
<dl><dd>f(n) = 1 + (1+2+3 + .... n)</dd></dl>
This can be simplified, using the formula for the sum of an <a href="http://en.wikipedia.org/wiki/Arithmetic_progression" title="Arithmetic progression">arithmetic progression</a>:<br />
<dl><dd> f(n) = 1+ n*(n+1)/2 = ( n^2+n+2)/2</dd></dl>
<br /></div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-39388646629047239792015-06-02T18:38:00.001+05:302015-06-02T18:38:50.213+05:30Lego Blocks Problem <div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<br />
Problem statement - https://www.hackerrank.com/challenges/lego-blocks<br />
solution - http://stackoverflow.com/questions/15424945/lego-blocks-dynamic-programming<br />
http://stackoverflow.com/questions/913566/has-anyone-seen-a-programming-puzzle-similar-to-this<br />
<br />
Code -<br />
<script src="https://gist.github.com/kinshuk4/2758b2a9a76e0630886c.js"></script>
<br />
Thanks.</div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-57369750704734547312015-05-25T08:47:00.001+05:302015-05-25T08:47:56.343+05:30K reverse a linked list with increasing K<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem</b><br />
<blockquote class="tr_bq">
Reverse k elements in the linked list such that k goes on increasing</blockquote>
<br />
<b>Example</b><br />
Eg. 1 - 2 - 3 - 4 - 5 - 6 - 7<br />
output - 1 - 3 - 2 - 6 - 5- 4 - 7<br />
<br />
<h3 style="text-align: left;">
Solution</h3>
You can take this problem <a href="http://k2code.blogspot.in/2012/01/k-reverse-linked-list.html">here</a>. Here we are just increasing k.<br />
<br />
<pre class="brush:java"> public static ListNode<Integer> reverseSubLinkLists(ListNode<Integer> headerNode) {
ListNode<Integer> nextNode = headerNode.next;
ListNode<Integer> startNode = null;
ListNode<Integer> endNode = null;
int k = 2;
while (nextNode != null) {
startNode = nextNode;
endNode = nextNode;
for (int i = 1; i < k; i++) {
endNode = endNode.next;
if (endNode == null) {
break;
}
}
if (endNode != null) {
// Save the node next to endNode
nextNode = endNode.next;
// Unlink the endNode
endNode.next = null;
// Reverse the list starting from startNode
startNode = reverseListIterative(startNode);
k++;
} else {
nextNode = null;
// // Save the node next to endNode
// nextNode = endNode.next;
// // Unlink the endNode
// endNode.next = null;
// Reverse the list starting from startNode
startNode = reverseListIterative(startNode);
}
if (headerNode == null) {
headerNode = startNode;
} else {
headerNode.next = startNode;
ListNode<Integer> temp = startNode;
while(temp!=null){
if(temp.next==null){
break;
}
temp = temp.next;
}
headerNode = temp;
}
}
return headerNode;
}
public static ListNode<Integer> reverseListIterative(ListNode<Integer> headerNode) {
ListNode<Integer> prevNode = null;
ListNode<Integer> currNode = headerNode;
ListNode<Integer> nextNode = null;
while (currNode != null) {
nextNode = currNode.next;
currNode.next = prevNode;
prevNode = currNode;
currNode = nextNode;
}
return prevNode;
}
</pre>
<br />
Time complexity - O(n)<br />
</div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-28849453343658009942015-05-16T14:51:00.000+05:302015-05-16T14:51:45.160+05:30Convert Binary Tree to Doubly linked list in level order <div dir="ltr" style="text-align: left;" trbidi="on">
<b>Question:</b> write an algorithm to convert a binary tree into a double linked list. For example, if the input is the binary tree below:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjkMWNwUSqPhvE9-xdASWwOsbyJEgIV4P7IYdgcn8LYbFDnEjy_5SlHSsBUgPjHz9KiGnHF9RjTjrWKSavWX5kY57LdmWhu1XnJTyO9VBjxf1TInKtB8ly3hi2uUlbSkSqRTrQD4O8ZoOmX/s1600/bst2dll_tree.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjkMWNwUSqPhvE9-xdASWwOsbyJEgIV4P7IYdgcn8LYbFDnEjy_5SlHSsBUgPjHz9KiGnHF9RjTjrWKSavWX5kY57LdmWhu1XnJTyO9VBjxf1TInKtB8ly3hi2uUlbSkSqRTrQD4O8ZoOmX/s1600/bst2dll_tree.png" /></a></div>
<br />
The output will be a double linked list like this:<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi25AU7465FG3bE5I1QzNZsbT8X4jCCodbIz9YQBR0HaM-BPYetwuiDWI_k8Jvu79qnW9lsQFTqIaY4aV-0r6LbjKC_IT_J_Uc7lGBsXipRnd5NbpkJvt8Wfcd27qNvMsFaF56qOmJqrtZl/s1600/bst2dll_dll.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="58" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi25AU7465FG3bE5I1QzNZsbT8X4jCCodbIz9YQBR0HaM-BPYetwuiDWI_k8Jvu79qnW9lsQFTqIaY4aV-0r6LbjKC_IT_J_Uc7lGBsXipRnd5NbpkJvt8Wfcd27qNvMsFaF56qOmJqrtZl/s1600/bst2dll_dll.png" width="320" /></a></div>
<br />
<br />
<b>Solution:</b> there are two tasks in converting a binary tree to a
linked list. First of all, we must traverse the tree and visit all the
nodes. Second of all, we must break each node from the tree and add it
into the linked list.<br />
For traversing the tree, we'll use level / order traversal a.k.a breadth first search.<br />
<br />
To construct the linked list, each node will have its left pointer point
to the node in front of it and its right pointer point to the node
behind it in the linked list. For instance, if node 1 is in front of
node 2 and node 3 is behind node 2 in the linked list, we'll set left
pointer of node 2 to node 1 and right pointer of node 2 to node 3 (see
picture above)<br />
<pre class="brush:cpp">#include<iostream>
#include<queue>
using namespace std;
struct Node
{
int data;
struct Node* left;
struct Node* right;
};
struct Node* bt2DoubleLinkedList(struct Node* root)
{
if (root == NULL)
return NULL;
queue nodeQueue;
struct Node* head = root; //reference to head of the linked list
struct Node* listIT = NULL; //current node being processed
struct Node* prevNode = NULL; //previous node processed
//initialize the stack
nodeQueue.push(root);
//convert to double linked list
while (!nodeQueue.empty())
{
//process next node in stack
prevNode = listIT;
listIT = nodeQueue.front();
nodeQueue.pop();
//add left child to stack
if (listIT->left != NULL)
nodeQueue.push(listIT->left);
//add right child to stack
if (listIT->right != NULL)
nodeQueue.push(listIT->right);
//add current node to linked list
if (prevNode != NULL)
prevNode->right = listIT;
listIT->left = prevNode;
}
//connect end node of list to null
listIT->right = NULL;
return head;
}
</pre>
<br />
<b>Explanation:</b> the method accepts a pointer to the tree's root as argument and returns the pointer to the head node of the linked list: <br />
<ol>
<li>If the root node is null, we return null because the tree is empty.</li>
<li>If the root is not null, we proceed by first creating a queue to
store the the nodes. Why do we use queue? That is how we traverse the
tree by level. Every time we reach a node, we store its children in the
queue for later processing. Thus, the queue will always have something
in it as long as there are still unvisited node in the tree.</li>
<li>Next, we create three pointers. <b>head</b> points to the head node of the linked list. <b>listIT</b> is our list iterator which used to build the list one node at a time. <b>prevNode</b>
is the last node added into the list. We need to keep track of such
node because we have to change the right pointer of that node to the
node immediate after it, which is the node that listIT will point to.</li>
<li>We initialize the queue by adding the root into it. The reason is
that we will use the condition of empty queue to end the while loop. </li>
<li>The while loop will run until no node left in queue to process. For each node in the queue, we do the following:<br /><br />
<b>prevNode = listIT</b> gets reference to the last processed node because we are about to process a new node<br /><br />
<b>listIT = nodeQueue.front()</b> gets reference to the top in the queue because we're going to add it into the list.<br /><br />
<b>nodeQueue.pop()</b> removes the top node out of the queue.<br /><br />
We then add the left and right child of the top node into the queue, so
we can process them later. Notice that we only add the children if they
are not null.<br /><br />
Finally, we connect the top node to the linked list. First, we set the
right pointer of the previous node (prevNode) to the top node. Then, we
set the left pointer of the top node to the previous node. As the
result, the top node becomes the end node of the linked list and the
previous node completely breaks off the tree.<br /><br />
</li>
<li>When the last node is added into the linked list and the while loop
exits, we have a double linked list. The only thing left is to set the
end node's right pointer (pointed to by listIT) to null because there is
no more node to add into the list.</li>
</ol>
</div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-32099015142163254012015-05-03T20:13:00.003+05:302015-05-03T20:13:50.630+05:30Number of steps required to convert string 1 to string2 when only bring character to first index operation is giving<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem</b><br />
Given 2 strings - s1 and s2, when only 1 operation is allowed - Moving character at a time but only to the first position.<br />
<br />
Example<br />
Example 1 <br />
Input <br />
s1 = abcd<br />
s2 = bacd<br />
<br />
Output<br />
Ans = 1<br />
Reason, just move b forward and we get it. <br />
<br />
Example 2<br />
Input<br />
A = (a)b(cd)e(f)g(hij)<br />B = ahdjcifbeg<br />
Output<br />
Ans =7<br />
Explanation<br />
A = (a)b(cd)e(f)g(hij)<br />B = ahdjcifbeg<br />
Characters b,e,g are in the order, rest characters have to brought first.<br />
<br />
<br />
<h3 style="text-align: left;">
Solution</h3>
This is a DP problem, LCS of the 2 strings is adf, and rest of the character are moved forward, and rest of the characters will be moved forward.<br />
<br /></div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-19302675348060239612015-05-03T20:13:00.002+05:302015-05-03T20:13:37.273+05:30Maximize the number of magical gems by passing through array of house<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem</b><br />
There was a thief, he has to pass through colored house - which can be red or blue, and contain 0 or more gems. The property of these gems is they multiply the previous gems by the current gems in the house. The houses are in array and thief can only visit once to steal the gems, with the goal of maximizing the gems. Find the range of house where he can maximize the gems in such a way that number of red houses are even.<br />
<br />
<b>Example</b><br />
Gem array = 1 2 0 4 5 6 2 3<br />
color array = 0 0 1 1 1 0 0 1 (r=1,b=0)<br />
o/p = 20 (4*5)<br />
<br />
<h3 style="text-align: left;">
Solution</h3>
This is similar to maximum product subarray, but there is another condition of red color.<br />
<br />
Here is the code below:<br />
<pre class="brush:java">int maximumMoney(int n, int[] colour, int[] gems) {
int max = 1;
int red = 0;
int start = 0, end = 0;
int actualMax=1;
for(int i=0;i<gems.length;i++){
if(gems[i]>0)
{
max = max*gems[i];
end++;
if(colour[i] == 1)
red++;
}else{
if(actualMax < max){
if(red%2==0)
{
actualMax = max;
}else{
int temp = max;
int startRed = -1, endRed = -1;
for(int i=start;i<end;i++){
if(colour[i]==1 && startRed==-1){
startRed = i;
endRed = i;
}else if(colour[i]==1)
endRed = i;
}
int tempProdStart = 1; tempEndProd = 1;
for(int i=start;i<=startRed;i++){
tempProdStart = a[i]*tempProdStart ;
}
for(int i=endRed;i<=end;i++){
tempEndProd= a[i]*tempEndProd;
}
int minProd = Math.min(tempProdStart, tempEndProd);
max = temp/minProd;
if(max > actualMax){
actualMax = max;
}
}
}
start = end+1;
end = end + 1;
}
}
}
</pre>
<br />
Time complexity - O(n)<br />
<br />
<br />
<br /></div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-38884865744789221322015-05-03T19:12:00.003+05:302015-05-03T19:12:54.317+05:30Find the least wastage in cutting the Trees?<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem</b><br />
You are given n Trees with their heights in an array.
and you are given a value k units , that much wood you need to collect.
You can have an axe of any height you want but you can use only 1 axe when you choose.<br />
<br />
Assume height to be integral value.<br />
<h3 style="text-align: left;">
Solution </h3>
So, if height of the tree is H, and you cut it at height X from the ground then H-X will be used will be used. If there is only 1 tree, we will cut it at height X, such that H-X = k. <br />
<br />
It is always possible to choose an axe height such that chopping <i>all</i> trees above this height will result in zero waste.<br />
To see this, just sort the trees in descending order of height, and
consider moving the axe height gradually down from the top of the
tallest tree.<br />
<br />
Suppose the tallest tree has height h. Notice that the
function:<br />
<br />
<pre class="brush:java">f(x) = total amount of wood cut by using an axe of height h - x to
chop all trees of at least this height
</pre>
<br />
<ul style="text-align: left;">
<li>Sort the trees by their height in descending order</li>
<li> starts at 0 when x = 0, and is an increasing piecewise linear
function of x, with no discontinuities. Every time x increases past the
point when one or more trees just start to become choppable, the rate
of change of f(x) increases, but this doesn't cause problems. </li>
<li>So for
any desired level of wood y, just (conceptually) intersect a horizontal
line of height y with the graph f(x), and drop a vertical line from this
point down to the x axis to find its value. (How to actually do this
in a program I leave as an exercise, but here's a hint: consider trees
in decreasing height order to find the pair of adjacent x values x1, x2
such that chopping at h - x1 produces too little wood, and h - x2
produces too much.)</li>
</ul>
<br />
<b>Reference</b><br />
<ul style="text-align: left;">
<li><a href="http://stackoverflow.com/questions/18053325/algorithm-find-the-least-wastage-in-cutting-the-trees">http://stackoverflow.com/questions/18053325/algorithm-find-the-least-wastage-in-cutting-the-trees</a></li>
</ul>
<br />
<br />
<br />
<br /></div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-2536246745777608042015-05-03T17:33:00.000+05:302015-05-03T17:33:48.796+05:30Implement a function similar to diff command in linux<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
Problem</h3>
<blockquote class="tr_bq">
Give logic for implementing "diff" command in Linux.<br />
Consider various test cases and explain what will happen in each. The two files are source code and are huge..<br />
For e.g.<br />
File 1: 1-2-3-4<br />
File 2: 1-3-4-2</blockquote>
<h3 style="text-align: left;">
Solution</h3>
The operation of diff is based on solving the longest common sub-sequence problem.<br />
In this problem, you have two sequences of items:<br />
a b c d f g h j q z<br />
a b c d e f g i j k r x y z<br />
and you want to find a longest sequence of items that is present in both original sequences in the same order. That is, you want to find a new sequence which can be obtained from the first sequence by deleting some items, and from the second sequence by deleting other items. You also want this sequence to be as long as possible. In this case it is<br />
a b c d f g j z<br />
From a longest common subsequence it's only a small step to get diff-like output: if an item is absent in the subsequence but present in the original, it must have been deleted. (The '–' marks, below.) If it is absent in the subsequence but present in the second sequence, it must have been added in. (The '+' marks.)<br />
e h i q k r x y<br />
+ - + - + + + +<br />
<br />
<br />
<b>Resource</b><br />
<ul style="text-align: left;">
<li><a href="http://www.careercup.com/questionthread?id=98911">http://www.careercup.com/questionthread?id=98911</a> </li>
</ul>
<br />
<br />
<br /></div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-87717365547026819402015-04-30T22:17:00.000+05:302016-03-15T17:29:15.228+05:30Maximum single sell profit from stock<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem</b><br />
Suppose we are given an array of n integers representing stock prices
on a single day. We want to find a pair (buyDay, sellDay), with buyDay
≤ sellDay, such that if we bought the stock on buyDay and sold it on
sellDay, we would maximize our profit.<br />
<br />
OR<br />
<br />
Given an array arr[] of integers, find out the difference between any two elements <b>such that larger element appears after the smaller number</b> in arr[]. <br />
<br />
<span id="more-6463"></span><br />
<b>Example</b><br />
Input = {5 10 4 6 7}<br />
Output = 5,10 => buy at 5 and sell at 7<br />
<br />
<br />
<h3 style="text-align: left;">
Solution</h3>
<br />
<b>Method 1 - Brute force</b><br />
Clearly there is an O(n<sup>2</sup>) solution to the algorithm by
trying out all possible (buyDay, sellDay) pairs and taking the best out
of all of them. However, is there a better algorithm, perhaps one that
runs in O(n) time?<br />
<br />
<pre class="brush:java">int maxDiff(int arr[], int arr_size)
{
int max_diff = arr[1] - arr[0];
int i, j;
for(i = 0; i < arr_size; i++)
{
for(j = i+1; j < arr_size; j++)
{
if(arr[j] - arr[i] > max_diff)
max_diff = arr[j] - arr[i];
}
}
return max_diff;
}
</pre>
<br />
<b>Method 2 - Divide and Conquer</b><br />
If we have a single day, the best option is to buy on that day and
then sell it back on the same day for no profit. Otherwise, split the
array into two halves. If we think about what the optimal answer might
be, it must be in one of three places:
<br />
<ol>
<li>The correct buy/sell pair occurs completely within the first half.</li>
<li>The correct buy/sell pair occurs completely within the second half.</li>
<li>The correct buy/sell pair occurs across both halves - we buy in the first half, then sell in the second half.</li>
</ol>
We can get the values for (1) and (2) by recursively invoking our
algorithm on the first and second halves. For option (3), the way to
make the highest profit would be to buy at the lowest point in the first
half and sell in the greatest point in the second half. We can find
the minimum and maximum values in the two halves by just doing a simple
linear scan over the input and finding the two values. This then gives
us an algorithm with the following recurrence:<br />
<pre><code>T(1) <= O(1)
T(n) <= 2T(n / 2) + O(n)
</code></pre>
Using the <a href="http://en.wikipedia.org/wiki/Master_theorem">Master Theorem</a>
to solve the recurrence, we find that this runs in O(n lg n) time and
will use O(lg n) space for the recursive calls. We've just beaten the
naive O(n<sup>2</sup>) solution!<br />
<br />
<b>Method 3 - Optimized divide and conquer</b><br />
But wait! We can do much better than this. Notice that the only
reason we have an O(n) term in our recurrence is that we had to scan the
entire input trying to find the minimum and maximum values in each
half. Since we're already recursively exploring each half, perhaps we
can do better by having the recursion also hand back the minimum and
maximum values stored in each half! In other words, our recursion hands
back three things:<br />
<ol>
<li>The buy and sell times to maximize profit.</li>
<li>The minimum value overall in the range.</li>
<li>The maximum value overall in the range.</li>
</ol>
These last two values can be computed recursively using a
straightforward recursion that we can run at the same time as the
recursion to compute (1):<br />
<ol>
<li>The max and min values of a single-element range are just that element.</li>
<li>The max and min values of a multiple element range can be found by
splitting the input in half, finding the max and min values of each
half, then taking their respective max and min.</li>
</ol>
If we use this approach, our recurrence relation is now<br />
<pre><code>T(1) <= O(1)
T(n) <= 2T(n / 2) + O(1)
</code></pre>
Using the Master Theorem here gives us a runtime of O(n) with O(lg n) space, which is even better than our original solution!<br />
<br />
<b>Method 4 - Use the difference between adjacent element</b><br />
First find the difference between the adjacent elements of the array and
store all differences in an auxiliary array diff[] of size n-1. Now
this problems turns into finding the maximum sum subarray of this
difference array. <br />
<pre class="brush:java">int maxDiff(int arr[], int n)
{
// Create a diff array of size n-1. The array will hold
// the difference of adjacent elements
int diff[n-1];
for (int i=0; i < n-1; i++)
diff[i] = arr[i+1] - arr[i];
// Now find the maximum sum subarray in diff array
int max_diff = diff[0];
for (int i=1; i<n-1; i++)
{
if (diff[i-1] > 0)
diff[i] += diff[i-1];
if (max_diff < diff[i])
max_diff = diff[i];
}
return max_diff;
}
</pre>
<br />
Example<br />
input = <br />
Time Complexity: O(n)<br />
Auxiliary Space: O(n)<br />
<br />
<b>Method 5 - Optimizing the diff approach</b><br />
We can modify the above method to work in O(1) extra space. Instead of creating an auxiliary array, we can calculate diff and max sum in same loop. Following is the space optimized version.<br />
<pre class="brush:java">int maxDiff (int arr[], int n)
{
// Initialize diff, current sum and max sum
int diff = arr[1]-arr[0];
int curr_sum = diff;
int max_sum = curr_sum;
for(int i=1; i<n-1; i++)
{
// Calculate current diff
diff = arr[i+1]-arr[i];
// Calculate current sum
if (curr_sum > 0)
curr_sum += diff;
else
curr_sum = diff;
// Update max sum, if needed
if (curr_sum > max_sum)
max_sum = curr_sum;
}
return max_sum;
}
</pre>
<br />
Time Complexity: O(n),
Auxiliary Space: O(1)<br />
<br />
<b>Method 6 - Dynamic programming (Preferred and easy :))</b><br />
But wait a minute - we can do even better than this! Let's think
about solving this problem using dynamic programming. The idea will be
to think about the problem as follows. Suppose that we knew the answer
to the problem after looking at the first k elements. Could we use our
knowledge of the (k+1)st element, combined with our initial solution, to
solve the problem for the first (k+1) elements? If so, we could get a
great algorithm going by solving the problem for the first element, then
the first two, then the first three, etc. until we'd computed it for
the first n elements.<br />
Let's think about how to do this. If we have just one element, we
already know that it has to be the best buy/sell pair. Now suppose we
know the best answer for the first k elements and look at the (k+1)st
element. Then the only way that this value can create a solution better
than what we had for the first k elements is if the difference between
the smallest of the first k elements and that new element is bigger than
the biggest difference we've computed so far. So suppose that as we're
going across the elements, we keep track of two values - the minimum
value we've seen so far, and the maximum profit we could make with just
the first k elements. Initially, the minimum value we've seen so far is
the first element, and the maximum profit is zero. When we see a new
element, we first update our optimal profit by computing how much we'd
make by buying at the lowest price seen so far and selling at the
current price. If this is better than the optimal value we've computed
so far, then we update the optimal solution to be this new profit.
Next, we update the minimum element seen so far to be the minimum of the
current smallest element and the new element.<br />
<br />
Since at each step we do only O(1) work and we're visiting each of
the n elements exactly once, this takes O(n) time to complete!
Moreover, it only uses O(1) auxiliary storage. This is as good as we've
gotten so far!<br />
As an example, on your inputs, here's how this algorithm might run.
The numbers in-between each of the values of the array correspond to the
values held by the algorithm at that point. You wouldn't actually
store all of these (it would take O(n) memory!),<br />
<br />
Time - O(n), Space - O(1) solution:<br />
<br />
<pre class="brush:java">public static int findMaxProfit(int[] stockPriceSamples) {
int maxProfit = 0;
int minTillNow = stockPriceSamples[0];
for (int i = 0; i < stockPriceSamples.length; i++) {
int profit = stockPriceSamples[i] - minTillNow;
maxProfit = Math.max(profit, maxProfit);
minTillNow = Math.min(stockPriceSamples[i], minTillNow);
}
return maxProfit;
}
</pre>
<br />
<b>Example</b><br />
input = {5 10 4 6 7}<br />
i = 0, maxProfit = 0, minTillNow=5<br />
i = 1, maxProfit=5, minTillNow=5<br />
i= 2, maxProfit = 5,minTillNow=4<br />
i=3,maxProfit=5,minTillNow=4<br />
i= 4,maxProfit=5,minTillNow=5<br />
<br />
<br />
<b>References</b><br />
<ul style="text-align: left;">
<li><a href="http://stackoverflow.com/questions/7086464/maximum-single-sell-profit">http://stackoverflow.com/questions/7086464/maximum-single-sell-profit</a></li>
<li><a href="http://www.geeksforgeeks.org/maximum-difference-between-two-elements/">http://www.geeksforgeeks.org/maximum-difference-between-two-elements/</a></li>
<li><a href="https://programming4interviews.wordpress.com/2012/02/27/maximize-the-single-sell-profit-of-a-stock/">https://programming4interviews.wordpress.com/2012/02/27/maximize-the-single-sell-profit-of-a-stock/</a> </li>
</ul>
</div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-3863712523602658192015-04-18T22:56:00.001+05:302016-03-28T02:40:49.846+05:30Reverse the doubly linked list<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
Problem</h3>
Reverse the doubly linked list<br />
<br />
<b>Input</b><br />
10 - 8 - 4 - 2<br />
<br />
<b>Output</b><br />
2 - 4 - 8 - 12<br />
<br />
<h3 style="text-align: left;">
Solution</h3>
<br />
<b>Method 1 - Reversing the prev and next references</b> <br />
Reversing a doubly linked list is much simpler as compared to reversing a singly linked list. We just need to swap the <span style="font-family: "courier new";">prev</span> & <span style="font-family: "courier new";">next</span> references in all the nodes of the list and need to make head point to
the last node of original list (which will be the first node in the
reversed list).<br />
<br />
<pre class="brush:java">void reverseDLL(Node head)
{
while(head!=null)
{
// Swapping the prev & next pointer of each node
Node t = head.prev;
head.prev = head.next;
head.next = t;
if(head.prev != null)
head = head.prev; // Move to the next node in original list
else
break; // reached the end. so terminate
}
}
</pre>
<br />
Time complexity - O(n)<br />
<br />
<b>Reference</b><br />
<a href="http://www.geeksforgeeks.org/reverse-a-doubly-linked-list/">http://www.geeksforgeeks.org/reverse-a-doubly-linked-list/</a></div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-64562551108128063092015-04-18T20:58:00.002+05:302015-04-18T21:05:43.154+05:30Doubly linked list ADT<div dir="ltr" style="text-align: left;" trbidi="on">
A doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.<br />
<br />
The beginning and ending nodes previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders. <br />
<br />
<h3 style="text-align: left;">
ADT</h3>
<pre class="brush:java"> class Node {
E element;
Node next;
Node prev;
public Node(E element, Node next, Node prev) {
this.element = element;
this.next = next;
this.prev = prev;
}
}
</pre>
<br />
<br />
<h3 style="text-align: left;">
Operations</h3>
<ul style="text-align: left;">
<li>Insert</li>
<li>Delete</li>
<li>Update</li>
<li>Find</li>
</ul>
<h3 style="text-align: left;">
Java usage</h3>
<a href="http://download.oracle.com/javase/6/docs/api/java/util/LinkedList.html"><code>java.util.LinkedList</code></a> is a doubly-linked list.<br />
<br />
<br />
<b>Reference</b><br />
<ul style="text-align: left;">
<li><a href="http://java2novice.com/data-structures-in-java/linked-list/doubly-linked-list/">http://java2novice.com/data-structures-in-java/linked-list/doubly-linked-list/</a></li>
</ul>
</div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-59863411222387018522015-04-17T03:06:00.001+05:302015-04-30T12:09:27.508+05:30Find the largest subarray with sum of 0 in the given array<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Problem</b><br />
<div class="post-text" itemprop="text">
An array contains both positive and negative elements, find the largest subarray whose
sum equals 0.<br />
<br />
<b>Example</b><br />
int[] input = {4, 6, 3, -9, -5, 1, 3, 0, 2}<br />
int output = {4, 6, 3, -9, -5, 1} of length 6<br />
<br />
<h3 style="text-align: left;">
Solution</h3>
<b>Method 1 - Brute force</b><br />
This is simple. Will write later (<span style="color: red;">incomplete</span>)<br />
<br />
<b>Method 2 - Storing the sum upto ith element in temp array</b><br />
Given an <code>int[] input</code> array, you can create an <code>int[] tmp</code> array where <code> </code><br />
<pre class="brush:java">tmp[i] = tmp[i - 1] + input[i];</pre>
<br />
<br />
Each element of tmp will store the sum of the input up to that element.<br />
<br />
<u>Example</u><br />
<pre class="brush:java">int[] input = {4 | 6| 3| -9| -5| 1| 3| 0| 2}
int[] tmp = {4 | 10|13| 4| -1| 0| 3| 3| 5}</pre>
<br />
Now if you check tmp, you'll notice that there might be values that are equal to each other.For example, take the element 4 at index 0 and 3, element 3 at index 6 and 7. So, it means sum between these 2 indices has remained the same, i.e. all the elements between them add upto 0. So, based on that we get {6, 3, -9} and {0}.<br />
<br />
Also, we know tmp[-1] = 0. When we have not started the array we have no element added to it. So, if we find a zero inside the tmp array, that means all the numbers starting 0th index to 5th index(where 0 exists in temp) are all 0s, so our subarray becomes {4,6,3, -9,-5,1}.<br />
<br />
Out of {6, 3, -9}, {0} and {4,6,3, -9,-5,1}, last one is our answer as it is the largest sub array.<br />
<br />
<u>To sum it up</u><br />
We notice that some values are same in tmp array. Let's say that this values are at indexes <code>j an k with j < k</code>, then the sum of the input till <code>j</code> is equal to the sum till <code>k</code> and this means that the sum of the portion of the array between <code>j</code> and <code>k</code> is 0! Specifically the 0 sum subarray will be from index j + 1 to k.
<br />
<ul>
<li>NOTE: if <code>j + 1 == k</code>, then <code>k is 0</code> and that's it! ;)</li>
<li>NOTE: The algorithm should consider a virtual <code>tmp[-1] = 0</code>;</li>
<li>NOTE: An empty array has sum 0 and it's minimal and this special
case should be brought up as well in an interview. Then the interviewer
will say that doesn't count but that's another problem! ;)</li>
</ul>
</div>
<br />
Here is the code<br />
<pre class="brush:java"> public static string[] SubArraySumList(int[] array, int sum)
{
int tempsum;
List<string> list = new List<string>();
for (int i = 0; i < array.Length; i++)
{
tempsum = 0;
for (int j = i; j < array.Length; j++)
{
tempsum += array[j];
if (tempsum == sum)
{
list.Add(String.Format("[{0}-{1}]", i, j));
}
}
}
return list.ToArray();
}
</pre>
<br />
Here is the solution using Hashmap, iterate over it again to get the max subarray:<br />
<br />
<pre class="brush:java">public static void subArraySumsZero() {
int [] seed = new int[] {1,2,3,4,-9,6,7,-8,1,9};
int currSum = 0;
HashMap<Integer, Integer> sumMap = new HashMap<Integer, Integer>();
for(int i = 0 ; i < seed.length ; i ++){
currSum += seed[i];
if(currSum == 0){
System.out.println("subset : { 0 - " + i + " }");
}else if(sumMap.get(currSum) != null){
System.out.println("subset : { " + (sumMap.get(currSum) + 1) + " - " + i + " }");
sumMap.put(currSum, i);
}else
sumMap.put(currSum, i);
}
System.out.println("HASH MAP HAS: " + sumMap);
}
</pre>
<br />
<br />
<b>References</b><br />
<ul style="text-align: left;">
<li><a href="http://stackoverflow.com/questions/5534063/zero-sum-subarray">http://stackoverflow.com/questions/5534063/zero-sum-subarray</a></li>
</ul>
</div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-72264525754904802212015-04-17T02:36:00.003+05:302015-04-17T02:36:43.650+05:30Einsteen's 5 house riddle<div dir="ltr" style="text-align: left;" trbidi="on">
Problem<br />
<h4>
Einstein wrote this riddle early during the 19th century. He said 98% of the world could not solve it. </h4>
<blockquote class="tr_bq">
<div class="clearfix">
"There are 5 houses in 5 different colors. In each
house lives a person with a different nationality. The 5 owners drink a
certain type of beverage, smoke a certain brand of cigar, and keep a
certain pet. No owners have the same pet, smoke the same brand of cigar,
or drink the same beverage."</div>
</blockquote>
<div class="clearfix">
<b>The question is:</b> Who owns the fish?</div>
<div class="clearfix">
<br /></div>
<div class="clearfix">
<b>Hints:</b></div>
<ol>
<li>The Brit lives in the red house.</li>
<li>The Swede keeps dogs as pets.</li>
<li>The Dane drinks tea.</li>
<li>The green house is on the left of the white house.</li>
<li>The green homeowner drinks coffee.</li>
<li>The person who smokes Pall Mall rears birds.</li>
<li>The owner of the yellow house smokes Dunhill.</li>
<li>The man living in the center house drinks milk.</li>
<li>The Norwegian lives in the first house.</li>
<li>The man who smokes Blend lives next to the one who keeps cats.</li>
<li>The man who keeps the horse lives next to the man who smokes Dunhill.</li>
<li>The owner who smokes Bluemaster drinks beer.</li>
<li>The German smokes prince.</li>
<li>The Norwegian lives next to the blue house.</li>
<li>The man who smokes Blend has a neighbor who drinks water.</li>
</ol>
<div class="clearfix">
<br /></div>
Solution<br />
a) We know that Norwegian lives in the 1st house (Hint: #9) and next
to him lives a guy who stays in a blue house (Hint: #14). So far we
have the following:<br />
<table border="0">
<tbody>
<tr>
<td><b>1st House</b></td>
<td><b>2nd House</b></td>
</tr>
<tr>
<td>Norwegian</td>
<td>Blue House</td>
</tr>
</tbody>
</table>
<br />
b) We know that the green house is on the left of the white house
(Hint: 4), therefore we can form a new group with the Green and White
house next to each other.<br />
<table border="0">
<tbody>
<tr>
<td>Green House</td>
<td>White House</td>
</tr>
<tr>
<td><br /></td>
<td><br /></td>
</tr>
</tbody>
</table>
<br />
c) Now think carefully the combination of (a) and (b). We should
reach to the conclusion that the Norwegean guy who lives in the first
house, he either lives in the Red or Yellow house since the Green &
White houses group can only have a position of either 3-4 or 4-5.<br />
d) Since the Brit is the guy who lives in the Red house (Hint: 1),
now we definitely know that the Norwegian lives in the Yellow house. So
far we have the following information:<br />
<table border="0">
<tbody>
<tr>
<td>1st House</td>
<td>2nd House</td>
</tr>
<tr>
<td>Norwegian<br />
Yellow</td>
<td>Blue</td>
</tr>
</tbody>
</table>
<br />
<table border="0">
<tbody>
<tr>
<td>British</td>
</tr>
<tr>
<td>Red</td>
</tr>
</tbody>
</table>
<br />
Group:<br />
<table border="0">
<tbody>
<tr>
<td>Green House</td>
<td>White House</td>
</tr>
<tr>
<td><br /></td>
<td><br /></td>
</tr>
</tbody>
</table>
<br />
e) Next, we know that the owner of the Green house drinks coffee
(Hint: 5) and the man living in the center house drinks milk (Hint: 8).
As a result, we conclude that the group of Green and Yellow house are
the 4th and 5th house in order and that the center house (number 3) is
the Brit.<br />
<table border="0">
<tbody>
<tr>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
<td>5</td>
</tr>
<tr>
<td>Norwegian</td>
<td><br /></td>
<td>British</td>
<td><br /></td>
<td><br /></td>
</tr>
<tr>
<td>Yellow</td>
<td><span style="color: black; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10.909090995788574px; line-height: normal;">Blue</span></td>
<td>Red</td>
<td>Green</td>
<td>White</td>
</tr>
<tr>
<td><br /></td>
<td><br /></td>
<td>Milk</td>
<td>Coffee</td>
<td><br /></td>
</tr>
<tr>
<td><br /></td>
<td><br /></td>
<td><br /></td>
<td><br /></td>
<td><br /></td>
</tr>
</tbody>
</table>
<br />
f) Hint 7 gives us another information on the first house (The owner
of the yellow house smokes Dunhill). In-addition, the man who keeps the
horse lives next to the man who smokes Dunhill (Hint 11), therefore the
man living in house #2 keeps horses.<br />
<table border="0">
<tbody>
<tr>
<td>House</td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
<td>5</td>
</tr>
<tr>
<td>Nation</td>
<td>Norwegian</td>
<td><br /></td>
<td>British</td>
<td><br /></td>
<td><br /></td>
</tr>
<tr>
<td>Color</td>
<td>Yellow</td>
<td>Blue</td>
<td>Red</td>
<td>Green</td>
<td>White</td>
</tr>
<tr>
<td>Drink</td>
<td><br /></td>
<td><br /></td>
<td>Milk</td>
<td>Coffee</td>
<td><br /></td>
</tr>
<tr>
<td>Pet</td>
<td><br /></td>
<td> Horses</td>
<td><br /></td>
<td><br /></td>
<td><br /></td>
</tr>
<tr>
<td><span style="color: black; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10.909090995788574px; line-height: normal;">Smoke</span></td>
<td><span style="color: black; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10.909090995788574px; line-height: normal;">Dunhill</span></td>
<td><br /></td>
<td><br /></td>
<td><br /></td>
<td><br /></td>
</tr>
</tbody>
</table>
<br />
g) Hint 15 states that "The man who smokes Blend has a neighbor who
drinks water." We conclude that only 2 people can have a neighbor who
drinks water (House 1&2), but since House #1 already smokes Dunhill
that means that House #2 smokes Blend and House #1 drinks water.<br />
<table border="0">
<tbody>
<tr>
<td>House</td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
<td>5</td>
</tr>
<tr>
<td>Nation</td>
<td>Norwegian</td>
<td><br /></td>
<td>British</td>
<td><br /></td>
<td><br /></td>
</tr>
<tr>
<td>Color</td>
<td>Yellow</td>
<td>Blue</td>
<td>Red</td>
<td>Green</td>
<td>White</td>
</tr>
<tr>
<td>Drink</td>
<td>Water</td>
<td><br /></td>
<td>Milk</td>
<td>Coffee</td>
<td><br /></td>
</tr>
<tr>
<td>Pet</td>
<td><br /></td>
<td> Horses</td>
<td><br /></td>
<td><br /></td>
<td><br /></td>
</tr>
<tr>
<td>Smoke</td>
<td>Dunhill</td>
<td> Blend</td>
<td><br /></td>
<td><br /></td>
<td><br /></td>
</tr>
</tbody>
</table>
<br />
h) Hint 12 states "The owner who smokes Bluemaster drinks beer." See
the table above and you will notice that we are missing the drink only
for houses 2 and 5 but since we already know that the owner of house 2
smokes Blend, then the combination of Hint 12 applies to house #5.<br />
<br />
<table border="0">
<tbody>
<tr>
<td>House</td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
<td>5</td>
</tr>
<tr>
<td>Nation</td>
<td>Norwegian</td>
<td><br /></td>
<td>British</td>
<td><br /></td>
<td><br /></td>
</tr>
<tr>
<td>Color</td>
<td>Yellow</td>
<td>Blue</td>
<td>Red</td>
<td>Green</td>
<td>White</td>
</tr>
<tr>
<td>Drink</td>
<td>Water</td>
<td><br /></td>
<td>Milk</td>
<td>Coffee</td>
<td>Beer </td>
</tr>
<tr>
<td>Pet</td>
<td><br /></td>
<td> Horses</td>
<td><br /></td>
<td><br /></td>
<td><br /></td>
</tr>
<tr>
<td>Smoke</td>
<td>Dunhill</td>
<td> Blend</td>
<td><br /></td>
<td><br /></td>
<td> Bluemaster</td>
</tr>
</tbody>
</table>
<br />
i) Hint 3 states that "The Dane drinks tea.". We are missing only the drink for house #2 therefore this applies to house #2.<br />
<table border="0">
<tbody>
<tr>
<td>House</td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
<td>5</td>
</tr>
<tr>
<td>Nation</td>
<td>Norwegian</td>
<td> Danish</td>
<td>British</td>
<td><br /></td>
<td><br /></td>
</tr>
<tr>
<td>Color</td>
<td>Yellow</td>
<td>Blue</td>
<td>Red</td>
<td>Green</td>
<td>White</td>
</tr>
<tr>
<td>Drink</td>
<td>Water</td>
<td>Tea </td>
<td>Milk</td>
<td>Coffee</td>
<td>Beer </td>
</tr>
<tr>
<td>Pet</td>
<td><br /></td>
<td> Horses</td>
<td><br /></td>
<td><br /></td>
<td><br /></td>
</tr>
<tr>
<td>Smoke</td>
<td>Dunhill</td>
<td> Blend</td>
<td><br /></td>
<td><br /></td>
<td> Bluemaster</td>
</tr>
</tbody>
</table>
<br />
j) Hint 10 states "The man who smokes Blend lives next to the one who
keeps cats." As a result, house #1 keeps cats since house #2 has the
owner who smokes Blend.<br />
<br />
<table border="0">
<tbody>
<tr>
<td>House</td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
<td>5</td>
</tr>
<tr>
<td>Nation</td>
<td>Norwegian</td>
<td> Danish</td>
<td>British</td>
<td><br /></td>
<td><br /></td>
</tr>
<tr>
<td>Color</td>
<td>Yellow</td>
<td>Blue</td>
<td>Red</td>
<td>Green</td>
<td>White</td>
</tr>
<tr>
<td>Drink</td>
<td>Water</td>
<td>Tea </td>
<td>Milk</td>
<td>Coffee</td>
<td>Beer </td>
</tr>
<tr>
<td>Pet</td>
<td>Cats</td>
<td> Horses</td>
<td><br /></td>
<td><br /></td>
<td><br /></td>
</tr>
<tr>
<td>Smoke</td>
<td>Dunhill</td>
<td> Blend</td>
<td><br /></td>
<td><br /></td>
<td> Bluemaster</td>
</tr>
</tbody>
</table>
<br />
k) Hint #13 states that "The German smokes prince". We are missing
the nationalities of the owners who live in house #4 and #5 but since
the owner of house #5 smokes Bluemaster, this hint applies to house #4.<br />
<table border="0">
<tbody>
<tr>
<td>House</td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
<td>5</td>
</tr>
<tr>
<td>Nation</td>
<td>Norwegian</td>
<td> Danish</td>
<td>British</td>
<td>German</td>
<td><br /></td>
</tr>
<tr>
<td>Color</td>
<td>Yellow</td>
<td>Blue</td>
<td>Red</td>
<td>Green</td>
<td>White</td>
</tr>
<tr>
<td>Drink</td>
<td>Water</td>
<td>Tea </td>
<td>Milk</td>
<td>Coffee</td>
<td>Beer </td>
</tr>
<tr>
<td>Pet</td>
<td>Cats</td>
<td> Horses</td>
<td><br /></td>
<td><br /></td>
<td><br /></td>
</tr>
<tr>
<td>Smoke</td>
<td>Dunhill</td>
<td> Blend</td>
<td><br /></td>
<td>Prince </td>
<td> Bluemaster</td>
</tr>
</tbody>
</table>
<br />
l) Hint #6 states that "The person who smokes Pall Mall rears birds". We are only missing the tabacco of House #3 therefore:<br />
<table border="0">
<tbody>
<tr>
<td>House</td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
<td>5</td>
</tr>
<tr>
<td>Nation</td>
<td>Norwegian</td>
<td> Danish</td>
<td>British</td>
<td>German</td>
<td><br /></td>
</tr>
<tr>
<td>Color</td>
<td>Yellow</td>
<td>Blue</td>
<td>Red</td>
<td>Green</td>
<td>White</td>
</tr>
<tr>
<td>Drink</td>
<td>Water</td>
<td>Tea </td>
<td>Milk</td>
<td>Coffee</td>
<td>Beer </td>
</tr>
<tr>
<td>Pet</td>
<td>Cats</td>
<td> Horses</td>
<td>Birds </td>
<td><br /></td>
<td><br /></td>
</tr>
<tr>
<td>Smoke</td>
<td>Dunhill</td>
<td> Blend</td>
<td> Pall Mall</td>
<td>Prince </td>
<td> Bluemaster</td>
</tr>
</tbody>
</table>
<br />
m) Finally hint #2 states that "The Swede keeps dogs as pets". This combination can only be applied to house #5.<br />
<table border="0">
<tbody>
<tr>
<td>House</td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
<td>5</td>
</tr>
<tr>
<td>Nation</td>
<td>Norwegian</td>
<td> Danish</td>
<td>British</td>
<td>German</td>
<td>Swedish</td>
</tr>
<tr>
<td>Color</td>
<td>Yellow</td>
<td>Blue</td>
<td>Red</td>
<td>Green</td>
<td>White</td>
</tr>
<tr>
<td>Drink</td>
<td>Water</td>
<td>Tea </td>
<td>Milk</td>
<td>Coffee</td>
<td>Beer </td>
</tr>
<tr>
<td>Pet</td>
<td>Cats</td>
<td> Horses</td>
<td>Birds </td>
<td><br /></td>
<td>Dogs </td>
</tr>
<tr>
<td>Smoke</td>
<td>Dunhill</td>
<td> Blend</td>
<td> Pall Mall</td>
<td>Prince </td>
<td> Bluemaster</td>
</tr>
</tbody>
</table>
<br />
n) Now who owns the fish? The <b>German</b> owns the fish!!!<br />
<b>Congratulations, according to Einstein you now belong to the 2% of the people who can solve this riddle!!!</b><br />
<table border="0"><tbody>
<tr>
<td>House</td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
<td>5</td>
</tr>
<tr>
<td>Nation</td>
<td>Norwegian</td>
<td> Danish</td>
<td>British</td>
<td>German</td>
<td>Swedish</td>
</tr>
<tr>
<td>Color</td>
<td>Yellow</td>
<td>Blue</td>
<td>Red</td>
<td>Green</td>
<td>White</td>
</tr>
<tr>
<td>Drink</td>
<td>Water</td>
<td>Tea </td>
<td>Milk</td>
<td>Coffee</td>
<td>Beer </td>
</tr>
<tr>
<td>Pet</td>
<td>Cats</td>
<td> Horses</td>
<td>Birds </td>
<td><b>FISH</b></td>
<td>Dogs </td>
</tr>
<tr>
<td>Smoke</td>
<td>Dunhill</td>
<td> Blend</td>
<td> Pall Mall</td>
<td>Prince </td>
<td> Bluemaster</td></tr>
</tbody></table>
<br />
<br />
<b>Reference</b><br />
<ul style="text-align: left;">
<li><a href="http://einsteinriddle.com/index.php/einstein-s-riddle-solution-explained">http://einsteinriddle.com/index.php/einstein-s-riddle-solution-explained</a> </li>
</ul>
<br /></div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-71472394300657401062015-04-17T01:33:00.000+05:302015-04-17T01:33:29.275+05:30 Find the maximum distance covered using n bikes<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
Problem</h3>
There are n bikes and each can cover 100 km when fully fueled. What is the maximum amount of distance you can go using n bikes? <span id="more-123895"></span> You may assume that all bikes are similar and a bike takes 1 litre to cover 1 km.<br />
<h3 style="text-align: left;">
Solution</h3>
There are couple of ways. Lets find the right solution. Say n = 50. <br />
<br />
<strong>Naive Solution:</strong><br />
<div style="padding-left: 30px;">
The most naive solution would be to just make all the bikes go together. Hence, the maximum distance travelled will be 100km.</div>
<div style="padding-left: 30px;">
<br /></div>
<strong>Better Solution:</strong><br />
<div style="padding-left: 30px;">
Move all the bikes 50km, so that each bike has half tank empty.</div>
<div style="padding-left: 30px;">
Now pour the fuel of 25 bikes (whose
tanks are half filled) into other 25 bikes. Now we have 25 bikes will
full tanks and these 25 bikes can go upto 100km each</div>
<div style="padding-left: 30px;">
Repeat the same after next 50 km.</div>
<div style="padding-left: 30px;">
Hence the number of bikes will go down after every 50 km, like:</div>
<div style="padding-left: 30px;">
50 -> 25 -> 12 -> 6 -> 3 -> 1</div>
<div style="padding-left: 30px;">
Total distance covered will be 5*50 + 100= 350 kms <i>(At the end you have a bike filled with 100km fuel)</i>.</div>
<div style="padding-left: 30px;">
<strong>Note:</strong> You can further
optimize few more km, because we are ignoring one bike’s (50 km fuel)
when 25->12 and 3->1.. Since it is not the best solution, I have
ignored that.</div>
<div style="padding-left: 30px;">
<br /></div>
<strong>Best Solution (Actual solution) :</strong><br />
<div style="padding-left: 30px;">
In this solution we will vacate the tank
of a bike as soon as there is capacity in other bikes (not waiting for
50 km). Lets do it by breaking into the cases. </div>
<div style="padding-left: 30px;">
<u>Case 1 - Only 1 bike</u> - The biker will drive for 100 km</div>
<div style="padding-left: 30px;">
<u>Case 2 - Only 2 bikes</u> - Both bikers will drive to the point such that first biker can transfer the fuel to the other guy. So, for the 1st 50km they will go together, and then the fuel in both will be 50L and then 1st biker will give fuel to the other biker, and that biker will cover the rest with 100L of fuel.</div>
<div style="padding-left: 30px;">
So, Distance = Distance covered together + distance covered by fuel transfer = 50 + 100 = 150 km</div>
<div style="padding-left: 30px;">
<u>Case 3 - Only 3 bikes</u> - All the bikers will travel together to the point where fuel of the 1st biker can fill the oil in other 2 bikes. So, first distance will be 33.3 km. After this other 2 bikers will take fuel from 1st one and it will become like the old case of 2 bikes. Answer = 33.3 + 150 = 100/3 + 100/2 + 100 /1 = 183.3 km.</div>
<div style="padding-left: 30px;">
<br /></div>
<div style="padding-left: 30px;">
So empty one bike into rest 49 bikes. (49*2 = 98).</div>
<div style="padding-left: 30px;">
Again travel a distance of 100/49km, that is sufficient to vacate the fuel of one more bike in other 48 bikes.</div>
<div style="padding-left: 30px;">
The actual number of km traveled will be:</div>
<div style="padding-left: 30px;">
= 100/50 + 100/49 +......+100/1 = </div>
<div style="padding-left: 30px;">
</div>
<div style="padding-left: 30px;">
<strong>= 449.92 km</strong></div>
<br /><br />
<br />
<b>References</b><br />
<a href="http://www.geeksforgeeks.org/find-maximum-distance-covered-100-bikes/">http://www.geeksforgeeks.org/find-maximum-distance-covered-100-bikes/</a><br />
<a href="http://www.ritambhara.in/maximum-distance-with-50-bikes-each-having-fuel-capacity-of-100-kms/">http://www.ritambhara.in/maximum-distance-with-50-bikes-each-having-fuel-capacity-of-100-kms/</a><br />
</div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0tag:blogger.com,1999:blog-3098638925089993315.post-29953999877013984972015-02-17T10:06:00.000+05:302015-02-17T10:06:16.624+05:30Angular JS interview questions<div dir="ltr" style="text-align: left;" trbidi="on">
Some good resources on Angular JS:<br />
<br />
<ul style="text-align: left;">
<li><a href="http://angularinterviewquestions.blogspot.in/2014/12/list-of-angular-interview-questions.html">http://angularinterviewquestions.blogspot.in/2014/12/list-of-angular-interview-questions.html</a></li>
</ul>
</div>
Kinshuk Chandrahttp://www.blogger.com/profile/01344610750518430564noreply@blogger.com0