CareerCup

I also thought the same O(NlogN)

void arrange(int a[],int n)
{
     int i=n-1,zero=n-1;
     for(;i>=0;)
     
     {
         if(a[i]==0)
          {
                i--;
     
          }
           else
            {
                  int t=a[i];
                  a[i]=0;
                  a[zero]=t;
                  zero--;
                  i--;
                  
            }
     }
}

void arrange(int a[],int n)
{
     int i=n-1,zero=n-1;
     for(;i>=0;)
     
     {
         if(a[i]==0)
          {
                i--;
     
          }
           else
            {
                  int t=a[i];
                  a[i]=0;
                  a[zero]=t;
                  zero--;
                  i--;
                  
            }
     }
}

try for 5

5
        4                         3
   3        2                2        1
2      1

there are 5 leaf nodes
but the answer will be 8
here is the sanpshot of my output for 5


1 1 1 1 1
1 1 1 2
1 1 2 1
1 2 1 1
1 2 2
2 1 1 1
2 1 2
2 2 1
Number of Paths :8Press any key to continue . . .

if i m missing something

array given in the question is wrong
correct one is
4 5 10 7 12 13
o/p:
1 3 4 9

here is the recursive code

#include <cstdlib>
#include <iostream>

using namespace std;


/* Function to swap values at two pointers */
void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void permute(char *a, int i, int n)
{
   int j;
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
            
                 if (a[i] == a[j] && i != j)
                continue;

          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //backtrack
       }
   }
} 


int main(int argc, char *argv[])
{
    
    char a[] = "ABC";
    permute(a, 0, 2);
    system("PAUSE");
    return EXIT_SUCCESS;
}

node CA(Node root,int key[])
   {
     if(root==null)
     return null;
     int i ;
     for(i=0;i<key.length;i++)
     {
       if(!contain(root.left,key[i])
        break;
     }
     if(i==key.length)
     return CA(root.left,key);

     int j ;
     for(j=0;j<key.length;j++)
     {
       if(!contain(root.right,key[j])
        break;
     }
     if(j==key.length)
     return CA(root.right,key);

     return node;
}

boolean contain(Node root,int key)
{
   if(root==null)
    return false;
   if(root.data==key)
    return true;
   return (contain(root.left,key)||contain(root.right,key));
}

suppose the tree is

1
    2     4
  3   5

5 is the right child of 2
now keys are 3 , 4 ,5

a/c to ur solution min is 3 and max is 5 so the CA should be 2
but CA should be 1

m i missing something

void mirror(TreeNode root)
{
if(root==null)
return;
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
mirror(root.left);
mirror(root.right);
}

here is the solution which prints number of paths as well as each path.
at every step we have to choices either take 1 step or take 2 step.

#include <cstdlib>
#include <iostream>

using namespace std;

int path(int a[],int index,int sum,int n)
{
     static int count=0;
     if(sum==n)
     {
          cout<<"\n";
          for(int i=0;i<index;i++)
          cout<<a[i]<<" ";     
          count++;
          return 0;
     }
     if(sum>n)
     return 0;
     for(int i=1;i<=2;i++)
     {
             a[index]=i;
             path(a,index+1,sum+i,n);
     }
     return count;
}      
     
int main(int argc, char *argv[])
{
    int n=8;
    int *a=new int[n];
    cout<<"\nNumber of Paths :"<<path(a,0,0,n);
    free(a);
    system("PAUSE");
    return EXIT_SUCCESS;
}

I write this in java

public class Main {

    
    static int sets [][]={{1,2},{3,4},{5,6,7}};
    static int count=0;
    
    public static void main(String[] args) 
    {
        // TODO code application logic here
        int a[]=new int[sets.length];
        crossProduct(a,0, sets.length);
        System.out.print("\n\nTotal Products "+count);
    }

    static void crossProduct(int[]a,int index,int n)
    {
        if(index==n)
        {
            System.out.print("\n");
            count++;
            for(int i=0;i<a.length;i++)
                System.out.print(a[i]+" ");
            return;
        }
        for(int j=0;j<sets[index].length;j++)
        {
            a[index]=sets[index][j];
            crossProduct(a,index+1,n);
        }
    }
}

we can modify the binary search

int find(int a[],int n)
{
 int low=0,up=n;
 int mid;
 while(low<=up)
 {
   mid=(up+low)/2;
   if(a[mid]>a[mid-1]&&a[mid]>a[mid+1])
      return a[mid];
   else if(a[mid]>a[mid-1]&&a[mid]<a[mid+1])
   low=mid+1;
   else if(a[mid]<a[mid-1]&&a[mid]>a[mid+1])
   up=mid-1;

 }
 
}

what about the following input.
51 ,517 answer should be 51751 (517+51)
56,563 answer should be 56563 (56+563)
how the radix will work here .

void encrypt(char str[])
{
     char h=find(str);
     cout<<"highst occuring character is "<<h<<"\n";
     int dif='e'-h;
    
     for(int i=0;i<strlen(str);i++)
     {
           int d=str[i]-97+dif;
           if(d<=0)
           str[i]=(d+26)%26+97;  
           if(d>0)
           str[i]=d%26+97;
           cout<<d;
     }
}

char find(char str[])
{
     int a[26]={0};
     for(int i=0;i<strlen(str);i++)
     a[str[i]-97]++;
     int max=a[0];
     int maxi=0;
     for(int i=1;i<26;i++)
     if(max<a[i])
     {
       max=a[i];
       maxi=i;
     }
     return maxi+97;
}

in this questions i would like to ask the interviewer about the type of keys and values and what operations are required.
then i will suggest the data structure.

in this questions i would like to ask the interviewer about the type of keys and values and what operations are required.
then i will suggest the data structure.

here is the code
logic is
1: traverse the array
2:if found 1 do nothing
2: if found 0 , swap it with 1 ( on left side)
3: if found 2 swap it with last. decrement last.

void swap(int a[],int first,int second)
{
int temp;
temp=a[first];
a[first]=a[second];
a[second]=temp;
}
void arrange(int a[],int size)
{
   int zero=0,one=0,two=size-1;
   while(one<=two)
   {
     switch(a[one])
      {
        case 0:
        swap(a,zero,one);
        zero++;
        one++;
        break;
        case 1:
        one++;
        break;
        case 2:
        swap(a,one,two);
        two--;
        break;

      }
   }
}

here is the solution using backtracking
1: fix the 1st character and swap the others
and so on

/* Function to swap values at two pointers */
void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void permute(char *a, int i, int n)
{
   int j;
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
            
                 if (a[i] == a[j] && i != j)// take care of duplicate characters
                continue;

          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //backtrack
       }
   }
}

see the code carefully , it is easy to understand.

B++ tree is best data structure for range queries , since values are stored in leaves only in sorted fashion.And each leave has pointer to next leaf node(with higher value). so accessing is also efficient.

here is the correct code , i just forget to include the print statemnt

printNodes(Node root,int m,int n)
{
    if(root==null)
     return;
    if(root.data>=m&&root.data<=n)
    print(root.data);
    if(m<root.data)
    printNode(root.left,m,n);
    if(n>root.data)
    printNode(root.right,m,n);
}

code for permutation using backtracking

void permute(char *a, int i, int n)
{
   int j;
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
            
                 if (a[i] == a[j] && i != j)
                continue;

          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //backtrack
       }
   }
}

here is the code

printNodes(Node root,int m,int n)
{
    if(root==null)
     return;
    if(n<root.data)
    printNode(root.left,m,n);
    if(m>root.data)
    printNode(root.right,m,n);
}

we cant do this because of main memory constraint

we have to just count the number of 1's (set bits) at even position and number of 1's (set bits) at odd position .

if((number of 1's at even position - number of 1's at odd position)%3==0)
then number is divisible by 3.

make a prefix tree
each leaf will have the corresponding character
for 2 =a
22 =b
222 =c
make a trie of 2, 22 ,222
and so on make trie of 3,33,333 .... 9,99,999

onc we made trie , we can easily decode the given sequence.

your approach is correct . but i dont think that interviewer want this approach, i mean it straight forward.

the program will definitely compile, but the behaviour is undefined. why here is the reason.

declaration int a[10] // it allocates 40 bytes and suppose 1000 is the starting address.
a[-1]=10 // access memory location 996 and put 10 at this location.
but we are not sure whether 996 memory location is read only ,part of stack, part of code segment.
if it is read only,part of stack or part of code segment, then surely we will get error like segmentation fault or access violation.

there is no memory leak, we will get memory access violation and sometime segmentation fault. so overall result will e unpredicatble.

nice approach

take three pointers one, two and three.
first of all search for a 1 and move( delete from current) it to head (if 1 is already at head then omit this step)
now traverse the list starting from 2nd node
if found 1 delete it and move it to the head (update the head also)
if found 2 dont do anything just move to nect node.
if found 3 move it to last .

dude
you should read the pointers first and then try with linkedlist because they require knowledge of pointers.

this approach will give a palendrom but not the next palendrom
for Ex 103 when we increment left till it become equal to right. it becomes 303
bot ans should be 111

yes trie will cost a lot of space I just given an approach.

we can use trie
make a trie of the strings of 1st array
now traverse the 2nd array and check whether string is present it trie or not.

but i think hashing will be better option.

oh sorry right
for 301, next palindrome is 303, not 313.
thanks anon

use a set
put the product ids starting with b
set doesnt allows duplicate elements

we have to fine the time interval in which all members are free
for ex 1 M1 - 8-11
m2 - 12-15
m3 - 15-18 office time is 8 to 18
have an array consisting elements 8 9 10 11 12 13 14 15 16 17 (not 18)
and now cross the hours in which any of the member is busy
here m1 8 - 11 so cross out 8 9 10 (not 11 bcoz he is free from 11)
m2 12 -15 so cross out 12 13 14 (not 15)
m3 15 - 18 so cross out 15 16 17

now find n consecutive hours which are not crossed here 11 is not crossed so we can schedule the meeting from 11 to 12

i have not done exhausted testing please check it out.

this is similar rat in maze problem . the only difference is that we have to find all the paths and find cast of the path . choose the path having minimum cast .

@ eugene.yarovoi

yeh your approach is similar to rat in maze .
in both approaches we have have to traverse recursively something like

path(i,j+1)
path(i-1,j-1)
path(i-1,j)

the reason is explained above

@ eugene.yarovoi
that is the side effects of macros we must take care of side effects of macros
any way it is correct

it should be char* sorry for mistake

@anonymous char* is necessary
becoz see here

int *p; // suppose p points to 100th memory location

when we do something like
(p+1)-(p)//(104-100)
but this expression will not give 4 but it give 1
becoz p is a pointer to an integer and such expressions tells how many elements are there in between (p+1) and p

when we typecast
char*(p+1)-(char*)p pointer p is converted in char*
(104)-(100) which is equals to 4 which is the size of int

hope that it is now clear to you dear.

use back tracking
for ex string ABC
first
keep A (first letter constant) and chane others
ABC cange 2n letter
ACB
change the first letter
BAC
BCA

and so on

here is the code

/* Function to swap values at two pointers */
void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void permute(char *a, int i, int n)
{
   int j;
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
            
                 if (a[i] == a[j] && i != j)
                continue;

          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //backtrack
       }
   }

@ Anonymous

at least check your approach with 1 or 2 examples before posting here.

Totally absurd and wrong.

@ varun
i think it is wrong it will always give 1.
it should be
#define sizeof(data)
{data *p=0; size = (char)(p+1) - (char)p }

although the solution posted by puneet (nicely explained by olnrao) is correct.
but getting unique elements requires extra space if using hashing or O(nlogn) if sort and then find unique elemnts.

solution with O(N) time complexity with constant space seems not possible any thoughts

I dont think the solution is correct
consider the matrix
1 5 9 12
6 12 16 18
7 16 17 20
8 18 20 25

answer should be 16
but with this approach it is 17

for hexadecimals need special care

do like this
have a loop
int sum=0

iterate
sum=sum*base+str[i]-'0';

where base is the given base

wrong solution , it is correct for only ur input

consider this
{1,2,4,3,4,3,3,5}

unique elements are 1,2,3,4,5
answer should be 4
but with ur solution it is 1 (the XOR of 1,2,3,4,5 is 1)