CareerCup

I think the question should be: you can do a pre-process, and after than, every search time is O(log n).

My solution is remove some un-usefull value (2,3,1,6,5,4) = > (2,3,,6,,) , because 1< 3, and 5,4<6. and then put the rest value in a binary search tree with their order number.

After the pre-process, the following search should be O(log n).

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;
    }
}

Right. O(log n) solution is not possible. Since the numbers in the array are not ordered there is no way to split the input into two parts and be able to select one over the other.

I don't think O(log n) is possible since the array is not sorted.

1. Using extra space is overkill if you still manage to do it in linear time.

2. You are not gaining anything in terms of time complexity if you take linear extra space.

mark.ak's linear time answer is short, simple and fair enough.

O(log N) is not possible. Here's the proof. Assume that is possible, find an instance of problem such that
1. the answer is the last element.
2. the algorithm produces correct answer.
Since the algorithm has O(log N) complexity, it can see at most O(log N) elements of the array. Hold these elements fixed and change the rest of the elements such that the correct answer changes. Feed the changed array to the algorithm. Since none of the elements the algorithm sees is changed, the algorithm is going to produce the same old answer which is wrong.

I'm sure I could prove O(logn) is not possible here.

Anything related to heap ??

can anybody pls tell me wat actually test cases mean... i.e. wat interviewer wants us to write when he asks for the test cases... it wud be gr8 if u can give a small eg... thanks ...

I agree with all of you, Is impossible to find a number in a not sorted array.
If the interviewer as you and your solution is not as expected. you can as the interviewer if he/she can show you the right answer or how he/she will do it!! in that way you are gonna show you are interested in the right solution and you want to learn and improved your programming skills

Suppose I give a number that is greater than any one in the array, it is obviously log(n) is impossible. But is this guy indicating this array is a max-heap.

Pre-process the array and build a binary search tree. Now for a given number n, find the number in tree O(log n), then call its findSuccessor function (pick the left most node from the right sub tree), this would take O(logn). This would be the next higher value in the array.
Complexity: O(logn + logn)

I think there is a solution.
To do it in O(logn) time we should traverse the array in the way as how we traverse "Array Representing heap". I know that all the nodes will not follow the heap property and henc it is not heap. I am just asking to traverse elements as if it was a heap starting from 1st element and everytime checking its children. Start with (i=1st) element and everytime check 2i and (2i+1)th elements. If the element is greater than A then store the position of number. Do this till we reach N/2th positioned element. (heap's second last level element). Everytime we find a number greater we check if the position of this element is falling earlier than the previously matching element( if there was one). Hence This will be done (logn) times.

I will interpret the requirement as "after preprocessing, use O(lgn) time". Then this problem can be solved by sorting decreasing subsequences in the array and search it.

Example: [ 3 2 8 7 3 6 4 5]
Decreasing subsequences[ [3 2] [8 7 3] [ 6 4] [5] ]
The sorting uses the first element of each subsequence as the key, namely 3, 8, 6, 5.
Note the answer to the question must be one of 3 8 6 5.

import java.util.ArrayList;

public class Test1 {
	
	public static void main(String[] args) {
		String test="dabc";
		ArrayList<String> results = findCombos(test);
		for(String res : results) {
			System.out.println(res);
		}
	}
	
	public static ArrayList<String> findCombos(String input) {
		ArrayList<String> buffer = new ArrayList<String>();
		if(input == null || input.length() == 0) {
			return buffer;
		}
		if(input.length() == 1) {
			buffer.add(input);
			return buffer;
		}
		
		String firstChar = input.substring(0,1);
		buffer.add(firstChar);
		ArrayList<String> results = findCombos(input.substring(1));
		buffer.addAll(results);
		for(String result : results) {
			buffer.add(firstChar + result);
		}
		return buffer;
	}
}

isn't it mergesort kinda thing without merge which would result in lgn solution ?

I think the intention is to allow an initialization process and after that, each looking up should take O(logn) time. In such case, it's possible.

just use approach similar to quicksort. Choose the center value of the list as the pivot.

quicksort() {
choose center value as pivot;
if (pivot <= input) {
scan the list from pivot to the right and if the value is > 6, put into a new list;
quicksort();
else {
scan the list from the 1st to the pivot and if the value is > 6, put into a new list;
quicksort();
}
}

Build a Cartesian Tree in O(N)
Then every query is O(lgN)


[2, 10,5,6,80] can be
80
/
10
/ \
2 6
/
5

This is a heap and when we find one node that is = than VAL and its parent is >= VAL,we return its parent if it's the right child, otherwise return itself.
But if the node is < VAL and parent is >= than VAL, we return its parent.

for 6, we traverse to 6 and return 10. (Right child,return parent)
for 5, we traverse to 5 and return 5. ( Left child)
for 20 we traverse to 10 and return 80. (Not equal, return parent)

The only way to achieve O(long) is with a sorted array, I assume the interviewer would allow to sort the array if the interviewee asks, so the code looks like this:

public static int firstGreatest(Integer[] arr, Integer findMe)
{
// array needs to be sorted !
Arrays.sort(arr);

// base cases
if (findMe >= arr[arr.length -1])
{
return arr[arr.length -1];
}
if (findMe <= arr[0])
{
return arr[0];
}

int low = 0;
int high = arr.length - 1;
int middle = 0;
// case item found in array O(logn)
while (low <= high)
{
middle = (low + high) / 2;
if (findMe > arr[middle])
{
low = middle +1;
}
else if (findMe < arr[middle])
{
high = middle - 1;
}
else
{
if (middle == arr.length-1)
{
return arr[middle];
}
else
{
return arr[middle + 1];
}
}
}
return arr[middle];
}
}

I think if we need a O(logN) algorithm, it means we can preprocess it. use the same trick we use to find max rectangle from histogram. and do a binary search. the time complexity is O(logN)

We can achieve O(log n) in average cases, by binary search (keep reducing the search space by half if possible)

int find(int *a, int s, int e, int target)
{
    if (s>e) return MAX_INT;

    int idx;
    int mid = (s+e)/2;

    if (a[mid] > target)
    {
        //if a[mid] is already large than target
        //we do only need to check the left part of the array
        idx = find(a,s,mid-1,target);
        if (idx != MAX_INT) return idx;
        else return mid;
    }
    else
    {
        //first find in left part, if found, we do not have to deal with right part
        int idx = find(a,s,mid-1,target);
        if (idx!=MAX_INT) return idx;

        return find(a,mid+1,e,target);
    }
}

int solve(int *a, int len, int target)
{
    int index = find(a,0,len-1,target);
    if (index==MAX_INT) return -1;

    return a[index];
}

int findfirstgreaterthanequal(int *a, int start, int end , int &index, int val)
{
if (start > end ) return 0;

int mid = (start + end )/2;

if(a[mid] >= val && mid < index )
{
index = mid;

}

findfirstgreaterthanequal(a, start, mid-1, index, val);
findfirstgreaterthanequal(a, mid+1, end, index, val);

return a[index];

}

sort(a.begin(), a.end());
while (cin >> query) 
{
        auto it = lower_bound(a.begin(), a.end(), query);
        if (it == a.end()) cout << "NOT FOUND" << endl;
        else cout << *it << endl;
}

// very nice question. needs a simple array (preprocessed)
// eg, suppose the input is 4, (assume we do linear search as of now)
// 2 : 4 > 2 next
// 10 : 4 < 10 , so ans is 10 and not 5..
// now 6
// 2 : 2 < 6 so next
// 10 : 10 > 6 and 10 is the first element greater than 6

for (int i=0; i < n; i++)
{
        if (pre.size() == 0) pre.push_back(a[i]);
        else if (a[i] > pre.back()) pre.push_back(a[i]);
}
while (cin >> query)
{
           int lo(0), hi(pre.size()-1), x, ans(-1);
           while (lo <= hi)
           {
                     x = lo + (hi-lo)/2 ;; // avoids overflow
                     if (a[x] >= query) { ans  = x; hi = x-1; }
                     else if (a[x] < query) { lo = x+1; }
           }
           cout << ans << endl; 
}

#include<stdio.h>
#include<stdlib.h>
void sort(int arr[] ,int n)
{ 
  int i,j,temp;
  for (i = 0 ; i < ( n - 1 ); i++)
  {
    for (j = 0 ; j <( n - i - 1); j++)
    {
      if (arr[j] > arr[j+1]) /* For decreasing order use < */
      {
        temp  = arr[j];
        arr[j]   = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
 
}
int main()
{
	int a[] = {2,10,5,6,80};
	int i, num = 2;
	sort(a,5);
	for(i=0;i<sizeof(a)/sizeof(int);i++)
	{
		if(a[i] <= num)
			;
		else
		{	
			printf(" The next value of given number is %d \n ",a[i]);
			break;
		}
	}


	return 0;
}

this is a simple question. What you need to do is implement actual merge sort, but with a slight change:
1) at lowest level merging stage, discard any values that are less than n
2)Also, for reaming number (which are > n), sort by position in original array

Thats it.

Traverse the array, keeping track of the smallest value seen that is larger than A.

int FindIndexOfNextGreater(int intArray[], int arraySize, int A)
{
   int index = -1;
   for (int i = 0; i < arraySize; ++i)
   {
      if (intArray[i] > A)
      {
         if (index == -1 || intArray[i] < intArray[index])
            index = i;
      }
   }
   return index;
}

I guess the situation was like this:
During the interview, this guy brought up a solution which takes O(n) time for a query.
Then the interviewer asked, could you do it better?
So he supposed the interviewer was looking for a O(logn) solution for each query.
Actually, we can do it better, but not this way. We can preprocess the whole array in O(nlogn) time, then use O(1) time for each query.

I wrote a piece of code for this:

#include <iostream>
#include <vector>
#include <limits>
using namespace std;
class BST
{
	struct _Node {
		int val;
		_Node * left, * right;
		_Node (int v = 0, _Node * l = nullptr, _Node * r = nullptr):val(v), left(l), right(r){

		}
	};

	_Node * _root;
	int _insert_and_report(int val, _Node *& pos)
	{
		if (pos == nullptr)
		{ 
			pos = new _Node(val);
			return numeric_limits<int>::min();
		}
		if (val < pos->val)
		{
			_insert_and_report(val, pos->left);
			return pos->val;        
		}else {
			return _insert_and_report(val, pos->right);
		}
	}

public:
	BST():_root(nullptr){}
	~BST(){//delete all nodes ...
	}
	int find(int val)
	{
		return _insert_and_report(val, _root);
	}
};
vector<int> buildFirstGreaterTable(int arr[], int size)
{
	vector<int> table;
	BST bst;
	for (int i = 0; i < size; ++i)
	{
		table.push_back(bst.find(arr[i]));
	}
	return table;
}

int main()
{
	int arr[] = {2 , 6,2, 9, 8,3,12,8,1,0};
	vector<int> table = buildFirstGreaterTable(arr, sizeof(arr)/sizeof(int));
	for (int i = 0; i < table.size(); ++i)
	{
		cout<<table[i]<<endl;//all queries
	}
}

The logic is quite simple.

Well, the question never mentions that we cannot sort the unsorted array. We can sort the array and then use it to find the first greater integer.