## Linkedin Interview Question for SDE1s

• 1

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
4
of 4 vote

Here is the concept :
If a number is lies more then half, then if we increment a counter when that required numbe comes and decrements the counter when any other number come ,then at the end the counter will have positive value.
Now in the problem, even if we have worst case, the counter will be +1, when for every other number we give one valid number, but for a general case, number from other one can also contribute from canceling their effect.

Use a counter (C = 0)and a integer variable (A),

``````M[1 to n] is given array
C = 1;A = M;
for i = 2 to n
if M[i] == A;
c++;
else
C--;
if(c == 0)
i++;
if(i > n)
output -1;
C = 1;
A = M[i];
if C > 0
check weather A is that number,
else
output -1;``````

complexity : O(n) + O(1)

Comment hidden because of low score. Click to expand.
0

how are you so sure M is the number?
if the array is
[5,6,7,7,7,7]
will this still work?

Comment hidden because of low score. Click to expand.
0

M is not that number, it is A, which may be M, or may be other.
like here :
1st step : C = 1, A = 5,
2nd step : C = 0, A = 6, which make C = 1, A = 7;
3rd step : C = 2,A = 7;
4th step : C = 3,A = 7;
5th step : C = 4,A = 7;
Now check weather A = 7 is that number, And in this example it is.

Comment hidden because of low score. Click to expand.
0

No you are right! only thing is how you check whether 7 is the correct candidate ..
So it will be O(n)+O(n) ?

Comment hidden because of low score. Click to expand.
0

Run one more for loop over the array, and check how much time 7 is available, if it more then half, then 7 is the right answer, otherwise not.
Note : When I write O(n)+ O(1) it means O(n) time complexity and O(1) space complexity.

Comment hidden because of low score. Click to expand.
1
of 1 vote

C++ implementation of sonesh' algorithm

``````int MoreThanHalfElem(int a[],int n)
{
int candidate;
int count =0;
for(int i= 0;i<n;i++)
{
if(count == 0)
{
candidate = i;
count =1;
}
else
{
if( a[i] == a[candidate])
count--;
else
count ++;
}
}
count =0;
for(int i=0;i<n;i++)
{
if(a[i] == a[candidate])
count++;
}
return count >=(n+1)/2?candidate:-1;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This will break if array is [ 5 4 3 5 5 5]

Comment hidden because of low score. Click to expand.
-1
of 1 vote

It won't work for [2 2 3 3 5 5]
because
2 - C = 1, A = 2
2 - C = 2, A = 2
3 - C = 1, A = 2
3 - C = 0 so it will go in if and increment i and i < n so, C = 1 A = 5
5 - C = 2 , A = 5

Comment hidden because of low score. Click to expand.
2

@Damn have you tested my code?for your test case,it will return index 0(number 5),it works.
As for test case [2 2 3 3 5 5],my code will return -1,cause there are 6 elements,but no element is repeated more than 3 times.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Moore's algorithm can be used.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Sort the array and traverse it from start. If any number occurs consecutively for more than half the size of an array, return the element. Otherwise, return -1.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I like this solution. Very simple and O(n) time and O(1) space.

Comment hidden because of low score. Click to expand.
0
of 0 vote

maintain a hastable where key is a number from the array and value its repeatation
Go through the array and keep inserting in dictionary :
if (element is already a key) then increase its count

Then go thourgh this dictionary and find if any count is > n/2

Comment hidden because of low score. Click to expand.
0

Space should be O(1).

Comment hidden because of low score. Click to expand.
0
of 4 vote

The element which is repeated more than half times is also called as majority element which can be found by Moore's Voting algorithm.

This is a two step process.
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.

------------------------------------------------------------------------------------------------

``````/* Function to find the candidate for Majority */
int findCandidate(int a[], int size)
{
int maj_index = 0, count = 1;
int i;
for(i = 1; i < size; i++)
{
if(a[maj_index] == a[i])
count++;
else
count--;
if(count == 0)
{
maj_index = i;
count = 1;
}
}
return a[maj_index];
}

/* Function to check if the candidate occurs more than n/2 times */
bool isMajority(int a[], int size, int cand)
{
int i, count = 0;
for (i = 0; i < size; i++)
if(a[i] == cand)
count++;
if (count > size/2)
return 1;
else
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

I tried it with the array {5,5,5,3,2,7,5,5,2,3,5,9}
It returns 9...

Comment hidden because of low score. Click to expand.
0

you have six 5s and array size 12.
questions asks "more than half number of times"

Comment hidden because of low score. Click to expand.
0

I meant it returns 9 as the majority element (i.e. which occurs the maximum no of times), which is wrong. The check for being greater than n/2 is done later.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I can give you a O(n) solution and I will explain why I do like this later:

``````#include<stdio.h>

int find_dest_num(int *a, int len) {
int i;
int temp = a;
int count = 1;
for(i = 1; i < len; i++) {
if(temp == a[i]) {
count++;
} else {
count--;
if(count == 0) {
temp = a[i];
count = 1;
}
}
}
count = 0;
for(i = 0; i < len; i++) {
if(a[i] == temp)
count++;
}
if(count * 2 > len)
return temp;
else
return -1;
}

int main(int argc, char *argv[]) {
int a[] = {2, 2, 2, 3, 3, 3, 1, 3, 3};
int len = sizeof(a) / sizeof(int);
find_dest_num(a, len);

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution with running time O(n) in python

``````def find_max_num(arr):
counter_dict = {} #this dictionary will be used to maintain the count of characters
for elem in arr:
val = counter_dict.get(elem,0)
counter_dict[elem] = val+1
# once we find the count of a character is equal / more than n/2+1 then we know that there can be no other character that can occur more hence we can break
if counter_dict[elem]>= len(arr)/2+1:
return elem
else:
# there was no return encountered during the for loop hence we return -1
return -1``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

/*
* Write a program to find the element in an array that is repeated
* more than half number of times. Return -1 if no such element is found.
*/

public class App {
private static boolean findOcc(int[] arr) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();

for (int i = 0; i < arr.length; i++) {
Integer value = map.get(arr[i]);
if (value == null)
value = 1;
else
value++;

map.put(arr[i], value);
}

for (Entry<Integer, Integer> entry : map.entrySet()) {
int value = entry.getValue();
if (value > (arr.length / 2))
return true;
}

return false;
}

public static void main(String[] args) {
int arr[] = { 4, 3, 10, 3, 7, 7, 6, 7, 7, 7, 78, 7, 7 };
System.out.println(Arrays.toString(arr));
System.out.println(findOcc(arr));
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

The algo can be written like this:-

1-Maintain a dictionary, D, of each element of Array, A, : increment count by 1 on each entry for the number
2- while traversing the array A compare the D[i] of A[i] with size(A)/2 and
3 - if D[i] > n/2 then break and return A[i] as the majority number in the array
4 - Algo completes in O(n) time only -- No extra loop is required to compare D[i] with n/2

PHP code: -

``````\$arr = array('4','4','1','3','4','2','4','4','5','4','4');
\$max = -1;

foreach (\$arr as \$k=>\$v){
if(!is_null(\$b[\$v])){
\$b[\$v]= \$b[\$v]+1;
}else{
\$b[\$v]= 1;
}
if(\$b[\$v] > sizeof(\$arr)/2){
\$max  = \$v;
break;
}

}
echo 'The Number is  = '.\$arr[ \$v] ;
echo \$max ;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<stdio.h>

int main()
{
int a={2,1,2,1,3,1,5,1}, A={0}, f={0}, i,j,k,c;

for(i=0,k=0,c=0;i<7,k<7,c<7;i++,k++,c++)
{

for(j=i+1;j<=7;j++)
{
if(a[i]==a[j])
{
A[k]++;
f[c]=a[i];
}
}

}
for(k=0,c=0;k<7,c<7;k++,c++)
{
if(A[k]>=3)
{
printf("%d is the ans",f[c]);
break;
}
}
system("PAUSE");
}``````

i know this code is not efficient but it works for every array....

Comment hidden because of low score. Click to expand.
0
of 0 vote

In Python:

``````def majority_voting(a):
count = 0
for el in a:
if count == 0:
current = el
if el == current:
count += 1
else:
count -= 1

recount = 0
for el in a:
if el == current:
recount += 1

if recount > (len(a)/2):
return True
else:
return False``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

There are three types of problems possible with String reverse
1) Reverse the whole string:
Input: This is a test
Output: tset a si sihT
2) Reverse words in place
Input: This is a test
Output: sihT si a tset
3) Reverse only the words:
Input: This is a test
Output: test a is This

So for first problem just we need to divide this into smaller problem to reverse this string
Then second one can be done by just reversing the Sub strings in place
Then third one , just a combination of first and two. Reverse this string, then reverse the words in place.

``````package com.problems;

public class ReverseString
{

public static void main(String[] args)
{
String test = "This is a test";

System.out.println("Orignal String: " + test);

char[] reverseCharacterArray = reverseString(test.toCharArray(), 0, test.toCharArray().length - 1);
System.out.println(String.valueOf("Reverse string: " + String.valueOf(reverseCharacterArray)));

reverseCharacterArray = reverseStringWordsInPlace(reverseCharacterArray);
System.out.println(String.valueOf("Reverse only words: " + String.valueOf(reverseCharacterArray)));

reverseCharacterArray = reverseStringWordsInPlace(test.toCharArray());
System.out.println(String.valueOf("Reverse words in place: " + String.valueOf(reverseCharacterArray)));

}

public static char[] reverseStringWordsInPlace(char[] chars)
{
int start = 0, end = 0;
for (int i = 0; i < chars.length; i++)
{
if (" ".equals(String.valueOf(chars[i])))
{
reverseString(chars, start, i - 1);
start = i + 1;
}
}

reverseString(chars, start, chars.length - 1);

return chars;
}

public static char[] reverseString(char[] chars, int start, int end)
{
if (end < start)
{
return chars;
}

if (chars.length == 0 || chars.length == 1)
{
return chars;
}
swap(chars, start, end);

return reverseString(chars, ++start, --end);
}

public static char[] swap(char[] chars, int i, int j)
{
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
return chars;
}

public static String reverseString(String s)
{
if (s == null || "".equals(s))
{
return "";
}

int length = s.length();
if (s.length() == 1)
{
return s;
}

return s.charAt(length - 1) + reverseString(s.substring(1, length - 1)) + s.charAt(0);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

It's Moore's Voting Algorithm
1) Find the candidate who can possibly present more than n/2 in array. Remember it's a candidate element, it's not a element who has maximum frequency in the index
2) Then check that obtained candidate is majority element i.e. it occurs more than n/2 times

``````package com.problems;

public class MooresVotingAlgorithm
{

public static void main(String[] args)
{
testMooreVotingAlgo();
}

public static void testMooreVotingAlgo()
{
int[] a = { 4, 4, 4, 5, 6, 7, 10, 8, 10 };
System.out.println("Length: " + a.length);
int candidate = findCandidate(a);
System.out.println("Candidate: " + candidate);
boolean isMajority = isMajority(a, candidate);

if (isMajority)
{
System.out.println("Majority element: " + candidate);
}
else
{
}
}

public static int findCandidate(int[] a)
{
int size = a.length;
int candidateIndex = 0;
int count = 1;

for (int i = 1; i < size; i++)
{
if (a[candidateIndex] == a[i])
{
count++;
}
else
{
count--;
}

if (count == 0)
{
candidateIndex = i;
count = 1;
}
}

return a[candidateIndex];
}

public static boolean isMajority(int[] a, int candidate)
{
int size = a.length;
boolean isMajority = false;
int count = 0;
for (int i = 0; i < a.length; i++)
{
if (a[i] == candidate)
{
count++;
}
if (count > size / 2)
{
isMajority = true;
break;
}

}
return isMajority;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can do this in
Time complexity O(n) and space complexity O(n) as follows.
1) Compare each even indexed element with odd indexed element, return when any two element are equal.
2) Compare each 1st,4th,7th,....indexed element with 2nd and 3rd, 5th and 6th, 8th and 9th,.... resp.
return when any two element are equal.

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Create Hash number Vs frequency
2. While adding check freq is greater than (length+1)/2

Complexity - O(n) + K Hashing == O(n)

Space complexity == 2n == O(n)

``````public static void main(String[] args) {

Integer[] a = { 1, 7, 1, 7, 1, 7, 1, 7, 1, 7, 1 };

int ln = a.length;

Map<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < a.length; i++) {

int freq = 0;

if (map.get(a[i]) == null) {

freq = 1;
map.put(a[i], 1);

} else {

freq = map.get(a[i]);

freq++;

map.put(a[i], freq);

}

if (freq > (a.length / 2)) {
System.out.println("Desired Number " + a[i]);
}
}

System.out.println(map);

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Create Hash number Vs frequency
2. While adding check freq is greater than (length+1)/2

Complexity - O(n) + K Hashing == O(n)

Space complexity == 2n == O(n)

``````public static void main(String[] args) {

Integer[] a = { 1, 7, 1, 7, 1, 7, 1, 7, 1, 7, 1 };

int ln = a.length;

Map<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < a.length; i++) {

int freq = 0;

if (map.get(a[i]) == null) {

freq = 1;
map.put(a[i], 1);

} else {

freq = map.get(a[i]);

freq++;

map.put(a[i], freq);

}

if (freq > (a.length / 2)) {
System.out.println("Desired Number " + a[i]);
}
}

System.out.println(map);

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.Arrays;
import java.util.Hashtable;

public static void main(String[] args) {
// TODO Auto-generated method stub

int inputArry[] = { 2, 2, 2, 5, 7 };
Arrays.sort(inputArry);
}

private static int hashLogicFindLeader(int[] inputArry) {
// TODO Auto-generated method stub
if (inputArry.length <= 0)
return (-1);
Hashtable<Integer, Integer> arrayMap = new Hashtable<Integer, Integer>();
int candidate = -1;
;
for (int i = 0; i < inputArry.length; i++) {
if (arrayMap.containsKey(inputArry[i]))
arrayMap.put(inputArry[i], arrayMap.get(inputArry[i]) + 1);
else
arrayMap.put(inputArry[i], 1);
}
for (Integer i : arrayMap.keySet()) {
if ((2 * arrayMap.get(i)) > inputArry.length)
candidate = i;
}
return candidate;
}

private static int sortedLogicFindLeader(int[] inputArry) {
if (inputArry.length <= 0)
return (-1);
int n = inputArry.length;
int count = 0;
int pos = n / 2;
int candidate = inputArry[pos];
for (int i = 0; i < inputArry.length; i++) {
if (inputArry[i] == candidate)
count = count + 1;
}
if ((2 * count) > n)
return candidate;
return (-1);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int half(int a[],int n)
{
int count=1,temp=a;
for(int i=1;i<n;i++)
{
if(a[i]==temp) count++;
else count--;
if(count==0) { temp=a[i]; count=1;}
}
count =0;
for(int i=0;i<n;i++)
{
if(temp== a[i] count++;
}
if(count>=(n+1)/2) return temp;
else return -1;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Moore's voting algorithm is most optimal way to solve this. Thanks to the ones who suggested this. Here is my java implementation.

``````public static int findMaximumFrequency(int[] array) {

int len = array.length;
int currentIndex = 0;
int count = 1;

for (int i = 2; i < len; i++) {
if (array[i] == array[currentIndex]) {
count++;
} else {
count--;
}

if (count == 0) {
currentIndex = i;
count = 1;
}
}
int tempCounter = 0;
for (int i = 0; i < len; i++) {
if (array[i] == array[currentIndex]) {
tempCounter++;
}
}
if (tempCounter > len / 2) {
return array[currentIndex];
} else {
return -1;
}

}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.