som
BAN USERThe min/max heap approach is good but , we can think it other simple way only. As this is the streaming and need to store only top 5 values at any given point of time, we can have a double array of 6 element which will store the values while read each stock data in a loop.
Time complexity should be O(nk) where K is limit, here 5.
C++ solution:
// Here size is streaming data size, limit is to be passed as 5
double* topFiveElement(double* Data, int size, int limit)
{
double *ptr = new double[limit+1];
for ( int index = 0; index <= limit; index++)
{
ptr[index] = 0.0;
}
// Read each value from stream
for( int i =0 ; i < size; i++)
{
// store it into a predefined array in decending order. Iterate at max five times only
ptr[limit] = Data[i];
for( int j = limit; j > 0; j--)
{
// Swap values if right element is larger
if( ptr[j] > ptr[j-1])
{
double tmp = ptr[j-1];
ptr[j-1] = ptr[j];
ptr[j] = tmp;
}
else{
// if the above condition does not staisfy exit the loop
break;
}
}
}
return ptr;
}
C/C++ based simple solution for in place duplicate char removal. An extra space has been used to store ASCII value of char.
void replace( char* S)
{
bool cArray[256];
for ( int index =0; index < 256 ; index++)
{
cArray[index] = false;
}
int start = 0;
char * ptr = S;
while ( *ptr != '\0')
{
if(! cArray[*ptr] )
{
cArray[*ptr] = true;
S[start] = *ptr;
start++;
}
ptr++;
}
S[start] = '\0';
cout <<"OUT:"<< S<<endl;
}
It can be done through inorder traversal. Check the left branch and update the value to the parent node( left branch sum + parent node). Python based solution.
class BTree:
def __init__(self, value):
self.left = None
self.right = None
self.key = value
# get leftsum
def leftSum(root):
if root == None:
return 0
root.key += leftSum(root.left)
return root.key + leftSum(root.right)
# Crate root Node
root = BTree(10)
root.left = BTree(5)
root.right = BTree(6)
root.left.left = BTree(3)
root.left.right = BTree(2)
root.left.right.left = BTree(1)
leftSum(root)
Python solution time complexity O(N)
def firstOccurrence(S):
dict = {}
Array = []
print "First Occurrence of Char:"
for index in range(len(S)):
if S[index] not in dict.keys():
dict[S[index]] = 1
Array.append(S[index])
else: # If multiple occurrence then set value to -1
dict[S[index]] = -1
#
for elm in Array:
if dict[elm] != -1:
print elm
break
S="californiac"
firstOccurrence(S)
This can be checked using BFS algorithm only.
It can be checked in tow ways, one checking the parent count for each node in a graph. In case of tree parent count for each node should not be more than one. Any node having more than one parent will determine it is a graph not tree.
Other way is checking the total number of times all the nodes in a graph has been checked . In case of tree it should not be more than twice of number of vertices.
// Iterative approach , Time complexity O(V+E)
bool Graph::BSF( int startVertex)
{
bool *enqueuedNodeList = new bool[numberOfVertices];
// Default set all vertices as 0
for ( int index = 0; index<numberOfVertices; index++ )
{
enqueuedNodeList[index] = 0;
}
queue<int> Q;
Q.push(startVertex);
enqueuedNodeList[startVertex] = 1; // Because first eelemnt has been pushed into the queue
//int nodeCount = 1; // for the first node as that has been enqueued
while (! Q.empty())
{
int v = Q.front();
Q.pop();
cout<<"Visited:"<<v<<endl;
int visitCount = 0;
for( auto & node : AdjacencyList[v] )
{
//nodeCount++;// Increament node
// Is node already enqued in the Q
if( ! enqueuedNodeList[node] )
{
enqueuedNodeList[node] = 1;
Q.push(node);
}
else
{
// Checking the parent, more than one parent is graph
// Check if visited adjacent node more than one
if (++visitCount == 2 )
{
return false;
}
}
}
}
// Delete explored
delete [] enqueuedNodeList;
/*cout <<"Node Visit Count:"<<nodeCount<<endl;
if ( nodeCount > 2 * numberOfVertices)
{
return false;
}*/
return true; // Its tree
}
C++ Solution
struct Node {
string data;
Node *next;
Node *prev;
};
Node* createNode(string& A, Node *prev, Node* next);
void display(Node* head);
bool isPalindrome(Node* firstNode, Node* lastNode);
void destroyList(Node* first);
int main(int argc, char** argv)
{
string A [] = {"A", "B","B","A"};
int size = sizeof(A) / sizeof(A[0]);
// Head Node
Node * firstNode = NULL;
Node * lastNode = NULL;
for ( int index=0; index <size ; index++ )
{
if ( firstNode == NULL )
{
firstNode = createNode(A[index], NULL, NULL);
lastNode = firstNode;
}
else
{
lastNode->next = createNode(A[index], lastNode, NULL );
lastNode = lastNode->next; // Move to the next node
}
}
display(firstNode);
// Check is plaindrome?
cout<<"Is Palindrome:"<< isPalindrome(firstNode, lastNode) <<endl;
display(firstNode);
return 0;
}
Node* createNode(string & A, Node* prev, Node* next)
{
Node* newPtr = new Node();
newPtr->data = A;
newPtr->next = next;
newPtr->prev = prev;
return newPtr;
}
// Is Palindrome
bool isPalindrome(Node* firstNode, Node* lastNode)
{
while( firstNode != lastNode)
{
if ( firstNode->data != lastNode->data)
{
return 0;
}
firstNode = firstNode->next;
lastNode = lastNode->prev;
}
return 1;
}
Should be pretty easy. And need to start from bottom left corner of the matrix
int main()
{
int matrix[4][4]={ {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 1, 1, 1},
{0, 1, 1, 1},
};
int row = 3 ;
int col = 0;
int zero = 0;
while( col < 4 )
{
if( matrix[row][col] == 0 )
{
zero += ( row + 1 );
col++;
}
else
{
row--;
}
}
printf("Zero:%d\n", zero);
}
C- Implementation
int main()
{
int matrix[4][4]={ {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 1, 1, 1},
{0, 1, 1, 1},
};
int row = 3 ;
int col = 0;
int zero = 0;
while( col < 4 )
{
if( matrix[col][row] == 0 )
{
zero += ( row + 1 );
col++;
}
else
{
row--;
}
}
printf("Zero:%d\n", zero);
}
I think it is easy implementing it in python.
def get_average_rating( arrayDict ):
average_rating = 0
hotel_id_rating = {}
for each_record in arrayDict:
# Sum of rating
average_rating += each_record['score']
hotel_id = each_record['id']
if hotel_id not in hotel_id_rating.keys():
hotel_id_rating[hotel_id] = each_record['score']
else:
hotel_id_rating[hotel_id] = ( hotel_id_rating[hotel_id] + each_record['score'] ) / 2
average_rating = average_rating / len(arrayDict)
print "Average Rating: %d" % average_rating
# List of hotel whose average rating is more than overall average rating
for key in hotel_id_rating:
if hotel_id_rating[key] >= average_rating:
print "Hotel ID: %d Avg Rating: %d" % ( key, hotel_id_rating[key])
We can update the values in the same input array only. Let assume a condition of number is even/odd and the function returns 1 if that is odd else 0. Now start traversing array from the 0th index and check util it reached to endIndex. Keep all the even on the left side and odd values to the right side. If the number is even , just increment startIndex and proceed else swap the values and decrement endIndex and proceed.
- som March 16, 2017