JoshMachine
BAN USERIf i am getting right, someone proposed an additional array of size n^2 so that you read elements one by one from the original array and put them in new array according to the index(assuming no duplicates). But while reading back the sorted array you have to again read n^2 spaces in new array. That still makes complexity of n^2.
The above strategy works when you have to sort n numbers in [0:m] where m = O(n)
What do you mean by "unique words". If uniques words are one that appear once than their count will be one or is the unique word given as input by the user and you have to calculate its occurrence?
- JoshMachine November 19, 2010Your solution has O(N) complexity
- JoshMachine November 15, 2010As so many ppl got a call, im planning to apply for same position ;)
- JoshMachine November 15, 2010Here u go sir!
#include <iostream>
using namespace std;
int dupSearch (int arr[], int mid, int num, int first, int arraySize){
if(first == 1)
{
if(arr[mid - 1] == num && mid > 0)
return dupSearch(arr, mid -1, num, first, arraySize);
else
return mid;
}
else{
if(arr[mid + 1] == num && mid < arraySize)
return dupSearch(arr, mid + 1, num, first, arraySize);
else
return mid;
}
}
int binarySearch(int arr[], int left, int right, int num, int first, int arraySize){
int mid = left + (right - left)/2;
if(right - left < 1)
return mid;
if(arr[mid] > num)
return binarySearch(arr, left, mid - 1, num, first, arraySize);
else if(arr[mid] < num)
return binarySearch(arr, mid + 1, right, num, first, arraySize);
else if(arr[mid] == num)
return dupSearch(arr, mid, num, first, arraySize);
}
int main(){
int arr[] = {1, 2, 2, 3, 3, 5, 6, 7, 8, 8};
int left = 0, arraySize = sizeof(arr)/sizeof(arr[0]);
int index0, index1, num1 = 4, num2 = 8;
index0 = binarySearch(arr, 0, arraySize - 1, num1, 1, arraySize);
index1 = binarySearch(arr, 0, arraySize - 1, num2, 0, arraySize);
cout << "Print elements in range of " << num1 << " and " << num2 << "\n";
for(int i = index0; i <= index1; i++){
cout << arr[i] << " ";
}
cout << "\n";
return 0;
}
Wrong. 4 and 5 are next to each other.
- JoshMachine November 15, 2010You didn't consider the case that number is not present in the array.
- JoshMachine November 15, 2010Then we need a handshake before a connection so that the receiver can know character-hoffman code pairing
- JoshMachine November 14, 2010There can actually be many solutions:
7|1|8|4
-------
5|3|6|2
7|3|6|4
-------
5|1|8|2
Only thing i can guess is that 1 and 8 should occupy those middle four square as they just have affinity for single number.
- JoshMachine November 11, 2010Above comment was mine I forgot to sign in
- JoshMachine November 10, 2010What I mean is to inorder traverse the left and right child of root separately and store in a stack and then compare the 2 stacks. I see no reason why it wont work. It is a long procedure as it waits till both stacks are fully created to compare.
4
12 12
5 6 5 6
7 8 9 3 7 8 9 3
so the stack created for left and right child of 4 will be
same 7->5->8->12->9->6->3
Correct me if i am wrong?
Create two stacks traversing inorder both left and right children of the root node separately.
Pop the values from the stack one at a time and compare.
Aaah! Thanks that sounds right and awesome explanation :)
- JoshMachine November 09, 2010Do we have to give output in integer or decimal points as well. Integer its straight forward subtraction
- JoshMachine November 08, 2010I don't understand those conditions and believe it doesn't work, its simple 2 pointer solution
count = 0; temp1 = start; temp2 = start;
while(temp1->next != NULL && temp2->next->next != NULL)
{
if(temp1 == temp2 && count !=0)
{ cout << "cycle"; break;}
count++;
temp1 = temp1->next;
temp2 = temp2->next->next;
}
Please explain it with an example:
Say the sequence is 2 8 0 5 4 2 3 8 0 4 8
Question is incomplete as it doesn't give any constrain, though reversing the list sounds like a better solution. Anyways you can tell both the solutions and let the interviewer choose.
- JoshMachine November 07, 2010Or something like in stackoverflow, where users can flag a question as 'incomplete' and flagged incomplete questions get deleted automatically!
- JoshMachine November 06, 2010Agreed, I also couldn't think something else either. Does it make a difference if the question states each alternate increasing/decreasing sequences are of length 'k'?
- JoshMachine November 06, 2010I have a question .. ead and eda .. 2 combinations or one?
- JoshMachine November 04, 2010#include <iostream>
using namespace std;
void findElement(int a[], int left, int right)
{
int mid = left + (right - left)/2;
if (right == left)
cout << a[left] << endl;
else if(( mid%2 != 0 && a[mid - 1] == a[mid]) || ( mid%2 == 0 && a[mid + 1] == a[mid]))
findElement(a, mid + 1, right);
else
findElement(a, left, mid);
}
int main()
{
int a[] = {0,0,1,1,2,3,3,4,4,5,5,6,6,7,7};
int n = sizeof(a)/ sizeof(a[0]);
findElement(a, 0, n-1);
return 0;
}
You are not using the case that the given array is sorted. Others did it in O(log n)
- JoshMachine November 02, 2010This is brute force approach .. Can it be done in better than O(n^3) ??
- JoshMachine November 02, 2010#include <iostream>
using namespace std;
int main()
{
int a[] = {0,0,1,1,0,1};
int b[] = {1,0,1,0,0,0};
int n = sizeof(a)/ sizeof(a[0]);
int p = 0, q = 0, sumA = 0, sumB = 0, sum = 0;
for(int k = 0; k < n-1; k++)
{
for (int j = n-1; j > 0; j--)
{
sumA = 0; sumB = 0;
for(int i = k; i <= j; i++)
{
sumA += a[i];
sumB += b[i];
}
if(sumA == sumB && j > k && (q-p) < (j-k))
{
p = k; q = j; sum = sumA;
}
}
}
cout << p << " " << " " << q << " " << sum << endl;
return 0;
}
Any reason of declaring tmp_str inside the loop as i guess it will create a new tmp_str variable in each loop iteration?
- JoshMachine November 02, 2010#include<iostream>
using namespace std;
int main()
{
int b[] = {0,0,2,0,3,0,0,4,5,6,7,0,0,8};
i = 0; j = 1;
int sizeOfArray = sizeof(b) / sizeof(b[0]);
while(j < sizeOfArray - 1)
{
while(b[i] != 0)
i++;
while(b[j] ==0)
j++;
b[i] = b[j] ;
b[j] = 0;
}
for (int i = 0; i <= 13; i++)
{ cout << b[i] << " ";}
}
#include <iostream>
using namespace std;
void swap(int * a1, int * a2)
{
int temp = *a1;
*a1 = *a2;
*a2 = temp;
}
int main()
{
int numberOfElements = 8;
int a[] = {1,3,6,8,-5,-2,3,8};
int i=0, j= numberOfElements/2;
while(i <= numberOfElements/2)
{
if(a[i] > a[j])
swap(&a[i], &a[j]);
j = numberOfElements/2 ;
while(j < (numberOfElements - 1))
{
if(a[j] > a[j+1])
swap(&a[j], &a[j+1]);
j++;
}
j= numberOfElements/2;
i++;
}
return 0;
}
Naa .. IMO it works just fine to give smallest 1 million nos as the new number we are taking in just for comparison with the top most element in the max heap and memory is only used for storing data.
- JoshMachine October 28, 2010
When 2nd adds his salary and passes it to the 3rd one everyone knows his salary and the same with the 3rd one.
- JoshMachine November 22, 2010So at each step everyone adds his salary and a random number and the same thing happens and after one circle every one subtract their random number and in the end they get total salary sum and the average.