There are 5 thieves. They are all numbered one to five. They have 500 pieces of gold which need to be distributed among themselves. First the number 1 distributes it and after that a voting is done : if he gets majority votes his distribution is carried out else he is killed, if the votes are equal, then also distribution is done his way. If he is killed then next numbered person does the distribution and this goes on till number 5. Each thief values his life more than the gold. So how does the first thief distribute gold to get maximum and to not get killed also ? 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: First of all try to understand the problem. Hit again for hints. Hints: Think first for small numbers and then generalize the pattern. Solution: Observing the pattern: For 2 thieves, the proposal would be (500, 0) as even if second disagrees, it does not matter. For 3 thieves, the proposal would be (499, 0, 1). In this case, second will disagree but third will agree because if he disagrees, then 2nd will propose next as (500, 0) and he would get nothing. So on for 5 thieves, the proposal is (498, 0, 1, 0, 1)

Two friends decide to meet at a cafe between 11 am and 12 pm i.e. one hour. They also decide that the one who reaches before the other waits for 5 minutes and if the other does not arrive he leaves. What is the probability of their meeting ? 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: Just imagine dude :P. Hit again for hints. Hints: Are you not able to solve this? or You want to check the solution. Hit again for Solution Solution: The probability is found using areas. The colored area represents the successful meeting since the difference between x and y co-ordinates of any point in the colored area is less than or equal to 5 on absolute value. Enlarge the image by clicking on it to see the answer

Run-length encoding (RLE) is a very simple form of data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run. Count of 1 is not indicated. Write a program to find RLE of given string. Eg. input = "aabbbcddeef" RLE = "a2b3cd2e2f" input = "aaabbcddeeeef" RLE = "a3b2cd2e4f" 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 remark dude :P. Hit again for hints. Hints: This is an intelligent problem, try to solve it without a hint. Hit again for Solution Solution: We simply use a switch while checking each character in input and count them if equal and print the count if count is greater than one. Complexity: 1. TIme : O(N) 2. Space : O(1) Code: void rle_encode(char[] input, int N, char[] output){ int index = 0, count = 1; char last = input[0]; for(int i=1; input[i]; i++){ if(last == input[i]){ count++; } else { output[index++] = last; if(count > 1){ output[index++] = count + '0'; count = 1; } last = input[i]; } } output[index++] = last; if(count > 1){ output[index++] = count + '0'; } }

You have 12 balls. All of them are identical except one, which is either heavier or lighter than the rest. You have a simple two-armed scale, and are permitted three weighing. Can you identify the odd ball, and determine whether it is heavier or lighter than the rest ? 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 remark dude :P. Hit again for hints. Hints: Its a puzzle to puzzle you. No hints will be provided. Hit again for solution. Solution: Due to some problem while formatting the answer, I was unable to write here. So please find the image of the answer for this question.

Given an integer N. Devise an algorithm to find out the smallest integer greater than N having the same number of bits set as that of N. (When a bit is 1, we say it is set) 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: Use concepts of bit manipulation. Hit again for hints. Hints: Try to find out general formula for number having same number of set bits. Hit again for solution Solution: Suppose N has last x bits 0 and then y bits 1, then in general the next number having same number of set bits is given by N + 2^(y-1) + 2^x - 1 -> Now 2^x is given by N&-N -> Suppose M = N + 2^x -> Similarly 2^(x+y) is given by M&-M -> So we get 2^(y-1) by (2^(x+y)/2^x >> 1) Complexity : Time : O(1) Space : O(1) Code : int next_equal_setbits(int N){ int K1 = N & -N; int M = N + K1; int K2 = M & -M; return K2 + ((K2/K1)>>1) - 1; }

Given a array of characters of size N. Devise an algorithm to generate all possible permutations of given size K (K <= N). 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: Find all the combinations first [:)]. I hope this was obvious. [:P] Hit again for hints. Hints: list the combinations using recursive procedure by selecting or not selecting characters until K length has been formed. Hit again for solution. Solution: We first list the combinations using recursive procedure by selecting or not selecting characters until K length has been formed. Then for each combination we permute them using another recursive procedure Complexity : Time : O(N!) Space : O(N!) when storing results; O(1) if directly output the result Code : void swap (char *x, char *y) { char temp; temp = *x; *x = *y; *y = temp; } void select(char *input, int start, int N, char *selection, int length, int K, stack<string> &combinations){ if(start <= N){ if(length == K){ selection[length] = '\0'; combinations.push(string(selection)); } else { select(input, start + 1, N, selection, length, K, combinations); selection[length] = input[start]; select(input, start + 1, N, selection, length + 1, K, combinations); } } } void permute(char *input, int index, int N, stack<string> &permutations) { if (index == N) permutations.push(string(input)); else { for (int i = index; i < N; i++) { swap(input + index, input + i); permute(input, index + 1, N, permutations); swap(input + index, input + i); } } } void all_permutations(char *input, int K, stack<string> &permutations){ int N = strlen(input); stack<string> combinations; char *selection = new char[K+1]; char *temp = new char[K+1]; select(input, 0, N, selection, 0, K, combinations); while(!combinations.empty()){ strcpy(temp, combinations.top().c_str()); permute(temp, 0, K, permutations); combinations.pop(); } }

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;
}