Greedy

Question 1

Activity Selection

Answer 1

the core of this program is to sort the start array and according to end array has to adjusted as well. Sort According to finish array.
Use Array.Sort(end, start) in c#

then check if the new element start is greater than the resultant end time present in the result set, add if greater.

TC O(nLogn)

Question 2

N meetings in one room

Answer 2

Same logic is in Activity selection
Sort according to finish time and add in result if start time of new element is greater than previous end time.

TC O(nLogn) due to sorting of arrays.

Question 3

Coin Piles

Answer 3

Calculate Minimum pile value
for each element in array calculate the diff between 
Minimum value and current element
if the difference is greater than k
increase counter value cnt = diff - k

TC : O(n)

Question 4

Maximize Toys

Answer 4

Sort the Array
While value is less the than the given sum add the elements in the array.

TC: O(nLogn)

Question 5

Page fault in LRU cache

Answer 5

One approach is to use hashmap

Create a HashTable
now there can be two condtions.
A. The number of elements is less than capacity
B. The number of elements is greater than capacity

In first case if the page is found in the cache
else increase the fault count and add into the table

in second case
if page not found in cache there is a page fault
so remove the first element in the table and insert into the table. increase the page fault count.

else. remove the element from its position and
add it to the table

TC O(n) since we process each element in the pages array

Question 6

Largest Number possible given the sum and number of digits

Answer 6

if sum is greater than 9 then add to the digits 9 and decrease from the sum 9
do this till m digits given
if sum is less than 9 then add the sum to the digits.
also check if s > 9m then number is not possible

TC O(m) m is the no of digits

Question 7

Minimize heights given k

Answer 7

First we sort the array
calculate the diff between highest and lowest
that is the current answer

next we calculate the big and small
arr[0] + k = small;
arr[n -1] - k = big;

for all the middle elements
if the number is in between this do nothing however
if big - subtract <= add - small
  big = subtract
else
 small = add

ans is the minimum between ans and big - small

TC O(nlogn) due to sorting

Question 8

Minimize the sum of product of two arrays with permutations allowed

Answer 8

idea is to sort both the array
then multiply the first element from first array and last element from the second array and so on

TC O(nlogn)due to sorting

Question 9

Shop in Candy Store given k

Answer 9

we need sorted array for this
For minimum amount
we take the the cheapest candies from the start and take highest candies from the back
n = n -k
similarly for maximum cost
we take candies from the end and take free candies from the beginning

TC O(nlogn)

Question 10

Geek collects the balls

Answer 10

idea is to check if arr1[i] < arr2[j] then add arr1 element else arr2 element to the sum
if equal check which contributes to the largest and use that and reset sum counters

finally add remaining elements and and to result

Question 11

Huffman Decoding

Answer 11

TBD

Question 12

Minimum Spanning tree

Answer 12

TBD