Select top N records from each category in PL/SQL

Background

Lets say you have 2 tables -

1. EMPLOYEE
2. EMPLOYEE_SALARY

EMPLOYEE table has employee id which is a primary key and his name.  EMPLOYEE_SALARY has employee id which is foreign key to id in EMPLOYEE table. This table has employee department and salary. You need to write a query that returns top 2 employees from each department that has highest salary.

Tables creation and data insertion

Table Queries :

create table schema8.EMPLOYEE(ID int, name varchar2(255));
alter table schema8.EMPLOYEE ADD CONSTRAINT PRIMARY_KEY PRIMARY KEY (ID);
create table schema8.EMPLOYEE_SALARY(EMPLOYEE_ID int, department varchar2(255), salary int);
alter table schema8.EMPLOYEE_SALARY ADD CONSTRAINT FK_EMP_ID FOREIGN KEY (EMPLOYEE_ID) REFERENCES schema8.EMPLOYEE(ID);

Data Queries for  EMPLOYEE table:

insert into schema8.EMPLOYEE values(1,'Aniket');
insert into schema8.EMPLOYEE values(2,'John');
insert into schema8.EMPLOYEE values(3,'Sam');
insert into schema8.EMPLOYEE values(4,'Ron');
insert into schema8.EMPLOYEE values(5,'Sky');
insert into schema8.EMPLOYEE values(6,'Paul');
insert into schema8.EMPLOYEE values(7,'Dan');
insert into schema8.EMPLOYEE values(8,'Jess');
insert into schema8.EMPLOYEE values(9,'Troy');
insert into schema8.EMPLOYEE values(10,'Mike');

 Data Queries for EMPLOYEE_SALARY table:

insert into schema8.EMPLOYEE_SALARY values(1,'IT',10000);
insert into schema8.EMPLOYEE_SALARY values(2,'Admin',500);
insert into schema8.EMPLOYEE_SALARY values(3,'Sales',1200);
insert into schema8.EMPLOYEE_SALARY values(4,'Sales',1500);
insert into schema8.EMPLOYEE_SALARY values(5,'IT',9000);
insert into schema8.EMPLOYEE_SALARY values(6,'Admin',4000);
insert into schema8.EMPLOYEE_SALARY values(7,'Admin',5000);
insert into schema8.EMPLOYEE_SALARY values(8,'IT',9500);
insert into schema8.EMPLOYEE_SALARY values(9,'Sales',1000);
insert into schema8.EMPLOYEE_SALARY values(10,'Admin',6000);

Final data :

select * from schema8.EMPLOYEE;
select * from schema8.EMPLOYEE_SALARY;

Solution

We are going to use RANK to partition by department and order by salary - 

select * from (
select id , name, department, salary, RANK() over (partition by department order by salary desc) as rank from(
select e.id, e.name, es.department,es.salary from schema8.EMPLOYEE e left OUTER join schema8.EMPLOYEE_SALARY es on (e.id=es.employee_id))
) where rank <= 2;

First we have done a left outer join so that we capture all employee records with their respective salaries and departments. In outer query we have ranked it based on their salaries in respective department. Finally we select all records that have rank <=2 i.e top 2 records.

Related Links

• Remove duplicate rows from table in Oracle(OSFG) 
• Basic PL/SQL syntax and query executions on Oracle 11g R2 database(OSFG) 
• How does database indexing work? (OSFG) 

Install Oracle instant client and sqlplus using Homebrew

Background

 In one of the previous posts we say how to install and run sql plus  and Oracle instant client  on Ubuntu operating system -

• Installing Oracle instant database client in Ubuntu

In this post we will see the same for a Mac.

This post expects you have homebrew installed. If not please refer -

•  Tips and Tricks for your MacBook

 Install Oracle instant client and sqlplus using Homebrew

For this you need to download following two files -

1. instantclient-basic-macos.x64-12.1.0.2.0.zip 
2. instantclient-sqlplus-macos.x64-12.1.0.2.0.zip 

You can download these files from oracle site - http://www.oracle.com/technetwork/topics/intel-macsoft-096467.html

Once download copy these files into following folder-

•  ~/Library/Caches/Homebrew 

 Once done run following commands -

• brew tap InstantClientTap/instantclient
• brew install instantclient-basic
• brew install instantclient-sqlplus

 This should install sqlplus for you.

Related Links

• Installing Oracle instant database client in Ubuntu(OSFG)
• Tips and Tricks for your MacBook(OSFG) 

How to Disable a MacBook’s Built-In TrackPad When Using a Mouse or Wireless Trackpad

Background

For me this became a requirement as my trackpad started malfunctioning. But it can be a useful feature as well. When we connect a mouse we would not want trackpad to work. For eg. lets say you are playing counter strike with a mouse you definitely don't want trackpad to change your aim in game. So it would be better if you disable in build trackpad while mouse is connected. In this post I will show you how you can do this.

Disable Trackpad in OS X Lion and Above

For this you need to go to -

• System Preferences > Accessibility > Mouse & Trackpad

Here you will find a checkbox saying "Ignore built-in trackpad when mouse or wireless trackpad is present". Click it and make sure you have checked it. Setting should take effect immediately.

Disable Trackpad in OS X Snow Leopard

Setting is the same here too. It's just at different path. So head to 

• System Preferences > Universal Access > Mouse & Trackpad

Here again you will find the same checkbox. Check it and you should be good to go.

How to install wine and run windows programs on your mac

Background

Sometimes it becomes necessary to install windows program on your Linux or mac machine. Like I mentioned in a post sometime back there may be some sites that require IE only -

• How to access websites on your Mac that requires Internet Explorer

In this post I will show you how to install wine on your mac. Wine is a very handy software that allows you to install and run windows programs in a windows like simulated environment.

Installing Wine on Mac

You need to have homebrew installed on your mac. If not please refer -

• Tips and Tricks for your MacBook

 Next Homebrew uses an extension called Homebrew Cask to install other programs. You can install the Cask extension by running following command -

• brew tap caskroom/cask

Wine needs -

• Java and 
• XQuartz 

as dependencies to be already installed. I am assuming you already have Java installed on your machine and set it up in classpath. You can install  XQuartz with following command -

• brew cask install xquartz

NOTE :  You can similarly install Java if you already done have it -

• brew cask install java

 Once dependencies are done you can directly install wine with following command -

• brew install wine

Also install winetricks -

• brew install winetricks

 Use winetricks to set environment as windows 7 -

• winetricks win7

Installing and running Windows program from wine

Go to the directory where you have downloaded your exec file and run -

• wine installer.exe

where installer.exec is your exe file.

 You can find installed files in dir -

• /Users/athakur/.wine/drive_c

You can then navigate to program files, find your installed program and run it -

 Once in the program directory you can simply run it as -

• wine ioexplorer.exe

And you are done :)

Related Links

•  How to access websites on your Mac that requires Internet Explorer(OSFG)

How to check if a Singly Linked List is a Palindrome or not

Background

This is another classic data structure interview question that fall into basic DS problems. You might have seen or known method to find if a String is palindrome or not. You can simply iterate on half of the String and check with reversed other half if it same.

Time Complexity : O(N)
Space Complexity : O(1)

It will be as simple as -

    public static boolean isPalindrome(String str) {
        if(str == null) {
            return false;
        }
        for(int i = 0; i< str.length()/2; i++) {
            if(!(str.charAt(i) == str.charAt(str.length() - i - 1))) {
                return false;
            }
        }
        return true;
    }

Test :

        System.out.println(isPalindrome("ABCDCBA"));
        System.out.println(isPalindrome("ABBA"));
        System.out.println(isPalindrome("ABCD"));

Output:

true
true
false

It can have a variant such that instead of a String you have a Linked List. Now if you have a double linked list it becomes very easy. You start from head and from the tails and keep comparing. Increment the header pointer and decrement the tail pointer in each iteration. Time complexity will be O(N) only.

However the question at hand is of Singly Linked List.

How to check if a Singly Linked List is a Palindrome or not

 

Method 1 : Using a String

 

Iterate over the Linked list and construct a String out of it and then check if that String is a Palindrome.Time complexity O(N) but space complexity is also O(N) since you are now creating a String.

Since interviewer asked you Linked List this is most definitely something he does not want. He could have asked a String palindrome itself if that was the case. But it never hurts to put it out what you are thinking and build upon your answer as you proceed.

 

Method 2 : Using a Stack

 

You can iterate over the Linked List put it's content in stack. Once iteration is over we can iterate over Linked List again and this time with each iteration compare Nodes content with Stacks popped out content. If it does not match it is not a palindrome.

This again has time complexity O(N) and space complexity O(N).

1) Traverse the given list from head to tail and push every visited node to stack.
2) Traverse the list again. For every visited node, pop a node from stack and compare data of popped node with currently visited node.
3) If all nodes matched, then return true, else false.

Code :

    public static boolean isPalindrome(ListNode<String> head) {
        boolean isPanindrome = true;

        Stack<String> stack = new Stack<>();
        ListNode<String> currentNode = head;

        while (currentNode != null) {
            stack.push(currentNode.getValue());
            currentNode = currentNode.getNext();
        }

        currentNode = head;
        while (currentNode != null) {
            if (!currentNode.getValue().equals(stack.pop())) {
                isPanindrome = false;
                break;
            }
            currentNode = currentNode.getNext();
        }
        return isPanindrome;
    }

I have also added it to my Data Structure github repo. Check isPalindrome() method in  https://github.com/aniket91/DataStructures/blob/master/src/com/osfg/questions/LinkedListPalindromeFinder.java 

 

Method 3 : Reversing the 2nd half of the Linked List

 

This is a better version and always one you should aim for. It provides O(N) time complexity and O(1) space complexity -

1) Get the middle of the linked list.
2) Reverse the second half of the linked list.
3) Check if the first half and second half are identical.
4) Construct the original linked list by reversing the second half again and attaching it back to the first half

4th point is optional and depends if you need original List back.

I have added it to my Data Structure github repo. Check isPalindrome2() method in  https://github.com/aniket91/DataStructures/blob/master/src/com/osfg/questions/LinkedListPalindromeFinder.java  

 

Related Links

• Function to check if a singly linked list is palindrome(GFG)
• Data Structure Github repository