Programming Geek
Rated 4.1/5 based on 446 reviews

Evernote Coding Challenge : Problem#2

This is the second problem of Evernote Coding Challenge powered by Interview street.

Frequency Counting of Words / Top N words in a document.
Given N terms, your task is to find the k most frequent terms from given N terms.

Input format

First line of input contains N, denoting the number of terms to add.
In each of the next N lines, each contains a term.
Next line contains k, most frequent terms.

Output format

Print the k most frequent terms in descending order of their frequency. If two terms have same frequency print them in lexicographical order.

Sample input

14
Fee
Fi
Fo
Fum
Fee
Fo
Fee
Fee
Fo
Fi
Fi
Fo
Fum
Fee
3

Sample output

Fee
Fo
Fi

Constraint

0 < N < 300000
0 < term length < 25.

Algorithm : 

Step 1: read n
Step 2: for i=0 to n do step3
Step 3: if ith term is already in hash map then
                        increment the value of value by 1.
            else
                        put an entry in hash map, key as ith term and value as 1.

 Step 4: create a list from hash map and sort the list based on values.
Step 5: Display k most frequent terms in descending order of the frequency as the list is now sorted.


Here goes the program for the same :


import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

/**
 *
 * @author VIK
 */
public class Solution {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine().trim());
        int k = 0;
        TreeMap<String, Integer> tm = new TreeMap<String, Integer>();
        for (int i = 0; i < n; i++) {
            String s = sc.nextLine();
            if (tm.containsKey(s)) {
                tm.put(s, tm.get(s) + 1);
            } else {
                tm.put(s, 1);

            }
        }
        k = Integer.parseInt(sc.nextLine().trim());
         
        ArrayList ls = new ArrayList(tm.entrySet());
        Collections.sort(ls, new Compare());
        Iterator iterator = ls.iterator();
        while (iterator.hasNext() && k > 0) {

            Map.Entry e = (Map.Entry) iterator.next();
            if (k != 1) {
                System.out.println(e.getKey());
            } else {
                System.out.print(e.getKey());
            }
            k--;
        }
        
    }

    static class Compare implements Comparator {

        @Override
        public int compare(Object o1, Object o2) {
            int result = 0;
            Map.Entry e1 = (Map.Entry) o1;
            Map.Entry e2 = (Map.Entry) o2;
            int val1 = (Integer) e1.getValue();
            int val2 = (Integer) e2.getValue();
            if(val1==val2)
                return ((String)e1.getKey()).compareToIgnoreCase((String)e2.getKey());
            return val2 - val1;

        }
    }
}

Evernnote Coding Challenge

Recently I took Evernote coding challenge powered by Interviewstreet. Here goes one of the problem of the contest.

Given a list of integers, your task is to write a program to output an integer-valued list of equal length such that the output element at index 'i' is the product of all input elements except for the input element at 'i'.
In other words, let inputArray by an integer array of length 'n'. The solution,computed into outputArray, would be:
for each j from 1 to n-2:
outputArr[ j ] = inputArray[0] * inputArray[1] * inputArray[2] * ... * inputArray[j-1] * inputArray[j+1] * inputArray[j+2] *...* inputArray[n-1]
for j = 0
outputArray[0] = inputArray[1] * outputArray[2] * ... * outputArray[n-1]
for j = n-1
outputArray[n-1] = outputArray[0] * outputArray[1] * outputArray[2] * ... * outputArray[n-2]
As an example, if inputArray = { 1, 2, 3, 4 }, then
outputArray = { 2*3*4, 1*3*4, 1*2*4, 1*2*3 }.
Your program should run in O(n) time and should be space efficient.

Input format

First line of input contains N , number of elements in list.
Next N lines will each contain an element (a signed integer)

Output format

Print the output list of numbers.

Sample input

4
5
2
2
3

Sample output

12
30
30
20

Constraint

You may assume that:
  • The input array size will always have at least two elements in it, that is, n >= 2.
  • The product of any subset of the input will never exceed the value of a 64 bit integer.
  • The maximum length of input array is 1000.
My Solution for this problem:
import java.util.Scanner;

/**
*
* @author VIK
*/
public class Solution {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = n=sc.nextInt();;
		int flag=0;
		int[] arr = new int[n];
		long mul = 1;
		for (int i = 0; i < arr.length; i++) {
			
			arr[i] = sc.nextInt();
			if(arr[i]==0)
			flag++;
			if(arr[i]!=0)
			mul *= arr[i];
		}
		for (int i = 0; i < arr.length; i++) {
			
			if(flag >0)
			
			if(arr[i]==0)
			if(flag>1)
			System.out.println(0);
			else
			System.out.println(mul);
			else
			System.out.println(0);
			else
			System.out.println(mul/arr[i]);
		}
		
	}
}


CodeVita : A Programming Contest by TCS

CodeVita 2014





TCS has announced the third edition of its programming contest CodeVita. This programming contest was started in 2012. Only final year students were eligible to participate then. In its second edition in 2013, following changes were made:

1. Participation in a team of 2 unlike teams of three in 2012.
2. Addition of new languages Perl, Python and Ruby.
3. Second Year, third Year and final year students were allowed to participate whereas only final year students were allowed to participate in its very first edition in 2012.


The second edition of CodeVita witnessed registration of about 1.3 Lakhs students and participation of around 51000 teams of two members in first round.

The third edition i.e. CodeVita 2014 has gone global. So here is your chance to compete with the students across the globe.  The contest schedule has been announced, so gear yourself to showcase your programming skills to solve real world problems.



It is a team contest. Each contestant needs to register for CodeVita on Campus Commune Portal. This is a 3 round contests and team must be formed in order to participate. 6 programming language ( C, Java, C#, C++, Python, Ruby and Perl ) was allowed in last year contest. You will be able to participate in round 1 and round 2 at home by visiting https://tcscodevita.com/ . Students passing in year 2015, 2016, 2017 and 2018 can participate in this contest in India.

This is a great opportunity for students to showcase their programming skills and grab awesome goodies & various opportunities to work at TCS.


Register yourself on TCS Next Step portal to participate in CodeVita 2014. On the day of contest you will be able to participate by visiting https://tcscodevita.com .

The previous year questions with solution can be found on this website and more will be updated soon. Till then stay connected.
Like us on Facebook & Google+  and stay updated with latest stuffs.


Past Contest

Codevita 2013



CodeVita
is a programming contest organised by TCS. This year TCS has announced the schedule of CodeVita 2013. Any student from science and engineering background can participate in this contest. Last year CodeVita was organized for 2013 batch so I could not participate. But this year student of any year can participate. The contest comprises of four phase.

First Phase : In first phase, participant can register on https://nextstep.tcs.com and form the team.

Second Phase : In second phase (round 1) , there will be an online programming contest. The top 300 or 5% of the participants will move to next round.

Third Phase : This is second round and teams qualifying from round 1 can participate in this round. Each team will be provided a set of questions and top 10 teams will be selected for the next round.

Fourth Phase : This is the final round and will be held at one of the office of TCS.





Registration for CodeVita 2013 begins on 22 July 2013 and ends on 10 August 2013. So what are you looking for. Here is your chance to show your algorithmic skill and win awesome goodies. I am participating for first time. Hope I can perform well in the contest.

Have query? Do leave a comment below ... 

Quicksort : Different Strategy to Improve Complexity

Quicksort is a sorting algorithm used to sort a number of element. It has an average case complexity O(nlogn) and worst case complexity O(n^2). It does not use extra memory like merge sort. The complexity depends on the number of comparison of elements. Here we discuss the ways to reduce number of comparison thereby reducing complexity.

There are two procedure quicksort and partition. Partition procedure chooses a pivot and partition the elements in two half, first half having elements lower than pivot element and other half having elements greater than pivot element. Again recursively sort the two halves. The number of comparison depends upon the pivot element. The different strategy employed to reduce the number of comparison are as follows :

First : Always Choose the first element of the list as pivot and recursively sort the array.

Second: Choose last element of the list as pivot and recursively sort the array.

Third : Select median of three elements i. e. median of first element, last element and middle element as the pivot. Let the list be 5, 8,1,6,9,12. The three elements are (5,1,12) and median of these three elements is 5. This slightly increases the work in choosing median but the number of comparisons are less compared to other two approach

 The quicksort algorithm based on these three pivoting rule is implemented below :



#include<stdio.h>

int total=0;

//partition the list(considering first element as pivot)
int partition1(int arr[],int l,int r)
{
 int i=l+1,j=l+1,temp;
 for(j=l+1;j<=r;j++)
 {
  if(arr[l]>arr[j])
  {
   temp=arr[j];
   arr[j]=arr[i];
   arr[i]=temp;
   i++;
  }
  
 }
 temp=arr[l];
 arr[l]=arr[i-1];
 arr[i-1]=temp;
 return i-1;
}

//partition the list (considering last element as pivot)
int partition2(int arr[],int l,int r)
{
 int temp=arr[l];
 arr[l]=arr[r];
 arr[r]=temp;
 return partition1(arr,l,r);
}

//choosing median element as pivot
int choosepivot(int arr[],int l,int r)
{
 int first=arr[l],last=arr[r],mid,midindex;
 if((r-l+1)%2==0)
 midindex=l+(r-l+1)/2-1;
 else
 midindex=l+(r-l+1)/2;
 mid=arr[midindex];
 if((first>mid && first<last) || (first>last &&first<mid))
 return l;
 else if ((mid>first && mid<last)||(mid<first && mid>last))
 return midindex;
 else return r;
}

//partition the list (considering median element as pivot)
int partition3(int arr[], int l, int r)
{ 
 
 int pivot=choosepivot(arr,l,r);
 int temp=arr[l];
 arr[l]=arr[pivot];
 arr[pivot]=temp;
 return partition1(arr,l,r);
 
}

//quicksort1
void quicksort1(int arr[],int l,int r)
{ int m;
 if(r>l)
 {
  m=partition1(arr,l,r);
  total+=m-1-l;
  quicksort1(arr,l,m-1);
  total+=r-m+1;
  quicksort1(arr,m+1,r);
 }
}


//quicksort2
void quicksort2(int arr[],int l,int r)
{ int m;
 if(r>l)
 {
  m=partition2(arr,l,r);
  total+=m-1-l;
  quicksort2(arr,l,m-1);
  total+=r-m+1;
  quicksort2(arr,m+1,r);
 }
}


//quicksort3
void quicksort3(int arr[],int l,int r)
{ int m;
 if(r>l)
 {
  m=partition3(arr,l,r);
  total+=m-1-l;
  quicksort3(arr,l,m-1);
  total+=r-m+1;
  quicksort3(arr,m+1,r);
 }
}

//execution logic
void main()
{
 int i,n,*arr1,*arr2,*arr3,choice;
 printf("Enter No. of elements:");
 scanf("%d",&n);
 printf("\nEnter %d elements:",n);
 arr1=(int*)malloc(sizeof(int)*n);
 arr2=(int*)malloc(sizeof(int)*n);
 arr3=(int*)malloc(sizeof(int)*n);
 for(i=0;i<n;i++)
 {
  scanf("%d",&arr1[i]);
  arr2[i]=arr3[i]=arr1[i];
 }
 total=0;
 quicksort1(arr1,0,n-1);
 printf("\nTotal Comparison Using Quicksort1 : %d",total);
 total=0;
 quicksort2(arr2,0,n-1);
 printf("\nTotal Comparison Using Quicksort2 : %d",total);
 total=0;
 quicksort3(arr3,0,n-1);
 printf("\nTotal Comparison Using Quicksort3 : %d",total);
 
 printf("\n\tSorted Numbers:\n-----------------------------\n");
 for(i=0;i<n;i++)
 printf("%d\t",arr1[i]);
 
}//main



C Program for Different Sorting Algorithm

Here goes a C program which implements the different sorting algorithms like bubble sort, selection sort, insertion sort, merge sort and quick sort.

//Implementation of different sorting algorithms like bubble sort, selection sort, insertion sort, mergesort, quicksort in C
/**
*
*@author VIKASH VIK VIKASHVVERMA
*
*/

#include<stdio.h>

//bubble sort
void bubblesort(int arr[],int n)
{
 int i,j,temp;
 for(i=0;i<n;i++)
 {
  for(j=1;j<n-i;j++)
  {
   if(arr[j-1]>arr[j])
   {
    temp=arr[j];
    arr[j]=arr[j-1];
    arr[j-1]=temp;
   }
  }
 }
}

//selection sort
void selectionsort(int arr[],int n)
{
 int temp,min,i,j;
 
 for(i=0;i<n;i++)
 { min=i;
  for(j=i+1;j<n;j++)
  {
   if(arr[j]<arr[i])
   {
    min=j;
   }
  }

  temp=arr[min];
  arr[min]=arr[i];
  arr[i]=temp;  
 }
}


//insertion sort
void insertionsort(int arr[],int n)
{
 int i,j,temp;
 
 for( i=0;i<n;i++)
 {
  temp=arr[i];
  for(j=i-1;j>=0;j--)
  {
   if(arr[j]>temp)
   {
    arr[j+1]=arr[j];
   }
   else
   break;
  }
  arr[j+1]=temp;
 }
}


//merge 
void merge(int arr[],int l,int m,int r)
{
 int len,i,j,k,*c;
 len=r-l+1;
 c=(int*)malloc(sizeof(int)*len);
 i=0;
 j=l;
 k=m+1;
 while(j<=m && k<=r)
 {
  if(arr[j]<arr[k])
  {
   c[i++]=arr[j++];
   
  }
  else
  {
   c[i++]=arr[k++];
   
  }
  
 }
 
 while(j<=m)
 {
  c[i++]=arr[j++];
 }
 
 while(k<=r)
 {
  c[i++]=arr[k++];
 }
 i=0;
 while(l<=r)
 {
  arr[l++]=c[i++];
 }
}


//mergesort
void mergesort(int arr[],int l,int r)
{
 int m=(l+r)/2;
 if(l<r)
 {
  mergesort(arr,l,m);
  mergesort(arr,m+1,r);
  merge(arr,l,m,r);
 }
}


//partition the list
int partition(int arr[],int l,int r)
{
 int j=l+1,k=r,temp;
 int num=arr[l];
 while(k>=j)
 {
  while(arr[j]<num)
  j++;
  while(arr[k]>num)
  k--;
  
  if(k>j)
  {
   temp=arr[j];
   arr[j]=arr[k];
   arr[k]=temp;
   
  }
 }
 temp=arr[k];
 arr[k]=arr[l];
 arr[l]=temp;
 return k;
}

//quicksort
void quicksort(int arr[],int l,int r)
{ int m;
 if(r>l)
 {
  m=partition(arr,l,r);
  quicksort(arr,l,m-1);
  quicksort(arr,m+1,r);
 }
}

//execution logic
void main()
{
 int i,n,*arr,choice;
 printf("Enter No. of elements:");
 scanf("%d",&n);
 printf("\nEnter %d elements:",n);
 arr=(int*)malloc(sizeof(int)*n);
 for(i=0;i<n;i++)
 scanf("%d",&arr[i]);
 printf("\n\tMenu\n---------------------------");
 printf("\n1 : to apply bubble sort!");
 printf("\n2 : to apply selection sort!");
 printf("\n3 : to apply insertion sort!");
 printf("\n4 : to apply mergesort");
 printf("\n5 : to apply quicksort!");
 printf("\n6 : to apply any sorting algorithm!");
 printf("\nAny other number to exit!");
 printf("\nEnter your choice:");
 scanf("%d",&choice);
 switch(choice)
 {
  case 1: bubblesort(arr,n);
    break;
  case 2: selectionsort(arr,n);
    break;
  case 3: insertionsort(arr,n);
    break;
  case 4: mergesort(arr,0,n-1);
    break;
  case 5: quicksort(arr,0,n-1);
    break;
  case 6: quicksort(arr,0,n-1);
    break;
  default: exit(0);
    
 }
 
 printf("\n\tSorted Numbers:\n-----------------------------\n");
 for(i=0;i<n;i++)
 printf("%d\t",arr[i]);
}//main

MUPHORIA - HIGH ON MATH (Second Edition)

MUPHORIA : Mu Sigma has launched the second edition of MUPHORIA contest. It is basically a programming contest to solve a real world situation. The objective is to develop an algorithm and meet the desired objective. The problem statement can be seen here .
                         



I participated last year in the first edition of this contest and got selected in top five thrice. Hope this time, I can do even better. So guys gear up to solve this problem and win  2 lakhs, each time you win the contest. Though you can win this contest not more than three times. Also you will get a chance of interview with Mu Sigma and if selected than a one time bonus of 3 lakhs on the completion of three months of employment  in Mu Sigma.

Time Period : Contest starts on12:00 AM IST on July 9th and ends on 11:59 PM IST on December 2013.

Elgibility : Any student enrolled in 4/5 year engineering program in India and is in final or pre-final year can participate in this contest.

Prizes : Prizes are worth 12 lakhs. Winner of each month will get a sum of 2 lakhs on the completion of the contest. Also winner will get a chance of interview with Mu Sigma and if selected than can get a one time bonus of 3 lakhs on completion of three months of employment in Mu Sigma.

Further information can be found on  http://www.mu-sigma.com/muphoria/ .

Program for Counting Inversion in an Array

Number of an inversion in array is the number of pair(a[i],a[j]) of elements such that i < j and a[i]  > a[j]. For an example if we have a list of element 2 3 6 9 1 then number of inversion is 4 and the pairs are   (2,1),  (3,1),  (6,1)  and  (9,1).

Algorithms :

Approach 1 : The naive algorithm for this problem is to use two loops and count all the inversion. The complexity of this approach would be O(n^2). Though for small number of input, it runs quickly but for large value of n, it takes much time.


Approach 2 :
                     
                   Divide      :  Divide the array in two parts a[0] to a[n/2] and a[n/2+1] to a[n].
                 
                   Conquer  :  Conquer the sub-problem by solving them recursively.

                  Combine  :  Combine the sub-problem to get the final result.

This algorithm is based on Divide and Conquer paradigm. It is implemented using merge sort. In this approach the time complexity will be O(n log(n)) . Actually in divide step we divide the problem in two parts. And then two parts are solved recursively. The key concept is two count the number of inversion in merge procedure. In merge procedure we pass two sub-list. The element is sorted and inversion is found as follows :

                1) Set count=0,0,i=left,j=mid. C is the sorted list.
                2) Traverse list1 and list2 until mid element  or right element is encountered .
                3) Compare list1[i] and list[j].
                        i) If list1[i]<=list2[j]
                              c[k++]=list1[i++]
                          else
                              c[k++]=list2[j++]
                              count = count + mid-i;
               4) add rest elements of list1 and list2 in c.
               5) copy sorted list c back to original list.
               6) return count.

Key  concept : If an element of list two is greater than an element of list1 than all the remaining element of list1 are greater than this element. That's why we increment count by mid-i. This recursively sort the list and find the number of inversion.

Implementation of naive algorithm :


//count number of inversion using naive approach
/**
*
*@author VIKASH VIK VIKKU VIKASHVVERMA
* 
*/

#include<stdio.h>

int findinversion(int a[],int n)
{
 int i,j,count=0;
 
 for(i=0;i<n;i++)
 {
  for(j=i+1;j<n;j++)
       {
   if(a[i]>a[j])
   count++;
    }
 }
 return count;
}

void main()
{
 int n,*a,i;
 printf("Enter nuber of elements : ");
 scanf("%d",&n);
 printf("Enter %d elements : ",n);
 a=(int*)malloc(sizeof(int)*n);
 for(i=0;i<n;i++)
 scanf("%d",&a[i]);
 printf("Number of inversion = %d",findinversion(a,n));
 
}



Implementation of approach 2 (Divide and Conquer ) :

C implementation :

#include<stdio.h>

int mergesort(int arr[],int l,int r);
int merge(int arr[],int l,int m,int r);


int findinv(int a[], int n)
{
 return mergesort(a,0,n);
}


void main()
{
 int n,*a,i;
 printf("Enter nuber of elements : ");
 scanf("%d",&n);
 printf("Enter %d elements : ",n);
 a=(int*)malloc(sizeof(int)*n);
 for(i=0;i<n;i++)
 scanf("%d",&a[i]);
 printf("Number of inversion = %d",findinv(a,n));
 
}

//merge 
int merge(int arr[],int l,int m,int r)
{
 int len,i,j,k,*c,count=0;
 len=r-l+1;
 c=(int*)malloc(sizeof(int)*len);
 i=0;
 j=l;
 k=m;
 while(j<=m-1 && k<=r)
 {
  if(arr[j]<=arr[k])
  {
   c[i++]=arr[j++];
   
  }
  else
  {
   c[i++]=arr[k++];
   count+=m-j;
   
  }
  
 }
 
 while(j<=m-1)
 {
  c[i++]=arr[j++];
 }
 
 while(k<=r)
 {
  c[i++]=arr[k++];
 }
 i=0;
 while(l<=r)
 {
  arr[l++]=c[i++];
 }
 
 return count;
}


//mergesort
int mergesort(int arr[],int l,int r)
{ int count=0;
 int m=(l+r)/2;
 if(l<r)
 {
  count+=mergesort(arr,l,m);
  count+=mergesort(arr,m+1,r);
  count+=merge(arr,l,m+1,r);
  
 }
 
 return count;
}





JAVA implementation :
import java.util.*;


class InversionCount
{
 public static void main(String... v)
 {
   Scanner sc=new Scanner(System.in);
   System.out.print("Enter number of elements : ");
   int n=sc.nextInt();
   System.out.print("Enter "+n+" elements :");
   int[] a=new int[n];
   for(int i=0;i<n;i++)
    a[i]=sc.nextInt();
    System.out.println("\nNumber of Inversion = "+mergeSort(a,0,n-1));;
 }
 
  static long mergeSort(int a[],int left,int right)
  {
  int mid;
  long  count = 0;
       if (right > left)
      {
   mid = (right + left)/2;
   count  = mergeSort(a, left, mid);
   count += mergeSort(a,  mid+1, right);
  
   
  count += Merge(a, left, mid+1, right);
   }
  return count;
  }
  
  static long Merge(int a[],int l,int m,int r)
  {
  
  int length=r-l+1;
  int c[]=new int[length];
  int i=0,j=l,k=m;
  long count=0;
  while(j<=m-1&&k<=r)
  {
   if(a[j]<=a[k])
   {
    c[i]=a[j];
    i++;j++;
   }
   else
   {
    c[i]=a[k];
    count+=m-j;
    i++;k++;
   }
  }
  
  while(j<=m-1)
  {
   c[i]=a[j];
   i++;j++;
  }
  
  while(k<=r)
  {
   c[i]=a[k];
   i++;
   k++;
  }
  i=0;
  while(l<=r)
  {
   a[l]=c[i];
   l++;
   i++;
  }
  return count;
  
  }
  
}