Monthly Archives: September 2012

Check divisibility by 7

Posted on September 30, 2012 by chesterli0130

Given a number, check if it is divisible by 7. (You are not allowed to use modulo operator, floating point arithmetic is also not allowed.) Thoughts: A simple method is repeated subtraction. There is another interesting method (only works for … Continue reading →

Posted in Mathematics and Probability | 1 Comment

Make a fair coin from a biased coin

Posted on September 30, 2012 by chesterli0130

You are given a function foo() that represents a biased coin. When foo() is called, it returns 0 with 60% probability, and 1 with 40% probability. Write a new function that returns 0 and 1 with 50% probability each. Your … Continue reading →

Posted in Mathematics and Probability | Leave a comment

Write a function to get the intersection point of two Linked Lists.

Posted on September 27, 2012 by chesterli0130

There are two singly linked lists in a system. By some programming error the end node of one of the linked list got linked into the second list, forming a inverted Y shaped list. Write a program to get the … Continue reading →

Posted in Linked List | Leave a comment

Find a sorted subsequence of size 3 in linear time

Posted on September 27, 2012 by chesterli0130

Given an array of n integers, find the 3 elements such that a[i] < a[j] < a[k] and i < j < k in 0(n) time. If there are multiple such triplets, then print any one of them. Examples: Input: … Continue reading →

Posted in Arrays | Leave a comment

Largest Sum Contiguous Subarray

Posted on September 25, 2012 by chesterli0130

Write function to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum. Thoughts: Kadane’s algorithm Simple idea of the Kadane’s algorithm is to look for all positive contiguous segments of the array … Continue reading →

Posted in Arrays | Leave a comment

Find the maximum sum of a sub-matrix in a 2-D Array

Posted on September 25, 2012 by chesterli0130

Problem: Given an N*N matrix of positive and negative integers, write code to find the submatrix with the largest possible sum. Thoughts: We can use Dynamic Programming. From the above rectangle: ValD = area(point(0, 0) -> point(x2, y2)) ValC = … Continue reading →

Posted in Arrays | Leave a comment

Find median of two sorted arrays

Posted on September 24, 2012 by chesterli0130

Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample, a population, or a probability distribution, from the lower half. There are different conventions to take median of an array with … Continue reading →

Posted in Arrays | 1 Comment

Check if a binary tree is balanced.

Posted on September 24, 2012 by chesterli0130

A balance tree is defined to be a tree such that heights of the two subtrees of any node never differ by more than one. Method 1 Thoughts: Compute the heights of each subtree. Codes: Time Complexity: O(N^2) Method 2 Thoughts: We can … Continue reading →

Posted in Trees & Graphs | 1 Comment