cctsinghua
BAN USERI think search can be applied on multiple attributes, for example, "name", "phone number", "company". Then we define the order we search from these attributes. Display relevant results.
c++ pseudo-code:
typedef struct ContactInfo
{
string name;
string company;
string address;
int phoneNumber[];
}
class ContactManipulate
{
public:
bool AddContact( ContactInfo c1 );
bool DeleteContact( ContactInfo* c1 );
bool UpdateContact( ContactInfo* c1 );
queue<ContactInfor> FindContact( string str );
bool IsContain( string searchString, string attr );
bool IsContain_phoneNum( int searchNum[], int phoneNum[] );
int GetNumOfContact();
ContactInfo* GetContactInfo( int i );
private:
int NumOfContacts;
}
// We can use KMP to match string,
// since we may just want part of attr match searchString
bool ContactManipulate::IsContain( string searchString, string attr )
{ }
queue< ContactInfo > FindContact( string str )
{
queue< ContactInfo > searchResults;
// Search all contacts,
// since we don't want to miss any info that matches search string.
for( int i = 0; i < length; i++ )
{
// If search string are all numbers, we search from phone numbers
if( StrIsNum(str) )
{
int num[] = StrToInt(str);
int phoneNum = GetContactInfo(i).phoneNumber );
if( IsContain_phoneNum( num, phoneNum )
searchResults.push(i);
// Otherwise, we can search from other fields.
else
{
if( IsContain( str, GetContactInfo(i).name )
searchResults.push(i);
else if( IsContain( str, GetContactInfo(i).company )
searchResults.push(i);
else if( IsContain( str, GetContactInfo(i).address )
searchResults.push(i);
}
}
return searchResults;
}
We can use a maxheap. The root of the maxheap is the minimum number. When checkout, we get the root. When checkin, we insert the number. GetRoot and Insert both take O(logn).
MaxHeap heap( LONG_MAX );
long CheckOut( MaxHeap heap ) return heap.GetRoot();
void CheckIn( MaxHeap heap, long input ) heap.Insert( intput );
You're right, just need to change a line. Now it is.
- cctsinghua April 28, 2013// We can make this problem more general.
// Consider more than 4 men, for example, a set {15, 14, 10, 7, 5}
// We can find that the mininum time is such a division that two subsets has a mininum difference.
// e.g subset1 = {15,10}, subset2 = {14,7,5};
// Ideally, the min time should be perfect match, pm = SumOfSet/2;
// If there is such a match, we find the answer, otherwise pm++;
// It can be solved recursively.
// C++ code:
#include <iostream>
#include <new>
using namespace std;
bool FindSubsetSumTo( int pm, int array[], int N, bool visited[] );
int MinCrossBridgeTime( int array[], int N );
int main( int argc, char* argv[] )
{
int a[] = {1, 3, 7, 10};
int b[] = {15, 14, 10, 7, 5};
int c[] = {2994, 1443, 533, 2324, 1133, 4444, 2382};
cout << "minimum time: " << MinCrossBridgeTime( a, 4 ) << endl << endl;
cout << "minimum time: " << MinCrossBridgeTime( b, 5 ) << endl << endl;
cout << "minimum time: " << MinCrossBridgeTime( c, 7 ) << endl << endl;
return 0;
}
int MinCrossBridgeTime( int array[], int N )
{
int pm = 0;
for( int i = 0; i < N; i++ ) pm += array[i];
if( pm %2 == 1 ) pm = pm/2 +1;
else pm /= 2;
bool* used = new bool[N];
bool found = false;
while( !found )
{
for( int i = 0; i < N; i++ ) used[i] = false;
found = FindSubsetSumTo( pm, array, N, used );
if( found )
{
cout << "subset1: ";
for( int i = 0; i < N; i++ )
if( used[i] ) cout << array[i] << " ";
cout << endl;
cout << "subset2: ";
for( int i = 0; i < N; i++ )
if( !used[i] ) cout << array[i] << " ";
cout << endl;
return pm;
}
else pm++;
}
}
bool FindSubsetSumTo( int pm, int array[], int N, bool used[] )
{
if( pm == 0 ) return true;
if( pm < 0 ) return false;
bool found = false;
int i = 0;
while( !found && i < N )
{
if( !used[i] )
{
used[i] = true;
found = FindSubsetSumTo( pm-array[i], array, N, used );
if( !found ) used[i] = false;
}
i++;
}
return found;
}
The result is:
subset1: 1 3 7
subset2: 10
minimum time: 11
subset1: 14 7 5
subset2: 15 10
minimum time: 26
subset1: 2994 2324 2382
subset2: 1443 533 1133 4444
minimum time: 7700
Hey, I have written code for that in c:
#include <stdlib.h>
#include <iostream>
using namespace std;
bool DeepCopy(char *a[], char ***b, int len);
int main( int argc, char* argv[] )
{
char *a[] = {"abc", "xyz", "def"};
char **b;
int len = sizeof(a)/sizeof(char*);
DeepCopy(a, &b, len);
return 0;
}
bool DeepCopy(char *a[], char ***b, int len)
{
int i,j,k;
(*b) = (char**) malloc (sizeof(char*) * len);
i = 0;
while( i < len )
{
j = 0;
while(true)
{
if( a[i][j] != '\0' ) j++;
else break;
}
(*b)[i] = (char*) malloc (sizeof(char) * (j+1));
k = 0;
while( k < j )
{
(*b)[i][k] = a[i][k];
k++;
}
(*b)[i][k+1] = '\0';
i++;
}
return true;
}
/*
//We can use Hash Table to solve this problem.
//First build a hash table for the array. Then for each element, find if z-A[i] is in the hash table.
//However, it returns one possible pair.
//But you can go through the whole array to get all pairs that satisfy A[i] + A[j] == z. Expected time is O(n).
*/
#include <stdio.h>
#include <iostream>
#include <unordered_map>
using namespace std;
bool ArraySum( int Array[], int N, int num );
int main( int argc, char* argv[] )
{
int a[] = {1,2,3,4,5,6,7,8,9,0};
int b[] = {-1,-2,-3,-5,-6,-7,-8,9,3,4,5,1,11};
int n1 = 4;
int n2 = 5;
int n3 = -5;
int n4 = 16;
int n5 = 10;
ArraySum(a, 10, n1);
ArraySum(a, 10, n2);
ArraySum(a, 10, n3);
ArraySum(a, 10, n4);
ArraySum(a, 10, n5);
ArraySum(b, 13, n1);
ArraySum(b, 13, n2);
ArraySum(b, 13, n3);
ArraySum(b, 13, n4);
ArraySum(b, 13, n5);
return 0;
}
bool ArraySum( int Array[], int N, int num )
{
if( N <= 0 ) return false;
unordered_map<int,int> HashTable;
for( int i = 0; i < N; i++ )
{
pair<int, int> onePair(Array[i], i);
HashTable.insert(onePair);
}
for( int i = 0; i < N; i++ )
{
if( HashTable.count(num-Array[i]) > 0 )
{
unordered_map<int, int>::const_iterator got = HashTable.find(num-Array[i]);
if( got->first != i ) cout << "Array[" << i << "] + Array[" << got->second << "]" << " == " << num << endl;
return true;
}
}
return false;
}
The result is:
Array[0] + Array[2] == 4
Array[0] + Array[3] == 5
Array[6] + Array[8] == 16
Array[0] + Array[8] == 10
Array[0] + Array[10] == 4
Array[4] + Array[12] == 5
Array[1] + Array[2] == -5
Array[10] + Array[12] == 16
Array[0] + Array[12] == 10
Repannadwilliams31, Applications Developer at National Instruments
I am Anthony, Human Resources specialist with a decade of successful experience in hiring and employee management.I am a ...
RepI believe in magic, power, aliens, parallel universe, god. I always dream about the powers and out of the world ...
Thanks, I thought it requires to return maximum. Use a max heap instead could return minimum.
- cctsinghua May 06, 2013