souravghosh.btbg
BAN USER- 0of 0 votes
AnswersWhy Bloomberg?
- souravghosh.btbg| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Behavioral - 0of 0 votes
AnswersGiven the following:
void foo (/* Add param here */) { } void main () { char *str; foo (/* Pass str somehow here */); printf ("%s\n", str); }
Complete foo.
- souravghosh.btbg
Follow up question was:
You probably used malloc or new in foo. That will cause memory leak. Write it in such a way so that memory does not leak (Basically use global or static).
Eazy peazy!| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer C - 0of 0 votes
AnswersGiven the stats that the highest occurring character in english text is 'e', given a cipher text as input, find out the plain text from it.
- souravghosh.btbg
E.g.:
Given input "bloomberg", the highest occurring characters are 'b' and 'o'. Let's consider 'b'. According to our metric, highest occurring character should be mapped to 'e'.
So 'b' maps to 'e' in plain text.
Now shift all the other characters in the input to the output with the same shift offset.
Output for "bloomberg" = "eorrpehuj".
Also take care for character overflow, i.e. 'z' + 1 should map to 'a' (WRAP AROUND).
ALL CHARACTERS ARE LOWERCASE. Assume.| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Algorithm - -3of 3 votes
AnswersGiven the input array:
- souravghosh.btbg
[2, 3, 5, 6, 12, 4, 2]
The output array is:
[2, 6, 18, 24, 30, 35, 38, 40].
Find the pattern between the two and write a program to convert input to output.
Simple enough.| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Algorithm
Hi thear,
I went to their website, uploaded my resume, filled out a couple of forms.
Then they contacted me, had the online test, then they came on campus for an interview (University of Southern California campus). After that they flew me out to their HQ in NYC.
Awesome.
I write down a wrong question. You fix it and give me the correct pattern!
Yes you are absoluetly right.
THERE IS AN ERROR IN THE ORIGINAL QUESTION. unnamed_array HAS THE CORRECT QUESTION.
Can't edit the original post now. Hope people see this.
Wow, didn't see your solution.
Good work making the change.
Thanks.
Kadane's solution.
As shown above.
Well, the time for the interviews is not really something that determines your success at the interviews, right?!?
Guess you'll just have to wait for the verdict!
All the best.
Don't know what's wrong with the CC edit function.
Small typo fixed:
Structure of node:
bool isLockedBool; // Initialize = false;
int lockedDescendentsInt; // Initialize = 0;
Node *parentNodePtr; // Points to the parent.
Node *childNodePtrPtr[N];
IsLock ():
IsLock () {
return isLockedBool;
}
Lock ():
if (lockedDescendentsInt > 0) {
// This node has a locked descendent.
// Return error.
}
isLockedBool = true;
// (1) Now move to parent from current node till we reach root.
// (2) At each step, we check if the node is locked or not.
// (3) If it is, current node CANNOT be locked. Revert changes and return error.
// (4) If not, increment the lockedDescendentInt count in each node
// and repeat from (1).
// O (log n)
unLock ():
isLockedBool = false;
// (1) Now move to parent from current node till we reach root.
// (2) Decrement the lockedDescendentInt count in each node
// and repeat from (1).
// O (log n)
Pseudo code. Too lazy to write actual code!
- souravghosh.btbg March 23, 2011An acute angled triangle has ALL angles less than 90*.
So yes no. of acute angles that can be formed = 8.
Some code in case you're interested:
// RandQuickSort.cc
// (c) souravgh@usc.edu
// Thu Mar 17, 1510
// Randomized quick sort.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define Exchange(a, b) {\
a += b;\
b = a - b;\
a = a - b;\
}
int partition (unsigned *arrIntPtr, int lowerInt, int upperInt) {
// Randomly select a pivot key.
int pivotIndexInt = rand () % (upperInt - lowerInt) + lowerInt;
int higherIndexInt = lowerInt, lowerIndexInt = upperInt - 1;
while (higherIndexInt < lowerIndexInt && higherIndexInt < upperInt && lowerIndexInt >= lowerInt) {
for ( ; higherIndexInt < upperInt - 1 && arrIntPtr[higherIndexInt] < arrIntPtr[pivotIndexInt];
higherIndexInt++);
for ( ; lowerIndexInt >= lowerInt && arrIntPtr[lowerIndexInt] >= arrIntPtr[pivotIndexInt];
lowerIndexInt--);
if (higherIndexInt < lowerIndexInt) {
Exchange (arrIntPtr[lowerIndexInt], arrIntPtr[higherIndexInt]);
if (pivotIndexInt == lowerIndexInt) {
pivotIndexInt = higherIndexInt;
} else if (pivotIndexInt == higherIndexInt) {
pivotIndexInt = lowerIndexInt;
}
}
}
if (higherIndexInt != pivotIndexInt) {
Exchange (arrIntPtr[higherIndexInt], arrIntPtr[pivotIndexInt]);
}
return higherIndexInt;
}
void quickSort (unsigned *arrIntPtr, int lowerInt, int upperInt) {
if (lowerInt >= upperInt - 1) {
return;
}
int pivotIndexInt = partition (arrIntPtr, lowerInt, upperInt);
quickSort (arrIntPtr, lowerInt, pivotIndexInt);
quickSort (arrIntPtr, pivotIndexInt + 1, upperInt);
}
int main (void) {
unsigned hugeArrIntPtr[5000];
srand (time (NULL));
quickSort (hugeArrIntPtr, 0, sizeof (hugeArrIntPtr) / sizeof (int));
fprintf (stdout, "THIS SHOULD GIVE YOUR TERMINAL SOMETHING TO DO:\nQuick sorted output:\n");
for (int indexInt = 0; indexInt < sizeof (hugeArrIntPtr) / sizeof (int); indexInt++) {
fprintf (stdout, "%u\n", hugeArrIntPtr[indexInt]);
}
return EXIT_SUCCESS;
}
Clearly since the 1 bil no.s fit into memory, external sorting is unnecessary.
Doing insertion sort or its variant will be O (n2).
Counting sort needs the knowledge that your no.s are within some range eg. no.s are from 1 to k. Without prior knowledge of the domain of no.s, counting sort cannot be used. Let's also not forget that we will need extra space to store the count array and the final output array along with the 1 bil no.s in memory.
Heaps are certainly a good option. Build it up in O (n) and find the 1 mil. largest no.s in O (n log n). Complexity = O (n)
I guess a Randomized Quicksort algorithm **should** do this job in O (n log n) and with no extra space.
Using O (1) space:
CANNOT BE DONE. Consider the case 1,2,3,4,5,6,7,8,9.
Using linked lists:
INSERTION : O (n) MEDIAN-FIND : O (1)
OR
INSERTION : O (1) MEDIAN-FIND : O (n)
Using BST:
INSERTION : O (n) MEDIAN-FIND : O (n)
Using 2 heaps (priority queues as shown above):
INSERTION : O (log n) MEDIAN-FIND : O (1)
Can we do better?
I have no idea what just happened. The question is:
"We have two unique sorted arrays. Need to find common elements from these arrays."
Your arrays are neither sorted nor do you find the common elements from these arrays.
The order O (n + m) solution is the most efficient. You have to see each no. at least once!
I still didn't understand why the address of i is the same as the address of array[5]? Even if you switch the order of the variable declarations from
int i=0;
int array[5];
to
int array[5];
int i=0;
, it seems to have the same behavior.
This is strictly compiler dependent I feel. This is the behavior under gcc.
Anybody?
// souravgh@usc.edu
// Wed 9 Mar 2011 2040
#include <stdio.h>
int main (void) {
int arr[50];
int indexInt = 0;
int locInt = 0;
for (indexInt = 0; indexInt < 50; indexInt++) {
arr[indexInt] = indexInt + 1;
}
arr[5 - 1] = 2;
arr[10 - 1] = 12;
arr[23 - 1] = 9;
arr[49 - 1] = 9;
for (indexInt = 0; indexInt < 50; indexInt++) {
locInt = arr[indexInt] < 1 ? -(arr[indexInt] + 1) : (arr[indexInt] - 1);
arr[locInt] = arr[locInt] > 0 ? -arr[locInt] : arr[locInt]; // Make it a -ve.
}
for (indexInt = 0; indexInt < 50; indexInt++) {
if (arr[indexInt] > 0) {
fprintf (stdout, "\t%d", indexInt + 1);
}
}
fprintf (stdout, "\n");
return 0;
}
O (n) time O (1) space. Of course this assumes that the 1 mil no.s are organized as an array similar to the 50 element array above, and that getting the value and setting the value at a particular index is O (1).
- souravghosh.btbg March 10, 2011@Salmok:
I see your point now. My code is complete garbage. So inorder traversal seems to be a safe bet for this problem. Thanks.
@nugarp:
So I guess we should have that check in both the if clauses. If either of the child has a key equal to it's parent, then it's also a violation of the BST constraint. Thanks.
@nugarp:
I figured we had a BST that didn't allow duplicate keys. Think we would have a little trouble finding a node with a given key if we allowed multiple nodes to have the same key.
@Salmok:
The code is correct as it is. We could also do it your way.
// strsep.c
// (c) souravgh@usc.edu
// Mon Feb 28 1803
#include <stdio.h>
#include <stdlib.h>
int isDelim (char currChar, char *delimCharPtr) {
if (currChar == '\0') {
return 1;
}
for (; *delimCharPtr; delimCharPtr++) {
if (currChar == *delimCharPtr) {
return 1;
}
}
return 0;
}
char *strsep (char *strCharPtr, char *delimCharPtr) {
static char *oldStrCharPtr = NULL;
if (strCharPtr) {
oldStrCharPtr = strCharPtr; // Remember this for subs. calls.
}
if (!oldStrCharPtr) {
return NULL;
}
while (isDelim (*oldStrCharPtr, delimCharPtr) && *oldStrCharPtr) {
oldStrCharPtr++;
}
if (!*oldStrCharPtr) {
return NULL;
}
strCharPtr = oldStrCharPtr; // This is our return value.
while (!isDelim (*oldStrCharPtr, delimCharPtr)) {
oldStrCharPtr++;
}
if (*oldStrCharPtr == '\0') {
oldStrCharPtr = NULL;
} else {
*oldStrCharPtr++ = '\0';
}
return strCharPtr;
}
int main (void) {
char str[] = "Hi;;Hello..There.;How..;";
char str2[] = "We can have no p P in small p Wow";
char *tokCharPtr;
for (tokCharPtr = strsep (str, ".;"); tokCharPtr; tokCharPtr = strsep (NULL, ".;")) {
fprintf (stdout, "%s\n", tokCharPtr);
}
for (tokCharPtr = strsep (str2, "p"); tokCharPtr; tokCharPtr = strsep (NULL, "p")) {
fprintf (stdout, "%s\n", tokCharPtr);
}
return 0;
}
bool isBST (Node *rootNodePtr) {
if (!rootNodePtr) {
return true;
}
if ((rootNodePtr->left && rootNodePtr->key <= rootNodePtr->left->key) ||
(rootNodePtr->right && rootNodePtr->key >= rootNodePtr->right->key)) {
return false;
}
return isBST (rootNodePtr->left) && isBST (rootNodePtr->right);
}
// Partition.cc
// (c) souravgh@usc.edu
// Mon Feb 28 1201
#include <stdio.h>
#define Swap(a,b) {\
int t = a;\
a = b;\
b = t;\
}
void partition (int *arrIntPtr, int sizeInt) {
int negPtrInt = 0, posPtrInt = 0;
// Find the no. of -ve no.s
for (int indexInt = 0; indexInt < sizeInt; indexInt++) {
posPtrInt = (arrIntPtr[indexInt] < 0) ? posPtrInt + 1 : posPtrInt;
}
int negCountInt = posPtrInt;
// Partition.
for (int currPtrInt = 0; currPtrInt < sizeInt && currPtrInt < negCountInt; ) {
if (arrIntPtr[currPtrInt] < 0) { // -ve
if (currPtrInt == negPtrInt) {
negPtrInt++;
currPtrInt++;
continue;
}
Swap (arrIntPtr[negPtrInt], arrIntPtr[currPtrInt]);
negPtrInt++;
} else { // 0 or +ve
if (currPtrInt == posPtrInt) {
posPtrInt++;
currPtrInt++;
continue;
}
Swap (arrIntPtr[posPtrInt], arrIntPtr[currPtrInt]);
posPtrInt++;
}
}
}
int main (void) {
int a[] = {1, 7, -5, 9, -12, 15};
partition (a, 6);
for (int indexInt = 0; indexInt < 6; indexInt++) {
fprintf (stdout, "%d ", a[indexInt]);
}
fprintf (stdout, "\n");
return 0;
}
O (n) time. O (1) space.
- souravghosh.btbg February 28, 2011I'm not sure it's working.
I tried running. Works fine for some input.
Endlessly loops for an array of size 100. Don't know what's wrong.
Is this just me?
Here is my output for a sample run:
ARRAY:
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
65 66 67 68 69 70 71 72
73 74 75 76 77 78 79 80
SPIRAL:
57
56 58
55 31 59
54 30 32 60
53 29 13 33 61
52 28 12 14 34 62
51 27 11 03 15 35 63
50 26 10 02 04 16 36 64
49 25 09 01 05 17 37 65
80 48 24 08 06 18 38 66
79 47 23 07 19 39 67
78 46 22 20 40 68
77 45 21 41 69
76 44 42 70
75 43 71
74 72
73
And for the interested, the code (It's messy):
// SpiralArray.c
// (c) souravgh@usc.edu
// Sun Feb 27 1130
// Prints a 2D array spirally.
#include <cstdlib>
#include <cstdio>
using namespace std;
#define RowsInt 10
#define ColsInt 8
typedef struct {
int xPosInt;
int yPosInt;
int noInt;
} Point;
#define ExchangePoints(p1, p2) {\
Point tempPoint = p1;\
p1 = p2; \
p2 = tempPoint; \
}
enum Direction {LeftUp, RightUp, RightDown, LeftDown};
void updateXY (int *xIntPtr, int *yIntPtr, Direction direction) {
int xDxInt = (direction == LeftUp || direction == LeftDown) ? -1 : 1;
int yDyInt = (direction == LeftUp || direction == RightUp) ? -1 : 1;
*xIntPtr += xDxInt;
*yIntPtr += yDyInt;
}
void calculateSpiralCoords (Point *pointPtr, int sizeInt) {
int lastXInt = 0, lastYInt = 0, countInt = 1;
Direction dirsPtr[4] = {LeftUp, RightUp, RightDown, LeftDown};
int currentDirectionInt = 0;
// Calculate the x,y positions of the points
// as if we are about to plot a 2D polygon graph.
for (int indexInt = 0; indexInt < sizeInt; ) {
for (int updateCountInt = 0; updateCountInt < countInt && indexInt < sizeInt; updateCountInt++) {
pointPtr[indexInt].xPosInt = lastXInt;
pointPtr[indexInt].yPosInt = lastYInt;
updateXY (&lastXInt, &lastYInt, dirsPtr[currentDirectionInt]);
indexInt++;
}
currentDirectionInt = (currentDirectionInt + 1) % 4;
if (currentDirectionInt % 2 == 0) {
countInt++;
}
}
// Do some base offset additions to all points.
// This brings all coordinates into +ve values.
// This could have been done in the same loop above,
// but enough was already being done there!
int minXInt = 0, minYInt = 0;
// Find the minimum x and y positions.
for (int indexInt = 0; indexInt < sizeInt; indexInt++) {
minXInt = (minXInt > pointPtr[indexInt].xPosInt) ? pointPtr[indexInt].xPosInt : minXInt;
minYInt = (minYInt > pointPtr[indexInt].yPosInt) ? pointPtr[indexInt].yPosInt : minYInt;
}
// minXInt and minYInt are now 0 or -ve.
// Offset all points.
for (int indexInt = 0; indexInt < sizeInt; indexInt++) {
pointPtr[indexInt].xPosInt -= minXInt;
pointPtr[indexInt].yPosInt -= minYInt;
}
}
void sortPoints (Point *pointPtr, int sizeInt) {
// Do a simple bubble sort to sort the points.
for (int iIndexInt = 0; iIndexInt < sizeInt; iIndexInt++) {
for (int jIndexInt = 0; jIndexInt < sizeInt - iIndexInt - 1; jIndexInt++) {
if (pointPtr[jIndexInt].yPosInt > pointPtr[jIndexInt + 1].yPosInt ||
(pointPtr[jIndexInt].yPosInt == pointPtr[jIndexInt + 1].yPosInt &&
pointPtr[jIndexInt].xPosInt > pointPtr[jIndexInt + 1].xPosInt)) {
ExchangePoints (pointPtr[jIndexInt], pointPtr[jIndexInt + 1]);
}
}
}
}
void plotPoints (Point *pointPtr, int sizeInt ,FILE *outFilePtr) {
// First we space out the points along the X axis.
for (int indexInt = 0; indexInt < sizeInt; indexInt++) {
pointPtr[indexInt].xPosInt *= 3;
}
for (int indexInt = 0; indexInt < sizeInt; ) {
int currYInt = pointPtr[indexInt].yPosInt;
int currXOffset = pointPtr[indexInt].xPosInt;
fprintf (outFilePtr, "%*s", currXOffset, " ");
for (; currYInt == pointPtr[indexInt].yPosInt && indexInt < sizeInt; indexInt++) {
fprintf (outFilePtr, "%*s%02d", pointPtr[indexInt].xPosInt - currXOffset, " ", pointPtr[indexInt].noInt);
currXOffset = pointPtr[indexInt].xPosInt;
}
fprintf (outFilePtr, "\n");
}
}
void printSpiral (int arrIntPtrPtr[RowsInt][ColsInt]) {
Point pointPtr[RowsInt * ColsInt];
fprintf (stdout, "\nARRAY: \n\n");
for (int yIndexInt = 0; yIndexInt < RowsInt; yIndexInt++) {
for (int xIndexInt = 0; xIndexInt < ColsInt; xIndexInt++) {
pointPtr[yIndexInt * ColsInt + xIndexInt].noInt = arrIntPtrPtr[yIndexInt][xIndexInt];
fprintf (stdout, "%3d ", arrIntPtrPtr[yIndexInt][xIndexInt]);
}
fprintf (stdout, "\n");
}
fprintf (stdout, "\nSPIRAL: \n\n");
// Calculate the spiral 2D coordinates.
calculateSpiralCoords (pointPtr, RowsInt * ColsInt);
// Sort the points by Y and break ties for same Y using X.
sortPoints (pointPtr, RowsInt * ColsInt);
// Plot points to stdout
plotPoints (pointPtr, RowsInt * ColsInt, stdout);
}
int main (void) {
int arrIntPtrPtr[RowsInt][ColsInt];
for (int yIndexInt = 0; yIndexInt < RowsInt; yIndexInt++) {
for (int xIndexInt = 0; xIndexInt < ColsInt; xIndexInt++) {
// Increasing ints.
arrIntPtrPtr[yIndexInt][xIndexInt] = yIndexInt * ColsInt + xIndexInt + 1;
}
}
printSpiral (arrIntPtrPtr);
return EXIT_SUCCESS;
}
@Paras: Given a sorted array, your approach is definitely higher in complexity. However if we are given an unsorted array, the sorting itself will take O (n lgn). Then your approach will also be O (n lgn). No loss no gain. However S's approach is recommended even in that case!
- souravghosh.btbg February 26, 2011I guess since we know they are all going to be phone numbers (10 digits), a simple radix sort would be O (10n) = O (n). Then finding duplicates in the sorted array is another O (n) operation; just check consecutive numbers for multiple occurences.
Overall complexity = O (n) guaranteed.
Simply amazing! The simplicity!
- souravghosh.btbg February 13, 2011You can store completely and reconstruct identically a bst, by storing it's pre order traversal.
To reconstruct the bst identical to original, read the file and after reading each key, insert into the bst using a simple binary search tree insert.
You need a recursive solution to this problem to generate all possible permutations.
Check out the phone string problem:
question?id=7712670
My solution for that problem is at the bottom of the page. This problem is similar.
asetech: your program bounced for the following input: bbccdbccefee ->
souravgh@souravgh-AOD255:~/NetBeansProjects/MaxPath$ ./test
0 0
3 5
4 7
1 4
the static index is:4
the string is:bbccdbccefee
the value of min is:0
the first unrepeated character is:a
Here is the O (n) time and O (1) space solution:
// Find the first non repeating character in a string.
// (c) souravgh@usc.edu
// Sat Feb 12 1750
#include <cstdio>
#include <cstdlib>
using namespace std;
#define NoCharsInt 256
// Find and print the first non repeating character
// from the given string.
// O (n) time, O (1) space.
void printFirstNonRepeat (const char *strCharPtr) {
int charCountIntPtr[NoCharsInt]; // O (1) space
// Initialize constant size array
// O (1)
for (int indexInt = 0; indexInt < NoCharsInt; indexInt++) {
charCountIntPtr[indexInt] = 0;
}
// Get the occurence of every character.
// O (n)
for (char *tempCharPtr = (char *)strCharPtr;
*tempCharPtr;
++charCountIntPtr[*tempCharPtr], tempCharPtr++);
// Find first non repeating character.
// O (n)
for (char *tempCharPtr = (char *)strCharPtr; *tempCharPtr; tempCharPtr++) {
if (charCountIntPtr[*tempCharPtr] == 1) {
printf ("First non repeating character = %c\n", *tempCharPtr);
return;
}
}
printf ("No non repeating character found in string.\n");
}
int main (void) {
const char *strCharPtr = "bcdbcefe";
printFirstNonRepeat (strCharPtr);
return EXIT_SUCCESS;
}
This can be used to find the nth non repeating character in a string.
- souravghosh.btbg February 13, 2011The only thing I can think of is inverting the node weights (1 / Node weight), then modelling the problem as a shortest path using Bellman Ford (to handle the -ve weights) and then finding the minimum path using the modified weights. Shortest path with inverted weights is longest path with non-inverted weights.
- souravghosh.btbg February 13, 2011Here is one solution.
It uses the dp constraint, that the max cost to a node is the cost of that node plus the max of the costs to it's 4 surrounding nodes from the source. We start from the destination.
Cost to this node = cost of this node + MAX (cost to node above, cost to node below, cost to node right, cost to node left);
This essentially degenerates into a brute force approach of finding all possible paths from source to destination and then picking one with the maximum cost. The complexity depends on the no. of paths from source to destination.
Here is an implementation, handles -ve node weights as well as +ve. Note: the code to print is incomplete:
// Prints the max cost path from source to destination.
// Calls the findCost method, and
// then prints out the stack trace.
void Path :: printMaxCostPath () {
int maxCostInt;
// Start from the destination and move towards the origin.
findCost (destRowInt, destColInt, &maxCostInt);
printf ("[%d]=> ", maxCostInt);
stack <int> tempIntStack;
// Reverse the stack
for ( ; pathIntStack.size (); pathIntStack.pop ()) {
tempIntStack.push (pathIntStack.top ());
}
// Now print out the correct path with the total cost.
for ( ; tempIntStack.size (); tempIntStack.pop ()) {
printf ("[%d, %d] -> ", tempIntStack.top () % MaxRowsInt, tempIntStack.top () / MaxRowsInt);
}
printf ("[0,0]\n");
}
// Recursive routine.
// Returns true if a path is possible from this node, else returns false.
// currRowInt and currColInt specify the node to inspect.
// costIntPtr holds the cost for the path through this node.
bool Path :: findCost (int currRowInt, int currColInt, int *costIntPtr) {
// Boundary condition.
if (currRowInt == srcRowInt && currColInt == srcColInt) {
// The cost to this node, is simply the cost of this node.
// We donot push this index onto the stack. It is implicit.
*costIntPtr = dataIntPtrPtr[currRowInt][currColInt];
// Successfully found a path.
return true;
}
// Some invalid bounds check.
if (currRowInt < 0 || currRowInt >= dataRowInt || currColInt < 0 || currColInt >= dataColInt) {
return false; // No path out here!
}
// This node has already been added to the path.
if (inspectedBoolPtrPtr[currRowInt][currColInt]) {
return false;
}
// First and foremost, mark this node inspected.
inspectedBoolPtrPtr[currRowInt][currColInt] = true;
// The directions are assigned following values:
// TOP: 0, RIGHT: 1, BOTTOM: 2, LEFT: 3
int maxDirectionInt = -1;
// Include the cost of this node in the final cost.
int maxCostInt = 0;
int tempCostInt = 0;
// Calculate the max cost by moving to the right.
if (findCost (currRowInt, currColInt + 1, &maxCostInt)) {
// There is a path.
maxDirectionInt = 1; // RIGHT
}
// Calculate the max cost by moving to the left.
if (findCost (currRowInt, currColInt - 1, &tempCostInt)) {
// There is a path, check if it has greater cost.
if (tempCostInt > maxCostInt) {
maxCostInt = tempCostInt;
maxDirectionInt = 3; // LEFT
}
}
// Calculate the max cost by moving to the top.
if (findCost (currRowInt - 1, currColInt, &tempCostInt)) {
// There is a path, check if it has greater cost.
if (tempCostInt > maxCostInt) {
maxCostInt = tempCostInt;
maxDirectionInt = 0; // TOP
}
}
// Calculate the max cost by moving to the bottom.
if (findCost (currRowInt + 1, currColInt, &tempCostInt)) {
// There is a path, check if it has greater cost.
if (tempCostInt > maxCostInt) {
maxCostInt = tempCostInt;
maxDirectionInt = 2; // BOTTOM
}
}
bool retBool = true;
// After probing all 4 directions, maxDirectionInt contains
// either -1 indicating no path to source or 0 - 3 indicating direction
// of max cost path with the max cost incurred stored in maxCostInt.
if (maxDirectionInt == -1) {
// From this node, there is no path to the source.
retBool = false;
} else {
// Else there is a path.
// Cost incurred:
*costIntPtr = maxCostInt + dataIntPtrPtr[currRowInt][currColInt];
// This node is part of the path, push it to the stack.
// Also push the next node onto the pathStack.
}
// Now this node is completely inspected, we unmark it.
// This is needed so that this node shows up on other paths.
inspectedBoolPtrPtr[currRowInt][currColInt] = false;
return retBool;
}
Maybe there is a better solution to this. Anyone?
- souravghosh.btbg February 13, 2011Amazon seems to be asking a lot of these power of 2 variations!!
- souravghosh.btbg February 12, 2011Here's some tested code:
/**
* PhoneChar.cc
* (c) souravgh@usc.edu
* Sat Feb 12 1423
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <stack>
using namespace std;
using namespace __gnu_cxx;
// Recursive procedure which inspects each possible permutation
// of strings formable using the digits given in inputCharPtr.
// inputCharPtr: The string containing the no. eg. "234"
void printChars (char *inputCharPtr);
int main () {
char inputCharPtr[10];
scanf ("%s", inputCharPtr);
printChars (inputCharPtr);
return EXIT_SUCCESS;
}
const char *digitLetterMapCharPtrPtr[] = {"+", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
stack <char> charStack;
// Print the entire string contained in the charStack
void printStack ();
// Recursive procedure which inspects each possible permutation
// of strings formable using the digits given in inputCharPtr.
// inputCharPtr: The string containing the no. eg. "234"
void printChars (char *inputCharPtr) {
if (!inputCharPtr[0]) {
printStack ();
return;
}
// Get the int representation of the current digit.
// Need this to index the digitLetterMapCharPtrPtr array.
int currentDigitInt = *inputCharPtr - '0';
// We start from the first character and inspect each character
// calling the procedure recursively with the next character.
for (int indexInt = 0;
indexInt < (int)strlen (digitLetterMapCharPtrPtr[currentDigitInt]);
indexInt++) {
charStack.push (digitLetterMapCharPtrPtr[currentDigitInt][indexInt]);
printChars (inputCharPtr + 1);
charStack.pop ();
}
}
// Print the entire string contained in the charStack
void printStack () {
stack <char> tempCharStack;
// Reverse the stack.
for( ; charStack.size (); charStack.pop ()) {
tempCharStack.push (charStack.top ());
}
printf ("=> ");
// Restore and print out the stack.
for ( ; tempCharStack.size (); tempCharStack.pop ()) {
printf ("%c", tempCharStack.top ());
charStack.push (tempCharStack.top ());
}
printf ("\n");
}
The complexity in this case depends on the no. of output permutations. To that effect I feel it's something like: O (3^n), where n is the length of the input string e.g. "234". (Why 3? Each digit has 3 possible characters associated with it. All except 0, 1, 7, 9).
- souravghosh.btbg February 12, 2011
This was for a full time position!
- souravghosh.btbg March 31, 2011