# Programming Problems 3

October 2, 2009 Leave a comment

**1. Zigzag**

A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

**2. Balanced Brackets**

Given a number n, print all possible combinations of n pairs of braces that are balanced

Input:1

Output:

()

Input:2

Output:

(())

()()

Input:3

Output:

((()))

(()())

(())()

()(())

()()()

**3. Find 2 missing numbers **

Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers in O(n)

**4. Find all missing numbers**

Given an array of size n. It contains numbers in the range 1 to n. Find the numbers which aren’t present.

**5. Modified Maximum Sum subsequence**

Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)

## Recent Activity