Linkedin Interview Question SDE1s
Country: India
Interview Type: Written Test
how are you so sure M[1] is the number?
if the array is
[5,6,7,7,7,7]
will this still work?
Can you please read the algorithm once again.
M[1] is not that number, it is A, which may be M[1], 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.
No you are right! only thing is how you check whether 7 is the correct candidate ..
So it will be O(n)+O(n) ?
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.
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;
}
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
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.
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
else add element with count=1
Then go thourgh this dictionary and find if any count is > n/2
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;
}
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[0];
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);
}
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
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));
}
}
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 ;
#include<stdio.h>
int main()
{
int a[8]={2,1,2,1,3,1,5,1}, A[8]={0}, f[8]={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....
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);
}
}
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
{
System.out.println("Majority element not found");
}
}
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;
}
}
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.
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);
}
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);
}
import java.util.Arrays;
import java.util.Hashtable;
public class FindLeaderInArray {
public static void main(String[] args) {
// TODO Auto-generated method stub
int inputArry[] = { 2, 2, 2, 5, 7 };
System.out.println("Hash Logic Leader: "
+ hashLogicFindLeader(inputArry));
Arrays.sort(inputArry);
System.out.println("Sort Logic Leader: "
+ sortedLogicFindLeader(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);
}
}
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;
}
}
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[1]; 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)
- sonesh March 19, 2013