Problem Given an array of n-1 unique integers. Each element in the array is an integer between 1 and n. Write a program to print the missing number in the array Solution To clarify this problem let us take a simple example. Assume n = 3 so the array consists from two elements only. Here

Problem Write a recursive function to compute (x) to the power of (n) where (x) and (n) are positive integers. Your algorithm should run in O(logn) time complexity Solution Use divide and conquer technique. For even values of (n) calculate x^(n/2) and return the square of that as the final result because x^n = x^(n/2)

Problem Given an array of positive integers. Find the n(th) largest element in the array. Solution Sort the array in decreasing order then loop through the sorted array while counting unique elements then stop when the count is equal to (n). In the code below we will assume the array is already sorted. You can

Divide and conquer largest two numbers problem Given an array of integers. Find the first and second largest elements in the array. Use divide and conquer technique. Divide and conquer algorithm largest two elements Simply divide the array into two halves then find the largest two elements in each half. At the end you need

Greedy algorithm interval scheduling problem An event starts at 9AM and finishes at 6PM. Several volunteers have signed to the event each providing a time period during which they can help. We need to cover the entire time of the event (9AM-6PM) with the least number of volunteers. Assume the next volunteer in line can

Optimized version of bubble sort Bubble sort is a slow comparison based sorting algorithm. Can you suggest one way to optimize it. Optimized bubble sort complexity and solution Bubble sort works by repeatedly visiting all elements of the list to be sorted comparing each pair of adjacent elements and swapping them if they are not

Most repeated character string Given a string of characters find the character that is repeated the most. Solution This is almost the same as the First None Repeating Char problem. We are going to borrow the same code however we will slightly modify it. The only code that we need to add is calculating the

Problem Develop an algorithm to print the first none repeating character in a string for example the first none repeating character in the string "baby" is "a" Hash character in string This is a typical interview question. A better solution to solve this problem in linear time is to use a hash table on the

Find non repeating character string Develop an algorithm to print the first none repeating character in a string for example the first none repeating character in the string "baby" is "a" Algorithm A brute force method requires us to use two nested loops for character comparison. The moment we find a match we break the

Running time of nested loop Given the following pattern matching algorithm which decides whether there is an occurrence of a pattern of size (m) in a text of size (n). The algorithm compares the pattern in a given location in the text checking all characters from left to right. //Includes #include <iostream> //STD using namespace