Log In

Monthly Archives for September, 2013



How many pairs?

Posted on: September 20th, 2013 by
1

Suppose x[k] is a periodic sequence of length m with x[i]=i for 0<=i<=m-1. Similarly y[k] is a periodic sequence of length n with y[i]=i for 0<=i<=n-1 Find the size of the set \{ (x[i],y[i]) : 0\le i \le \infty \}

Skyscraper

Posted on: September 19th, 2013 by
2

In the figure below, every cell represents a building. The number in the cell represents the height of the building. Taller buildings obscure shorter buildings. A number at the end of a row or column indicates the number of buildings that are visible when viewed from that location. Fill numbers from 1 to 4 in all the cells so that each row and column contains Continue reading the story "Skyscraper"

Find the area

Posted on: September 18th, 2013 by
4

In the figure below, the numbers marked represent the area of the shaded region. Find the area of the region indicated by a '?'. You guessed it right: the figure is a rectangle. geom_9_16

Segregation

Posted on: September 17th, 2013 by
Comments Disabled
Consider an n x n grid. 30% of the cells are colored green and another 30% are colored blue at random. The remaining cells are empty. It is preferred that each colored cell has 3 neighbors (of the 8 neighbors) of the same color. Colored cells which do not have 3 same color neighbors are called "wrong". The following process occurs: At each time step, Continue reading the story "Segregation"

Arrange cards

Posted on: September 16th, 2013 by
Comments Disabled
You have m cards numbered 0 and n cards numbered 1. Your goal is to arrange them so that the sequence can be written as a concatenation of K strictly increasing sequences. For example, the sequence 0110100101=(01)(1)(01)(0)(01)(01) contains 6 strictly increasing sequences. Given m,n and K, count the number of sequences formed by using all the (m+n) cards that can be decomposed into exactly K Continue reading the story "Arrange cards"

3 or less from 7

Posted on: September 15th, 2013 by
7

An anthropologist came across a very interesting native custom that is performed once a year. The reason behind the custom is so the chief may collect the yearly taxes which are collected from every male in the community. The taxes are in the form of grain. All men gather in the center of town to pay a number of pounds of grain equal to their age Continue reading the story "3 or less from 7"

Two points at distance d

Posted on: September 14th, 2013 by
1

All points in a plane are colored either red, blue or green. Given any distance d, show that there exist two points of the same color that are distance d apart. via Mike Earnest, here

Lazy walker

Posted on: September 14th, 2013 by
Comments Disabled
You are standing in the middle of a row of countably infinite doors. You have a key that fits in exactly one of the doors. You must try each door once until you find the door that the key fits into. Find a strategy that minimizes the worst case X/N where X is the distance you travel and N is the distance of the door Continue reading the story "Lazy walker"

Subarray of maximum sum

Posted on: September 13th, 2013 by
Comments Disabled
A Google interview question: Given an array of n elements containing both positive and negative elements, find the sub-array with the largest sum. Note: A sub-array with start s and end e are the elements a[s], a[s+1], .... a[e]. - via My Tech Interviews

An algorithm puzzle

Posted on: September 12th, 2013 by
2

Given a binary sequence of n bits, you may in 1 operation either flip the i-th bit for some i or flip the first i bits for some i. Write an O(n) algorithm to find the minimum number of operations required to convert the given sequence in to an all 0 sequence. A highly simplified version of a problem in Topcoder algorithms contest.

{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}