nim
 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
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
January 24, 2012 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
January 17, 2012 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
January 17, 2012 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;
}

nim
September 07, 2011 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
September 05, 2011 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 January 24, 2012