Problems Involving Arrays

From Algopedia
Revision as of 06:09, 29 September 2013 by Cristian (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Problems with Arrays

This is a small list of exercises involving sequences of numbers, for beginners. However, they require storage, thus they have solutions using arrays. Some of the very introductory problems may be solved without using arrays. They are here to familiarize you with arrays, so solve them using arrays, please.

Problems with arrays

Array Sum

Calculate the sum of all elements in an array.

Search Array

Given an array with n elements and an extra element e find the index in the array where element e appears first.

Minimum, Maximum

Find the value and position of the minimum and maximum elements of an array. For extra credit do it with 3 * n / 2 comparisons (worst case).

Minimum, Maximum Multiple

Find the value of the minimum and maximum elements in an array and the number of times they appear. Try to solve it using just one pass over the array.

Insert in Array

Given an array of n integers, another integer e and a position k, insert integer e in the array at position k.

Delete from Array

Given an array of n integers and a position k delete element at position k.

Reverse Array

Given an array with n elements reverse the order of elements. That means change the order of the elements in the array such that the last element is now first, the second to last is now second, and so on.

Rotate Array

Given an array with n elements, rotate the array to the left by one position. That means that, in the end, the second element should be the first, the third should be the second, and so on. The first element goes to the last position. Example: [1, 6, 2, 7, 4, 3, 2] goes to [6, 2, 7, 4, 3, 2, 1].

Rotate Array Multiple h

The same problem, but you have to rotate the array by k positions. The problem is hard(ish) when solved without an additional array and in linear time.

Binary Search

Given an array of numbers sorted in ascending order find the position of a given element.

Prime Numbers Generation

Given a positive integer n generate and display all prime numbers less than or equal to n.

Select Sort

Given an array of n numbers sort the array using selection. Sorting means that in the end the numbers should be in ascending order in the array. Using selection means going through the array, finding the maximum number, then swapping the maximum with the last element. Then reiterate with the array minus the last element. Repeat with smaller and smaller parts of the array.

Insert Sort

Sort an array using insertion. Take second element and insert it in A[1..1], making A[1..2] sorted. Then insert third element in A[1..2]. Keep inserting element on position k into sorted array A[1..k-1] up to k = n.

Moving Zeroes

Change an array of integers such that in the end all zero elements are the last ones in the array.

Set Array

Change an array into a Set array. Meaning, eliminate all duplicates, in place, without using another array.

GCD on Array

Compute the GCD (greatest common divider) of all elements in an array.

Conversion to another base

Given number n and base b, 1 < b < 17, convert and display its conversion to base b.

Eval Poly

Given a polynomial stored in an array, least significant coefficent first, and a number x evaluate the value of the polynomial in point x.

Substring Search h

Given two arrays, s (search array) and p (pattern array) find out how many time p appears in s. For instance, if s = [1, 2, 1, 2, 1, 3, 1, 2, 1] and p = [1, 2, 1] then p appears three times in s. The problem is hard only when solved in linear time.

Counting Overlaps h

Given two bracelets made of n black and white beads each, find the number of overlaps bead to bead such that overlapping beads have the same color. You can rotate the bracelets when setting them on top of each other. The problem is only hard when solved in linear time.

Array Comparison

Given two arrays of different length find their lexicographical order (meaning which one should appear first in the dictionary).

Set operations

Do the basic operations on sets: intersection, union, difference. Sets are stored as arrays with unique elements, in no particular order.

Sorted Sets Operations

The same requirement as the previous exercise, but this time the sets are stored as arrays with unique sorted elements

Bit Sets Operations

The same requirement as the previous exercise, but this time the sets are stored as arrays with binary elements. Array[i] is 1 if element i is part of the set, 0 otherwise.

Merge Arrays

Given two sorted arrays, build a third sorted array consisting of all the elements in the first two arrays. Duplicates are allowed.

Big Number Addition, Subtraction, Multiplication

Given two big numbers stored as arrays, one decimal digit per element, compute the sum, difference and product of these numbers.

Selection h

Given an array and a position in the array find the number that sits in that position when the array is sorted. The problem is hard when solved in worst case linear time.

Quicksort h

Sort an array using Quicksort method. Considered hard because it needs recursion.

Merge Sort

Sort an array using Merge Sort method.

Bicriterial Sort

Given two arrays of integers, E and W, where E[i] is just a number and W[i] is the weight of E[i], sort the arrays such that numbers in E are in ascending order and if two numbers in E are equal then the one with higher weight should come first.

Majority Element h

A majority element in an array a[] of size n is an element that appears more than n/2 times (and hence there is at most one such element). Given an array find if it has a majority element. The problem is somewhat hard when solved in linear time.



Legend:

  • h means hard. The problem is difficult.