Palidromes

Given a string find the minimum number of characters to be inserted for converting a string into a palidrome

A Collection of Bit Programming Interview Questions solved in C++ (Volume 3)

A Collection of Bit Programming Interview Questions solved in C++ (Volume 3)

Palindrome String

Compute the longest palindrome string

Dynamic Programming -

Given an array of integers find the longest bitonic sequence

Coin change

Given  n dollars, how many different ways there are to make the change into a set of coins

A Collection of Dynamic Programming Interview Questions Solved in C++ (Volume 1)

A Collection of Dynamic Programming Interview Questions Solved in C++ (Volume 1) 

Binomial coefficient

Compute the binomial coefficient

Catalan numbers

Compute the catalan numbers

Integer Knapsack

A knapsack has max capacity C and there are n items each with weight wi, and value vi. Maximize the value in the knapsack without exceeding its max capacity

Jump stairs

There ia stair with n steps. You can climb either one step or two steps at a time. How many different ways there are to climb the stair?

Edit distance

Compute the edit distance

Dice

Given a dice count how many ways to get sum s

Palindromes

Given a string find the minimum number of characters to be inserted for converting the string into a palindrome.

Bridge matching

N cities are on the northern bank of a river and n cities are on the southern bank. You can build a bridge only between cities with the same number

Sum subset

Given an array of integers of size n, partition it in such a way that the two subsets have equal sum s.

Partition set

Partition a multiset S of positive integers into two subsets S1 and S2, such that the sum of the numbers in S1 equals the sum of the numbers in S2

Segment partition

Given a segment of integer length n, cut into different integer parts in such a way to maximize the product of the lengths of all parts

Cutting a rod

Given a rod of length n and a vector of prices for different lengths, cut the rod for maximizing the gain

Max matrix 0/1

Given a matrix consisting only of 0 and 1 find the maximum size square submatrix with all 1.

Matrix parentization

Given a set of m matrices find the most efficient way of multiplying them

Max submatrix

Given a matrix of size n x n fine the maximum sum rectangle

BST and dynamic programming

Given a binary search tree, find the size of the largest independent set of nodes

Games of coins

A set of coins are aligned and two players can pick one coin from each side in turn. Maximize the value of the coins picked by the first player

Maximum value contiguous subsequence

Given an array of real numbers, find a contiguous subsequence with max sum S

Stock prices

Given an histogram array of unsigned integers encoding the price of a stock title during previous year, compute the area for the largest rectangle contained in this histogram

Ship battle

Given a matrix M and an array V match the array in the matrix

Scheduling

Given n jobs, each one with a processing time t1 a profidt p1 and a deadline di maximize the profit

Boolean parentesization

Given a boolean expression of AND, OR, XOR, TRUE, FALSE find the number of ways to parenthesize and evaluate to true

Balanced partition

Given an array of integers between 0 and M divide the integers into two sets such that the difference of their sum is minimized

WEIGHTED DOMINANT SET OF INTERVALS

WEIGHTED SHORTEST PATHS WITH COST ASSOCIATED TO THE NODES

FIND THE FLOW NETWORK USING FORD–FULKERSON’ALGORITHM

FIND THE FLOW NETWORK USING FORD–FULKERSON’ALGORITHM

ASSIGNMENT MATCHING PROBLEM

FIND AN EULERIAN CIRCUIT

Egg drops

Given k eggs and n floors in a building, find the minimum number of trials required to determine the lowest floor from which when we drop an egg it does not break. Provide a Dynamic Programming solution.

Bridge Matching

n cities are sitting on the northern bank of a river and n cities are sitting on the southern bank. You can build a bridge only between cities with the same number. Provide a dynamic programming solution.

LBS

Given an array of integers find the longest bitonic sequence. Provide a dynamic programming solution

Box Stacking

Given a set of 3d boxes compute the largest stack of boxes. A box can be stacked only on the top of another box with lager base. Provide a dynamic programming solution for stacking the boxes

Boolean Parentization

given a Boolean expression of and, or, xor, true, false, find the number of ways to parenthesize and evaluate to true. Provide a dynamic programming solution

Box Stacking

Given a set of 3d boxes compute the largest stack of boxes. A box can be stacked only on the top of another box with lager base.

Maximum value contiguous subsequence

given a real numbers’ array find a contiguous subsequence with max sum. Provide a dynamic programming solution

Balanced partition

given an array of integers between 0 and M divide the integers into two set such that difference of sums is minimized. Provide a dynamic programming solution

Scheduling

given n jobs each of which with a processing time, a profit and a deadline maximize the profit. Provide a dynamic programming solution

Print the binary representation of an unsigned

compute whether or not an unsigned number is a power of two

Find the position with only one bit set in an unsigned

given an unsigned int swap odds and even bits

Multiply two binary strings representing the value of two integers

Add two numbers without using arithmetic operators

Generate all the bit patterns from 0 to 2n-1 such that successive patterns differ by one

Chapter 3 is done

This chapter is about Graph computation and there are classical algorithms (BFS, DFS, MST). MST is implementing the classical Prim's algo but using Fibonacci heap available in Boost. Here you find the first version of the graph code

Writing a programming / algorithmic book

I wanted to take on a new challenge and start writing a book about algorithms and design. The intent is to have Simplicity by Design (SD): every Chapter is a collection of 15-30 questions, followed by the solution, followed by a C++ code snippet which can be easily re-used.

So far, I have drafts for 3 chapters: bit programming, dynamic programming, and graphs. Here an example of graph code with very classical questions: implement a graph, implement bfs, implement dfs, implement topological sort, I already have code for other graph problems.  Dynamic programming has more mathematical content and I will publish an excerpt next weeks.

A number of questions:

1. Should I publish code for public review? If so, can i still use it for the book?
2. Should I publish questions for public review?

I think that this will be one of my side projects off work for the next year or so.

Create your Team

you have a pool of players. Each player ha a set of skills. For creating a team you need to hire the minimum number of players who have together a predetermined set of skills

P0 - what people are saying

Here some previous postings

• PageZero and Ted
• Project PageZero
• What they've said about new Knowledge Suggestions @ Bing

Find i = n^3 + m^3

how can a number be expressed as sum of two cubes?

52 cards

You have 52 cards half of them are red and half of them are black. You have a given amount of money M and every time you can bet k < M money. If you predict the right colour you will win 2k money, if not you will loose k. What is the best strategy?

Sort lexicographically an array of strings in C++ and in C

Create a complete C++ class for bitmaps

Conflits in k keywords

A keyword is made up of n bits. Given k keywords generated with uniform probability what is the probability to have collision? Provide an evaluation and write the code.

Radix Sort -

Write a radix sort implementation in C++

PageZero and Ted

I enjoyed attending Ted and give a talk about PageZero. While I was listening a number of very inspiring talks, I asked to myself would this PageZero really help users?

So I started to write {Ted} and immediately PageZero suggested {Ted Talks} as first suggestions and {Speakers} Speakers as su-bintent. That's exactly what I was looking for!!! I am impressed.

Then, I thought and what if I was interested in the Movie? PageZero predicted that potential choice too. Kind of cool, no?

Buying with constrains

You have a bag with capacity C and can insert items with value wi which will occupy space si. You cannot exceed the capacity. Write an algorithm in C++

Project PageZero

SearchBox never changed since 1993, when the first search engine was created. Bing is disrupting the box by bridging the gap with the World of Entities. Names, Web Sites, and Generic Entities are directly accessible and understood as soon as you type.

http://www.slideshare.net/antoniogulli/project-page-zero-bi 

Given a stream of integers, select one integer with uniform probability

k balls, n floors

There is a building with n floors and you have k balls.  Balls are identical and when you drop them they can break or not. You need to figure out the highest floor of the building an egg can be dropped without breaking.

In a network of n nodes elect a leader

what is the algorithm you would suggest?

In a stream of integers find the ones that appears at least k times

Optimal in space and time

Given a set of intervals (i, j) overlapping find the maximun number of those overlapping

Design Patterns : C++ full collection of Gamma's patterns

Design Patterns : C++ full collection of Gamma's patterns

Full collection of Gamma's patterns in Full collection of Gamma's patterns in c++: 

1. Creational: Abstract Factory, Builder, Factory, Prototype, Object Pool, Singleton,
2. Structural: Adapter, Bridge, Composite, Decorator, Facade, Flyweight, Proxy patterns,
3. Behavioral: Chain of Responsibility, Command, Iterator, Mediator, Memento, Observer, State, Strategy, Template, Visitor, and Interpreter

Capped payrolls

In a company there are different payrolls pi, and we want to find a cap C such that the total amount of money paid is not above a maxim M. How can you determine C?

Int 16 bit - compute the sqrt

Given an integer in 16 bits compute the sqrt

Given an array of sorted lists merge them

in optimal time and space

Given a list find the k largest integers

Count all the safe configurations of queens on a chessboard

Given a BST and two nodes find the common ancestor

How can you detect the endianess of your computer?

Given an array of integers longest non decreasing

Compute and print the longest non decreasing sequence of integers

Given a list of words, detect the longest word

made by concatenating other words in the list

Given a stream of integers select k random entries

Given two integers select the maximum with no comparison

(10^9)!

count the number of trailing zeros

Given two numbers a and b

Swap them with no temp variable. How many way  do you know for achieving that?

What is the complexity for computing x^n

What is the probability of dropping m balls in the same bin?

Suppose there are n bins

Load balancing

We have a set of task i={1, ..., n} and each one has a cost b_i, how can we assigned to m servers so that the load is balanced?

Generate all the permutations of a string

Given an array of 1 million entries

Pick the smallest int.

Implement a class for smart pointers

Triangle and Ants

On a triangle, there are 3 ants what is the probability that they collide when they move

In a number of 64 bits

Swap odd and even bits.

What is wrong with this code?

string FindAddr( list emps, string name )
{
  for( list::iterator i = emps.begin();
       i != emps.end();
       i++ )
  {
    if( *i == name )
    {
      return i->addr;
    }
  }
  return "";
}

generate strings

Write a program that generates from the string "abcdefghijklmnopqrstuvwxyz{" the following: a bcb cdedc defgfed efghihgfe fghijkjihgf ghijklmlkjihg hijklmnonmlkjih ijklmnopqponmlkji jklmnopqrsrqponmlkj klmnopqrstutsrqponmlk lmnopqrstuvwvutsrqponml mnopqrstuvwxyxwvutsrqponm nopqrstuvwxyz{zyxwvutsrqpon

Add two integers without using '+'

How can you add two integers without using + operator

isNumeric(string s)

write the method

Swap two integers

with no temp. How many ways do you know?

how many ways do you know to swap variables?

without using temp vars?

Use a dictionary

Given a string like "thisisalongstringwithmisakenoten" and a dictionary of words, split the string so that the number of non matched words are minimized. Try to optimize the code

Implement a smartpointer class

using templates in C++

Smartpointer s1(T * ptr)
Smartpointer s1(Smartpointer & s2)
and the assigment
s1=s2

Allocate a matrix of ints reducing the fragmentation