N Queen problem

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.

CODE

solveNQUtil(board, 0);
bool solveNQUtil(int board[N][N], int col)
{
    if (col >= N)
        return true;
 
    for (int i = 0; i < N; i++)
    {
        if ( isSafe(board, i, col) )
        {
            board[i][col] = 1;
 
            if ( solveNQUtil(board, col + 1) == true )
                return true;
 
            board[i][col] = 0; // BACKTRACK
        }
    }
    return false;
}

bool isSafe(int board[N][N], int row, int col)
{
    int i, j;
 
    /* Check this row on left side for attacking queens*/
    for (i = 0; i < col; i++)
    {
        if (board[row][i])
            return false;
    }
 
    /* Check upper diagonal on left side */
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
    {
        if (board[i][j])
            return false;
    }
 
    /* Check lower diagonal on left side */
    for (i = row, j = col; j >= 0 && i < N; i++, j--)
    {
        if (board[i][j])
            return false;
    }
 
    return true;
}

Implement Stack using Queues

push(s,  x)
1) Enqueue x to q1 (assuming size of q1 is unlimited).

pop(s)
1) One by one dequeue everything except the last element from q1 and enqueue to q2.
2) Dequeue the last item of q1, the dequeued item is result, store it.
3) Swap the names of q1 and q2
4) Return the item stored in step 2.
// Swapping of names is done to avoid one more movement of all elements from q2 to q1.
CODE

struct stack
{
  struct sNode *queue1;
  struct sNode *queue2;
};

void push(struct stack *s, int x)
{
  enqueue(&s-> queue1, x);
}

int pop(struct stack *s)
{
   int x; 
  
   if(s-> queue1== NULL && s->queue2== NULL)
   {
      printf("Stack is empty");
      exit(0);
   }

   while(queue1.getSize() != 1 )
   {
       x = queue1.dequeue();
       queue2.enqueue(x);
   }
   int value = queue1.dequeue();
   
   while( ! queue2.isEmpty() )
   {
       queue1.enqueue(queue2.dequeue() );
   }
   return value;
}

Stack  can also be implemented using one user Queue and one Function Call Queue (Recursion).
push(x)
1) Enqueue x to Queue1.

Pop():
1) If queue1 is empty then error.
2) If queue1 has only one element then return it.
3) Recursively pop everything from the queue1, store the popped item
in a variable res,  push the res back to queue1 and return res

struct stack
{
  struct sNode *queue1;
};

void push(struct stack *s, int x)
{
  enqueue(&s-> queue1, x);
}
  
int pop(struct stack *s)
{
   int x, res; 
  
   if(q->queue1== NULL)
   {
     printf("Stack is empty");
     exit(0);
   }
   else if(q->queue1->next == NULL)
   {
      return dequeue(&q->queue1);
   }
   else
   {
      x = dequeue (&q->queue1);
      res = pop(q);
      enqueue (&q->queue1, x);
  
      return res;
   }
}

Implement Queue using Stacks

enQueue(q,  x)
1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.

CODE

struct queue
{
  struct sNode *stack1;
};

/* Function to enqueue an item to queue */
void enQueue(struct queue *q, int x)
{
   push(&q->stack1, x);
}
  
/* Function to dequeue an item from queue */
int deQueue(struct queue *q)
{
   int x; 
  
   /* If both stacks are empty then error */
   if(q->stack1 == NULL && q->stack2 == NULL)
   {
      printf("Q is empty");
      getchar();
      exit(0);
   }
 
   /* Move elements from satck1 to stack 2 only if stack2 is empty */
   if(q->stack2 == NULL)
   {
     while(q->stack1 != NULL)
     {
        x = pop(&q->stack1);
        push(&q->stack2, x);
     }
   } 
 
   x = pop(&q->stack2);
   return x;
}

Queue can also be implemented using one user stack and one Function Call Stack (Recursion).
enQueue(x)
1) Push x to stack1.

deQueue:
1) If stack1 is empty then error.
2) If stack1 has only one element then return it.
3) Recursively pop everything from the stack1, store the popped item in a variable res,  push the res back to stack1 and return res

struct queue
{
  struct sNode *stack1;
};

void enQueue(struct queue *q, int x)
{
  push(&q->stack1, x);
}
  
/* Function to dequeue an item from queue */
int deQueue(struct queue *q)
{
   int x, res; 
  
   if(q->stack1 == NULL)
   {
     printf("Q is empty");
     getchar();
     exit(0);
   }
   else if(q->stack1->next == NULL)
   {
      return pop(&q->stack1);
   }
   else
   {
      /* pop an item from the stack1 */
      x = pop(&q->stack1);
  
      /* store the last dequeued item */
      res = deQueue(q);
  
      /* push everything back to stack1 */
      push(&q->stack1, x);
  
      return res;
   }
}

bitwise question

You are given two 32-bit numbers, N and M, and two bit positions, i and j. Wirte a method to insert M into N such that M starts at bit j and ends at bit i. You can assume that the bits j through i have enough space to fit all of M. That is, if M = 10011, you can assume that there are at least 5 bits between j and i. You would not, for example, have j = 3 and i = 2, beacause M could not fully fit between bit 3 and bit 2.
EXAMPLE
Input: N = 100 0000 0000, M = 10011, i =2, j = 6
Output: N = 10001001100″ [1]

Solution
Hint
First, create a number with all ones. We call this number “allOnes”. So allOnes = 1111 1111 1111 1111 1111 1111 1111 1111.
Second, shift the number left by j+1 bits. We call this number “left”. So left = 1111 1111 1111 1111 1111 1111 1000 0000.
Third, shift number 1 left by i bits. The number should be 0000 0100.
Fourth, use this number to minus 1. We call the result “right”. So right = 0000 0100 – 0000 0001 = 0000 0011.
Fifth, calculate left OR right. We call this result as “mask”. So mask = left | right = 1111 1111 1111 1111 1111 1111 1000 0011.
Sixth, M = M & mask. So M = 100 0000 0000.
Seventh, shift N left by i bits. So N = N << i = 100 1100.
The final result = M | N = 100 0000 0000 | 100 1100 = 100 0100 1100.
Code

int insertNum(int m, int n, int i, int j)
{
    if(i >= j)
    {
        cout << "Cannot insert number because i > j" << endl;
        return m;
    }
    int allOnes = ~0;
    int left = allOnes << (j+1);
    int right = (1 << i) - 1;
    int mask = left | right;
    m = m & mask;
    n = n << i;
    return m | n;
}

Count Inversions in an array

int _mergeSort(int arr[], int temp[], int left, int right)
{
  int mid, inv_count = 0;
  if (right > left)
  {
     mid = (right + left)/2;
  
     inv_count  = _mergeSort(arr, temp, left, mid);
     inv_count += _mergeSort(arr, temp, mid+1, right);
     inv_count += merge(arr, temp, left, mid+1, right);
  }
  return inv_count;
}
  
int merge(int arr[], int temp[], int left, int mid, int right)
{
  int i, j, k;
  int inv_count = 0;
  
  i = left;
  j = mid; 
  k = left;
  while ((i <= mid - 1) && (j <= right))
  {
    if (arr[i] <= arr[j])
    {
      temp[k++] = arr[i++];
    }
    else
    {
      temp[k++] = arr[j++];
    }
      inv_count += (mid - i);
    }
  }
  
  while (i <= mid - 1)
    temp[k++] = arr[i++];
  
  while (j <= right)
    temp[k++] = arr[j++];
  
  for (i=left; i <= right; i++)
    arr[i] = temp[i];
  
  return inv_count;
}

Longest Increasing Subsequence

for(int i = 1; i < n; i++)
{
    LS[i] = 1;
    for(int j = 0; j <= i; j++)
    {
        if (arr[i] > arr[j] && LS[i]<=LS[j])
            LS[i] = 1 + LS[j];
    }
}

//find max in LS array
return max(LS[]);

AUTO COMPLETE FORM CODE

<script>
 function autocomplete(fieldId, ajaxurl) {
        $('#'+fieldId).autocomplete({
            source: function( request, response ) {
                 $.ajax({  type: "GET",
                    url: ajaxurl, 
                    dataType: "json",
                    cache:false,
                    data: { userInput: request.term},
                    statusCode: {    401: function() {      alert("Page Not Found");    }  }})
                    .fail(function() { alert("Session Timed Out"); })
                   .done(
                    function( data )
                     {
                       response( $.map( data, function( item ) {
                            return {
                                label: item.sfullName,
                                value: item.sfullName
                            }
                        }));  
                        
                     });
            },
            minLength: 2,
            open: function() {
                $( this ).removeClass( "ui-corner-all" ).addClass( "ui-corner-top" );
            },
            close: function() {
                $( this ).removeClass( "ui-corner-top" ).addClass( "ui-corner-all" );
            }               
        });           
      
  }
</script>

public ActionForward execute(ActionMapping mapping, ActionForm form,
                    HttpServletRequest request, HttpServletResponse response)
{
    if(session.getAttribute("associateNamesList")!=null)
    {  
        associatesList=(List<AssociateSearchBean>)session.getAttribute("associateNamesList");
    }
    else
    {
        //get all usernames from db using select query into a list
        associatesList =objDB.getAssociateNames();           
        session.setAttribute("associateNamesList",associatesList);
    }

    //here userinput is whatever user types which should be more than 3 characters
    List<AssociateSearchBean> suggestions = getAssociates(associatesList,userInput);
    String suggestionsJson = gson.toJson(suggestions);  /Convert Java object to JSON format
    writeTextResponse(response, suggestionsJson);
}    
public  List<AssociateSearchBean> getAssociates(List<AssociateSearchBean> associateSearchResultList,final String userInput) {
        
        List<AssociateSearchBean> filteredlist = new ArrayList<AssociateSearchBean>();
        int count = 0;
        for (AssociateSearchBean associateName : associateSearchResultList) {
            if(associateName!=null)
            {
            if (userInput!=null && userInput.length() >= 2 && associateName.getFirstName().toLowerCase().startsWith(userInput.toLowerCase())) {
                filteredlist.add(associateName);
                count++;
                continue;
            }
                
            if (userInput!=null && userInput.length() >= 2 && associateName.getLastName()!=null && associateName.getLastName().toLowerCase().startsWith(userInput.toLowerCase())) {
                filteredlist.add(associateName);
                count++;
            }
            //so that only first 12 entries are displayed
            if (count >= 12) {
                break;
            }
        }
    }
    return filteredlist;
}
protected void writeTextResponse( HttpServletResponse resp, String content )
{
    try
    {
        resp.setContentType("text/html");
        resp.setHeader("Cache-Control", "no-cache");
        resp.getWriter().print(content);
        resp.getWriter().close();
    }
    catch (Exception ex)
    {
        logger.logDebug(ex.getMessage());
    }
}

<script type="text/javascript">
   $(document).ready(function() {
     autocomplete('sFullNameId','<%=request.getContextPath()%>/searchADPian.do?action=processAutoSearch');
   });
</script>

Add and substract two numbers without using arithmetic operators

Add two numbers without using arithmetic operators

int Add(int x, int y)
{
    // Iterate till there is no carry  
    while (y != 0)
    {
        // carry now contains common set bits of x and y
        int carry = x & y;  
 
        // Sum of bits of x and y where at least one of the bits is not set
        x = x ^ y; 
 
        // Carry is shifted by one so that adding it to x gives the required sum
        y = carry << 1;
    }
    return x;
}

Subtract two numbers without using arithmetic operators

int subtract(int x, int y)
{
    // Iterate till there is no carry
    while (y != 0)
    {
        // borrow contains common set bits of y and unset bits of x
        int borrow = (~x) & y;
 
        // Subtraction of bits of x and y where at least
        // one of the bits is not set
        x = x ^ y;
 
        // Borrow is shifted by one so that subtracting it from
        // x gives the required sum
        y = borrow << 1;
    }
    return x;
}

Build Lowest Number by Removing n digits from a given number

void buildLowestNumberRec(string str, int n, string &res)
{
   if (n == 0)
   { 
      res.append(str);
      return;
    }
    int len = str.length();
    if (len <= n)
        return;
     int minIndex = 0;
     for (int i = 1; i<=n ; i++)
        if (str[i] < str[minIndex])
            minIndex = i;
     res.push_back(str[minIndex]);
     string new_str = str.substr(minIndex+1, len-minIndex);
     buildLowestNumberRec(new_str, n-minIndex, res);
 }

How to print maximum number of A’s using given four keys

int findoptimal(int N)
{
    // The optimal string length is N when N is smaller than 7
    if (N <= 6)
        return N;
 
    // Initialize result
    int max = 0;
 
    // TRY ALL POSSIBLE BREAK-POINTS
    // For any keystroke N, we need to loop from N-3 keystrokes
    // back to 1 keystroke to find a breakpoint 'b' after which we
    // will have Ctrl-A, Ctrl-C and then only Ctrl-V all the way.
    int b;
    for (b=N-3; b>=1; b--)
    {
            // If the breakpoint is at b'th keystroke
            int curr = (N-b-1)*findoptimal(b);
            if (curr > max)
                max = curr;
     }
     return max;
}

Explanation
For N = 7
Case1
B = n-3 = 4
AAAA Ctrl-A Ctrl-C Ctrl-V = 8;    n-b-1 = 7-4-1 = 2 * findoptimal(4) = 2*4 = 8

Case2
B = 3
AAA Ctrl-A Ctrl-C Ctrl-V Ctrl-V= 9;  n-b-1 = 7-3-1 = 3* findoptimal(3) = 3*3 = 9

Case3
B = 2
AA Ctrl-A Ctrl-C Ctrl-V Ctrl-V Ctrl-V =  8; n-b-1 = 7-2-1 = 4* findoptimal(2) = 4*2 = 8

Case4
B = 1
A Ctrl-A Ctrl-C Ctrl-V Ctrl-V Ctrl-V Ctrl-V = 5; n-b-1 = 7-1-1 = 5* findoptimal(1) = 5*1 = 5

For N = 10
B = n-3 = 7

n-b-1 = 10-7-1 = 2*findoptimal(7)