Goldman Sachs Interview Question Software Engineer / Developers
Hi,
This is pretty good. But was wondering is it possible to solve it in the space complexity of O(1) as now its O(2).
-Pallav
You make me cry :))))
O(1) means space which doesn't depend on input size.
And I don't know what is O(2) :))))
@gevorgk
awesome work man!!!!
don't worry what netappreject has said. when such people don't have any point to make this is what they do...
@netappreject
There is better way to say this....Please be nice to people who are sharing their knowledge and helping you...
O(2) is a nonstandard way to say O(1). Pallav, if using two ints bothers you, just pack them both into a long.
@gevorgk - Can you also pls explain, your thinking process - how you approach the problem and devise the solution - I assume here you approached it as the number which occurred more than n/2 has to either alternate starting from 1st position (e.g. 1 2 1 4 1 5 1) or has to occur consecutively atleast 1 (e.g. 5 4 1 1 6 1 1)
If the element is repeated more than n/2 times, than it definitely occurs consecutively atleast once...
I doubt he came up with the algorithm because the code looks very similar to the algorithm in taylor.thursday.com pdf. But if he came up with it great!
This solution has a flaw.
If numbers are in this form
1, 20, 2, 20, 3, 20, 4, 20 ...
Then this solution doesn't work.
Because it never get a chance to store 20 in elem.
if the code is modified a little bit like mentioned below.
......
else
{
--count;
--i;
}
........
Then things work fine.
Ya But then I don't know what will be the complexity.
In worst case It probably comes out to be O(n+n/2), i.e. O(3n/2), i.e. O(n).
Please comment on it.
Please point out if you see any problem in it or type "CORRECT" if it is correct.
- Nitin
Point here is definition of majority is (n/2) + 1. thats way:
1 20 2 20 3 20 4 20 needs to keep another 20, for n/2 it fails several cases.
Array space already given as input is used in 2quick select so we can say that no extra space is used so space complexity is constant.
Hi gevorgk , as you are setting again count=0 . It making count logic of first for loop useless. I am not getting why that is required. also according to my analysis your logic will be definitely failed for array {3,1,1}
The first loop finds the required element if it exists and an arbitrary element otherwise. The second loop checks whether this element occurs more n/2 times, which is sort of pointless given that the input is guaranteed to have that property.
It's not useless, count logic in first loop guarantees that element with more than n/2 occurrence will survive.
And I don't see any problem with {3, 1, 1}.
3 - elem = 3, count = 1
1 - elem = 3, count = 0
1 - elem = 1, count = 1
So we have elem = 1 after first loop and check if it occures more than n/2 in second loop.
<pre lang="c++" line="1" title="CodeMonkey87435" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
String s;
while (!(s=r.readLine()).startsWith("42")) System.out.println(s);
}
}
</pre><pre title="CodeMonkey87435" input="yes">1
2
10
42
11
</pre>
#include<stdio.h>
#define arraysize 6
int array[arraysize]={1,3,3,3,4,3};
int repeatedElem(int array[], int size)
{
int index = 0;
int count = 0;
int val;
int elem;
count = 0;
for(index=0;index<size;++index)
{
elem = array[index];
if(count ==0)
{
val = elem;count++;
}
else if(val == elem)
{
count++;
}
else
{ count--;}
}
if(count>0)
{
return val;
}
else{return -1;}
}
int main()
{
int ans = repeatedElem(array, arraysize);
printf("answer is %d ", ans);
return 0;
}
I found Bond's solution the best.It works and i'm not that good with calculating complexity but I m sure there is only one for loop so complexity must be less.
Nice solution gevorgk .
I would like to comment for second loop.
First loop will at least give us most occurred element in the array. (As you can see ppl have posted sequence in which algo doesn't work).
Second for loop is just for the confirmation that we have chosen the correct element, if ele given by first loop is not occurring n/2 times then no element is there.
Hope it make sense.
Assuming no other numbers are repeated except the one N. N will consecutively repeat itself at least once. complexity between O(1) - O(n) with 1 var.
int findRepeaterNum(int *arr)
{
int *i=arr+1;
while(*arr++!=*i++);
return *i;
}
- gevorgk June 01, 2010//returns -1 if not found int maxRepeatedElement(int arr[], int size) { if( size <= 0) return -1; int count = 0; int elem; for (int i = 0; i < size; ++i) { if (count == 0) { elem = arr[i]; count = 1; } else if (elem == arr[i]) { ++count; } else { --count; } } count = 0; for(int i = 0; i < size; ++i) { if (arr[i] == elem) { ++count; } } if (count > size/2) { return elem; } return -1; }