R
BAN USERI dont think Alex solution is so bad, he is asking to maintain count not insert in hash table, which should be constant theoretically, practically unless I insert same set of keys, collision will hardly occur so this works as O(n). Coming to selection you can use max heap of size k, to get max k elements in a constant time. nlog(k) is complexity, in a worst case of k=n(or approaching n), heap insertion becomes constant.
By the way, what is the interviewer response to your solution
I assume this is what is being asked ?
static void Main(string[] args)
{
// Given a number n write a program to print all binary numbers starting from 1. For example n=6, print 1, 10, 11, 100, 101, 110
// Consequent numbers 111, 1000, 1001 1010
string str = "1";
int n = 100;
int nextPosToSearch = 0;
for (int i = 1; i <= n; i++)
{
Console.WriteLine(str);
char[] digits = str.ToCharArray();
for(int j = nextPosToSearch; j >=0; j--)
{
if (digits[j] == '1')
{
if (j == 0)
{
digits = new char[digits.Length + 1];
digits[0] = '1';
for (int k = 1; k < digits.Length; k++)
digits[k] = '0';
nextPosToSearch = digits.Length-1;
}
else
{
digits[j] = '0';
nextPosToSearch = j;
}
}
else
{
digits[j] = '1';
nextPosToSearch = j - 1;
break;
}
}
str = new string(digits);
}
Console.Read();
}
Finding a original question is interviewer problem not the interviewees problem :).
Even if all of them are in internet or not this is what any can think of commonly unless some one is a geek or a weird
1. Methods to finding a duplicate element in an array. geeksforgeeks.org/archives/7953
2. The original efficient solution you suggested.
Cobra,
Single pass or two pass is said in terms of time taken to do the task. If you are traversing the whole list once and again traverse to find 5th element from tail that is 2 pass. If you use 2 variables, you can traverse the list in 1 pass's time only so this method of using 2 variable is considered as one pass and not two pass.
I hope I made myself clear.
I think minor quicken the algo ?
- R August 04, 20141. We can use min heap for storing the server memory spaces. Search will be faster and insertion, deletion is easier to do.
2. You can sort task list as well in descending order and traverse through that order. This will help quicken the search process and you can remove the heap root, if it doesnt fit the task capacity.