Ricky
BAN USERI think the return value should be single node* which should be pointing to entry of data[0][0]. As all elements are reachable from there.
Here is my solution in C++
struct node{
int data;
node* next;
node* down;
};
node* getLinkedList(int **data,int M,int N) {
// Create a linked list for first row the normal way.
node* parentNode = NULL;
node* currentNode = new node();
node* head = currentNode;
for(int j = 0 ; j < M; j++) {
currentNode->data = data[0][j];
currentNode->next = currentNode->down = NULL;
if ( parentNode) {
parentNode->next = currentNode;
}
parentNode = currentNode;
}
// We will keep upper row pointer so that it can be updated with down row pointer.
node* upperRowHead = head;
//Iterate on rest of matrix and create list accordingly.
for(int i = 1 ; i < N; i++) {
node* currentParentNode = NULL;
node* currentNode = new node();
node* currentHead = currentNode;
for(int j = 0 ; j < M; j++) {
currentNode->data = data[i][j];
currentNode->next = currentNode->down = NULL;
if ( currentParentNode) {
currentParentNode->next = currentNode;
}
currentParentNode = currentNode;
upperRowHead->down = currentNode;
upperRowHead = upperRowHead->next;
}
upperRowHead = head;
}
return head;
}
It can be done as follows:
// Take two int(s) for the sum as leftSum & rightSum.
int start = 0, end = n-1;
int leftSum = data[start];
int rightSum = data[end];
while ( start < end )
{
If ( leftSum > rightSum )
{
rightSum += data[--end];
}
else
{
leftSum += data[++start];
}
}
if(leftSum == rightSum)
{
return true;
}
return false;
Just found another way from geeks for geeks website.
A number n can be a mulpile of 5 in two cases. When last digit of n is 5 or 10. If last bit in binary equivalent of n is set (which can be the case when last digit is 5) then we multiply by 2 using n<<=1 to make sure that if the number is multiple of 5 then we have the last digit as 0. Once we do that, our work is to just check if the last digit is 0 or not, which we can do using float and integer comparison trick.
#include<stdio.h>
bool isMultipleof5(int n)
{
/* If n is a multiple of 5 then we make sure that last
digit of n is 0 */
if ( (n&1) == 1 )
n <<= 1;
float x = n;
x = ( (int)(x*0.1) )*10;
/* If last digit of n is 0 then n will be equal to (int)x */
if ( (int)x == n )
return true;
return false;
}
/* Driver program to test above function */
int main()
{
int i = 19;
if ( isMultipleof5(i) == true )
printf("%d is multiple of 5\n", i);
else
printf("%d is not a multiple of 5\n", i);
getchar();
return 0;
}
Just found another way from geeks for geeks website.
A number n can be a mulpile of 5 in two cases. When last digit of n is 5 or 10. If last bit in binary equivalent of n is set (which can be the case when last digit is 5) then we multiply by 2 using n<<=1 to make sure that if the number is multpile of 5 then we have the last digit as 0. Once we do that, our work is to just check if the last digit is 0 or not, which we can do using float and integer comparison trick.
#include<stdio.h>
bool isMultipleof5(int n)
{
/* If n is a multiple of 5 then we make sure that last
digit of n is 0 */
if ( (n&1) == 1 )
n <<= 1;
float x = n;
x = ( (int)(x*0.1) )*10;
/* If last digit of n is 0 then n will be equal to (int)x */
if ( (int)x == n )
return true;
return false;
}
/* Driver program to test above function */
int main()
{
int i = 19;
if ( isMultipleof5(i) == true )
printf("%d is multiple of 5\n", i);
else
printf("%d is not a multiple of 5\n", i);
getchar();
return 0;
}
It can be done as follows:
IsValidBST(root,-infinity,infinity);
bool IsValidBST(BinaryNode node, int MIN, int MAX)
{
if(node == null)
return true;
if(node.element > MIN
&& node.element < MAX
&& IsValidBST(node.left,MIN,node.element)
&& IsValidBST(node.right,node.element,MAX))
return true;
else
return false;
}
O(n)
1. Find the cube of each number starting from 1 to (n-3) and store in an array.
2. Search the combination of numbers which can sum to n ( I used binary search to do so)
// Use binary search to find the element.
int getIndex(int* data, int start, int end, int num)
{
if ( start < end )
{
if ( data[(start + end)/2] == num )
{
return ((start + end)/2);
}
else if ( data[(start + end)/2] > num )
{
return getIndex(data,start,(start + end)/2, num);
}
else
{
return getIndex(data,(start + end)/2 + 1, end, num);
}
}
else if ( start == end)
{
return data[start] == num ? start : -1;
}
return -1;
}
void printAllCombination(const int num)
{
//std::map<int,int> cube;
const int cubeArrsize = (num/3) + 1;
int *cubeArr = new int[num + 1];
// Find the cube of each number and store in array.
for ( int i = 1; i< cubeArrsize; i++)
{
cubeArr[i] = i*i*i;
}
// Do a binary search for the remaining number from the given position.
for ( int i = 1; i< cubeArrsize; i++)
{
int j = getIndex(cubeArr, i+1, cubeArrsize,num - cubeArr[i]);
if ( j > 0 )
{
std::cout<<"\n"<<i<<" , "<<j;
}
}
delete[] cubeArr;
}
int main()
{
printAllCombination(224);
std::cout<<std::endl;
getch();
}
Got another optimized way.
Algo:
1. Check at which position 4 is found i.e. one, tens, hundred, thousand etc.
2. Skip that much of elements
a. If 4 is found at one position then we can't skip checking of any element
b. For others starting from tens position we can skip elements as 9, 99 , 999 ,9999 so on.
I created both the function optimized and non optimized to check the result, and calculate the performance on the basis of checking being done. I am able to achieve upto 46% of less comparison in optimize method.
int getCountForNumberOptimized(int num)
{
int count = 0;
int numDigits = 1;
int posFoundAt = 0;
int checkDone = 0;
for (int i = 1; i< num; i++)
{
++checkDone;
numDigits = 1;
posFoundAt = 0;
int temp = i;
while ( temp )
{
if ( temp % 10 == 4 )
{
//Digit 4 found. Dont' stop we need to fing the position for top most occurence of 4
posFoundAt = numDigits;
}
temp /= 10;
++numDigits;
}
if ( posFoundAt == 0)
{
++count;
}
if ( posFoundAt >= 2)
{
// Digit 4 exists in the number for sure.
// Check the position if it exists from tens position ownwards we can skip the checking for that number range.
int getSkippedNumber = 1;
while(posFoundAt > 1)
{
getSkippedNumber *= 10;
--posFoundAt;
}
getSkippedNumber -= 1;
i += getSkippedNumber;
}
}
std::cout<<"\nNumbers found in Optimize way: "<<count;
std::cout<<"\nChecks Done in Optimize way : "<<checkDone;
return checkDone;
}
int getCountForNumber(int num)
{
std::cout<<"\n\n\t****Range upto "<<num<<"****"<<std::endl;
int count = 0;
int checkDone = 0;
for (int i = 1; i< num; i++)
{
++checkDone;
int temp = i;
while ( temp )
{
if ( temp % 10 == 4 )
{
//Digit 4 found.
break;
}
temp /= 10;
}
if ( temp == 0)
{
++count;
}
}
std::cout<<"\nNumbers found in normal way : "<<count;
std::cout<<"\nChecks Done in normal way : "<<checkDone;
return checkDone;
}
void compareBothMethod(int num)
{
int normalChecks, optimizeChecks;
normalChecks = getCountForNumber(num);
optimizeChecks = getCountForNumberOptimized(num);
if ( normalChecks > optimizeChecks )
std::cout<<"\nPerformance Achieved : "<<( ( (normalChecks - optimizeChecks) / (normalChecks * 1.0) ) * 100.0)<<"%";
}
int main()
{
int num = 10;
for ( int i =0; i < 7;i++)
{
compareBothMethod(num);
num *= 10;
}
std::cout<<std::endl;
}
Another approach would be:
1. Traverse each array and insert the value in the map and if value already exists in the map then update the counter for the same.
2. After all array set is traversed. Traverse the map and check if any data is having count equal to 5 then print that.
Limitation: Make sure the array contains unique values only.
void insertTheDataInMap(std::map<int,int>& mapCounter, int* data, int length)
{
std::map<int,int>::iterator it;
for ( int i = 0; i < length; i++)
{
it = mapCounter.find(data[i]);
if ( it == mapCounter.end() )
{
mapCounter.insert(std::make_pair<int,int>(data[i],0));
}
mapCounter[data[i]] += 1;
}
}
int main()
{
int arr1[] = {7,10,12};
int arr2[] = {8,7,10};
int arr3[] = {7,10,9};
int arr4[] = {13,10,7};
int arr5[] = {6,7,10};
// Insert the whole array in map, if value already exists then increment the counter.
// Later traverse the map and check if count ==5 then print that element.
std::map<int,int> mapCounter;
insertTheDataInMap(mapCounter, arr1, 3);
insertTheDataInMap(mapCounter, arr2, 3);
insertTheDataInMap(mapCounter, arr3, 3);
insertTheDataInMap(mapCounter, arr4, 3);
insertTheDataInMap(mapCounter, arr5, 3);
std::map<int,int>::iterator it;
for ( it = mapCounter.begin(); it != mapCounter.end(); ++it)
{
if ( it->second == 5 )
{
std::cout<<"\t"<<it->first;
}
}
}
bool isBST(Node* root, int& previousValue)
{
if ( root )
{
if ( !isBST(root->m_left,previousValue) )
{
return false;
}
std::cout<<"\t"<<root->m_data<<" prev :"<<previousValue;
if ( root->m_data < previousValue )
{
return false;
}
previousValue = root->m_data;
if ( !isBST(root->m_right, previousValue) )
{
return false;
}
}
return true;
}
Every time find the mid of the array/sub-array and make it as root.
e.g. array is 1,2,3,4,5,6,7,8,9
1. Find mid i.e. 5 which will be root.
2. Elements at the left hand side of 5 will be left sub tree and rest will be right sub tree.
3. Recursively call left and right sub array.
1. Traverse the whole number and store each digit in array
2. Start from last position to first position
i = n-1, j = n -2
while ( j >= 0)
{
if ( data[n - i] > data [i -2]
{
swap the value for (n - i) & (n-j). Print the same and break.
}
else
{
// Swap the value for (n - i) & (n-j).
}
i = j ;
--j;
}
1. Traverse the whole number and store each digit in array
2. Start from last position to first position
i = n-1, j = n -2
while ( j >= 0)
if ( data[n - i] > data [i -2]
{
swap the value for (n - i) & (n-j). Print the same and break.
}
else
{
// Swap the value for (n - i) & (n-j).
}
i = j ;
--j;
Perform a binary search to find that member exists in the list or not.
1. If not found then return -1. Complexity will be log (n)
2. If found then start looking backward in the list till you hit lower variable then the current item, and then return the index of currentItem. Worst case complexity will be log(n) + n
I think that approach will not work in normal way. Let's consider a case.
Lift is going upwards, currently at Floor 2.
Some one calls at Floor 1 then it goes there instead of Floor 10
and take person from floor 1 and then start moving to floor 10 again someone call at floor 1.
By doing this lift will be in infinite loop in floor 1 and floor 2.
#include<iostream>
#include<conio.h>
bool isArmstrong(const int number)
{
int a,b,c;
a = number%10;
b = (number/10)%10;
c = (number/100)%10;
return ( ( (a * a * a) + (b * b * b) + ( c * c * c)) == number );
}
int main()
{
std::cout<<"\n Armstrong number are : ";
for ( int i =100;i<1000;i++)
{
if ( isArmstrong(i) )
{
std::cout<<"\t"<<i;
}
}
getch();
}
Assumption user will enter +ve value starting from one.
void InterviewQuestions::findValueInSequence()
{
std::string outputStr = "a";
int positionRequested = 28;
std::cout<<"\nEnter the position requested (+ve number only starting from one) : ";
std::cin>>positionRequested;
// Decrement as value is calculated as per the index 0;
--positionRequested;
int i = 0;
int n = positionRequested/26;
int rem = positionRequested%26;
while ( i < n )
{
if (outputStr.size() == 1)
{
outputStr.insert(0,1,'a');
}
else
{
char ch = outputStr[0];
if ( ch == 'z')
{
outputStr[0] = 'a';
outputStr.insert(0,1,'a');
}
else
{
ch += 1;
outputStr[0] = ch;
}
}
i++;
}
// add the reminder to the first character of the output string.
char ch = outputStr[outputStr.size() - 1];
for ( i = 0; i< rem; i++)
{
++ch;
}
outputStr[outputStr.size() - 1] = ch;
std::cout<<"\nRequested Character is : "<<outputStr.c_str()<<"\n";
}
void compress(char* source)
{
int currentPos = 0;
int start = 0;
int next = start + 1 ;
int count = 1;
do
{
if ( source[start] == source[next])
{
++count;
}
else if ( count > 1)
{
// check count is how many digits i.e. 10,100,1000...n
int digitCount = 1;
int tenCount = 10;
while ( ( count / tenCount ) >= 1 )
{
tenCount = tenCount * 10;
++digitCount;
}
// Enter the string count next to the start position.
source[currentPos] = source [next -1];
int newPosition = currentPos + digitCount + 1;
while(digitCount)
{
tenCount = 10;
source[currentPos + digitCount] = 48 + (count%tenCount);
--digitCount;
count = count/tenCount;
}
currentPos = newPosition;
count = 1;
}
else
{
source[currentPos] = source[start];
++currentPos;
}
++next;
++start;
} while (source[next] != '\0');
if ( count > 1)
{
// check count is how many digits i.e. 10,100,1000...n
int digitCount = 1;
int tenCount = 10;
while ( ( count / tenCount ) >= 1 )
{
tenCount = tenCount * 10;
++digitCount;
}
// Enter the string count next to the start position.
source[currentPos] = source [next -1];
int newPosition = currentPos + digitCount + 1;
while(digitCount)
{
tenCount = 10;
int temo = count%tenCount;
source[currentPos + digitCount] = 48 + (count%tenCount);
--digitCount;
count = count/tenCount;
}
currentPos = newPosition;
count = 1;
}
else
{
// write last character as it is.
source[currentPos] = source[start];
++currentPos;
}
source[currentPos] = '\0';
}
Rephallieriddic, HR Executive Trainee at Barclays Capital
I am Hallie, Dedicated and experienced administrative secretary who excels at prioritizing , completing multiple tasks simultaneously and following through to ...
Repaaronmdunlap6, Area Sales Manager at Achieve Internet
Hi, I am an HR Analyst with extensive experience delivering innovative solutions at the corporate level. Expertise in employee relations ...
1. Keep count of each character.
2. Sort them in decreasing order based on there number of count.
3. Pick first two and start decrementing from both of them till one of them reaches to Zero.
4. Item which count is zero remove that and move to step 2 again.
If only one char left with any count then it's not possible.
Another Note:
- Ricky September 14, 2017