Rownum and the Top-N query

Rownum is a special column that can be used to limit the number of results returned by a query. However, not understanding exactly how it works can lead to unexpected results. Let’s go into some simple scenarios involving the rownum clause.

Here’s our table definition:
create table employee (empname varchar(20), empid number(10));

Let’s say we want to retrieve 5 rows from this table. This is what the query might look like.
select * from employee where rownum <= 5;

Now if we want the top 5 empids from this table, here’s a novice attempt.  This query will not return the top 5 empids as desired, but just some 5 rows sorted by empids.
select * from employee where rownum < 5 order by empid desc;

Here’s what we need to do. What follows is called a Top-N query. This query contains a nested query that retrieves the rows from this table sorted by the empids, and then applies a rownum clause on the results of this query to return the desired result.
select * from (select * from employee order by empid desc) where rownum <=5;

Essentially a Top-N query is a query used to retrieve the top N rows from a table, based on desired conditions. In our example, our query was attempting to retrieve the top 5 empids from the employee table.

(Please note that all queries listed here were run and tested on Oracle.)

Programming Practice: Prime Numbers

Problem: Compute all prime numbers less than specified integer

Example:
Input: 100
Output: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Algorithm:
We use an algorithm known as the Sieve of Eratosthenes to solve this problem. How it works is that for each prime number starting from 2, we mark all multiples of that number as non prime. At the end of this process, all the prime numbers are identified.

Here’s the detailed steps.
1. Create an array of n items, and mark all values as 1 to mark them as prime.
2. Iterate over the array going from i = 2 to sqrt(n). If i is prime, mark all multiples of i as 0 (non prime)

Java Code:

Programming Practice: Remove specified characters from input string

Problem: Given two input strings, remove all occurrences of all the letters in the second string from the first one

Examples:

Input: “Battle of The Vowels”, “aeiou”, Output: “Bttl f Th Vwls” (removing all vowels from the input string)

Algorithm:

We could iterate over the remove string and for each character, remove all occurrences from the input string. Give input string of length ‘n’ and remove string of length ‘m’, this brute force algorithm would lead to a complexity of O(mn).

Here’s a more efficient algorithm. Iterate over the remove string, and store each character in an array. Later as we iterate over the input string, we lookup this array, and if that character is present in this array, then we remove it from the input. This algorithm works if the array lookup is a constant time operation. The net complexity of this algorithm would be O(m+n), much better than the O(mn) brute force algorithm described earlier.

The detailed steps are as folllows:

1. Create an array ‘flags‘ of 256 characters. Entries in this array serve as flags denoting whether character ‘i’ is to be removed or not. Initialize all elements of this array to false.
2. Iterate over the remove string. For each character i in the string, mark flags[i] as true
3. Iterate over the input string. For each character in the string, if flags[i] is true, then copy it to an output array. Otherwise continue to the next character.
4. At the end of this iteration, the output array will contain all characters of input minus all letters of remove.

Java Code: