Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is, Table[i][j] ≤ Table[i][j + 1], Table[i][j] ≤ Table[i + 1][j]

# Author Archives: 1337c0d3r

# Searching a 2D Sorted Matrix Part II

Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is, Table[i][j] ≤ Table[i][j + 1], Table[i][j] ≤ Table[i + 1][j]

# Searching a 2D Sorted Matrix Part I

Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is, Table[i][j] ≤ Table[i][j + 1], Table[i][j] ≤ Table[i + 1][j]

# Excel Sheet Row Numbers

Given the sequence S1 = {a,b,c,d,…,x,y,z,aa,ab,ac…. } and given that this sequence corresponds (term for term) to the sequence S2 = {0,1,2,3,….}. Write code to convert an element of S2 to the corresponding element of S1.

# Print All Combinations of a Number as a Sum of Candidate Numbers

Given a target number, and a series of candidate numbers, print out all combinations, so that the sum of candidate numbers equals to the target.

# Serialization/Deserialization of a Binary Tree

Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called ‘serialization’ and reading back from the file to reconstruct the exact same binary tree is ‘deserialization’.

# Saving a Binary Search Tree to a File

Describe an algorithm to save a Binary Search Tree (BST) to a file in terms of run-time and disk space complexity. You must be able to restore to the exact original BST using the saved format.

# How to Pretty Print a Binary Tree

Have you ever thought of pretty-printing a binary tree?

# Printing a Binary Tree in Zig Zag Level-Order

Given a binary tree, print out the tree in zig zag level order (ie, from left to right, then right to left for the next level and alternate between). Output a newline after the end of each level.

# Binary Tree Level-Order Traversal Using Depth First Search (DFS)

Given a binary tree, print out the tree in level order (ie, from left to right, level by level). Output a newline after the end of each level. Breadth First Search (BFS) is not allowed.

# Printing a Binary Tree in Level Order

Given a binary tree, print out the tree in level order (ie, from left to right, level by level). Output a newline after the end of each level.

# Determine if a Binary Tree is a Binary Search Tree (BST)

Write a function isBST(BinaryTree *node) to verify if a given binary tree is a Binary Search Tree (BST) or not.

# Detecting a Loop in a Singly Linked List

Given a singly linked list, find if there exist a loop.

# Splitting Linked List

Given a list, split it into two sublists — one for the front half, and one for the back half. If the number of elements is odd, the extra element should go in the front list. So FrontBackSplit() on the list {2, 3, 5, 7, 11} should yield the two lists {2, 3, 5} and […]

# Number of 1 bits

Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has.

# Fun with Bit Operations

What does the following function mystery() do?

1 2 3 |
bool mystery(unsigned int x) { return !(x & (x-1)); } |

# Problem C: Theme Park Solution (Google Code Jam Qualification Round 2010)

Read the question here from GCJ Qualification Round 2010:» Problem C: Theme Park

# Problem B: Fair Warning Solution (Google Code Jam Qualification Round 2010)

Read the question here from GCJ Qualification Round 2010:» Problem B: Fair Warning

# Problem A: Snapper Chain Solution (Google Code Jam Qualification Round 2010)

Read the question here from GCJ Qualification Round 2010:» Problem A: Snapper Chain

# Google Code Jam Qualification Round 2010

Google Code Jam has begun and there is still time to compete, so register and start coding now if you have not! » Participate in Google Code Jam Now!