A glance at Linux achievements - 2013

First of all it's almost time for new year. So wishing everyone a Very happy New Year! May all your wishes come true. And may Linux and FOSS have more amazing next year.

2013 was an amazing year for Linux and it is just not possible to list them all. However I am attempting to list a few ones here.

• ANDROID
  
  
  
  
  
  Year 2013 marked a record of Android phone activation. The figure is 1.5 Million devices per day. Over 900 million Android devices have been activated since being introduced in 2008 and this figure is set to hit 1 billion soon. Not to mention behind Android as an OS there is Linux kernel running.
• Raspberry pi
  
  
  
  One of the greatest development ever in the history of Low cost, single board computer was Raspberry pi. Raspberry pi was intended to promote Linux computing in schools and elsewhere and the board was highly welcomed by the FOSS Community and still continuing.
• Linux in Space
  
  
  
  Manager of the Space Operations Computing (SpOC) for NASA Keith Chuvala said , "We migrated key functions from Windows to Linux because we needed an operating system that was stable and reliable -- one that would give us in-house control. So if we needed to patch, adjust, or adapt, we could." Distribution used was Debian,
•  SteamOS
  
  
  
  2013 was indeed a great and marvelous year for Linux gaming.SteamOS, a debian based distribution was designed for Stream Machine Game Console and released in the mid of December 2013. With the trend of GNU/Linux into gaming environment is certainly a very welcome act.
• The Firefox OS
  
  
  
  Firefox OS (project name: Boot to Gecko, also known as B2G) is a Linux-based open-source operating system for smartphones and tablet computers.It was released in late April 2013. The ARM based Linux distribution for mobile devices, shows promising future.
• Ubuntu Touch
  
  
  
  
  
  Canonical released Ubuntu Touch 1.0, the first developer/partner version on 17 October 2013, along with Ubuntu 13.10 that "primarily supports the Galaxy Nexus and Nexus 4 phones. 
• Chromebooks
  
  
  
  Chromebooks wins the market of notebook computers, with a lot of high-end manufacturer viz., Samsung, ASUS giving place to GNU/Linux OS over Proprietary OS’s.
• Kali Linux
  
  
  
  
  From the developers of BackTrack Linux comes Kali Linux. Kali is a Linux distribution based on Debian, the mother OS which is Primarily developed for Penetration testing and shares a lot of repository of Debian, one of the most rich Distro. Kali Linux holds the record download, in a very less time of its release.
• Android Kitkat
  
  
  
  
  
  One of the Most awaited release was named Kitkat. Google Announced Android 4.4 aka KitKat in September of 2013. Although the release had been expected to be number 5.0 aka Key Lime Pie. Kitkat has been optimised to run on a large variety of devices having a minimum of 512 MB RAM.
• Miscellaneous
  
  Linux was not only constrained to desktops, tablets and smartphones but was also used in automobiles, space station, robots etc. 2013 was indeed a great year for Linux and the coming years we may see further boost.

Some memorable Linux milestones

 

How to reverse a LinkedList in Java?

A very basic interview question asked. In an earlier post we had see the LinkedList class in java and how to reverse it using Collections.revere(). You can refer to that post. Point to note that the LinkedList class defined in java is infact a doubly Linked list and that is not what the interviewer will be interested in.  Yes you can give that as your 1st answer as it will depict you have java knowledge but at some point you will have to fall back to basics.

Before we write the code to actually reverse the LinkedList lets write the code for the LLNode  data structure which will form our LinkedList.

LinkedList Node 

public class LLNode {

    int value;
    LLNode nextNode;

    public  LLNode(int value){
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public LLNode getNextNode() {
        return nextNode;
    }

    public void setNextNode(LLNode nextNode) {
        this.nextNode = nextNode;
    }

    public static void printLL(LLNode head){
        if (head != null){
            System.out.println(head.getValue());
            printLL(head.getNextNode());
        }
    }
}

Note : In this data structure we have also provided a method printLL() to print the Linked List.

Now lets go ahead and write our code to reverse this Linked List

Linked List Reversal

public class LLReverser {

    public static LLNode reverse(LLNode root){

        if(root.getNextNode() == null){
            return root;
        }

        LLNode next = root.getNextNode();
        root.setNextNode(null);

        while(next != null){
            LLNode temp = null;
            if(next.getNextNode() != null)
                temp = next.getNextNode();
            next.setNextNode(root);
            root = next;
            next = temp;
        }

        return root;

    }
}

Now let us test it out

Testing the logic

    public static void main(String args[]){

        LLNode root = new LLNode(1);
        LLNode second = new LLNode(2);
        root.setNextNode(second);
        LLNode third = new LLNode(3);
        second.setNextNode(third);
        LLNode fourth = new LLNode(4);
        third.setNextNode(fourth);

        System.out.println("Before");
        LLNode.printLL(root);
        System.out.println("After");
        LLNode.printLL(LLReverser.reverse(root));

    }

Output :

Before
1
2
3
4
After
4
3
2
1

What is Android Debug Bridge (adb)?

This post is essentially dedicated to understand what Android Debug Bridge (adb) really is. How can we use it.

As we know Android has Linux kernel underneath. To execute a process via we need to provide corresponding command line command. Unless you root your android device you cannot really instal the terminal emulator application. The shell can be accessed via ADB (Android Debug Bridge) command tool.

What is Android Debug Bridge?

Android Debug Bridge (adb) is a versatile command line tool that lets you communicate with an emulator instance or connected Android-powered device. 

It is a client-server program that includes three components: 

• A client, which runs on your development machine. You can invoke a client from a shell by issuing an adb command. Other Android tools such as the ADT plugin and DDMS also create adb clients.  
• A server, which runs as a background process on your development machine. The server manages communication between the client and the adb daemon running on an emulator or device. 
• A daemon, which runs as a background process on each emulator or device instance.  

A client can be you adb shell that you run or your IDE(Eclipse). As for the server you can check the status, kill it or start it through ADB command line tool utility. To check the daemon process you can simply type adb in your android terminal(if rooted).

 To get the overview of ADB refer to following picture

Where can I find ADB tool utility?

You can find the adb tool in <sdk>/platform-tools/. You can download the SDK from here.

More on ADB....

When you start an adb client, the client first checks whether there is an adb server process already running. If there isn't, it starts the server process. When the server starts, it binds to local TCP port 5037 and listens for commands sent from adb clients—all adb clients use port 5037 to communicate with the adb server. 

The server then sets up connections to all running emulator/device instances. It locates emulator/device instances by scanning odd-numbered ports in the range 5555 to 5585, the range used by emulators/devices. Where the server finds an adb daemon, it sets up a connection to that port. Note that each emulator/device instance acquires a pair of sequential ports — an even-numbered port for console connections and an odd-numbered port for adb connections. For example: 

Emulator 1, console: 5554
Emulator 1, adb: 5555
Emulator 2, console: 5556
Emulator 2, adb: 5557
and so on...

As shown, the emulator instance connected to adb on port 5555 is the same as the instance whose console listens on port 5554.

 Once the server has set up connections to all emulator instances, you can use adb commands to access those instances. Because the server manages connections to emulator/device instances and handles commands from multiple adb clients, you can control any emulator/device instance from any client (or from a script).[Source]

Usage Common Usage Examples

1.  adb device(shows all the devices with device id the adb server is connected to)
2. adb help( Shows adb version and all possible commands)
3. adb start-server(To start adb server if not started already)
4. adb kill-server(To kill adb server)
5. adb push <local> <remote>(To push a file from local machine to remote device/emulator)
6. adb pull <remote> <local>(To get a file from remote device/emulator to local machine)
7. adb version(Shows version number of adb running)
8. adb reboot(Reboots the device)
9. adb root(Restarts the adbd daemon with root priveledges)
10. adb backup(Used to backup your device. You can backup everything with -all argument)
11. adb restore (Restore from a backup taken earlier).
12. adb install (Push and Install a package)
13. adb uninstall (Uninstall a package)
14. adb shell(get shell access to your Android device)

Note : How to completely backup your android device has been already covered in a previous post. You can go through that post.

Related Links

• Installing Google Nexus 5 USB Drivers (for ADB)

Program to create Mirror image of a binary tree.

Question :

Write a Program in Java to print the mirror image of a given binary tree. Example is provided in following diagram

Solution :

Do a normal BFS traversal. In each call copy the left child's content to create right node of the mirror tree and the right child's content to create left child.

Code : 

public class TreeMirrorImageCreator {

    public static Node createMirrorImage(Node originalNode,Node mirroredNode){

        mirroredNode.setValue(originalNode.getValue());

        if(originalNode.getRight() != null){
            mirroredNode.setLeft(createMirrorImage(originalNode.getRight(),new Node(0)));
        }

        if(originalNode.getLeft() != null){
            mirroredNode.setRight(createMirrorImage(originalNode.getLeft(), new Node(0)));
        }

        return mirroredNode;

    }
}

Now lets write the code to test out this code.

    public static void main(String args[]){

        Node root = new Node(1);

        Node l = new Node(2);
        Node r = new Node(3);

        Node l1 = new Node(12);
        Node l2 = new Node(13);

        Node r1 = new Node(6);
        Node r2 = new Node(8);

        root.setLeft(l);
        root.setRight(r);

        l.setLeft(l1);
        l.setRight(l2);

        r.setLeft(r1);
        r.setRight(r2);

        System.out.println("Orig Tree : ");
        LevelTraversal.printLeveltraversal(root);
        Node mirroredRoot = new Node(0);
        TreeMirrorImageCreator.createMirrorImage(root,mirroredRoot);
        System.out.println("Mirrored Tree : ");
        LevelTraversal.printLeveltraversal(mirroredRoot);
}

Note :  Code for the Node data structure and level order traversal can be found here.

Related Links

• DataStructures github link

Deepest left leaf node in a binary tree

Question : 

Given a Binary Tree, find the deepest leaf node that is left child of its parent. For example, consider the following tree. The deepest left leaf node is the node with value 9.

Code:

 public class DeepestLeftLeafNodeFinder {

    Node deepestNode;
    int deepestNodeDepth;

    public Node findDeepestLeftLeafNode(Node root,boolean isLeftNode,int depth){

        if(isLeftNode){
            if(depth > deepestNodeDepth){
                deepestNode = root;
                deepestNodeDepth = depth;
            }
        }

        if(root.getLeft() != null){
            findDeepestLeftLeafNode(root.getLeft(),true,depth + 1);
        }

        if(root.getRight() != null){
            findDeepestLeftLeafNode(root.getRight(),false,depth+1);
        }

        return deepestNode;
    }
}

Test :

    public static void main(String args[]){

        Node root = new Node(1);

        Node l = new Node(2);
        root.setLeft(l);
        Node r = new Node(3);
        root.setRight(r);

        Node l1 = new Node(4);
        l.setLeft(l1);

        Node r1 = new Node(5);
        r.setLeft(r1);
        Node r2 = new Node(6);
        r.setRight(r2);

        Node r12 = new Node(7);
        r1.setRight(r12);

        Node r121 = new Node(9);
        r12.setLeft(r121);

        Node r22 = new Node(8);
        r2.setRight(r22);

        Node r222 = new Node(10);
        r22.setRight(r222);

        System.out.println("Deepest left node of the tree is : " +
                new DeepestLeftLeafNodeFinder().findDeepestLeftLeafNode(root,false,0).getValue());
    }

Output :

Deepest left node of the tree is : 9 

Note : Complexity of above code is O(N) as we are visiting each node at most once. Do let me know if anyone has a better solution.