avikodak
BAN USERUse recursion
bool CheckSingleLinkedListIsPalindromeOrNotRecursion(linkedListNode *ptr,linkedListNode **begin){
if(ptr == NULL){
return true;
}
if(ptr->next == NULL){
//Reached last node
if(ptr->value == (*begin)->value){
*begin = (*begin)->next;
return true;
}
return false;
}
bool truthValue = CheckSingleLinkedListIsPalindromeOrNot(ptr->next,begin);
if(!truthValue){
return false;
}
return ptr->value == (*begin)->value?(*begin)=(*begin)->next,true:false;
}
I don't think we have to check whether entire array is sequential for each assumption . It would be sufficient to check the first two numbers(for each assumption units,tens,hundreds ... and handle cases when it is largest number for each assumption ie it is 9 ,99,999....) and see that the difference accounts to either one or two
- avikodak August 29, 2013If there are only parent node . The diameter of the tree would the largest path from the leaves to the root
For example consider the tree
10
2 3
4 6
7
Diameter : Longest path between two nodes
For the example above the longest path would be from 7 to 10 (10 has no child pointers) since all the paths are directed paths from the leaves to root .
Algo 1:
Use two pointers
linkedListNode *FindFifthElementFromEnd(linkedListNode *ptr){
if(ptr == NULL){
return NULL;
}
linkedListNode *frontCrawler = ptr,*tailCrawler= ptr;
int counter = 5;
while(counter){
if(frontCrawler->next != NULL){
frontCrawler = frontCrawler->next;
}else{
return NULL;
}
}
while(frontCrawler->next!= NULL){
frontCrawler = frontCrawler->next;
tailCrawler = tailCrawler->next;
}
return tailCrawler;
}
Algo 2:
1) Use hashmap
2) return appropriate node
linkedListNode *FindFifthElementFromEndHashMap(linkedListNode *ptr){
if(ptr == NULL){
return NULL;
}
hash_map<int,int> nodeIndexMap;
int counter = -1;
linkedListNode *crawler= ptr;
while(crawler != NULL){
nodeIndexMap.insert(pair<int,int>(++counter,ptr->value));
crawler = crawler->next;
}
if(counter < 4){
return NULL;
}
return nodeIndexMap[counter-4];
}
Algo 3:
1) Find length of linkedlist
2) Return node length - 5
linkedListNode *FindFifthElementFromEndUsingLength(linkedListNode *ptr){
if(ptr == NULL){
return NULL;
}
linkedListNode *crawler = ptr;
int lengthOfLinkedList = 0;
while(crawler != NULL){
lengthOfLinkedList++;
crawler = crawler->next;
}
if(lengthOfLinkedList < 5){
return null;
}
lengthOfLinkedList -= 5;
crawler = ptr;
while(lengthOfLinkedList--){
crawler = crawler->next;
}
return crawler;
}
Algo 1:
---------
Convert binary to decimal and then from decimal to base 4 number
int ConvertBase2NumberToBase4(long userInput){
int decimalNumber,numberInBase4;
int lastDigit;
int multiply = 1;
while(userInput){
lastDigit = userInput % 10;
userInput /= 10;
decimalNumber += (lastDigit * multiply);
multiply *= 2;
}
while(decimalNumber < 4){
lastDigit = userInput %4;
userInput /= 4;
numberInBase4 = (numberInBase4 *10) + lastDigit;
}
return numberInBase4;
}
2) Club two two digit and find the equivalent in base 4
int ConvertBase2NumberToBase4Merging2Digits(long userInput){
int lastTwoDigits,cummulativeSum,numberInBase4 = 0;
while(userInput){
lastTwoDigits = userInput % 100;
cummulativeSum = lastTwoDigits%10;
lastTwoDigits /= 10;
cummulativeSum = 2 * (lastTwoDigits %10);
numberInBase4 = numberInBase4 << 3 + numberInBase4 << 1 + cummulativeSum;
userInput /= 100;
}
return numberInBase4;
}
1) Take the current elevators position in an array from top to bottom (sorted order)
2) Find the floor and ceil for the user position using binary search. Take the minimum distance from user position to floor and ceil and return the appropriate index
int FindClosestElevatorUsingBinarySearch(int elevatorsPositionInOrder[],int startArray,int endArray,int key){
if(startArray > endArray){
return INT_MIN;
}
int middleIndex = (startArray + endArray)/2;
if(elevatorsPositionInOrder[middleIndex] == key){
return middleIndex;
}
if(middleIndex-1 < startArray){
if(elevatorsPositionInOrder[middleIndex] < key){
return middleIndex;
}
}
if(middleIndex+1 > endArray){
if(elevatorsPositionInOrder[middleIndex] > key){
return middleIndex;
}
}
if(elevatorsPositionInOrder[middleIndex-1] < key && elevatorsPositionInOrder[middleIndex+1] < key){
return abs(key - elevatorsPositionInOrder[middleIndex-1]) > abs(key-elevatorsPositionInOrder[middleIndex+1])?middleIndex+1:middleIndex-1;
}
if(elevatorsPositionInOrder[middleIndex] > key){
return FindClosestElevatorUsingBinarySearch(elevatorsPositionInOrder,startArray,middleIndex-1,key);
}else{
return FindClosestElevatorUsingBinarySearch(elevatorsPositionInOrder,middleIndex+1,endArray,key);
}
}
int MElevatorsNFloors(int elevatorsPositionInOrder[],int noOfElevators,int userRequest){
if(elevatorsPositionInOrder == NULL || noOfElevators == 0){
return INT_MIN;
}
return FindClosestElevatorUsingBinarySearch(elevatorsPositionInOrder,0,noOfElevators-1,userRequest);
}
Algo 1: O(n^2)
void RearrangeAnArrayUsingSwapZeroON2(int userInputSource[],int userInputTarget[],int sizeOfArray){
if(userInputSource == NULL && userInputTarget == NULL){
return;
}
if(userInputSource == NULL || userInputTarget == NULL){
return;
}
int zeroIndex=0,targetElementIndex,tempForSwap;
int outerCounter,innerCounter;
for(outerCounter = 0;outerCounter < sizeOfArray;outerCounter++){
if(userInputTarget[outerCounter] == 0){
continue;
}
if(userInputSource[outerCounter] == userInputTarget[outerCounter]){
continue;
}
if(userInputSource[zeroIndex] != 0){
for(innerCounter = 0;innerCounter < sizeOfArray;innerCounter++){
if(userInputSource[innerCounter] == 0){
zeroIndex = innerCounter;
}
if(userInputSource[innerCounter] == userInputTarget[innerCounter]){
targetElementIndex = innerCounter;
}
}
}
tempForSwap = userInputSource[zeroIndex];
userInputSource[zeroIndex] = userInputSource[outerCounter];
userInputSource[outerCounter] = tempForSwap;
tempForSwap = userInputSource[targetElementIndex];
userInputSource[targetElementIndex] = userInputSource[zeroIndex];
userInputSource[zeroIndex] = tempForSwap;
zeroIndex = targetElementIndex;
}
}
Algo 2: O(NlogN)
------------------------
1) Sort the first set of numbers
2) Perform a binary Search (Handle when middle index points to zero .... no need to move the numbers)
int BinarySearchForZeroSwap(int userInput[],int startArray,int endArray,int key){
if(startArray > endArray){
return INT_MIN;
}
int middleIndex = (startArray + endArray)/2;
if(userInput[middleIndex]==key){
return middleIndex;
}
if(userInput[middleIndex] == 0){
if(middleIndex-1 > startArray){
if(userInput[middleIndex-1] > key){
return BinarySearchForZeroSwap(userInput,startArray,middleIndex-1,key);
}else{
return BinarySearchForZeroSwap(user,middleIndex+1,endArray,key);
}
}else{
return BinarySearchForZeroSwap(userInput,middleIndex+1,endArray,key);
}
}
if(userInput[middleIndex] > key){
return BinarySearchForZeroSwap(userInput,startArray,middleIndex-1,key);
}else{
return BinarySearchForZeroSwap(userInput,middleIndex+1,endArray,key);
}
}
void RearrangeAnArrayUsingSwapZeroSortingONLOGN(int userInputSource[],int userInputTarget[],int sizeOfArray){
if(userInputSource == NULL && userInputTarget == NULL){
return;
}
if(userInputSource == NULL || userInputTarget == NULL){
return;
}
sort(userInputSource,userInputSource+sizeOfArray);
int zeroIndex = 0;
int targetElement,targetElementIndex,tempForSwap;
for(int counter = 0;counter < sizeOfArray;counter++){
targetElement = userInputTarget[counter];
targetElementIndex = BinarySearchForZeroSwap(userInputSource,counter,sizeOfArray-1,targetElement);
tempForSwap = userInputSource[zeroIndex];
userInputSource[zeroIndex] = userInputSource[targetElementIndex];
userInputSource[targetElementIndex] = tempForSwap;
zeroIndex = targetElementIndex;
}
}
Algo O(N) :
--------------
1) Use hash map
2) Store the indexes and swap by traversing the target array
void RearrangeAnArrayUsingZeroHashMapON(int userInputSource[],int userInputTarget[],int sizeOfArray){
if(userInputSource == NULL && userInputTarget == NULL){
return;
}
if(userInputSource == NULL || userInputTarget == NULL){
return;
}
hash_map<int,int> elementMapOfSource;
for(int counter =0;counter < sizeOfArray;counter++){
elementMapOfSource.insert(pair<int,int>(userInputSource[counter],counter));
}
int targetElement,tempForSwap,indexOfTargetElement,zeroIndex;
zeroIndex = elementMapOfSource.find(0)->second;
for(int counter =0;counter < sizeOfArray;counter++){
targetElement = userInputTarget[counter];
indexOfTargetElement = elementMapOfSource.find(targetElement)->second;
tempForSwap = userInputSource[zeroIndex];
userInputSource[zeroIndex] = userInputSource[indexOfTargetElement];
userInputSource[indexOfTargetElement] = tempForSwap;
zeroIndex = indexOfTargetElement;
elementMapOfSource[0] = zeroIndex;
}
}
Method 1:
--------------
For O(N) complexity use hashmap or binary search tree
Method 2:
--------------
For O(NLOGN) complexity sort both the strings and traverse both the strings one by one . If at any index if both are not equal then return false else return true
bool CheckWhetherTwoStringsAreAnagramsONLOGN(char *userInput1,char *userInput2){
if(userInput1 == NULL && userInput2 == NULL){
return true;
}
if(userInput1 == NULL || userInput2 == NULL){
return false;
}
if(strlen(userInput1) != strlen(userInput2)){
return false;
}
sort(userInput1,strlen(userInput1));
sort(userInput2,strlen(userInput2));
for(int counter = 0;counter < strlen(userInput1);counter++){
if(userInput1[counter] != userInput2[counter]){
return false;
}
}
return true;
}
Method 3:
--------------
For O(N^2) use two loops
You can use this recursion formulae
P(crawlerFromBeginning,crawlerFromEnd) =
if(word[crawlerFromBeginning]== word[crawlerFromEnd]){
2 + P(crawlerFromBeginning+1,crawlerFromEnd-1) // if the characters at the position
are equal
}
else{
max(P(crawlerFromBeginning+1,crawlerFromEnd) ,P(crawlerFromBeginning,crawlerFromEnd-1) )
}
Found this solution
Question: You are given an array that contains integers. The integers content is such that every integer occurs 3 times in that array leaving one integer that appears only once.
Fastest way to find that single integer
eg:
Input: [2,1,4,5,1,4,2,2,4,1]
Answer: 5
Answer: I couldn't solve this question myself at first go in O(n) with O(1) space. Searched for it and found an excellent answer here. Sharing the answer and explanation for that:
int main()
{
int B[] = {1,1,1,3,3,3,20,4,4,4};
int ones = 0 ;
int twos = 0 ;
int not_threes, x ;
for( i=0; i< 10; i++ )
{
x = B[i];
twos |= ones & x ;
ones ^= x ;
not_threes = ~(ones & twos) ;
ones &= not_threes ;
twos &= not_threes ;
}
printf("\n unique element = %d \n", ones );
return 0;
}
Explanation:
The code works in similar line with the question of "finding the element which appears once in an array - containing other elements each appearing twice". Solution is to XOR all the elements and you get the answer.
Basically, it makes use of the fact that x^x = 0. So all paired elements get XOR'd and vanish leaving the lonely element.
Since XOR operation is associative, commutative.. it does not matter in what fashion elements appear in array, we still get the answer.
Now, in the current question - if we apply the above idea, it will not work because - we got to have every unique element appearing even number of times. So instead of getting the answer, we will end up getting XOR of all unique elements which is not what we want.
To rectify this mistake, the code makes use of 2 variables.
ones - At any point of time, this variable holds XOR of all the elements which have
appeared "only" once.
twos - At any point of time, this variable holds XOR of all the elements which have
appeared "only" twice.
So if at any point time,
1. A new number appears - It gets XOR'd to the variable "ones".
2. A number gets repeated(appears twice) - It is removed from "ones" and XOR'd to the
variable "twice".
3. A number appears for the third time - It gets removed from both "ones" and "twice".
The final answer we want is the value present in "ones" - coz, it holds the unique element.
So if we explain how steps 1 to 3 happens in the code, we are done.
Before explaining above 3 steps, lets look at last three lines of the code,
not_threes = ~(ones & twos)
ones & = not_threes
twos & = not_threes
All it does is, common 1's between "ones" and "twos" are converted to zero.
For simplicity, in all the below explanations - consider we have got only 4 elements in the array (one unique element and 3 repeated elements - in any order).
Explanation for step 1
------------------------
Lets say a new element(x) appears.
CURRENT SITUATION - Both variables - "ones" and "twos" has not recorded "x".
Observe the statement "twos| = ones & x".
Since bit representation of "x" is not present in "ones", AND condition yields nothing. So "twos" does not get bit representation of "x".
But, in next step "ones ^= x" - "ones" ends up adding bits of "x". Thus new element gets recorded in "ones" but not in "twos".
The last 3 lines of code as explained already, converts common 1's b/w "ones" and "twos" to zeros.
Since as of now, only "ones" has "x" and not "twos" - last 3 lines does nothing.
Explanation for step 2.
------------------------
Lets say an element(x) appears twice.
CURRENT SITUATION - "ones" has recorded "x" but not "twos".
Now due to the statement, "twos| = ones & x" - "twos" ends up getting bits of x.
But due to the statement, "ones ^ = x" - "ones" removes "x" from its binary representation.
Again, last 3 lines of code does nothing.
So ultimately, "twos" ends up getting bits of "x" and "ones" ends up losing bits of "x".
Explanation for step 3.
-------------------------
Lets say an element(x) appears for the third time.
CURRENT SITUATION - "ones" does not have bit representation of "x" but "twos" has.
Though "ones & x" does not yield nothing .. "twos" by itself has bit representation of "x". So after this statement, "two" has bit representation of "x".
Due to "ones^=x", after this step, "one" also ends up getting bit representation of "x".
Now last 3 lines of code removes common 1's of "ones" and "twos" - which is the bit representation of "x".
Thus both "ones" and "twos" ends up losing bit representation of "x".
1st example
------------
2, 2, 2, 4
After first iteration,
ones = 2, twos = 0
After second iteration,
ones = 0, twos = 2
After third iteration,
ones = 0, twos = 0
After fourth iteration,
ones = 4, twos = 0
2nd example
------------
4, 2, 2, 2
After first iteration,
ones = 4, twos = 0
After second iteration,
ones = 6, twos = 0
After third iteration,
ones = 4, twos = 2
After fourth iteration,
ones = 4, twos = 0
Explanation becomes much more complicated when there are more elements in the array in mixed up fashion. But again due to associativity of XOR operation - We actually end up getting answer.
Take an element and take the first bit and divide them into two groups ...
ie all the elements with 1's on one side and 0's on the other side ... now count the left side elements and right side elements ( use the quick sort divide strategy ) and take the side which is not the multipple of 3 now again divide recursively untill you get 3 elements on one side and one elements on the other side .. that one element is the culprit ...
This is the best which i can get ... should try some logical operators
Solution 1:
If we are allowed to take extra space .. then we can use the hash_map and store all visited addresses and store it in the hash_map and increment the counter............. and then when node->next = any visited break the loop ... counter gives the length of the linked list .. o(n) time
Solution 2:
Add an additional element to the structure say add boolean visited ( instead of hashmap) we can check whether node->next == visited node break the loop return the counter
Use a hash map (hash_map<string,list<string>). The key for the hash map will be the sorted form of the scanned word.If the key doesnt exists in the hash map then create a list and the append the word to the list . This list serves as the value.If the key exists then append the scanned word for the list
- avikodak December 15, 2012
This method does not work
- avikodak December 22, 20141) if the lengths of the given arrays are not equal
2) if the arrays lengths is less than k