nim
BAN USER- 1of 3 votes
AnswersFirst greater number in an array. Given a large array of positive
- nim in United States
integers, for an arbitrary integer A, we want to know the first integer in
the array which is greater than or equal A . O(logn) solution required
ex [2, 10,5,6,80]
input : 6 output : 10
input :20 output : 80| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
It is an old interview question from google. here is my solution:
#include <iostream>
#include <vector>
using namespace std;
typedef vector<pair<int, int> > Vec;
Vec v;
void Preprocess(vector<int>& input)
{
int max = input[0];
v.push_back(make_pair(0, input[0]));
for (int i = 1; i < input.size(); ++i)
{
if (input[i] > max) {
max = input[i];
v.push_back(make_pair(i, input[i]));
}
}
/*
for (int i = 0; i < v.size(); ++i)
{
cout << v[i].first << " " << v[i].second << endl;
}
*/
}
int FindGreaterIndex(int n)
{
int low = 0, high = v.size() - 1;
int mid;
while (low < high - 1)
{
mid = low + (high - low) / 2;
if (v[mid].second >= n) {
high = mid;
} else {
low = mid;
}
}
if (v[low].second >= n) {
return v[low].second;
} else if (v[high].second >= n) {
return v[high].second;
}
return -1;
}
int main()
{
vector<int> input;
input.push_back(2);
input.push_back(10);
input.push_back(5);
input.push_back(6);
input.push_back(80);
Preprocess(input);
int n;
while (cin >> n) {
cout << FindGreaterIndex(n) << endl;
}
}
void StockProcess(const vector<int>& stocks,
int* buyday,
int* sellday)
{
int min_index = 0;
*buyday = 0;
*sellday = 0;
for (int i = 1; i < stocks.size(); ++i) {
if (stocks[i] < stocks[min_index]) {
min_index = i;
} else if ( (stocks[i] - stocks[min_index]) > (stocks[*sellday] - stocks[*buyday])) {
*buyday = min_index;
*sellday = i;
}
}
}
Time Complexity: O(n)
I think the problem just want you to check whether this tree is a BST or not.
bool isBSTHelper(BinaryTree *p, int low, int high) {
if (!p) return true;
if (low < p->data && p->data < high)
return isBSTHelper(p->left, low, p->data) &&
isBSTHelper(p->right, p->data, high);
else
return false;
}
bool isBST(BinaryTree *root) {
// INT_MIN and INT_MAX are defined in C++'s <climits> library
return isBSTHelper(root, INT_MIN, INT_MAX);
}
int FindInMultiString(const char* mstr, const char* str)
{
int i = 0, j = 0;
while (true) {
while ((str[j] != '\0') && (mstr[i + j] != '\0')) {
if (mstr[i + j] != str[j]) {
break;
}
++j;
}
if (str[j] == '\0') {
return i;
}
if (!(mstr[i + j] == '\0' && mstr[i + j + 1] == '\0') {
i = i + j + 1;
j = 0;
} else {
return -1;
}
}
return -1;
}
I have tested it and it has passed all the test cases
}
int maxsum(int a[], int length)
{
int b = 0;
int sum = INT_MIN;
int start_index = 0, end_index = 0;
int new_start_index = 0;
for(int i = 0; i < length; ++i)
{
if(b > 0)
{
b += a[i];
}
else
{
new_start_index = i;
b = a[i];
}
if(b > sum)
{
start_index = new_start_index;
end_index = i;
sum = b;
}
}
for(int i = start_index; i <= end_index; ++i)
{
printf("%d ", a[i]);
}
printf("\n");
return sum;
}
}
- nim September 11, 2011#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *newNode(int data)
{
struct node *node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
void insert(struct node *&node, int data)
{
if(node == NULL)
{
node = newNode(data);
return;
}
else
{
if(data > node->data)
{
insert(node->right, data);
}
else if(data <= node->data)
{
insert(node->left, data);
}
}
}
void Inorder(struct node *root)
{
if(root != NULL)
{
Inorder(root->left);
printf("%d ", root->data);
Inorder(root->right);
}
}
node *minimum(node *p)
{
if(p == NULL)
return NULL;
while(p->left != NULL)
p = p->left;
return p;
}
node* maximum(node *p)
{
if(p == NULL)
return NULL;
while(p->right != NULL)
p = p->right;
return p;
}
node *Successor(node *root, node *p)
{
if(root == NULL || p == NULL)
return NULL;
if(p->right != NULL)
return minimum(p->right);
node *q = root;
node *parent = q;
if(q == p)
return NULL;
while(q != NULL)
{
parent = q;
if((q->data < p->data) && (q != p))
q = q->right;
else
break;
}
if(q == NULL || q != p)
return NULL;
return parent;
}
node *Predecessor(node *root, node *p)
{
if(NULL == p || NULL == root)
return NULL;
if(p->left != NULL)
{
return maximum(p->left);
}
node *q = root;
node *parent = q;
if(q == p)
return NULL;
while(q != NULL)
{
parent = q;
if(q->data >= p->data && (q != p))
q = q->left;
else
break;
}
if(q == NULL || q != p)
return NULL;
return parent;
}
node *findnode(node *root, int key)
{
if(NULL == root)
return NULL;
node *p = root;
while(p != NULL && key != p->data)
{
if(key <= p->data)
p = p->left;
else
p = p->right;
}
return p;
}
If you want to deal with same character, you can use next_permutation in STL.
Below is the implementation of next_permutation
template <typename BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
{
if(first == last)
return false;
BidirectionalIterator i = first;
++i;
//if only one element
if(i == last)
return false;
i = last;
--i;
for(;;)
{
BidirectionalIterator j = i;
--i;
if(*i < *j)
{
BidirectionalIterator k = last;
while(!(*i < *--k))
;
std::iter_swap(i,k);
std::reverse(j,last);
return true;
}
if(i == first)
{
std::reverse(first, last);
return false;
}
}
}
string encodeRLE(const string &src)
{
size_t len = src.length();
ostringstream os;
for(size_t i = 0; i < len; ) {
size_t j;
int count = 1;
for(j = i + 1; j < len; j++) {
if(src[i] == src[j])
++count;
else
break;
}
if(count != 1)
os << src[i] << count;
else
os << src[i];
i = j;
}
return os.str();
}
yes, i think O(logn) is not possible the first time I saw the question. If the found integer is not in the array, we must scan the whole array and it is O(n) time complexity. I think this question is not very good as the preprocess time is O(n) and every query time is O(lgn)。 I don't know whether it is the answer that the interviewer wants
- nim January 24, 2012