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
Monthly Archives for September, 2013
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"
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"
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"
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"
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
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"
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
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.