Amazon Interview Question
Software Engineer / DevelopersA = given array.
Ab = ASCII of A % no need to initialize
Initialize B with size max(Ab)
Go thru Ab one by one, get the number 'n' and add 1 to the nth index B.
Finally get the max(B).
Time:2*o(n)
Space:2*o(n)
Rather I would say initialize an array of size 27 to zero
int a[27];
after that for every character encountered in the given array update the count in initialized array and maintain a counter max and maxChar which will be updated any time u found a new max.
This method is = O(n) , space complexity is constant because irrespective of how many characters in the array the size will be same.( I am assuming input to be lower case characters only.)
I was expected to give a time and space efficient solution. There weren't any constraints given.
Using O(n) extra space is one option. That would be O(n) time.
You can sort the array in O(nlogn) time and get the result with one traversal and O(1) space.
I can't think of any better solution.
//Voting algorithm
List<int> li16 = new List<int>();
li16.Add(1);
li16.Add(2);
li16.Add(2);
li16.Add(2);
li16.Add(1);
li16.Add(1);
li16.Add(2);
li16.Add(3);
li16.Add(2);
li16.Add(3);
int candidate16 = li16[0];
int count16 = 1;
for (int i = 1; i < li16.Count; i++)
{
if (li16[i] == candidate16)
count16++;
else count16--;
if (count16 == 0)
{
candidate16 = li16[i];
count16++;
}
}
any constraint given... like o(n) Time complexity and o(1) or o(n) space complexity
- asetech February 10, 2011