Find if number occurs exactly n/2 times in an array

You have an array of number/characters. If there is a number which occurs exactly n/2 times.
and all other elements in the set/array are distinct, can you find the the repeating number?

Expected time complexity : O(n)
Expected space complexity : O(1)

What if the other members are not distinct?
Can we solve the problem in O(log n) time complexity? (distinct and / or not distinct)

Source : http://inder-gnu.blogspot.com/2009/08/number-occuring-n2-times.html

Dividing array into groups

Divide a list of numbers into groups of consecutive numbers but their original order should be preserved.

Example:
<8,2,4,7,1,0,3,6>

should be divided into two groups like this:
<2,4,1,0,3> <8,7,6>

Source : http://discuss.techinterview.org/default.asp?interview.11.770712.8

Sort on second key when, first key in a set is sorted

Assume that we are given as input n pairs of items, where

1. the first item is a number
2. the second item is one of three colors (red, blue, or yellow).

Further, assume that the items are sorted by number. Give an O(n) algorithm to sort the items by color (all reds before all blues before all yellows) such that the numbers for identical colors stay sorted.

For example: (1,blue), (3,red), (4,blue), (6,yellow), (9,red) should become (3,red), (9,red), (1,blue), (4,blue), (6,yellow).

Find if summation of numbers from two lists is given number

Problem: Given two lists A & B define an algo, which will identify two numbers 'a' and 'b', such that a + b = x, where 'x' is the input.

Wife?

Got this from a colleague of mine. Found it hilarious...

Open Source Developers @ Google Speaker Series

Open Source Developers @ Google Speaker Series: Ben Collins-Sussman and Brian Fitzpatrick

Open Source Speaker Series: Practical MythTV video on Google Videos :
http://video.google.com/videoplay?docid=-6641045817693171683

Linux Bash Starters

I've been using Linux fo quite sometime now. One of my friends - Viraj Turakhia - who started using Linux lately, came up with a couple of questions on using Bash and customizing it for ease of use. This text is a result of the answers to his questions - for Linux starters this will definitely be a boon and I'm sure there are many of us who have been using the shell for a long time, yet will find these articles a good learning.

First - what the hell is a shell?
A shell is interface to the underlaying complexities of an operating system. Mostly shell is used for a command line / text based UI - however, the term is generic enough. Latest Linux distributions ship with those cool GUIs and make the shell a bit less prominent. Nevertheless, you use the GUI or not, working with the terminal ( or konsole or sh or ksh or csh or bash) is fun sometime or the other.

Second - what is Bash?
Bash - acronym for "Bourne-again shell" is a "shell, or command language interpreter, that will appear in the GNU operating system. Bash is an sh-compatible shell that incorporates useful features from the Korn shell (ksh) and C shell (csh)" and is probably the most widely used shell scripting environment. Most of the items here apply for shell scripting on Bash.

Ok, enough of supplements, where is the real stuff?
For all those users who want to get shell-started, I've populated a list of articles and tutorials. These will help you grasp the concepts to use when working on Linux and scripting using Bash. Since the articles will overlap on a few topics, I've included my comments on what to expect from each :

1. Tutorial: The best tips & tricks for bash, explained by Rechosen - The Linux Tutorial blog features this must for every Linux Starter. This tutorial explains the basic concepts we use in everyday scripting - most importantly stream redirection (stdout, stderr, stdin), foreground and background jobs (fg, bg), and piping.
   
   
2. Linux Shell Scripting Tutorial - A Beginner's handbook by Vivek G. Gite - is a detailed tutorial on shell scripting. It covers the basics of Linux (from getting Linux) to the advanced topics like expressions, IO, awk and more... This link is good for users who have just started using the shell and need help moving around. Finally, there is a whole section for sample shell scripts to check if you got the tutorial right :).
   
   
3. Linux Tutorial by Clarica Grove - Knowledge about the Linux filesystem, its directories, and their usage is very important for effectively working on the shell. This tutorial helps the user get comfortable with the Linux environment. It also explains other important aspects of a shell and their usage. Another important entry in this tutorial is a topic on permissions - I've witnessed many people who get pissed of working on the shell, just because they have they have not done their homework on this topic!
   
   
4. BASH Programming - Introduction HOW-TO by Mike G - One of my favorite sites for Bash - its clean and simple. However, as the site says "It does not intend to be an advanced document (see the title). I am NOT an expert nor guru shell programmer. I decided to write this because I'll learn a lot and it might be useful to other people" this tutorial is for basics.
   
   
5. Power Shell Usage by Simon Myers - One of my favorites when it comes to shell customization and power usage. Arm yourself with these simple tricks and you'll love using the ease of using the shell! This page is actually a presentation by Simon and includes notes for explanation. A PDF version of the same is here.My Favorite bash Tips and Tricks by Prentice Bisbal - is a good deal for users looking for those nifty magic shell tricks!
   
   
6. Red Hat Knowledge Base explains shortcuts and inputrc basics - This article from the Red Hat Knowledgebase briefs about using keyboard shortcuts and customizing the inputrc file.

I suppose these links should be a very good start into shell programming - so, that's ll folks! There are many other advanced tutorials on shell scripting - IO, regex, looping, piping and more..., but these links will arm you with the basics of shell scripting - using which the advanced topics will seem pretty simple.

While running behind your links for a perfect shell tutorial, if you find something even better than those listed here, please do share it with me.

Happy scripting. Books are the best companion to get learn anything. Following are my recommendations :