heuristican
BAN USER- 0of 0 votes
AnswersWrite a function that takes an array as an input and returns starting and ending indexes
- heuristican
within the array such that if we add elements from the starting and ending index we would get
maximum possible sum of any contiguous set of elements within that array.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer
1. Get ith pointer in the array.
2. Starting from (i+1)th pointer
2.1 check auxillary counter in order to decide continuation
2.2 if it's ith pointer's prev or next element.
2.2.1 If so increment counter.
2.2.2. Increment auxillary counter
struct DLL
{
int data;
struct DLL *prev;
struct DLL *next;
};
int findNumOfConNodes(struct DLL *a[], int size)
{
int connected = 0;
short fullConnected = 0; // both prev and next node is in the array
for (int i = 0; i < size; i++)
{
fullConnected = 0;
for (int j = i+1; j < size; j++)
{
if (fullConnected == 2) break; // no need to continue
if (a[i]->prev == a[j] || a[i]->next == a[j])
{
connected++;
fullConnected++;
}
}
}
return connected;
}
@adam Your point is good but I don't think it is recursion. Recursion is (mostly) implemented with stack DS but that doesn't necessarily mean every procedure implemented using stack is recursive. For example 5! = 5 * 4! is a recursive definition but if we implement a procedure that first pushes elements from 5 to 1 in a stack and then multiplying them by popping one by one wouldn't be considered as a recursive solution I guess. Due to the nature of SLL this problem fits very well to recursion and if recursion can not be used stack is a natural alternative. I think that's what made you think using stacks is equal to recursion. But as I said your point is good and it's possible for the interviewer not to like this solution.
- heuristican December 03, 2012
1. Sort arrival and departure times in increasing order.
- heuristican December 15, 20122. Starting from the first element in the sorted array add 1 when an arrival time is encountered, subtract 1 when a departure time is encountered. By this way find the max. number of people that are at the party at the same time which gives the min. number of glasses needed.
Time complexity of 2nd step is linear. 1st step depends on the sort algo chosen.