CareerCupDom
BAN USER- 0of 0 votes
AnswersQ: Print out the number that is a duplicate in this unsorted array.
My follow up clarification questions:
Are the pairs always guaranteed to be sequential? Yes
Do we always know the size of the array? Yes
Will there always be just one number that does not have a pair? Yes
Original problem:int main() { int pairs[] = {1,1,7,7,3,3,19,19,4,10,10,11,11,15,15,2,2}; }
My solution:
void PrintDuplicate() { int pairs[] = { 1, 1, 7, 7, 3, 3, 19, 19, 4, 10, 10, 11, 11, 15, 15, 2, 2}; int size = 17; bool numberFound = false; for (int i = 0; i < size; i += 2) { if (i + 1 > size || pairs[i] != pairs[i + 1]) { std::cout << pairs[i] << std::endl; numberFound = true; break; } } if (!numberFound) { std::cout << "All pairs matched" << std::endl; } }
I believe this should give an O(n log n) solution with no extra space necessary.
- CareerCupDom in United States
After this solution they gave me a hint about using a binary search or a BST.
I do not see how that would have made this solution better than mine. Taking the array then moving the data to a BST would just be duplicating the process.
You could use a hashtable and every time you encounter a number see if it matches one you have already found, but that is only useful if this was an unsorted array.
What are the thoughts on my solution and why they would have gave me a hint at using a BST or a binary search on the array?| Report Duplicate | Flag | PURGE
Game Programmer Algorithm
Note that this works well if we have X columns and X rows of hexagons. If you can have arbitrarily long chains of hexes attached you would be better off having a graph where each hex contain a pointer to the next hex in each of the six valid directions.
- CareerCupDom May 15, 2015I see the 2D array differently.
If you line up the hexes into rows, either by shifting the even columns up half a row or the odd columns down half a row, you get a 2d array.
From any position in the 2d array you can go left, right, up, or down.
For odd columns you can additionally go up left and up right.
For even columns you additionally go down left and down right.
I'm not seeing why in the answer provided by tjcbs you can only go up/down + right on even rows and up/down + left on odd rows.
Wouldn't this time complexity be O(n^2), where n is the number of jobs, since you have to iterate over all of the jobs twice?
- CareerCupDom May 15, 2015No the question is poorly worded. The "good" company does not make 100% "good" chips and the "bad" company does not make 100% failing chips. A good company has a chance of making bad chips. By saying the "first chip in the pack is good", he does not mean from the "good" company but he mean good as in it is not a failing chip.
- CareerCupDom May 15, 20150.2 * 0.2 = .4 not .04.
- CareerCupDom May 15, 2015// Ignores everything except alpha characters
bool isPalindromeAlpha(char* inputString, char* startPos, char* endPos)
{
bool isPalindrome = true;
char charToCompare1 = '\0';
char charToCompare2 = '\0';
while (startPos < endPos)
{
// Skip over characters that are not letters
while ( ((*startPos < 'a' || *startPos > 'z') && (*startPos < 'A' || *startPos > 'Z')) && startPos < endPos)
{
startPos++;
}
while (((*endPos < 'a' || *endPos > 'z') && (*endPos < 'A' || *endPos > 'Z')) && endPos > startPos)
{
endPos--;
}
// Make all letters lowercase
charToCompare1 = *startPos;
if (charToCompare1 >= 'A' && charToCompare1 <= 'Z')
{
charToCompare1 = 'a' + (charToCompare1 % 'A');
}
charToCompare2 = *endPos;
if (charToCompare2 >= 'A' && charToCompare2 <= 'Z')
{
charToCompare2 = 'a' + (charToCompare2 % 'A');
}
if (charToCompare1 != charToCompare2)
{
isPalindrome = false;
break;
}
else
{
startPos++;
endPos--;
}
}
return isPalindrome;
}
int _tmain(int argc, _TCHAR* argv[])
{
char inputString[] = "A man, a plan, a canal, Panama!";
//char inputString[] = "#!@$% Ab !@%!@ B !%@!%!@% a 1 % !@% C !@%!@% a 1 % !@% B 1 % !@% b @!#)(*) A ";
cout << inputString << (isPalindromeAlpha(inputString, inputString, inputString + strlen(inputString) - 1) ? " is " : " is not ") << "a palindrome";
return 0;
}
You could add an extra count for the current depth and instead of doing the check every time you see a '(' to set the max depth you could just do one check when the open count == 0. Probably doesn't matter much either way but could lead to a speed vs space discussion, however minor it is.
int GetMaxParenthesisDepth(char* inputString)
{
int maxDepth = 0;
int openCount = 0;
while (*inputString != '\0')
{
// Found open
if (*inputString == '(')
{
openCount++;
if (openCount > maxDepth)
maxDepth = openCount;
}
// Found close
else if (*inputString == ')')
{
// If found a close but there was no open so far then this is a mismatch
if (openCount == 0)
{
maxDepth = -1;
break;
}
openCount--;
}
inputString++;
}
// If we didn't close everything then this is an error
if (openCount != 0)
maxDepth = -1;
return maxDepth;
}
int _tmain(int argc, _TCHAR* argv[])
{
char inputString[] = "abc(123(xyz))m(((n)))o";
cout << inputString << " = " << GetMaxParenthesisDepth(inputString) << endl;
char inputString1[] = "abc(123(xyz))m(((n))o";
cout << inputString1 << " = " << GetMaxParenthesisDepth(inputString1) << endl;
char inputString2[] = "abc)(123(xyz))m(((n)))o";
cout << inputString2 << " = " << GetMaxParenthesisDepth(inputString2) << endl;
char inputString3[] = "(((())))";
cout << inputString3 << " = " << GetMaxParenthesisDepth(inputString3) << endl;
char inputString4[] = "()()()()";
cout << inputString4 << " = " << GetMaxParenthesisDepth(inputString4) << endl;
return 0;
}
void ModifyString(char* inputString);
void UpperWord(char* inputString, char* startChar, char* endChar);
void ReverseWord(char* inputString, char* startChar, char* endChar);
void ModifyString(char* inputString)
{
char* startChar = inputString;
char* endChar = startChar;
bool isOddWord = true;
// Walk the string
while (1)
{
// If we found the end of a word
if (*endChar == ' ' || *endChar == '\0')
{
// Make word upper case
if (isOddWord)
UpperWord(inputString, startChar, endChar);
// Reverse string, not including the word ending character
else
ReverseWord(inputString, startChar, endChar - 1);
isOddWord = !isOddWord;
// Set our new start character, skipping over the ending character of space or null
startChar = endChar + 1;
}
// If we hit the end of the string then exit
if (*endChar == '\0')
break;
// Otherwise skip over our space character
else
endChar++;
}
}
void UpperWord(char* inputString, char* startChar, char* endChar)
{
// Convert the string not including the ending character (space or null)
while (startChar != endChar)
{
// If this is a letter and it is lowercase
if (*startChar >= 'a' && *startChar <= 'z')
{
*startChar = 'A' + (*startChar % 'a');
}
startChar++;
}
}
void ReverseWord(char* inputString, char* startChar, char* endChar)
{
while (startChar < endChar)
{
char swapChar = *endChar;
*endChar = *startChar;
*startChar = swapChar;
startChar++;
endChar--;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
char inputString[] = "This is a test String!!";
ModifyString(inputString);
cout << inputString << endl;
return 0;
}
The managers id seems unnecessary depending how your tree is built. Hierarchical organization is usually searched with a breadth first search.
Assuming your tree is setup as root links to a set of employees, then employees that report to those nodes are linked to it, etc.
You would:
1) Do a BFS until you find your matching employee id in the queue
2) Save off a pointer to that node and clear the queue because we dont care about anyone that this employee reports to, only who reports to him
3) Push all the nodes that are connected to this node onto the stack and list them out, this answers part 1 and lists all directly reporting employees
4) Continue doing a bfs until the queue is empty. Every time you push a node you will list out this employee. This answers part two and will report all indirectly reporting employees.
It seems like there should be a quicker way to getting to the first node without having to search the first part of the tree. If space isn't a concern you could have a hashmap with a kv pair of employee id to a pointer to his node. This would give you a fast lookup to start. You could limit the size of the table by only including ids that have at least one report.
There is no way to avoiding walking every node after the starting id is found since you want to list out all of those nodes.
Maybe I am not understanding the problem.
Why is 22 not an output?
Why is 112 output twice?
This swap progressively smaller chunks of the array.
a1 [a2 a3 a4] [b1 b2 b3] b4
a1 b1 [b2 b3] [a2 a3] a4 b4
a1 b2 a2 [a3] [b2] b3 a4 b4
a1 b2 a2 b2 a3 b3 a4 b4
int _tmain(int argc, _TCHAR* argv[])
{
int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
InterlaceArray(array, 10);
DumpArray(array, 10);
return 0;
}
void InterlaceArray(int* inputArray, int arraySize)
{
// Swap a chunk
for (int startIndex = 1; startIndex < arraySize / 2; startIndex++)
{
// Swap elements in a chunk
for (int swapIndex = startIndex; swapIndex < arraySize / 2; swapIndex++)
{
std::swap(inputArray[swapIndex], inputArray[swapIndex + (arraySize/2 - startIndex)]);
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
unsigned long long num = 8754365;
cout << "Orig: " << num << endl;
cout << "Num: " << GetLargestNumber(num) << endl;
cout << "String: " << GetLargestNumberString(num) << endl;
return 0;
}
std::string GetLargestNumberString(unsigned long long num)
{
std::stringstream largestNumberString;
// Count the digit values
int digitArray[10] = {};
while (num > 0)
{
digitArray[num % 10]++;
num /= 10;
}
for (int arrayIndex = 9; arrayIndex >= 0; arrayIndex--)
{
for (int digitCount = 0; digitCount < digitArray[arrayIndex]; digitCount++)
{
if (digitArray[arrayIndex] > 0)
{
largestNumberString << arrayIndex;
}
}
}
return largestNumberString.str();
}
unsigned long long GetLargestNumber(unsigned long long num)
{
unsigned long long largestNumber = 0;
// Count the digit values
int digitArray[10] = {};
while (num > 0)
{
digitArray[num % 10]++;
num /= 10;
}
int power = 0;
for (int arrayIndex = 0; arrayIndex < 10; arrayIndex++)
{
for (int digitCount = 0; digitCount < digitArray[arrayIndex]; digitCount++)
{
if (digitArray[arrayIndex] > 0)
{
largestNumber += arrayIndex * pow(10, power);
power++;
}
}
}
return largestNumber;
}
int _tmain(int argc, _TCHAR* argv[])
{
int arraySize = 9;
int array[] = { 3, 3, 4, 5, 5, 6, 7, 7, 7 };
int lastUniqueIndex = CreateUniqueArray(array, arraySize);
cout << "Last unique index = " << lastUniqueIndex << endl;
_getch();
return 0;
}
int CreateUniqueArray(int* inputArray, int arraySize)
{
int replacementIndex = 0;
for (int inputArrayIndex = 1; inputArrayIndex < arraySize; inputArrayIndex++)
{
if (inputArray[inputArrayIndex] != inputArray[replacementIndex])
{
// Since each number is a unique index, increment the replacement position
// whenever we find a new one
replacementIndex++;
// Copy unique value into next available position
inputArray[replacementIndex] = inputArray[inputArrayIndex];
}
}
return replacementIndex;
}
I like nikamirumukmeen's solution but I didn't want to have to keep creating 2 extra temporary variables each time we validated another node although I ended up with the same problem by creating 2 bool each call. Also wasn't a fan of copying the whole object on each validate call when we could just pass a pointer.
bool IsValidBST(BTnode* rootNode)
{
return ValidateNode(rootNode);
}
bool ValidateNode(BTnode* node)
{
bool bValidLeft = true;
bool bValidRight = true;
if (node->m_pLeft != NULL)
{
if (node->m_pLeft->m_nKey < node->m_nKey)
bValidLeft = ValidateNode(node->m_pLeft);
else
return false;
}
if (bValidLeft && node->m_pRight != NULL)
{
if (node->m_pRight->m_nKey > node->m_nKey)
bValidRight = ValidateNode(node->m_pRight);
else
return false;
}
return bValidLeft && bValidRight;
}
EDIT: I misread your code and thought you were checking == 0 not != 0 when checking 4. It looks like yours works, my mistake.
I don't think your leap year calculation is correct. You need nested if statements for the check.
This is because if the year is divisible by 4 and not by 100 it IS a leap year.
if(year % 4 == 0)
{
leap = true;
if(year % 100 == 0)
{
leap = false;
if(year % 400 == 0)
{
leap = true;
}
}
}
or smush them all into one statement
(year % 4 == 0 && year % 100 != 0) || ( year % 400 == 0)
Same implementation but with more meaningful variable names for people who haven't seen it before.
void DrawPascalTriangle(int maxRows)
{
int columnValue;
// Loop rows
for (int currentRow = 0; currentRow < maxRows; currentRow++)
{
// Create row, have height number of entries per row
for (int currentColumn = 0; currentColumn <= currentRow; currentColumn++)
{
columnValue = Pascal(currentRow, currentColumn);
printf("%3d", columnValue);
}
printf("\n");
}
}
int Pascal(int currentRow, int currentColumn)
{
if (currentColumn == 0 || currentRow == currentColumn)
return 1;
else
return Pascal(currentRow - 1, currentColumn - 1) + Pascal(currentRow - 1, currentColumn);
}
Since the order of operations is just left to right we can just keep a running left to right total.
// Assumes a null terminated input string, integers values, and valid expression
int EvaluateString(char* inputString)
{
int currentTotal = GetNumber(inputString);
while (*inputString != '\0')
{
switch (*inputString)
{
case '*':
currentTotal *= GetNumber(++inputString);
break;
case '-':
currentTotal -= GetNumber(++inputString);
break;
case '+':
currentTotal += GetNumber(++inputString);
break;
default:
inputString++;
break;
}
}
return currentTotal;
}
int GetNumber(char* &inputString)
{
int currentNumber = 0;
int isPositive = 1;
if (*inputString == '-')
{
isPositive = -1;
inputString++;
}
while (*inputString >= '0' && *inputString <= '9')
{
// Multiply our current number by 10 and add the current parsed number
currentNumber = (currentNumber * 10) + (*inputString - '0');
inputString++;
}
return currentNumber * isPositive;
}
void PrintIncrementingTriangle(int currentDepth, int endingDepth)
{
int currentNumber = ((currentDepth * (currentDepth - 1)) / 2) + 1;
std::stringstream ssOutput;
// Build string
for (int numbersToDisplay = 0; numbersToDisplay < currentDepth; numbersToDisplay++)
{
if (numbersToDisplay != 0)
{
ssOutput << " * ";
}
ssOutput << currentNumber;
currentNumber++;
}
ssOutput << endl;
// Print string
cout << ssOutput.str();
// Print next string if necessary
if (currentDepth < endingDepth)
{
PrintIncrementingTriangle(currentDepth + 1, endingDepth);
}
// Print bottom half of triangle as we recurse out
cout << ssOutput.str();
}
Yeah, after looking around I saw the xor solution. Looking at mine it looks like my worst cast solution isn't actually n log n, it's n/2 in the worst case because I am jumping over each paired item so only needing to check half the elements.
- CareerCupDom June 30, 2015I still don't see why they were pushing a BST or binary search solution.