C,C++/JAVA/BASH/ASM ARENA

वह प्रदीप जो दीख रहा है झिलमिल दूर नही है थक कर बैठ गये क्या भाई मन्जिल दूर नही है चिन्गारी बन गयी लहू की बून्द गिरी जो पग से चमक रहे पीछे मुड देखो चरण-चिनह जगमग से बाकी होश तभी तक, जब तक जलता तूर नही है थक कर बैठ गये क्या भाई मन्जिल दूर नही है अपनी हड्डी की मशाल से हृदय चीरते तम का, सारी रात चले तुम दुख झेलते कुलिश का। एक खेय है शेष, किसी विध पार उसे कर जाओ; वह देखो, उस पार चमकता है मन्दिर प्रियतम का। आकर इतना पास फिरे, वह सच्चा शूर नहीं है; थककर बैठ गये क्या भाई! मंज़िल दूर नहीं है। दिशा दीप्त हो उठी प्राप्त कर पुण्य-प्रकाश तुम्हारा, लिखा जा चुका अनल-अक्षरों में इतिहास तुम्हारा। जिस मिट्टी ने लहू पिया, वह फूल खिलाएगी ही, अम्बर पर घन बन छाएगा ही उच्छ्वास तुम्हारा। और अधिक ले जाँच, देवता इतन क्रूर नहीं है। थककर बैठ गये क्या भाई! मंज़िल दूर नहीं है।

Adobe Written Test Questions October 27, 2013

Today Adobe took written test for C++ development(1-3 Yrs) @Bangalore on 27th Oct 2013. This was taken  by Elitmus.The test consisted of 8 C++ questions(Objective) and 2 Algo/Ds questions. I am posting my approach of Algo/DS questions.
C++ questions were mostly of OOPS type e.g classes, constructor, inheritance, public, private, protected concepts. Some programs were given in c++ and we needed to identify the problem/aim and choose correct option. As i don’t remember those questions, i am not posting those.

Question1 – Ideone Link

Question2 – Ideone Link

Update

Ooops a friend suggested these questions were exactly from geeksforgeeks

Question1

Question2


/*Adobe Elitmus Written Test on 27-10-2013  @Bangalore - Algo/DS questions
 *Question 1
 */

/* Reverse every alterante K elements of a list
 * It is to be noted that Nodes have to reversed and not the values
 * e.g. if k=3 and list is
 * Input 1->2->3->4->5->6->7->8->9->NULL
 * Output 3->2->1->4->5->6->9->8->7->NULL
 *
*/

#include<stdio.h>
#include<stdlib.h>

typedef struct SLL{
	int element;
	struct SLL *next;
}Node;

Node *start=NULL;

void InsertNode(Node *start, int item)
{
	Node *tmp=start;

	if(tmp == NULL)
	{
		printf("Error : Start pointer is NUll\n");
		return;
	}

	//construct a node with item element
	Node *node=malloc(sizeof(Node));
	node->next=NULL;
	node->element=item;

	while(tmp->next !=NULL) tmp=tmp->next;

	tmp->next=node; //node inerted at end
}

void PrintListElements(Node *start)
{
	Node *tmp=start;

	while(tmp != NULL)
	{
		printf("%d->",tmp->element);
		tmp=tmp->next;
	}
		printf("NULL\n");
}

void ReverseAlternateKElements(Node *start, int K, Node **startPointer)
{
	int i,j,count;
	Node *current=start;
	Node *prev=NULL,*prev2=NULL;
	Node *save=NULL;
	Node *next=NULL;
	Node *tmp=NULL;

	for(i=0;;)
	{
		if(current == NULL) break;
		if(i%K==0)
		{
			count=0;
			save=current;
			//printf("current=%d\n",current->element);
			for(j=0;j<K;)
			{
				if(current == NULL) break;
				next=current->next;
				current->next=prev;
				prev=current;
				current=next;
				j++;
				++count;
			}
			if(i<K)
			{
				*startPointer=prev;
				tmp=prev;
			}
			save->next=current; // for last node of the series to point to next current;

			if(prev2 != NULL)
				prev2->next=prev;
			if(current == NULL) break;
			//PrintListElements(tmp);
			i=i+count+1;

		}
		else
		{

			current = current->next;
			if(current == NULL) break;
			i++;
			if(i%K==0)
			{
				prev=current;
				prev2=current;
				current=current->next;
			}
		}
	}

	printf("----Reversal Done!!! :)\n");
	//PrintListElements(tmp);

}

int main()
{
	int K=4; //Input
	start=malloc(sizeof(Node));

	start->next=NULL;
	start->element=1; // Inputs
	InsertNode(start,2); //Inputs .....
	InsertNode(start,3);
	InsertNode(start,4);
	InsertNode(start,5);
	InsertNode(start,6);
	InsertNode(start,7);
	InsertNode(start,8);
	InsertNode(start,9);
	InsertNode(start,10);
	InsertNode(start,11);
	InsertNode(start,12);
	InsertNode(start,13);
	InsertNode(start,14);

	printf("Element Before Reversal:\n");
	PrintListElements(start);

	ReverseAlternateKElements(start, K, &start);

	printf("Element After Reversal:\n");
	PrintListElements(start);

	return 0;
}

 

/*Adobe Elitmus Written Test on 27-10-2013  @Bangalore - Algo/DS questions
 *Question 2
 */

/*
 * In a given set of elements(any order), find  K largest numbers
 * e.g arr[]={1,4,5,108,10,14,90,43,100} let K=3
 * Ouput = {108,100,90}
 */

/*Approach: Modified Bubble Sort
 * As we know that bubble sort in Ith pass places the ith largest number at last
 * After Kth pass, the results will be available and no need to sort further
 */

#include<stdio.h>
#include<stdlib.h>

//Its Modified Bubble sort
void FindKLargestNumbers(int arr[], int n, int K, int output[])
{
	int i,j,count,tmp;

	for(i=0;i<n;i++)
	{
		for(j=0;j<n-1;j++)
		{
			if(arr[j]>arr[j+1])
			{
				tmp=arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=tmp;
			}
		}
		if(i==K) break; // K largest numbers are bubbled at top(last indices)
	}

	count=0;
	for(i=n-1;i>=n-K;i--)
	{
		output[count++]=arr[i];
	}

}

void PrintKLargestNuners(int output[] ,int K)
{
	int i;

	printf("The K=%d largest numbers in the given array are\n",K);
	for(i=0;i<K;i++)
	{
		printf("%d ",output[i]);
	}
	printf("\n");
}

int main()
{
	int n=9;//no of elements in the array
	int K=3;//largest K numbers
	int arr[9]={1,4,5,108,10,14,90,43,100};
	int output[3];//output array

	FindKLargestNumbers(arr,n,K,output);

	PrintKLargestNuners(output,K);

	return 0;
}

 

Interview question – Linked list June 1, 2011

Filed under: Algo & Data Structure,Interview Questions — whoami @ 08:44

/*
Given a linked list of the form, 1->2->3->4->5->6, convert it into the form 2->1->4->3->6->5.
Note that the nodes need to be altered and not the data contained in them;

*/

#include<stdio.h>
#include<malloc.h>

struct node{
 int a;
 struct node *next;
}*start=NULL;

void add(int item)
{
  struct node *tmp=(struct node *)malloc(sizeof(struct node));
  struct node *tmp2;
  tmp->a=item;
  tmp->next=NULL;

  tmp2=start;
  if(tmp2!=NULL)
  {
  while(tmp2->next!=NULL) tmp2=tmp2->next;

    tmp2->next=tmp;
  }
  else
   start=tmp;

}

void display()
{
  struct node *tmp=start;
  while(tmp!=NULL){
    printf("%d ",tmp->a);
    tmp=tmp->next;
  }
}

void reverse()
{
  struct node *tmp=start;
  struct node *tmp2=start->next;
  struct node *tmp3=tmp2;
  if(start->next==NULL) return;
  tmp->next=NULL;
  while(tmp2!=NULL)
  {
    tmp3=tmp2->next;
    tmp2->next=tmp;
    tmp=tmp2;
    tmp2=tmp3;
  }
   start=tmp;

}

void swap()
{
   struct node *tmp=start;
   struct node *tmp2=tmp->next,*tmp3,*save;
   if(tmp2==NULL) return;

   if(tmp2->next==NULL)
   {
      tmp3=tmp;
      tmp->next=tmp2->next;
      tmp2->next=tmp;
      start=tmp2;
      return ;
   }

   if(tmp2->next->next==NULL)
   {
      tmp3=tmp2->next;
      tmp->next=tmp3;
      tmp2->next=tmp;
      start=tmp2;
      return ;
    }

   tmp3=tmp2->next;
   tmp2->next=tmp;
   tmp->next=tmp3->next;
   start=tmp2;
   tmp=tmp3;
   tmp2=tmp->next;
   while(1)
   {
     if(tmp2==NULL||tmp2->next==NULL||tmp2->next->next==NULL) break;
     tmp3=tmp2->next;
     if(tmp==NULL||tmp3->next==NULL) break;
     tmp2->next=tmp;
     tmp->next=tmp3->next;

     tmp=tmp3;

     tmp2=tmp->next;

   }

   if(tmp!=NULL&&tmp2!=NULL)
   {
     if(tmp2->next==NULL)
     {
      tmp2->next=tmp;
      tmp->next=NULL;

     }
     else if(tmp2!=NULL)
     {

       save=tmp2->next;
       tmp2->next=tmp;
       tmp->next=save;

     }
   }

}

int main()
{
  int item;
  printf("enter the item one by one\nenter -1 to stop\n");
  while(1)
  {

     item;

     scanf("%d",&item);
     if(item==-1) break;
     add(item);
  }
  printf("\nThe single linked list is\n");
  display();
  reverse();
  printf("\nThe reversed linked list is\n");
  display();
  printf("\nThe single linked list is\n");
  reverse();
  display();
  printf("\nThe swapped(only 2 adjacent elements) linked list is\n");
  printf("\nGiven a linked list of the form, 1->2->3->4->5->6, convert it into the form 2->1->4->3->6->5. Note that the nodes need to be altered and not the data contained in them.\n\n");
  swap();
  display();

return 0;
}

 

Majority Element Problem April 16, 2010

Majority element problem: – Here we need to find the element from the array of size with occurence>n/2.

1.The algorithm is simple to learn
2.Its complexity is O(n)
Read

 

Proving running times -Algorithms February 12, 2010

Filed under: Algo & Data Structure — whoami @ 22:18
Tags:

(more…)

 

TJU 1138. Binomial Showdown January 26, 2010

TJU 1138. Binomial Showdown
-AC–

#include<iostream>
#include<stdlib.h>

using namespace std;

class A{
   long long int i,j,k,N,K,tmp;
  public:
    void input(){
         cin>>N>>K;
         
         if(N==0&&K==0) exit(0);
    }
    void calc(){
       i=N-K;
       if(N==K||K==0) {tmp=1;}
       else if(K==1){tmp=N;}
       else  if(i>K)
       {
          j=1;
          tmp=1;
          
          while(j<=K)
          {
            if(N%j==0)
            tmp=tmp*(N/j);
            else if(tmp%j==0)
             tmp=N*(tmp/j);
            else tmp=(N*tmp)/j;
             
            j++;
            N--;
         
          }
        }
        else if(i<=K)
        {       
           j=1;
           tmp=1;
          while(j<=i)
          {
            if(N%j==0)
            tmp=tmp*(N/j);
            else if(tmp%j==0)
            tmp=N*(tmp/j);
            else tmp=(N*tmp)/j;
            j++;
            N--;
           }
         }
       }
      void output(){
         cout<<tmp<<endl;
      }
};

int main()
{
  A a;
 
  while(1){
    a.input();
    a.calc();
    a.output();
  }

return 0;
}


 

RAM model of computation

Filed under: Algo & Data Structure — whoami @ 12:10
Tags:

RAM (here Random Access Machine) model of compuation is an abstract model in which we try to analyze the working of our ALGORITHMS . Thought this model is different from real computers, it is helpful in many way.

LINK

 

SPOJ 1025. Fashion Shows December 8, 2009

SPOJ 1025. Fashion Shows
Problem code: FASHION

–AC–
sorting based problem(qsort implemnted)