Algorithm tasks

This page contains a collection of various algorithms which you should be able to independently create a solution for. You will find algorithm tasks with similar complexity in the test. Some of the algorithms on this page will be completed within various lab tasks and homework.

Reminder!

  1. The algorithm shouldn’t not contain language-specific aspects. Algorithms should be programming language agnostic. Implementation language is up to the developer.
  2. You are not expected to be able to program all of the tasks on this page by the time of the test – e.g. files and strings will be covered later. However you should be able to devise the algorithm how to solve it.

Algorithm 1: Food scale

  • Create an algorithm that mimics the behavior of the food scales in grocery stores
  • Your inputs are the weight of the produce and the product code.
  • You must find the product based on the code, it’s price per kilo and the total cost.
  • Solution must handle various errors that may occur with inputs.

Algorithm 2: ATM

  • Your task is to mimic the behavior of an ATM.
  • Client wishes to withdraw cash from an ATM and will enter the amount manually.
  • The ATM currency is euro and it carries all euro banknotes in use in Estonia.
  • User entered withdrawal amount must be verified.
  • Give out the banknotes with the intention of giving the least possible amount of banknotes.
  • E.g.: 537€ -> error; 195€ -> 1×100€ + 1×50€ + 2×20€ + 1×5€

Variation 1: Small banknotes

  • User will select small banknotes from the menu.
  • ATM has limits on giving out small notes. If the user entered amount exceeds the amount possibly by the smallest note, a larger note will be given instead.
  • Limits
    • 5€ euro notes for 25€
    • 10€ euro notes for 50€
    • 20€ euro notes for 100€
    • 50€ euro notes for 500€
    • 100€ euro notes for 1000€
    • The rest will be given as 200€ banknotes.
  • Example:
    • 25€ -> 5×5€
    • 30€ -> 1×10€ + 4×5€
    • 35€ -> 1×10€ + 5×5€

Variation 2: Equal distribution

  • The banknote counting algorithm will try to create an equal distribution of notes. The difference between the most and least used should must be 1.
  • Example:
    • 40€ -> 1×20€ + 1×10€ + 2×5€
    • 45€ -> 1×20€ + 2×10€ + 1×5€
    • 1500€ -> 2×500 €+ 1×200€+ 2×100€ + 1×50€ + 1×20€ + 2×10€ + 2×5€
    • 2000€ -> 2×500 €+ 3×200€+ 2×100€ + 2×50€ + 3×20€ + 3×10€ + 2×5€

Algorithm 3: Reordering negative and positive numbers

  • You are given an array of N integers as input.
  • Reorder the numbers in the array in such a way that negative numbers are in the beginning of the array, followed by the positive numbers.
  • Do not change the order of appearance
  • Example:
    Input: 5, -7, -87, -221, 7, 97, 1, -5, 5
    Result: -7, -87, -221, -5, 5, 7, 97, 1, 5

Variation 1: The same rules apply for the number 0 as was for the positive integers.

Variation 2: All occurrences of the number 0 will be removed. The resulting array may be shorter.

Variation 3: All occurrences of 0 will be pushed to the end of the array

Algorithm 4: Sorting facility

  • The company has 2 small warehouses (warehouse A and B) and a larger sorting facility that they operate in. The packages arrive in the smaller warehouses and are then sent over to the sorting facility.
  • All packages are given as integers, which represent the weight in kilograms.
  • All packages are put together when they arrive in the sorting facility. Once there, they are sorted in a way that when they exit, the heaviest packages leave first.
  • Example:
    • Warehouse A: 7, 59, 1, 93, 15, 27, 48, 6
    • Warehouse B: 9, 3, 1, 94
    • Exit order from sorting facility: 94, 93, 59, 48, 27, 15, 9, 7, 6, 3, 1, 1

Algorithm 5: Package ratios

  • Read product weights and tracking numbers from a file
  • Find and output the extreme values (the heaviest and lightest package), followed by the list of packages and their ratios to the extremums.  The list must include tracking codes alongside ratios.
  • Example:
    • Weights: 6, 7, 2, 10, 4
    • Tracking codes: EE790A1, EE001A1, EE117CA, EE000A2, EE01010
    • Extreme values: minimum 2 kg, maximum 10 kg
    • Package EE790A1 ratios are 3.0 and 0.6
      Package EE001A1 ratios are 3.5 and 0.7
      Package EE117CA ratios are 1.0 and 0.2
      Etc.

Algorithm 6: Finding the lowest possible number base

  • User enters 4-character strings from the keyboard
  • Find the lowest possible number base from the selection: base-2, base-16. The ones that don’t match any possible number bases from the list must also be displayed separately.
  • Example: 0110, AZY1, 001F, 0101, 0Y24

Algorithm 7: Converting decimal numbers to the desired number system

  • User enters decimal integers from the keyboard until they insert the number 0, which terminates the input.
  • User will enter the desired new number base from the keyboard.
  • All numbers will be converted to the new base and printed alongside the original input.

Algorithm 8: Converting binary numbers

  • Binary numbers are read from the file. One number is 4 bytes long.
  • All read numbers will be converted to hexadecimal.
  • The results are printed into a new file. They are printed side-by-side with the binary numbers, one pair per line.

Algorithm 9: Date validation

  • 8-digit integers are read from a file. Each of them represents a date.
  • The dates are based on the Gregorian calendar.
  • Validate and output which of the dates exist and which do not.
  • Make sure to check for leap years!
  • Example: 27041998, 29022003, 58042013, 04132013

Algorithm 10: Finding results from a matrix

  • Create a matrix  A(m * n) , where n > 5, m > 5. Matrix will be composed of randomly generated integers -100 ≤ ai ≤ 100.
  • Find the following results
    • The sum of negative numbers from the last row
    • The sum of positive elements in a column. Find one sum per column from all columns to the right of the third column.
    • The product of negative elements in a row. Find one product per row from rows that are higher than the third row.
  • Print all of the results you found.

Algorithm 11: Printing a matrix, column by column transposed

  • User enters a matrix A(m * n)
  • The following conditions must be met > 5, m > 5
  • The contents of the matrix A will be copied to the vector B, one column at a time.
  • The matrix will be printed on the screen only through the vector B. One column at a time, transposed as a row.

Algorithm 12: Rate of occurrence of characters and number of sentences

  • The text (e.g. a book or a newspaper article) is read from a file.
  • Find and print the rates of occurrence
    • Your algorithm should be case-insensitive (must ignore capitalization).
  • Find and print the number of sentences in the text. A sentence can end by a point, exclamation or a question mark.

Algorithm 13: Character replacement

  • A novella is read from a file.
  • Make the following replacements in the text:
    • a -> u
    • u -> a
  • Print the number of replacements made on the screen.
  • Update the novel in the file.