Finding the max repeated element in an array
Posted on January 18, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem : Find the element which occurs maximum number of times.
METHOD 1 : Sorting the array and scanning the array
The simple solution is to
Sort the array Scan the array such that keep the track of the elements which occurred max number of times METHOD 2 : Using Binary Search Tree
We can have a binary search tree with an extra field count, which indicates the number of times an element appeared in the input.
[Read More]Remove duplicate characters in a string
Posted on January 18, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem Given a string, Write a program to remove duplcate characters from the string.
Input String : kodeknight
Output String : kodenight
Solution Method 1 : Brute force
void removeDuplicates(char \*str) { if (!str) return; int len = strlen(str); if (len < 2) return; int tail = 1; for (int i = 1; i < len; ++i) { int j; for (j = 0; j < tail; ++j) if (str
i == str
j) break; if (j == tail) { str
tail = str
i; ++tail; } } str
tail = '\\0'; } Time Complexity : O(N^2)
[Read More]Find first non repeating character in a string
Posted on January 18, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
You are given a string, find its first non-repeating character?
Algorithm:
- Scan the string from left to right and construct the count array.
- Again, scan the string from left to right and check for count of each character, if you find an element who’s count is 1, return it.
Code :
#include<stdlib.h>
#include<stdio.h>
#define NO\_OF\_CHARS 256
/\* The function returns index of first non-repeating
character in a string \*/
int getFirstNonRepeating(char \*str)
{
int \*count = (int \*)calloc(sizeof(int), NO\_OF\_CHARS);
int i;
for (i = 0; \*(str+i); i++)
count\[\*(str+i)\]++;
int index = -1;
for (i = 0; \*(str+i); i++)
{
if(count\[\*(str+i)\] == 1)
{
index = i;
break;
}
}
return index;
}
Time complexity: O(N)
Finding an integer that repeats odd number of times in an array of positive integers
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Question: In an array of positive integers, all but one integer repeats odd number of times. Can you find that integers in O(n) time complexity?
Solutions
Answer: in order to solve this problem in O(n) time, we need to use bitwise manipulation. Since there is only one integer that repeats odd number of times, we can use the XOR operator to find out that number. When a number XOR with itself, it will become 0.
[Read More]Find the First Duplicated Integer in an Array containing numbers from 1 to N Without Using Extra Memory
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
let the array be 3 1 2 1 3 4 first repeated integ… Unknown - Mar 6, 2013let the array be 3 1 2 1 3 4
first repeated integer is 3 here
start from the first and go till the end
add n+1 to the a[a[i]] where i is the current index.
iterate again dividing the values by n+1 if values comes 1 . the remainder is the repeated one.
[Read More]Find the First Duplicated Integer in an Array containing numbers from 1 to N Without Using Extra Memory
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Question: There is a size-N array of integers whose values range from 1 to N. Some integers are duplicated. Find the first duplicate and its index without using any extra memory (not even O(1)).
Solution There are a few keys in the question that we should consider:
The array size is a finite number N which is also the upper limit for any integer inside the array. Hence, if the array size is 10, then there are ten elements in the array and each of those elements is between 1 and 10.
[Read More]Remove duplicates from an unsorted linked list
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
Write code to remove duplicates from an unsorted linked list.
FOLLOW UP: How would you solve this problem if a temporary buffer is not allowed?
**Example **
Input/Output
Original linked list:
2 -> 3 -> 2 -> 5 -> 2 -> 8 -> 2 -> 3 -> 8 -> null
After deleting duplicate node:
2 -> 3 -> 5 -> 8 -> null
We have already seen deleting duplicates from the sorted list.
[Read More]First non repeating element in the array
Posted on December 31, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Question: Write an algorithm to find the first non-repeated character in a string. For example, the first non-repeated character in the string ‘abcdab’ is ‘c’.
Answer: Seems trivial enough right? If a character is repeated, we should be able to search the string to determine if that character appears again. So if we go about doing this for every character in the string, our worst case run time would O(n^2). Here is some code to show this logic.
[Read More]Majority element in the array
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Majority Element: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).
Problem: Given an array consisting of N integers, find the number with the maximum occurrences, i.e. majority element, given the assumption that the number occurs more than N/2 times in the array.
Example
I/P : 3 3 4 2 4 4 2 4 4
[Read More]One duplicate , one missing element in an array
Posted on October 1, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
You have an array of size 100 which stores integers from 0 to 99.
In this array one number is a duplicate, that means one is missing.
How can we find duplicate and missing ?
Method 1
1. Since one element is missing , some element must be repeated once in the array.
2. Let x be the missing and y be the repeated element
3. Calculate the sum of all the elements and sum of squares of all the elements of array.
[Read More]