Recovering a broken partition table

Issue

• Accidentally deleted a partition containing ext3/ext4 filesystem
• Parted rescue is unable to detect the filesystem
• Disk partition has been deleted and fdisk will not re-create it as before

# fdisk -lu /dev/sdb

Disk /dev/sdb: 2147 MB, 2147483648 bytes
67 heads, 62 sectors/track, 1009 cylinders, total 4194304 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0xfc9532cc

   Device Boot      Start         End      Blocks   Id  System