Mars at Opposition on March 3rd 2012

Tomorrow (March 3 2012) Mars will be closest to Earth. This event is known as opposition, since Sun and Mars will be in the two opposite sides of earth. Mars reaches it's opposition in about every two years. Have you ever tried to find Mars in the night sky? It is very easy to find during opposition. On 3rd March 2012 sunset it will be the brightest (and it even has a reddish hue to set it apart) star in the eastern sky. Mars will shine brightly in the constellation Leo. Here is a photo of Mars after sunset in the eastern sky (viewed from London,Ontario, Canada).

I took the screenshot from the best astronomy software Stellarium. You can also try google sky app in your anroid phone to find Mars easily in the night sky.

Find the number(s)

1. Given an array of 2n+1 numbers where n numbers are duplicated. Find the non duplicated number.

Ans: XOR all the elements. O(n)

2. Given an array of 2n+2 numbers where n numbers are duplicated. There are two numbers that are non-duplicated. Find the two non duplicating number.

Ans: This problem can also be solved in O(n). XOR all the numbers. If the the ith bit is set in the result, then divide the array into two sub sets A (where ith bit of all elements are 0) and B (where ith bit of all elements is 1). Now XOR the elements of A to get the first number and XOR the elements of B to get the second number.

3. An array A of n elements contain all elements from 1 to n, except that one is missing and one is duplicated. find both the numbers.

Ans:

If we do not have any duplication or missing elements then.
sum=1+2+3.........+n
sum=n(n+1)/2

squared_sum=1^2+2^2+3^2+..........+n^2
suqared_sum=n(n+1)(2n+1)/6


Now find sum(A) and squared_sum(A). if element a is missing and b is duplicated then

a-b=sum-sum(A)
a^2-b^2=squared_sum-squared_sum(A)

by solving the above equation we can find a and b.

Lunar Eclipse and Venus Transit on the same week.

Lunar Eclipse on 4 June 2012:

There will be a partial lunar eclipse on 4 June 2012.  Here is the map of the lunar eclipse. It will be visible in North America during moon rise (early morning).

Venus Transit on 5-6 June 2012:
There will be a transit of Venus on 5-6 June 2012. Here is the map of the visibility of the transit.

I must observe this transit, otherwise I will have to wait another 105 years (Next Venus transit will be on December 2117). It will be visible in North America before sunset.


Photos taken from NASA.

Stars and moon at my windows.

Here is a star trail photo that I took 2011.

Stars at My Window
----------------------------
Camera: Canon T1i (500D)
Number of Images: 445
Shutter speed: 30 Sec. for each Image
Focal Length: 18mm
ISO: 400
Aperture: f/6.3
Duration: 19 Mar 2011 11:15 pm - 20 Mar 2011 3:15 am
Location: London, Ontario (42.99705°N 81.27653°W)
Rotation of earth: About 60 degree or 1 Degree Radian.
Major Stars: Polaris (North Star), Vega and Kochab.
Images stacked by: Startrails

 

Here is the time elapse video.

Waxing gibbous moon at my window.

Reading list for technical interview.

• Cracking the Coding Interview: 150 Programming Questions and Solutions.
• The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company.
• Programming Interviews Exposed: Secrets to Landing Your Next Job.
• How Would You Move Mount Fuji? Microsoft's Cult of the Puzzle - How the World's Smartest Company Selects the Most Creative Thinkers.
• CareerCup.
• LeetCode.
• Project Euler.
• ACM.

Topics to prepare:

• Data Structures
• Array
• Linklist
• Tree
• BT, BST, B+ tree, B tree, Red Black tree, AVL tree
• Graph
• BFS, DFS, Dijkstra Algo etc
• Skip List
• Heap
• Hash Table
• Hash function, collision resolution
• Bit Manipulation
• Object Oriented Design
• Sorting and Searching
• Bubble Sort
• Quick Sort
• Heap Sort
• Bucket Sort
• Radix Sort
• External Sort
• Recursion
• Time complexity analysis of recursive functions
• MySQL
• C/C++
• Java
• Testing
• Testing real world objects (pen, car, elevator etc)
•  Brain Twisters
• Big Table / SimpleDB
• Data structure for Google/Amzon/Facebook etc
• MapReduce
• Hadoop
• How does Google process 24 petabytes (10^15 bytes) of data per day?
• Complexity Analysis
• Big O notation
• P, NP, NP Hard, NP Complete analysis, P!=NP analysis
• Keep in mind that interviewer sometime ask to solve problem X in O(nlogn) even if O(nlogn) solution does not exist.
• Approximation Algorithms
• How to solve "hard" problems using approximation
• Approximation ratio
•  Behavioral questions
• Why company X?
• Why position Y?
• Where do you want to see you in 5 years?
• What is you weekness/strength?
• Why we should hire you?
• Projects that you worked on.
• Prepare good questions to ask the interviewer at the end of interview
• Always study the company and if possible study the interviewer

Worlds best Illusion - Kokichi Sugihara

Here is an award winning optical illusion by my Masters Supervisor Prof. Kokichi Sugihara at the University of Tokyo.

Generating sorted random number

This is a very nice algorithm to generate random number in sorted order.

/*
generate n random number in rand (0,k) in O(n)
to compile this program we need to write gcc -lm Sorted_Random_Numbers.c
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<math.h>

int n=100;
int k=10;
int main()
{
    float sum=0.0,resutl[10000];
    int i;
    srand(time(NULL));
    for(i=1;i<=n;i++)
        resutl[i]=sum=sum-(log((float)rand()/(float)RAND_MAX)); // I think it can be done without using log also
    sum=sum-(log((float)rand()/(float)RAND_MAX));
    for(i=1;i<=n;i++)
        resutl[i]=(resutl[i]/sum)*k;
    for(i=1;i<=n;i++)
        printf("%8d\n",(int)resutl[i]);
}