cooldaa
BAN USERThanks for pointing the bug. The correction is that I initialize both max and secondMax to the lowest possible integer value and then traverse the loop from the first element.
int secondMaxEle(int a[], int len) {
int max = INT_MIN, secondMax = INT_MIN, i;
for(i = 0; i < len; i++) {
if(a[i] > max) {
secondMax = max;
max = a[i];
}
else if(a[i] > secondMax && a[i] < max)
secondMax = a[i];
}
return secondMax;
}
We will use two index variables, one to traverse through the entire original string, the other to write at appropriate place in the string to generate the compressed string.
void compress(char str[]) {
int i = 0, j = 0, count = 0;
do {
if(str[i] == str[j])
count++;
else {
if(count > 1)
str[++j] = count + '0';
str[++j] = str[i];
count = 1;
}
} while(str[i++] != '\0');
str[++j] = '\0';
}
One way is to create a hash map of all the numbers from 1 to 100, which will record the count of each number. If any count of any number is incremented twice, we get the repeating number.
void findRepeatedEle(int a[], int len) {
int hash[len], i;
for(i = 0; i < len; i++)
hash[i] = 0;
for(i = 0; i < len; i++) {
if(hash[a[i]]) {
printf("The repeated element is %d\n", a[i]);
break;
}
hash[a[i]]++;
}
}
The other way is to create a binary search tree. When a node in the tree matches the value of the next element being inserted, we get the repeating element.
- cooldaa January 30, 2012It can be done by performing Counting Sort twice.
For the first time the frequency of each number is counted in another array.
For the second time, we perform counting on the frequencies with same value.
Space complexity = O(4n). Time Complexity = O(5n). So basically both space and time complexities are of the order n.
#include <stdio.h>
# define ARY_SIZE 50
//a[] is input array, d[] is output array
int sortByFreq(int a[], int d[], int len) {
int b[len], c[len], i, newLen = 0;
for(i = 0; i < len; i++) {
b[i] = 0;
c[i] = 0;
}
// Frequency of each element is stored in b[]
for(i = 0; i < len; i++)
b[a[i]]++;
// Counting for freq with same value in c[]
for(i = 0; i < len; i++)
c[b[i]]++;
// indexing for the output in array d[]
for(i = len - 2; i > 0; i--)
c[i] += c[i+1];
// d[] is finally created now
for(i = len - 1; i >= 0; i--) {
if(b[a[i]]) {
d[c[b[a[i]]] - 1] = a[i];
c[b[a[i]]]--;
b[a[i]] = 0;
newLen++;
}
}
return newLen;
}
int main() {
int len = 0, n;
int a[ARY_SIZE];
printf("Enter the numbers of the array:\n");
while(scanf("%d", &n) == 1)
a[len++] = n;
int d[len];
len = sortByFreq(a, d, len);
printf("The sorted array in decreasing frequency is:\n");
for(n = 0; n < len; n++)
printf("%d ", d[n]);
printf("\n");
}
void maxCount(int a[], int len) {
int i = 0;
int maxNum, maxCount = 0, curr_num, curr_count = 0;
for(i = 0; i < len; i++) {
if(a[i] == curr_num) curr_count++;
else {
if(curr_count > max_count) {
max_count = curr_count;
max_num = curr_num;
}
curr_count = 1;
curr_num = a[i];
}
}
printf("%d has maximum count of %d", max_num, max_count);
}
This is too much for a phone interview. because infix expressions need parenthesis to correctly identify the order of evaluation, you will need to form a precedence table of operators, including parenthesis. A stack is also needed to hold the operands. There is a detailed discussion about it in the "Data Structures using C & C++" by Langsam, Augenstein and Tenenbaum.
- cooldaa January 29, 2012Modified Binary search will do
int search(int a[], int l, int u, int x) {
while (l <= u) {
int m = (l + u) / 2;
if (x == a[m]) {
return m;
} else if (a[l] <= a[m]) {
if (x > a[m]) {
l = m+1;
} else if (x >=a [l]) {
u = m-1;
} else {
l = m+1;
}
}
else if (x < a[m]) u = m-1;
else if (x <= a[u]) l = m+1;
else u = m - 1;
}
return -1;
}
int circular_shift(int num, int k, char dir) {
int n = 1;
if (dir) //assume dir = 1 for left shift
n = ~n; // for left shift, n will hold 1 in the highest bit position
while(k--) {
if(dir) {
if(num&n) //if highest bit holds 1;
num = num<<1 + 1; //then add 1 to the left shift
else num = num<<1; //otherwise, just simply shift
} else {
if(num&n) //if lowest bit holds 1
num = (num>>1) | ~n; //add 1 to highest bit
else num = num>>1; //otherwise just make simple right shift
}
}
}
I feel BVargese need to correct just a bit. instead of comparing first half with second, we need to compare reverse of first half with second. If the reverse of first half is greater, we just have to paste it as such. Otherwise, if the reverse of first half is smaller, add one to the original, reverse and then paste.
eg:
4135: reverse(41) = 14 < 35. So, 41+1=42, reverse(42) = 24. So, 4224 is the answer.
41935: 419+1=420. So, 42024 is an answer.
I feel all cases are included now.
if the use of space is not permitted, the solution provided by wdong seems plausible.
- cooldaa February 03, 2012