Binary Search Algorithm Variations and Problems

Binary Search is a simple algorithm but is tricky when it comes to implementing it. The lower and upper bounds have to be set carefully to avoid those silly errors.
I personally prefer the iterative version to avoid unnecessary use of recursive calls.

Below is the standard algorithm

bool search(int x[], int n, int k) {
    int l = 0, r = n-1;
    while (l <= r) {
        int m = (l+r)/2;
        if (x[m] == k) return true;
        if (x[m] < k) l = m+1; else r = m-1;
    }
    return false;
}

Now lets try to find the first element greater than given element

int search(int x[], int n, int k) {
    int l = 0, r = n-1;
    while (l <= r) {
        int m = (l+r)/2;
        if (x[m] < k) l = m+1; 
        else {
              r = m-1;
              index = m;
        }
    }
    return index;
}

i will continue updating this post

How to install j2me in windows?

As i wasted hours installing the sofware for developing java mobile applications, i thought i would summarise the method i followed so that in future nobody wastes as much the time i wasted.
Basically you could install j2me via one of these ways

• Jave ME SDK
• Netbeans or Eclipse integration with plugin
• External softwares 

I tried the first two and ended up regretting, so i tried the third method and it worked :)

I used Sun-Wireless Toolkit 2.5.2 ML

 

download link :choose: Sun Java Wireless Toolkit for CLDC 2.5.2 ML

NOTE: you must have 32 bit JRE,JDK for this to work. If you dont have 32 bit version download it from java website. If you are not sure whether you have 32 bit version go to

 C:\Program Files (x86)\Java\ 

if you have both jdk and jre , fine you are ready to continue further else install the missing parts

Start the installation:

After installing open the s/w ( you would have a shortcut in desktop)

Click new project to create a new project

Give project name, Midlet class name with be the name of the program

Note down the project location which is shown in the screen, you have to save your source code in the "src" folder  which is inside ur projecct folder ( here project folder name is Helloworldproject)

here is a sample code to test:

Saved the file as Helloworldmidlet.java ( in src folder inside the Project folder )

<code>

import javax.microedition.lcdui.Display;
import javax.microedition.lcdui.Form;
import javax.microedition.lcdui.StringItem;
import javax.microedition.lcdui.TextField;
import javax.microedition.midlet.MIDlet;

public class Helloworldmidlet extends MIDlet {

    
    // The MIDlet's Display object
    protected Display display;
    
    // Flag indicating first call of startApp
    protected boolean started;
    
    protected void startApp() {
        if (!started) {
            display = Display.getDisplay(this);
            
            Form form = new Form("Item Layout");
            
            form.append("Hello");
            form.append("World");
            
            form.append("\nLet's start\na new line\n");
            form.append("This is quite a long string that may not fit on one line");
            
            form.append(new TextField("Name", "J. Doe", 32, TextField.ANY));
            form.append("Address");
            form.append(new TextField(null, null, 32, TextField.ANY));            
            
            display.setCurrent(form);
            
            started = true;
        }
    }

    protected void pauseApp() {
    }

    protected void destroyApp(boolean unconditional) {
    }
}

</code>

Microsoft Internship Interview experience - 2015 MIT(Madras Institute of Technology)

i have described my internship interview experience below, but its highly subjective and varies from college to college also depends on the team which came to interview you, so be prepared for the worst!

until 2014 only MS-IDC(Mircrosoft India Developement Center) used to visit our campus, but this year to our surprise we had both MS-IDC and MS-IT. Google to find the difference between them but pay package is same for both.

Round 1:

As usual this round was hosted on cocubes.com and comprised of 15 questions. Time alloted was 30 minutes

Topics covered: Datastructures,GeneralAptitude,C,C++,Java,OS

You must be lucky to get easy ques set, i got a somewhat difficult set thought i wouldnt clear but fortunately i cleared this round.

out of some 250 students nearly 70-80 were selected

Round 2:

This was an online coding round. Time alloted was 1 hour. Just 2 questions

1. Find the sum of all nodes that are K distant away from given node in a binary tree
2. Given two arrays, both are arrays of digits, replace the digits in first array with second array (optional) so that when you view the first array as a number it is the largest possible 

ex: a[] = {7,5,3,1} b[]={1,9,2} 

answer : a[] = {9,5,3,2} which is 9532

word of advice: 

• Performing well in this round is very important. You will be ranked high based on this round and since i performed well i had chance to choose MS-IDC or MS-IT.
• Microsoft considers cumulative score of all rounds so each and every round matters
• Beleive me, the questions that my friends got was exactly the same posted recently in Geeksforgeeks Microsoft Internship Interview experience. we even discussed about it but were lethargic that we wont get the same. So check all the questions recently posted before your coding round.

Totally 25 students got selected.

Round 3: MS-IT

Since i solved both questions in coding round, myself and a few were allowed to appear for both IDC and IT. They first conducted the round for MS-IT

It was a group fly round. Question was unexpected and boring, here is it

Q: Design a railway reservation system that is futuristic and handles the disadvantages of IRCTC

  They expected design, features, implementation faesibility etc.. always question your mentors what they expect from your answer. It matters a lot as they are the ones who validate your answers

Time alloted: 30 mintues

I was selected along with other 9 students.

I gave my priority as MS-IDC. So they asked me to continue further rounds in MS-IT if am not selected in MS-IDC

Round 3: MS-IDC

Group Fly round

Time alloted:30 minutes

Q: Print all the palindromes present in a string

Note: 

• All those who gave DP solution were rejected.
• Optimize ur code.
• Talk to your mentors and share you solution before you write.(I could have gone wrong with my solution if i hadnt questioned him , i actually trimmed white spaces, but he said he wanted to preserve it)
• Write neat, clear code
• Dont strike and name the variables and functions properly 

Around 10 were seletecd from this round

Round 4: MS-IDC

It was actually a personal interview, but since my interviewer was a higher level guy he interviewed me along with 3 others. He conducted it similar to group fly round.

Q: find an element in a row wise and column wise sorted matrix.

Once i told my approach in 5 minutes he asked me to code it. It was O(n) solution. I knew better solution exists but since he asked to code after hearing my approach i proceeded.

He kept on increasing conditions each time. Like duplicate values. etc..

I managed to answer all his questions.

Q2: Suggest a better way to ensure security during read, write, execute operations for file.

I had no idea what he was talking about :P . So i kept on asking him questions and finally he leaked the solution unknowingly :). I used that as clue and wrote my idea. It was something like blocking the process and distinguishing users.

Around 6 were selected

Round 5:MS-IDC

This was worst round i ever faced. The interviewer seemed strict. Scanned my resume. Asked some questions and finally proceeded to the question

Q: Given a sentence validate it.

He wantedly gave a vague question. As usual i kept on asking the interviewer for constraints. I realized the more I ask , the more complicated the question began. But fortunately he limited the conditions.

I told my approach and he asked me to code.

He saw my code and his reaction totally made me flabbergasted. He whined that my code was bad. Lots of if-else, etc..

i suggested improvements to whatever he said. But he seemed unsatisfied. I thought i am done, but i dont want to give up , I asked for a clue, He gave me a clue. I tried to build my solution with that. I could reach to a partial solution. He asked me to sketch my idea. It actually came in the form of automata. He asked me to map it in the form of table. I started thinking but the interviewer left the room. Tough guy! 

With no effing expectation waited for results. To my surprise myself and 4 other got intern offer at MS-IDC.

so anything can happen in an interview, never lose your cool even if the interviewer acts tough. I heard that was a stress interview. In the end it only matters whether you impressed your interviewer.

All the Best.

RANDOMIZED QUICK SORT C/C++ PROGRAM

Its obvious that Quick sort performs at O(nlogn) running time, but the worst case running time of Quick sort is O(n ^2).
When does this case happen? It happens when a pivot was chosen such that the array is not divided into two haves i.e
      consider 1,2,3,4,5 when 5 is chosen as pivot ,
AFTER PARTITION
                                             left subarray : 1,2,3,4
                                             right subarray : (empty)

when this trend continues we actually perform n times the sorting function and since each call performs a partition O(n) total complexity is O(n*n) i.e O(n^2)

Hence to avoid this situation we chose pivot randomly instead of choosing the last element as pivot(traditional way)

you can however argue that even choosing the pivot randomly can lead to worst case, but statistically the probablity for such case to occur is low compared to normal way.

Here is the C++ code (To Convert to C code just replace cin,cout with printf,scanf)

CODE:
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;

int partition(int *a,int p,int r)
{
srand(time(0));
int pivot = rand()%(r-p);
pivot += p;
swap(a[r],a[pivot]);
pivot = r;
int temp = a[r];
int i = p-1;
for (int j = p; j < r ;j++) {
if ( a[j] <  temp ) {
i++;
swap (a[i],a[j]);
}
}
i++;
swap (a[r],a[i]);
return i;
}


void quicksort(int *a,int p,int r)
{
if (p < r)
{
int q = partition(a,p,r);
quicksort(a,p,q);
quicksort(a,q+1,r);
}
}

int main() {
// your code goes here
int a[] ={2,5,6,2,1,9,8};
quicksort (a,0,6);
for (int i=0;i<7;i++)
cout << a[i] << endl;
return 0;
}

CALCULATING THE SIZE OF STRUCTURE IN C/C++:

consider a strucure

struct X
{
    short s; 
    int   i; 
    char  c; 
             
};

what do you think the size of structure will be? 2 + 4 + 1 ?

Sorry, then you are wrong. Because to reduce the lookup time by CPU compiler pads up the bytes untill it becomes a multiple of 4. This is however dependent on hardware,but most compilers does so.

so what happens is 

struct X
{
    short s; /* 2 bytes */
             /* 2 padding bytes */
    int   i; /* 4 bytes */
    char  c; /* 1 byte */
             /* 3 padding bytes */
};

but this is not the best way to declare the struct , why? because you waste space due to  padding of bytes. So here are some tricks to reduce the eat up of byte padding







struct Y
{
    int   i; /* 4 bytes */
    char  c; /* 1 byte */
             /* 1 padding byte */
    short s; /* 2 bytes */
};

struct Z
{
    int   i; /* 4 bytes */
    short s; /* 2 bytes */
    char  c; /* 1 byte */
             /* 1 padding byte */
};

POST YOUR DOUBTS IN THE COMMENTS

SPOJ : NEG2 SOLUTION

I suggest you read wikipedia link. But i can summarise you in a nut shell. Our task is to convert the given decimal to a negative base(2) number to binary form
i.e take for example  7(base 10)

Basically pick the remainder as the positive even when remainder is negative (tricky pay attention!)

 7 = -3*-2 + 1. (least significant digit)
-3 =  2*-2 + 1
 2 = -1*-2 + 0
-1 =  1*-2 + 1
 1 =  0*-2 + 1. (most significant digit)

as you can notice in 2nd step -3 % -2 is actually -1, but we have to store as 1 as binary representation cant contain negative numbers.

so we add 1 to n/2 i.e  -3/-2  = 1 adding 1 we get 2 ( this ensures remainder is always postive)


posting the logic:

  string s="";
     if(n==0)
     {
             printf("0\n");
             return;
     }
     int i=-2;

     while(n)
     {
             if(n%i<0)
             {

             s=(char)(((n%i)+2)+'0')+s;   // When the remainder is negative 

             n=(n/i)+1;                    // adding one so that when divided remainder is > 0
             }
             else
             {
             s=(char)((n%i)+'0')+s;
             n=n/i;
             }

     }
    cout<<s;

SPOJ : ACPC 10D Trigraphs Solution

This problem could be solved by using DP.
Step 1:
        Initialse the adjacent nodes to the source node.
Step 2:
        Loop Across the other i nodes from 2 to N and initialise them.

P re-Requesite: DP
     However Learning Floyd Warshall Algorithm would help you in solving this problem.



Code:


#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;

int main()
{
int i=1;
while(1) {
int n;
cin >>n;
if(n==0)
return 0;
int a[n][3];
for (int i=0;i<n;i++)
cin >>a[i][0]>>a[i][1]>>a[i][2];
cout<<i<<". ";
if(n==1)
cout<<a[0][1]<<endl;
else {
                                                               // Initialisation Step
a[1][0] += a[0][1];
a[0][2] += a[0][1];
a[1][1] += min(min(a[1][0],a[0][1]),a[0][2]);
a[1][2] += min(min(a[0][2],a[0][1]),a[1][1]);


                                                                 // Calculating the remaing nodes
for(int i  = 2 ; i<n;i++)
{
a[i][0] += min(a[i-1][0],a[i-1][1]);
a[i][1] += min(min(min(a[i][0],a[i-1][0]),a[i-1][1]),a[i-1][2]);
a[i][2] += min(min(a[i][1],a[i-1][1]),a[i-1][2]);
}
cout <<a[n-1][1]<<endl;
i++;
}
}
return 0;
}