Interview Question Analysts
Country: United States
Interview Type: Phone Interview
Use a hash/ dictionary with account number as key and an array or a structure as key.
It'll be o(n) to populate the hash.
to display in the new dataset , sum all the positive values for total money transferred in and sum -ve for out
Perhaps I was not clear. There are no negative values unless you would define a new variable for there to be negative values. The original spreadsheet would look like this:
_____________________________
| Acct From | |Acct To| | Amount |
The new spreadsheet would look like:
______________________________________
| Account | |Total Incoming | | Total Outgoing |
think the accounts number are the node of a weighted directed graph, and the amount transfer from the account is represented by an outgoing edge, and amount transfer to the account is represented by an incoming edge. so first populate the graph(means adjacency list) and then just sum it up and create new three columns
We can have a hashmap for new data set, with Account number as key and an object of class containing only two members Total Incoming and Total Outgoing.
- Rajat January 12, 2013Now we will traverse the original data set's first column - Account From, for each row we check if this account no. is present in our hashmap in O(1) time-
a. If NO, we create a new entry in hashmap with this account no. and value object will contain Total Incoming = 0 and total Outgoing = amount in third column of original data set.
b. If YES, we just add amount in third column of Original data set, to the existing Total Outgoing amount for the object corresponding to this key.
This process will take O(n) time.
Now we will again traverse the complete original data set, but now this time we will traverse second column (Acct To). For each entry of account no. we will check if an entry is there in our output hashmap in O(1) time -
a. If NO we will create a new entry in hashmap with this account no. and value object will contain Total Incoming = amount in third column of original data set and Total Outgoing = 0.
b. If YES, we just add amount in third column of Original data set, to the existing Total Ingoing amount for the object corresponding to this key.
This process will take O(n) time.
Total time O(n).