nim
 1of 3 votes
AnswersFirst greater number in an array. Given a large array of positive
 nim on January 24, 2012 in United States Edit  Report Duplicate  Flag
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
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;
}
}

nim
on January 24, 2012 Edit  Flag View
Reply
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)

nim
on January 17, 2012 Edit  Flag View
Reply
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);
}

nim
on January 17, 2012 Edit  Flag View
Reply
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 on September 11, 2011 Edit  Flag View Reply#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;
}

nim
on September 07, 2011 Edit  Flag View
Reply
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;
}
}
}

nim
on September 05, 2011 Edit  Flag View
Reply
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();
}
Open Chat in New Window
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 on January 24, 2012 Edit  Flag View Reply