Give a method to swap two numbers without using additional memory. Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: No remarks buddy, it's an easy one :P Hints: Do you really think this needs a hint? If you can't solve it, you can't. Solution: We may use addition/subtraction or XOR to achieve this. XOR does not cause overflows and hence is superior. Complexity: Time : O(1) Space : O(1) void swap_xor(int &num1, int &num2){ num1 ^= num2; num2 ^= num1; num1 ^= num2; } void swap(int &num1, int &num2){ num1 = num1 + num2; num2 = num1 - num2; num1 = num1 - num2; }

Give a fast method to multiply a number by 7. Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: Remember when you were studying maths in junior high-school Hints: In how many ways can you multiply a number by 7? Solution: We multiply by 7 by first multiplying by 8 and subtracting the number from the result. Multiplication by 8 is equivalent to shifting left 3 bits. Complexity: Time : O(1) Space : O(1) Code: int multiply_7(int N){ return (N << 3) - N; }

Given 2D array with integers sorted both horizontally and vertically. Devise an efficient algorithm to search for key in the 2D array. What is the complexity ?  Eg.      1 4 7 13      2 5 9 15      3 6 10 16 Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: Assume the row is sorted from left to right and column from top to bottom so that the least number is at top-left. Hints: While searching just look for the relevant data for existence of the required key. i.e. Think in which area there is a possibility of finding the key. Solution: Two solutions exists : First one is : Start from left-bottom While within boundary If key found print and exit If key is smaller move up else move right Second one : Let M < N (otherwise interchange the usage below) for each M 1D arrays do binary search in O(log N) Complexity: First : Time : O(M + N) Space : O(1) Second : Time : O(M log N) M < N Space : O(1) The advantage of second method is seen when M << N where second method degenerates to binary search whereas first method degenerates to sequential search. Code: /** * M rows * N columns * (row, col) position of searched key if successful **/ Method 1: bool search_2D(int *input, int M, int N, int key, int *row, int *col){ *row = M-1; *col = 0; while(*row > 0 && *col < N){ int current = *(input + N*(*row) + (*col)); if(key == current) return true; else if(key < current) (*row)--; else (*col)++; } return false; } Method 2: bool search_2D(int *input, int M, int N, int key, int *row, int *col){ int increment = 1, total_rows = M, total_cols = N; if(M > N){ increment = N; total_rows = N; total_cols = M; } for(*row =0; *row < total_rows; i++){ *col = 0; if(search_1D(input + *row, total_cols, key, col, increment)){ return true; } } return false; } bool search_1D(int *input, int N, int key, int *index, int increment){ int low = 0, high = N-1; while(low <= high){ *index = (low + high)/2; int value = *(input + (*index)*(increment)); if(value == key) return true; else if (value < key) low = *index + 1; else high = *index - 1; } return false; }

Assume you have infinite memory. Design an algorithm using stacks that can find the minimum and maximum at any point while reading an infinite sequence of numbers in least possible time. Eg. 5, 9, 2, 35, 23, 1, ... After 3rd element, the algorithm would tell min = 2, max = 9 After 6th element, algorithm would tell min = 1, max = 35 Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: There is an unlimited space. Hints: Use 3 stacks. Click again for solution. Solution: 1. 1st stack will be the main stack in which we are pushing all elements 2. 2nd stack will contain maximum elements up to that point 3. 3rd stack will contain minimum elements up to that point. So range can also be found in O(1) time, by popping from 2nd stack & 3rd stack and taking their difference. Complexities : Time : O(1) Space : Unlimited Code : template <class T> class range_stack<T> { private : stack<T> main, min, max; public : int push(T value){ main.push(value); if(main.empty()){ min.push(value); max.push(value); } else { if(min.top() > value) min.push(value); else min.push(min.top()); if(max.top() < value) max.push(value); else max.push(max.top()); } } T pop(){ T tmp = main.top(); main.pop(); min.pop(); max.pop(); return tmp; } T range(){ return max.top() - min.top(); } }

A high school has a strange principal. On the first day, he has his students perform an odd opening day ceremony:There are one thousand lockers and one thousand students in the school. The principal asks the first student to go to every locker and open it. Then he has the second student go to every second locker and close it. The third goes to every third locker and, if it is closed, he opens it, and if it is open, he closes it. The fourth student does this to every fourth locker, and so on. After the process is completed with the thousandth student, how many lockers are open ?

You are given a weighing machine. Find the minimum number of denominations of weights you need to measure any N kgs given that you may use the denominations on any side of the weighing machine.

Devise an algorithm to find whether a given number N is of the form 2^x + 2^y (^ means exponentiation, x and y are positive). Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: No remarks for this one. Hints: No hints will be provided for this problem. Think more buddy, Yes! you can. Solution: The solution is using bitmaps (arrays of bits) 1. Initialization will take O(N) but checking for existence will be done in O(1) 2. Bitmap array will be char[M/8] since a char is 8 bits long Complexities : Time : O(N) in initialization, O(1) in access Space : O(M) Code : // init() is called once for all numbers in list one by one to initialize the bitmap void init(int[] bitmap, int M, int num){ int base = num/8; int offset = 1 << (n%8); bitmap[base] |= offset; } bool exists(int[] bitmap, int M, int num){ int base = num/8; int offset = 1 << (n%8); return (bitmap[base] & offset); }

Devise an algorithm to find whether a given number N is of the form 2^x + 2^y (^ means exponentiation, x and y are positive). Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj, Gurpreet & Ankit Remarks: Use concepts of bit manipulation. Check for right-most bit. Hints: The rightmost bit may be set to zero by (N & N-1), so we do it twice and if the number becomes zero, it means it had 2 bits as 1 before thus having the required form 2^x + 2^y. Also consider the case where x = y separately. Solution: The rightmost bit may be set to zero by (N & N-1), so we do it twice and if the number becomes zero, it means it had 2 bits as 1 before thus having the required form 2^x + 2^y. When x = y: The number of bits set to 1 in binary representation of N is one. Applying N=(N & N-1), once will make N=0. Now, one cannot apply N= (N & N-1) again, as this will change the value of N ( ! = 0 ). Hence, one must check if after using the formula N=(N & N-1) ,N has become 0 or not. Another test case is when N=1 , 0 . In that case N&(N-1) = 0 and it doesnt mean x=y. So in our algorithm the first step must be modified as : if(N>1), use the formula N=(N& (N-1) ) and check if N=0. Hence, We consider the case when x=y, so only one bit is set. Also we check if number is not 0 or 1 initially for which answer is false. bool check_form(int N){ if(N < 2) return false; N = N & (N-1); if(!N) return true; return !(N & (N-1)); }

Fint out the matching socks: Michael have ten pairs of black socks, eight pairs of white socks and seven pairs of green socks. Everything is mixed in a draw. As there is no light he were not able to identify the color of the socks. How many of the socks did he want to take to match one pair ? p.s. - For Remarks please hit the question name once, given in the question itself. For Hint, hit it twice and for the solution, hit it thrice. Remarks: There is no difference between left and right socks. Hints: The principle used is the Pigeon Hole Principle. Try to learn more about it from Wikipedia, since many clever solutions result from clever application of the principle. Solution: The answer is 4 since in worst case all 3 socks taken first will be different color then the 4th one would be repetition. However if we consider a left sock to be different from right one, then at least 10 + 8 + 7 + 1 = 26 socks are needed.

A blind search (also called an uninformed search) is a search that has no information about its domain. The only thing that a blind search can do is distinguish a non-goal state from a goal state.

For more read here about Blind Search

Code:
 

#include<iostream>
#include<cstdlib>
#include<map>
#define MAX 50
using namespace std;

map <int,int> mp;

void printpath(int start)
{
 if (mp[start]==-1)
 {
  cout<<start<<endl;
  return;
 }
 else
 {
  cout<<start<<"  ";
  printpath(mp[start]);
 } 
}
int main()
{ 
 int n,adj[MAX][MAX],v[MAX];
 int rnd,start,end,temp;
 bool solve=false;
 cout<<"enter the no of nodes : ";
 cin>>n;
 cout<<"enter the adjacency matrix : ";
 for(int i=0;i<n;i++)
  for(int j=0;j<n;j++)
   cin>>adj[i][j];
 for(int i=0;i<n;i++)
  v[i]=0;
 cout<<"enter the start and end node: ";
 cin>>start>>end;
 temp=start;
 v[start]=1;
 mp[end]=-1;
 while(!solve)
 {
  rnd=random()%n;
  //cout<<"reached here";
  //cout<<"  "<<rnd<<endl; 
  if(rnd==end && adj[start][rnd]==1)
  {
   mp[start]=rnd;
   solve=true;
  }
  else
  {
   if(adj[start][rnd]==1 && v[rnd]==0)
   {
    mp[start]=rnd;
    //cout<<mp[start]<<endl;
    v[rnd]=1;
    start=rnd;
   }
   else
    continue;
  }
 } 
 printpath(temp);
 return 0;
}

In computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by incrementally changing a single element of the solution. If the change produces a better solution, an incremental change is made to the new solution, repeating until no further improvements can be found.

For example, hill climbing can be applied to the Traveling Salesman Problem. It is easy to find an initial solution that visits all the cities but will be very poor compared to the optimal solution. The algorithm starts with such a solution and makes small improvements to it, such as switching the order in which two cities are visited. Eventually, a much shorter route is likely to be obtained.

Read more about Hill Climbing Problem

Code:

#include<iostream>
#include<cstdio>
using namespace std;
int calcCost(int arr[],int N){
 int c=0;
 for(int i=0;i<N;i++){
  for(int j=i+1;j<N;j++) if(arr[j]<arr[i]) c++;
 }
 return c;
}

void swap(int arr[],int i,int j){
 int tmp=arr[i];
 arr[i]=arr[j];
 arr[j]=tmp;
}

int main(){
 int N;
 scanf("%d",&N);
 int arr[N];
 for(int i=0;i<N;i++) scanf("%d",&arr[i]);
 int bestCost=calcCost(arr,N),newCost,swaps=0;;
 while(bestCost>0){
  for(int i=0;i<N-1;i++){
   swap(arr,i,i+1);
   newCost=calcCost(arr,N);
   if(bestCost>newCost){
    printf("After swap %d: \n",++swaps);
    for(int i=0;i<N;i++) printf("%d ",arr[i]);
    printf("\n");
    bestCost=newCost;
   }
   else swap(arr,i,i+1);
  }
 }
 printf("Final Ans\n");
 for(int i=0;i<N;i++) printf("%d ",arr[i]);
 printf("\n");
 return 0;
}

Minimax (sometimes minmax) is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case (maximum loss) scenario. Alternatively, it can be thought of as maximizing the minimum gain (maximin). Originally formulated for two-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision making in the presence of uncertainty.

For more please refer Minimax

Code:

#include<iostream>
#include<cstdlib>
#include<vector>
using namespace std;

vector <int> vec;

int large(int a,int b)
{
 if(a>b)
  return a;
 else
  return b;
}

int small(int a,int b)
{
 if(a>b)
  return b;
 else 
  return a;
}

void max_min(int p,int q,int *max,int *min)
{
 if(p==q)
 {
  *max=vec[p];
  *min=vec[q];
 }
 
 else if(p==(q-1))
 {
  if(vec[p]>vec[q])
  {
   *max=vec[p];
   *min=vec[q];
  }
  else
  {
   *max=vec[q];
   *min=vec[p];
  }
 }
 
 else
 {
  int m=(p+q)/2;
  int max1,max2,min1,min2;
  
  max_min(p,m,&max1,&min1);
  max_min(m+1,q,&max2,&min2);
  *max=large(max1,max2);
  *min=small(min1,min2);
 }
}

int main()
{
 int a,n=0;
 int min=0,max=0;
 
 cout<<"enter the elements (enter -1 to quit) :  ";
 while(1)
 {
  cin>>a;
  if(a==-1)
   break;
  else
  {
   vec.push_back(a);
   n++;
  }
 }
 max_min(0,n-1,&max,&min);
 
 cout<<"MAX = "<<max<<"\t"<<"MIN = "<<min<<endl;
 
 return 0;
}

Random Selection from a Linked List There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.  Conditions :  Use random number function rand() that returns a number between 0 and 1. It must be done in O(N) time p.s. - For Remarks please hit the question name once, given in the question itself. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. For hints, please hit the question name again. Hints: No hints. For the solution, please hit the question name again. Solution: 1. Take 2 arrays R[K] and Num[K] 2. For each element in sorted array read one by one and do :      1. Generate a random number r.      2. If R is not full, insert r into R and element into Num array else replace r with highest random number in R and insert current element into corresponding index in Num array (Note that we want to keep the least K random numbers and corresponding elements in list) 3. Print Num[] Complexities : Time : O(N) Space : O(K) Code : void random_selection(int[] input, int N, int K){ int number[K]; double random[K]; int count = 0; for(int i=0; i<N; i++){ double r = rand(); if(r < number[count-1]){ index = insert(random, K, &count, r); number[index] = input[index]; } } for(int i=0; i<K; i++){ printf("%d ", number[i]); } } int insert(double *list, int K, int *count, double entry){ if(*count == K-1){ (*count)--; } int i = *count; while(*(list+i) > entry){ *(list + i + 1) = *(list + 1); i--; } *(list + i + 1) = entry; (*count)++; return i+1; }