Saturday, 20 December 2014

CodeChef problem

Question : 


STATEMENT

There are n events. Each has a start time and end time. You wish to attend maximum of such events.

NOTE:If start time of one event is same as end time of other you cannot attend both. You can imagine some time to travel from event1 to event2.

INPUT

The first line will contain an integer T, denoting the number of test cases.

Each test case contains several lines.

The first line of each test case will contain an integer N, denoting the number of events.

The next N lines, one for each event, contain two space separated integers, starttime and endtime.

1 <= T <= 10
1 <= N <= 10000
0 <= starttime < endtime <= 1000000000

OUTPUT

For each test case, output a single integer denoting the maximal number of events that you can attend.
EXAMPLE
INPUT

2
5
0 5
0 2
3 5
3 4
5 6
6
0 8
8 10
11 12
11 15
2 5
7 9
OUTPUT

3
3
EXPLANATION

In the first case you can attend events (0, 2), (3, 4), (5, 6)



Solution


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;

/**
 * 
 * @author athakur
 *
 */
public class Quark1 {

    public static void main(String args[]) throws IOException {
        
         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
         PrintWriter writer = new PrintWriter(System.out,true);
        
         int noOfTestCases = Integer.parseInt(reader.readLine());
        
         for(int i=0; i<noOfTestCases; i++) {
             int noOfEvents = Integer.parseInt(reader.readLine());
             Event[] events = new Event[noOfEvents];
             for(int j=0; j< noOfEvents; j++) {
                 String[] times = reader.readLine().split(" ");
                 events[j] = new Event(Integer.parseInt(times[0]),Integer.parseInt(times[1]));
             }
             writer.println(getMaxEvents(events));
         }
    }
    
    private static int getMaxEvents(Event[] events) {
        Arrays.sort(events);
        int i=0;
        int count = 1;
        for (int j=1; j<events.length;j++) {
            if(events[j].startTime > events[i].endTime) {
                count++;
                i=j;
            }
        }
        return count;
    }
    
    static class Event implements Comparable<Event>
    {
        int startTime;
        int endTime;
        
        public Event(int startTime, int endTime) {
            this.startTime = startTime;
            this.endTime = endTime;
        }

        @Override
        public int compareTo(Event event) {
            return this.endTime > event.endTime ? 1 : (this.endTime < event.endTime ? -1 : 0);
        }
    }
    
}
 

Explanation : 

First we sort the events based on the finish time because we want to attend earliest events first. Now if end times if two events are same we can attend either. So we don't bother about it. On sorting such events can have sequential positioning (one after the other) in either way. Next we start from first event in sorted events list. We can only attend next event if it's start time is greater (mind even equals will not work as we have to consider commute delay) than the end time of current event. Current event is tracked with i variable where as next event is tracked with j.

Friday, 19 December 2014

Android Programming Tips and Tricks


Showing Toast in Android

//Toast shown for  short period of time
Toast.makeText(getApplicationContext(), "Toast Message", Toast.LENGTH_SHORT).show();

//Toast shown for long period of time
Toast.makeText(getApplicationContext(), "Toast Message", Toast.LENGTH_LONG).show();
 
OR using custom layout for your toast

Toast myToast = new Toast(getApplicationContext());
myToast.setGravity(Gravity.CENTER_VERTICAL, 0, 0);
myToast.setDuration(Toast.LENGTH_LONG);
myToast.setView(myLayout);
myToast.show();

Getting all running Apps in Android

    private List<String> getRunningApps() {
        ActivityManager activityManager = (ActivityManager) getSystemService(Context.ACTIVITY_SERVICE);
        PackageManager packageManager = getPackageManager();
        final List<RunningAppProcessInfo> runningProcesses = activityManager.getRunningAppProcesses();
        List<String> runningAppNames = new ArrayList<String>();
        for(RunningAppProcessInfo processInfo : runningProcesses) {
            CharSequence appName = null;
            try {
                appName = packageManager.getApplicationLabel(packageManager.getApplicationInfo(processInfo.processName, PackageManager.GET_META_DATA));
                runningAppNames.add(appName.toString());
            } catch (NameNotFoundException e) {
                Log.e(TAG,"Application info not found for process : " + processInfo.processName,e);
            }
        }
        return runningAppNames;
    }


Above code required permission -
  <uses-permission android:name="android.permission.GET_TASKS" />

Killing Background App

You can use  -

 ActivityManager activityManager = (ActivityManager) getSystemService(Context.ACTIVITY_SERVICE);
activityManager.killBackgroundProcesses(packageName);


You can't kill the app in the foreground (your App) by this. You need to finish(). Also note this is for API 8 and above.

Dynamically Creating Layout

LinearLayout linearLayout = new LinearLayout(this);
linearLayout.setOrientation(LinearLayout.VERTICAL);
LayoutParams layoutParams = new LayoutParams(LayoutParams.MATCH_PARENT, LayoutParams.WRAP_CONTENT);
Button button = new Button(this);
button.setText(appName);
linearLayout.addView(button, layoutParams);

Adding Scroll bar over a Layout

LinearLayout rootLinearLayout = new LinearLayout(this);
LinearLayout linearLayout = new LinearLayout(this);
LayoutParams layoutParams = new LayoutParams(LayoutParams.MATCH_PARENT, LayoutParams.WRAP_CONTENT);
ScrollView scrollView = new ScrollView(this);
scrollView.addView(linearLayout, layoutParams);
rootLinearLayout.addView(scrollView, layoutParams);

Closing current Activity

finish();
return;

Note : You should put a return statement after that finish, because the method that called finish will be executed completely otherwise.

Getting Resources

getResources().getString(R.string.app_name);
getResources().getLayout(R.layout.myLayout); 
getResources().getColor(R.color.MY_RED);

Resources are under res directory. For example String resources are in res/string.xml  with content like - 

<?xml version="1.0" encoding="utf-8"?>
<resources>

    <string name="app_name">Simple App Killer</string>
    <string name="about">About</string>

</resources>

Getting View or Activity Content View

findViewById(R.id.myView);
this.getWindow().getDecorView().findViewById(android.R.id.content);
this.findViewById(android.R.id.content);
this.findViewById(android.R.id.content).getRootView(); 

Note : R.layout.* are layouts you provide (in res/layout, for example).android.R.layout.* are layouts that ship with the Android SDK. Infact R.layout is actually shortcut for your.package.R.layout

Creating Menu

    @Override
    public boolean onCreateOptionsMenu(Menu menu) {
        MenuInflater inflater = getMenuInflater();
        inflater.inflate(R.menu.appkiller_menu, menu);
        return true;
    }

You need to override onCreateOptionsMenu method and use MenuInflater to inflate your menu. You also need to provide menu .Create a file name appkiller_menu.xml under res/menu with content like -

<?xml version="1.0" encoding="utf-8"?>
<menu xmlns:android="http://schemas.android.com/apk/res/android" >
   
<item android:id="@+id/about"
          android:title="@string/about" />

</menu>

To set onclick on the menu items you need to override onOptionsItemSelected method as follows -

    @Override
    public boolean onOptionsItemSelected(MenuItem item) {
        // Handle item selection
        switch (item.getItemId()) {
             case R.id.about:
                Toast.makeText(getApplicationContext(), "This App is created by Aniket Thakur", Toast.LENGTH_LONG).show();
                return true;
            default:
                return super.onOptionsItemSelected(item);
        }
    } 

Getting Managers

ActivityManager activityManager = (ActivityManager) getSystemService(Context.ACTIVITY_SERVICE);
PackageManager packageManager = getPackageManager();

Note : these manages will not be available before onCreate() method.

PS : This list will keep updating. If you want me to add something in above list please provide it in the comments.

Hiding Action Bar App Icon and App Name

getActionBar().setDisplayShowTitleEnabled(false);
getActionBar().setDisplayShowHomeEnabled(false)

Note : This requires API level 11 or above.

Good Read


Difference between Running Task and Running Process in Android

Background

Tasks and processes are different in Android. I am going to discuss the same in this post. I ran into this question when I was trying to figure out the difference between the calls

final List<RunningTaskInfo> runningTasks = activityManager.getRunningTasks(Integer.MAX_VALUE);

and

final List<RunningAppProcessInfo> runningProcesses = activityManager.getRunningAppProcesses();

So lets see the difference.


Running Task and Running Process in Android

Android has Linux kernel. So process is similar to processes in Linux. Each process can have multiple threads. When a process starts it is single thread execution by default. This thread is called the main thread or UI thread. You may have other worker or asynchronous threads running in a process.

Task or Application on the other hand can be visualized as set of activities in an application. It is possible that each activity in the task is configured to run in different processes. Same goes for other entitles of Android - services, providers etc. Infact components of different tasks/applications can run in same process (provided that the applications share the same Linux user ID and are signed with the same certificates).

When System memory is low of running application an older process is killed. Again note this may have components of different application.

activityManager.getRunningTasks(Integer.MAX_VALUE)


Above will give you Running tasks or rather lets call it application consisting of set of activities. (List of RunningTaskInfo objects). This in turn will have two main things.
  1. baseActivity : component launched as the first activity in the task
  2. topActivity : activity component at the top of the history stack of the task

and

activityManager.getRunningAppProcesses()


Above will give all running processes in the System. Since it is a process it will have associated pid (processId) and `uid (userId). Some of the important fields here are -
  1. processName : The name of the process that this object is associated with
  2. pid : The pid of this process; 0 if none
  3. uid : The user id of this process.
  4. pkgList : All packages that have been loaded into the process.

To get all running app name we do something like - 

    public List<String> getRunningApps() {
        ActivityManager activityManager = (ActivityManager) getSystemService(Context.ACTIVITY_SERVICE);
        PackageManager packageManager = getPackageManager();
        final List<RunningAppProcessInfo> runningProcesses = activityManager.getRunningAppProcesses();
        List<String> runningAppNames = new ArrayList<String>();
        for(RunningAppProcessInfo processInfo : runningProcesses) {
            CharSequence appName = null;
            try {
                appName = packageManager.getApplicationLabel(packageManager.getApplicationInfo(processInfo.processName, PackageManager.GET_META_DATA));
                runningAppNames.add(appName.toString());
            } catch (NameNotFoundException e) {
                Log.e(TAG,"Application info not found for process : " + processInfo.processName,e);
            }
        }
        return runningAppNames;
    }

 In above code we are essentially getting information about all running processes. Then with the help of process name of each such process we are getting corresponding application package.


Interesting Read

First of all you need to understand what you can kill and what not. By android's point of view an application is not like other OSes. An android application consists of many components (activities, broadcast receivers, services, most important tasks etc) which are packed in a package. A package can have more that one processes running depending on its components running. 

Now the interesting part is that an android package isn't considered (by android) "killed" or "stopped" if any or all of its processes have killed, in fact a package can still running even with no processes running at all. 

You can see this effect if you start an emulator start a program (i.e. Browser) and then kill its process via DDMS, after that go to the application's package settings (Settings --> Applications --> Manage Applications --> All --> Browser), you can see the "Force Stop" button enabled, this means that the application is still running (from android's point of view). 

What happened here is that the application has one or more tasks "frozen". That is, android has saved the state of the application's activities (task or tasks) and so the package is still running or better if the user returns to it he will land on the last thing he was doing. Now if you click the "Force Stop" button, android will discard all of these "frozen" tasks and when the user returns to the application he will see the first activity. 

A Task is something you cannot kill (since froyo) only the user (from "Force Stop" button), the system or a third party application which is signed with the same key of the system can do that (and maybe a root capable application but I have not confirmed this). On the other hand a Process is something you can kill and reclaim the memory it uses, as long as you follow some restrictions:
  1. You have the "android.permission.KILL_BACKGROUND_PROCESSES" permission.
  2. The processes are not system or root processes.
  3. The process is not belonging to a component which is persistent.
  4. The process is not a critical for the system to operate by any other means.

Besides the no 1 rule you do not have to do something about them, android will take care of this.

ActivityManager has a handy function you can use in order to kill all of the processes a package has at once. When you invoke it android will kill any process can be killed and thus freeing up some memory. However the state of the tasks for this package will be saved and when the user returns to the application he will see the last thing he was doing unless the system itself has killed them. This can occur either because it needs resources or the state was saved long time ago (about 30 minutes). The side-effect is that because users are thinking that all applications are like in desktop operating systems, they do not believe that the application is really closed but this is the life with android.

(Source - SO)

Related Links

Friday, 12 December 2014

Difference between Comparator and Comparable in Java

Background

How do we sort numbers in Java. Following is the simple program to do that - 

    public static void main(String args[]) {
        int[] myArray = new int[]{5,10,2,1,6};
        Arrays.sort(myArray);
        for(int no : myArray) {
            System.out.print(no + " ");
        }
    }

And we get the output as : 1 2 5 6 10 

Same goes for Collections as well.

But that is for simple numbers. How do we sort complex custom Objects. For example lets say you have Student Objects and you need to sort them on the basis of their age or some other scenario may require them to be sorted alphabetically by name. In this post we will see exactly how to do this.

Ordering Custom Objects


Lets create our Student class first.

Student.java


public class Student {
    
    private String name;
    private int age;
    
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    
    @Override
    public String toString() {
        return "Student [name=" + name + ", age=" + age + "]";
    }
}



For simplicity I have just kept two parameters - name and age. Before we proceed to create group of students and order them we need to answer a question -

What is the natural ordering ? The answer will vary depending on the scenario for which you are writing your code. In this scenario we will take age as natural ordering criteria.

Why did we answer above question ? Because it is the basis of the title of this post - Difference between Comparator and Comparable in Java.

Difference between Comparator and Comparable in Java

Implementing Comparable means "I can compare myself with another object." This is typically useful when there's a single natural default comparison.

Implementing Comparator means "I can compare two other objects." This is typically useful when there are multiple ways of comparing two instances of a type - e.g. you could compare people by age, name etc.

In our case we decided age will be our natural ordering. So we will handle age comparison in Comparable interface where as handle name in Comparator.

Note : Both Comparator and Comparable are interfaces. You need to implement them. Your model class which needs to be naturally ordered implements Comparable interface where as you need to create a separate class that implements Comparator to handle non natural ordering. When you call methods like sort we need to supply instance of this class that implemented Comparator interface.

 Comparable interface is in package java.lang whereas Comparator interface is in java.util package. Also when you implement Comparable interface you override a.compareTo(b) method where as in case of Comparator you override compare(a, b). Don't worry about the technicality. We will see this with example.

Implementing Comparable interface - natural ordering

As I mentioned earlier with reference to our Student object I am going to use age as natural ordering criteria.

Lets rewrite our Student class which will now implement Comparable interface.


public class Student implements Comparable<Student> {
    
    private String name;
    private int age;
    
    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    
    @Override
    public String toString() {
        return "Student [name=" + name + ", age=" + age + "]";
    }
    
    @Override
    public int compareTo(Student o) {
        return (this.age > o.age ? 1 : (this.age < o.age ? -1 : 0));
    }
}


Notice the logic in compareTo() method. We return 1 if current object is higher in order, -1 if lower and 0 if same. Lets test this now - 

public class OrderingTester {

    

    public static void main(String args[]) {

        Student[] allStudents = new Student[] { new Student("John", 21),

                new Student("Rita", 19), new Student("Sam", 26),

                new Student("Claire", 16) };


        System.out.println("Before natural sorting");

        for(Student student : allStudents) {

            System.out.println(student);

        }

        Arrays.sort(allStudents);

        System.out.println("After natural Sorting");

        for(Student student : allStudents) {

            System.out.println(student);

        }

    }

}

And the output is - 

Before natural sorting
Student [name=John, age=21]
Student [name=Rita, age=19]
Student [name=Sam, age=26]
Student [name=Claire, age=16]
After natural Sorting
Student [name=Claire, age=16]
Student [name=Rita, age=19]
Student [name=John, age=21]
Student [name=Sam, age=26]


That's how natural ordering/comparable interface work. Now lets move on to comparator interface.

Implementing Comparator interface - Custom ordering

Lets start by writing our comparator class - 

public class StudentNameComparator implements Comparator<Student> {

    @Override
    public int compare(Student student1, Student student2) {
        return student1.getName().compareTo(student2.getName());
    }

}

and now lets test this - 

public class OrderingTester {
    
    public static void main(String args[]) {
        Student[] allStudents = new Student[] { new Student("John", 21),
                new Student("Rita", 19), new Student("Sam", 26),
                new Student("Claire", 16) };
        
        System.out.println("Before custom sorting");
        for(Student student : allStudents) {
            System.out.println(student);
        }
        Arrays.sort(allStudents, new StudentNameComparator());
        System.out.println("After custom Sorting");
        for(Student student : allStudents) {
            System.out.println(student);
        }
    }

}

And the output is - 

Before custom sorting
Student [name=John, age=21]
Student [name=Rita, age=19]
Student [name=Sam, age=26]
Student [name=Claire, age=16]
After custom Sorting
Student [name=Claire, age=16]
Student [name=John, age=21]
Student [name=Rita, age=19]
Student [name=Sam, age=26]


Logic in compare() method that we override on implementing Comparator interface is same as compareTo() method that we override on implementing Comparable interface.

Notice how we just gave the array to sort in Arrays.sort() in natural sorting where as we gave the comparator with custom ordering logic as a separate argument to sort method.

Hope this clarifies the difference. Let me know if you still have any doubts or questions.

Related Links


Tuesday, 9 December 2014

Enum Data Types in Java

Background

Sometime we need to program to restrict use inputs. Lets take a scenario - you are opening a pet store. As a starter you decide only to provide  - Dogs, Cats and Parrots. Next you have to design a Java program to provide the pet to customers. One way would be as follows - 

class PetStore {
    
    public static final String CATEGORY_DOGS = "Dogs";
    public static final String CATEGORY_CATS = "Cats";
    public static final String CATEGORY_PARROTS = "Parrots";
    
    public void getPet(String petType) {
        switch(petType){
        case CATEGORY_DOGS : System.out.println("You are opting for a pet Dog");
                            break;
        case CATEGORY_CATS : System.out.println("You are opting for a pet Cat");
                            break;
        case CATEGORY_PARROTS : System.out.println("You are opting for a pet Parrot");
                            break;
        default : System.out.println("We do not provide other pet animals");
        }
    }
}


It serves the purpose. But it does not stop user from entering Lion, Tiger does it ? Program would fall back to default saying we do not provide other pet Animals. But Lion, Tiger are not pet in the first place. One way to restrict user input is declaring an Enum. Lets come to that.



Using Enums

enum PetTypes {
    DOGS,CATS,PARROTS
}

class PetStore {
    
    public void getPet(PetTypes petType) {
        switch(petType){
        case DOGS : System.out.println("You are opting for a pet Dog");
                            break;
        case CATS : System.out.println("You are opting for a pet Cat");
                            break;
        case PARROTS : System.out.println("You are opting for a pet Parrot");
                            break;
        }
    }
}

Now you have successfully restricted user from entering one of the three allowed values. That is not it Enums has other advantages too.Lets come to those. Lets say you also need to store the number of available pet of each category. You can store that in enum too. Each enum value can have multiple attributes.


enum PetTypes {
    DOGS(10),CATS(7),PARROTS(9);
    
    int availableUnits;
    
    //enum constructors are implicitly private
    PetTypes(int availableUnits) {
        this.availableUnits = availableUnits;
    }

    public int getAvailableUnits() {
        return availableUnits;
    }
    
}

class PetStore {
    
    public void getPet(PetTypes petType) {
        switch(petType){
        case DOGS : System.out.println("You are opting for a pet Dog.");
                            break;
        case CATS : System.out.println("You are opting for a pet Cat");
                            break;
        case PARROTS : System.out.println("You are opting for a pet Parrot");
                            break;
        }
        System.out.println("Available units are : " + petType.getAvailableUnits());
    }
}


You can test it by

    public static void main(String args[])
    {
        new PetStore().getPet(PetTypes.CATS);
    }


You will get :

You are opting for a pet Cat
Available units are : 7

Note : When you say DOGS(10), corresponding constructor is called i.e PetTypes(10).

Important Points

  • Enums are implicitly private, static and final. 
  • Each declared enum implicitly inherits java.lang.Enum.
  • You can use valueOf() and name() methods on enums.
  • You can compare enums with == operator.
  • You cannot use new operator on enums. Not even inside enum definition. Outside you cannot because constructor is implicitly private. 
  • Enums cannot be local meaning you cannot declare them inside a method. They should be declared and defines inside of a top level class or an interface.

Question : 

 1. What happens when you compile the following code - 

enum PetTypes {
    int availableUnits;             //  #1
    DOGS(10),CATS(7),PARROTS(9);    //  #2
    
    //enum constructors are implicitly private
    PetTypes(int availableUnits) {
        this.availableUnits = availableUnits;
    }

    public int getAvailableUnits() {
        return availableUnits;
    }
 }

Above enum definition is incorrect and will not compile. You need to declare enum elements first before any other attributes. In short you need to interchange line #1 and #2 for above code to compile.


t> UA-39527780-1 back to top