Activity selection problem greedy algorithm Assume that you are an administrator who is in charge of a conference room equipped with some expensive telepresence system. Different employees or groups of employees need to have access to the conference room but they can not use the telepresence system at the same time. Every day employees who
Maximal independent set problem You have a set of radio stations all having the same transmission frequency. Signals from adjacent stations interfere with each other which causes data loss. We need to choose the largest set of stations that can operate at the same time without data loss. Assume the list of stations is represented
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. (1) Assuming (m) is much smaller
Problem You have the following function signature int Contains(char* s1, char* s2, int n1, int n2) where s1, s2 are two strings and n1, n2 are their respective lengths. The function should return 1 if the s1 contains s2 otherwise it returns 0. For example if s1 = abcdefg and s2 = acg then it
Problem Write code to simulate the SQL statement “Select unique emp_name from employees” Solution Assuming we have an array of employee names we need to write a function that prints the unique employee names in the array. We can use a built in hash table for that matter. Just hash all names then print the
Problem Write a C++ function to check string for repeated characters. Algorithm Using brute force we can start with the first character then compare it to the rest of the characters. If we can find a match then the string does have repeated characters otherwise we move to the next character and so on. If
Problem Write a C++ function that takes two strings of the same length as input and return true if the strings are anagrams otherwise returns false. Two strings are anagrams if they are permutations of each other ignoring spaces and capitalization. For example “CAT” and “ACT” are anagrams. Assume the input strings have small letter
Merge sort c++ string Given a character string in small letter case. Write a C++ function to sort the string using Merge Sort Algorithm. Merge sort c++ implementation Merge sort is a popular sorting algorithm that runs in O(nlogn). It uses divide and concur technique so it keeps dividing the input array into two halves
Problem Given a square two dimensional integer array of size (n). Both rows and columns are sorted in ascending order. Give an algorithm to search for a particular element in the array in O(Log(n)) time complexity. Assume the array has no duplicates. Solution This problem is a follow up from the previous post. Modified binary
Problem Given a square two dimensional integer array of size (n). Both rows and columns are sorted in ascending order. Write an efficient code to search for a particular element in the array. Assume the array has no duplicates. Solution A brute force solution is to loop through the entire array until we find the