Yahoo Interview Question
Software Engineer / Developers<div class="cpp" style="font-family:monospace;color: #006; border: 1px solid #d0d0d0; background-color: #f0f0f0;"><ol><li style="font-weight: normal; vertical-align:top;font: normal normal 130% 'Courier New', Courier, monospace; color: #003030;"><div style="font: normal normal 1em/1.2em monospace; margin:0; padding:0; background:none; vertical-align:top;color: #000020;"><span style="color: #0000ff;">int</span> main<span style="color: #008000;">(</span><span style="color: #008000;">)</span> </div></li>
<li style="font-weight: normal; vertical-align:top;font: normal normal 130% 'Courier New', Courier, monospace; color: #003030;"><div style="font: normal normal 1em/1.2em monospace; margin:0; padding:0; background:none; vertical-align:top;color: #000020;"><span style="color: #008000;">{</span></div></li>
<li style="font-weight: normal; vertical-align:top;font: normal normal 130% 'Courier New', Courier, monospace; color: #003030;"><div style="font: normal normal 1em/1.2em monospace; margin:0; padding:0; background:none; vertical-align:top;color: #000020;"> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> N <span style="color: #000080;">=</span> <span style="color: #0000dd;">3</span><span style="color: #008080;">;</span></div></li>
<li style="font-weight: normal; vertical-align:top;font: normal normal 130% 'Courier New', Courier, monospace; color: #003030;"><div style="font: normal normal 1em/1.2em monospace; margin:0; padding:0; background:none; vertical-align:top;color: #000020;"> <span style="color: #0000ff;">int</span> ar<span style="color: #008000;">[</span>N<span style="color: #008000;">]</span> <span style="color: #000080;">=</span> <span style="color: #008000;">{</span><span style="color: #0000dd;">1</span>, <span style="color: #0000dd;">2</span>, <span style="color: #0000dd;">2</span><span style="color: #008000;">}</span><span style="color: #008080;">;</span><span style="color: #666666;">//, 2, 3, 3, 4, 4, 5, 6, 6}; </span></div></li>
<li style="font-weight: bold; vertical-align:top;font-weight: bold; color: #006060;"><div style="font: normal normal 1em/1.2em monospace; margin:0; padding:0; background:none; vertical-align:top;color: #000020;"> std<span style="color: #008080;">::</span><span style="color: #0000dd;">cout</span> <span style="color: #000080;"><<</span> getit<span style="color: #008000;">(</span>ar, N<span style="color: #008000;">)</span><span style="color: #008080;">;</span></div></li>
<li style="font-weight: normal; vertical-align:top;font: normal normal 130% 'Courier New', Courier, monospace; color: #003030;"><div style="font: normal normal 1em/1.2em monospace; margin:0; padding:0; background:none; vertical-align:top;color: #000020;"><span style="color: #008000;">}</span></div></li>
</ol></div>
In one pass, find the min of the list
In second pass, print the min as you encounter it on the list. If we were allowed extra memory, we could have a kept the counter of the min and avoid second pass.
Now we have found the min element. Do this for the rest of the list to find the second min
O(n^2).
public void print(Node root){
- Anonymous September 12, 2010int count=0;
//count the number in the first round
while(node!=null){
count ++;
}
int smallest =integer.MIN_VALUE;
int previoussmallest =integer.MIN_VALUE;
int times;
for(int i=0;i<count;i+=times){
while(node!=null){
//find next smallest one, i don't have time to write it now
}
for(int j=0;j=times;j++)
system.out.println(smallest );
}
}