Saturday 12 March 2016

interview preparation

Recursion

sort a stack using recursion

Given a stack, sort it using recursion. Use of any loop constructs like while, for..etc is not allowed. We can only use the following ADT functions on Stack S:

is_empty(S)  : Tests whether stack is empty or not.
push(S)     : Adds new element to the stack.
pop(S)     : Removes top element from the stack.
top(S)     : Returns value of the top element. Note that this
               function does not remove element from the stack.
Example:

Input:  -3  <--- Top
        14 
        18 
        -5 
        30 

Output: 30  <--- Top
        18 
        14 
        -3 
        -5

below the code of you to perform it

1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
#ifndef M
#define M 1000000007
#endif
typedef pair<int,int>pp;
typedef std::vector<pp> vpp;
typedef long long ll;
#ifndef pb
#define pb push_back 
#endif 
int min(int x,int y){return(x<y)?x:y;}
int max(int x,int y){return(x>y)?x:y;}
void sorted(stack<int> *s)
{
 int f=s->top();
 s->pop();
 if(s->empty())
 {
  s->push(f);
  return;
 }
 if(s->top()>f)
 {
  int x=s->top();
  s->pop();
  s->push(f);
  sorted(s);
  s->push(x);
 }
 else
 {
  sorted(s);
  s->push(f);
 }
}
int main(int argc, char const *argv[])
{
 int n,x;
 scanf("%d",&n);
 stack<int> s;
 for(int i=0;i<n;i++)
 {
  scanf("%d",&x);
  s.push(x);
 }
 sorted(&s);
 while(!s.empty())
 {
  printf("%d\n",s.top());
  s.pop();
 }
 return 0;
}

Print all non-increasing sequences of sum equal to a given number x

Given a number x, print all possible non-increasing sequences with sum equals to x.

Examples:

Input: x = 3
Output: 1 1 1
        2 1
        3

Input: x = 4
Output: 1 1 1 1
        2 1 1
        2 2
        3 1
        4



1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
#ifndef M
#define M 1000000007
#endif
typedef pair<int,int>pp;
typedef std::vector<pp> vpp;
typedef long long ll;
#ifndef pb
#define pb push_back 
#endif 
int min(int x,int y){return(x<y)?x:y;}
int max(int x,int y){return(x>y)?x:y;}
int a[100]={0};
void print(int *a,int index)
{
 for(int i=0;i<=index;i++)
  printf("%d ",a[i] );
 printf("\n");
}
void recurse(int x,int n,int *a,int index)
{
 if(x<=n && x!=0)
 {
  a[index]=x;
  if(x==n)
   print(a,index);
  recurse(x,n-x,a,index+1);
  recurse(x-1,n-x,a,index+1);
 }

}
int main(int argc, char const *argv[])
{
 int n;
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
  recurse(i,n,a,0);
 return 0;
}

Print a pattern without using any loop

Given a number n, print following pattern without using any loop.

Input: n = 16
Output: 16, 11, 6, 1, -4, 1, 6, 11, 16

Input: n = 10
Output: 10, 5, 0, 5, 10
We basically first reduce 5 one by one until we reach a negative or 0. After we reach 0 or negative, we one one add 5 until we reach n.


1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
#ifndef M
#define M 1000000007
#endif
typedef pair<int,int>pp;
typedef std::vector<pp> vpp;
typedef long long ll;
#ifndef pb
#define pb push_back 
#endif 
int min(int x,int y){return(x<y)?x:y;}
int max(int x,int y){return(x>y)?x:y;}
int a[100]={0};
void print(int *a,int index)
{
 for(int i=0;i<=index;i++)
  printf("%d ",a[i] );
 printf("\n");
}
void recurse(int x,int n,int flag)
{
 if(x>=n && flag==0)
  flag=1;
 if(x<=0 && flag==1)
  flag=0;
 if(flag)
 {
  printf("%d,",x-5 );
  if(x-5!=n)
  recurse(x-5,n,flag);
 }
 else
 {
  printf("%d,",x+5 );
  if(x+5!=n)
  recurse(x+5,n,flag);
 }
}
int main(int argc, char const *argv[])
{
 int n;
 scanf("%d",&n);
 printf("%d,", n);
 recurse(n,n,0);
 printf("\n");
 return 0;
}

Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)