CareerCup

O(nLogn) solution using C++ map (BST). Scanning the array from right to left, insert the element into the map (BST). If the element inserted is the max., then print -1, else print the next highest element. This could also have been achieved using PriorityQueue in C++.

Note that the output is in reverse order.

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;

int main(int argc, char const *argv[])
{
	int n, temp;
	cin>>n;
	std::map<int, bool> m;
	vector<int> in;
	for (int i=0; i<n; i++)
	{
		cin>>temp;
		in.push_back(temp);
	}
	for (int i = n-1; i >= 0; --i)
	{
		temp = in[i];
		pair<map<int, bool>::iterator,bool> p = m.insert(make_pair(temp,true));
		
		if(!m.empty() && (p.first)->first != (m.rbegin())->first)		//checking if the new element added is not the highest
			cout<<(++p.first)->first<<"\t";
		else	
			cout<<"-1\t";
	}
	return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

int n;
std::vector<int> in;

void printSubset(std::vector<int> &partialSubset)
{
	for (int i = 0; i < partialSubset.size(); ++i)
	{
		cout<<partialSubset[i]<<",";
	}
	cout<<endl;
}

void findSubSet(int pos, int sum, std::vector<int> &partialSubset)
{
	if(sum == 0) 
	{
		printSubset(partialSubset);
		return;
	}
	if(pos >= n) return;
	if(in[pos] > sum) return;


	do {
		partialSubset.push_back(in[pos]);
		findSubSet(pos+1, sum - in[pos], partialSubset);
		partialSubset.pop_back();
		
		do{
			pos++;
		}while(pos<n && in[pos-1]==in[pos]);
	} while(pos < n);
}

int main(int argc, char const *argv[])
{
	int temp,sum;
	cin>>n;
	for (int i = 0; i < n; ++i)
	{
		cin>>temp;
		in.push_back(temp);
	}
	cin>>sum;
	sort(in.begin(), in.end());

	int i=0;
	while(i<n)
	{
		std::vector<int> partialSubset(1,in[i]);
		findSubSet(i+1,sum-in[i], partialSubset);
		do {
			i++;
		}while(i<n && in[i-1]==in[i]);
	}
	return 0;
}

Following code works on all inputs, even corner cases which include 0 in the input string. I have assumed that if more than two consecutive 0's occur in the input string, there is no valid interpretation of the given string since we do not have any character which maps to 0.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

char toChar(char a)
{
	return a-'0' + 'a' -1;
}
void gen(std::vector<char> str, string num)
{
	if (num[0]=='0') return;

	if (num.size()==0)
	{
		for (int i = 0; i < str.size(); ++i)
		{
			cout<<str[i];
		}
		cout<<endl;
		return;
	}

	str.push_back(toChar(num[0]));
	gen(str, num.substr(1));

	if (num.size()>=2)
	{
		int next=num[1]-'0' + (num[0]-'0')*10;
		if (next<=26)
		{
			str.pop_back();
			str.push_back('a'+next-1);
			gen(str, num.substr(2));
		} 
	}
}

int main(int argc, char const *argv[])
{
	std::vector<char> str;
	string num("101523");
	gen(str, num);
	return 0;
}

LOL. Just look at the code above your answer by sc.shobhit (me). Uncannny similarity :\

It feels good that my code proved to be useful for you but atleast don't repost exactly same version.

@Jie
How would you find the duplicates in O(N) time and O(N) space. The duplicate elements might repeat more than twice, in which case, we need to store the indices of all the prev occurences of the element. For example, if the cummulative array were
[0, -1, -4, 0, 5, 3,0, -4]
There is a pair 0, that means the range from 0 to 2.
There is a pair 0, that means the range from 0 to 5.
There is a pair 0, that means the range from 3 to 5.

So, for this, probably we need to create a bucket kind of structure with each bucket refering to the elements of the cumm. array and each bucket containg a list of indices of occurence of the bucket element in the cumm. array. This would lead to worst case time complexity of O(n^2) {when all elements of cumm. array are same; we need to print all n_Choose_2 pairs} and O(max_value_of_sum_in_cumm_array*n) space.

Can you suggest an improvement over this approach.

@Anon No, my code returns 1 only, which is the correct answer. On input "a", my code would enter the following if condition

if (str.length() == 1)
	{
		if(str[0]<prev)	return (str[0] - 'a' + 1);
		else return (str[0] - 'a');
	}

and further enter the first if statement -

if(str[0]<prev)	return (str[0] - 'a' + 1);

and return 'a'-'a'+1=1

Got same problem in my Facebook coding test today. The above code passed all the test cases (sample as well as hidden/advanced ones)

#include <iostream>
#include <string>
using namespace std;


int count(string str, char prev, char prevToPrev)
{
	if (prev==prevToPrev)	return 0;
	if (str.length() == 1)
	{
		if(str[0]<prev)	return (str[0] - 'a' + 1);
		else return (str[0] - 'a');
	}

	int res = 1;

	int firstPos = str[0] - 'a';
	if (firstPos==0) res=0;

	if(prev < str[0])	firstPos--;

	for (int i = 0; i < str.length() - 1; i++)
	{
		res *= 25;
		res=res%1009;
	}
	return (firstPos * res + count(str.substr(1), str[0], prev))%1009;
}

int main()
{
	string str;
	cin>>str;
	cout << count(str, 'z' + 1, 'z'+2) << endl;
	return 0;
}

Your interpretation of question is incorrect. You seem to have interpreted the question as "A string is called sstring if it consists of lowercase english letters and no two of characters are the same."
You have overlooked the term CONSEQUTIVE CHARACTERS.

Adding few more checks in your code does the job. Also, the first check of
{{ if(str.lenght()>26) return 0; }} has to be removed as only CONSEQUTIVE CHARACTERS are not allowed.

Would post the working code soon