Google Interview Question : Find depth of a k-ary tree given a parent array

Problem statement: You are given a k-ary tree with parent array $P$ such that $P[i], 0 \le i < N$ gives the parent of node $ i $ and $N$ is the total nodes in the tree. What is the time and space complexity of finding the depth of the tree?


Solution 1 and Solution 2 are available with $ O (n^2) $ complexity. Solution 3 gives $ O(n) $ algorithm.

Code Complete by Steve McConnell : Chapter 6

A module is a collection of data and the routines that act on the data. The author provides empirical evidence to prove that modularity contributes more to maintainability than structure does and is the most important factor in preventing corrective maintenance. Modular programming also improves maintainability and comprehension by programmers.

The author emphasizes on loose coupling of modules and strong cohesion among routines belonging to a single module.

The author then enlists the benefits of Information hiding such as:

1. Hide module level secrets: These include
• Data Structures
• Algorithms
• Areas that can change
• Hardware interaction
• Data size
• Input and Output
• Nonstandard language features
2. Ease of Modification: Changes are localized to routines of module when information is hidden from the rest of the program.
3. Better Readability:
   
4. Increased Reliability:
   

The author then enlists barriers that prevent usage of information hiding:

1. Excessive distribution of Information: If implementation of employee records as an array of 1000 elements is known to every part of the program, it deters use of information hiding.
2. Circular Dependencies among modules: If more than one modules are using the same set of data, the data would not be kept hidden from the rest of the modules.
   
3. Perceived performance penalties: The belief that information hiding will result into degrade in performance deters the use of information hiding.
   

The author then enlists some of the areas of a program around which modules can be created:

1. User Interface
2. Hardware Dependencies
3. System Dependencies
4. Data Management
5. Real world objects and abstract data types
6. Related Operations
7. Reusable Code

The author concludes the chapter showing the ways modules can be implemented in different programming languages.

Code Complete by Steve McConnell : Chapter 5

The author discusses a low-quality routine and enlists the problems associated with it which include:

• Bad name
• No documentation
• No error check on input data
• Use of magic numbers instead of constants
• Unused parameters
• Modification of global variables
• Too many parameters
• Poor parameter ordering

The author emphasizes importance of routines in computer science and discusses about reasons to create a routine:

• Reducing complexity: A routine hides information and makes it easier to manage complex programs.
• Minimize code size: Similar code at different places in the program can be put into a routine to reduce size of code.
• Improve correctness: Code in a routine is likely to be more correct since it is called with different inputs from several places.
  
• Improve maintainability: If a defect is discovered, the code needs to be changed at only one place.
• Limit effects of changes: Isolate areas that are likely to change in future.
• Hiding sequences: A routine hides the sequences of events and bundles them as a single operation.
• Improve performance: If a routine's performance is improved, many parts of the code benefit.
• Hiding implementation: A routine will hide implementation details of an operation be its data structures or algorithm.
  
• Promoting code reuse: Code in a routine can be reused in another program more easily.
• Improve readability: Putting a section of a code in a routine and giving it a proper name improves readability of the code where the routine is invoked.
• Improving portability: Use of routines isolate non-portable capabilities.

The author provides guidelines to create effective routine names:

• For a procedure, a verb followed by an object is a good combination, e.g. PrintReport, CheckOrder, etc... For Object Oriented languages, the object is not required in the name because it is already part of the procedure call, e.g. report.Print, order.Check, etc...
  
• For a function (which returns a value), the description of the return value should be used as the name, e.g. NextCustomer, CurrentPenColor, etc...

The author suggests to include everything that a routine does in a name and if the name becomes too long to describe everything it does, it should be broken in several parts. The author suggests that a good routine name has an average length of 15 to 20 characters against 9 to 15 for that of a good variable name.

The author enlists several types of acceptable and unacceptable cohesion in a routine as below:

• Acceptable
• Functional Cohesion: This occurs when a routine does one and only one operation.
• Sequential Cohesion: This occurs when a routine performs operations in a specific order sharing data from step to step and makes only a part of a bigger operation.
• Communicational Cohesion: This occurs when operations in a routine make use of the same set of data and aren't related in any other way.
  
• Temporal Cohesion: This occurs when operations are combined into a routine because they are all done at the same time.
• Unacceptable 
• Procedural Cohesion: This occurs when a routine performs operations in a specific order but the operations do not share any data.
  
• Logical Cohesion: This occurs when several operations are combined into a routine and one of the operations is selected by a control flag that is passed in.
• Coincidental Cohesion: This occurs when operations in a routine are not at all related.
  

The author discusses the idea of coupling. The degree of coupling between two routines describe the strength of connection between them. It is a complement to cohesion and it is better to have as loose coupling as possible. The author then discusses several parameters for coupling:

1. Size: Small routines with less number of parameters are loosely coupled compared to large ones or with lots of parameters.
2. Intimacy: The routines should try to interact directly through parameters and avoid interaction through indirect ways like global variables or database records.
   
3. Visibility: The connection between different routines should be prominent and not hidden.
4. Flexibility: It refers to how easily you can change the connections between routines.

The author gives examples of good and bad coupling.

1. Simple-data coupling: Two routines are simple-data coupled if all the data passed between them is non-structured and through a parameter list.
2. Data-structure coupling: Two routines are data-structure coupled if the data passed between them is structured.
3. Control coupling: Two routines are control coupled if one routine passes data to the other that tells the second routine what to do.
4. Content (Pathological) coupling: Two routine are pathologically coupled if one uses the code inside another or if one alters the local data used inside another.
   

The first two kind of coupling are acceptable while the last two are not.

The author then discusses about ideal length of a routine. Contrary to general belief, the author provides some empirical results to show that:

1. The size of routine is inversely proportinal to the number of errors per line of code. Small routines have more errors per line of code than larger routines.
2. Larger routines were cheaper to develop per line of code.
3. Code needed to be changed the least when routine averaged 100 to 150 lines of code.

But author still warns on writing routines larger than 200 lines of code since they become difficult to understand.

The author discusses about defensive programming, a technique where if a routine receives incorrect input, the behaviour of the routine is still defined and consistent. The author enlists several techniques of using defensive programming:

1. Assertions: The author suggests to use preprocessor macros for assertions and warns against putting executable code in assertions since the assertions may not execute in production code.
   
2. Check values of data input and routine parameters: Routines should be coded to verify the range of values for data obtained from a file or user and all the input parameters. A strategy should be in place on the software's behaviour on invalid data.
3. Exception Handling: Unexpected situations/errors should generate exceptions that becomes obvious in development and are recoverable in production code.
4. Change: Anticipate changes that can happen to a program and code in such a way that least number of routines get affected.
5. Function Return Values: Code should be written to always check function return values even if it will always be success.
   

The author then provides guidelines for function parameters:

1. Parameters should be in input-modify-output order.
2. If several functions have similar parameters, their orders should match.
3. Never have unused parameters.
4. Put status or error variable last.
5. Never change the routine parameters. Take a copy and operate on the copy.
6. Document assumptions about parameters
• Whether the parameter is input, modify or output
• Units (Millisecond, Inch, etc...)
• Range of expected values
• Special values used for error etc... that should never appear
• Meanings of status codes and error values
  
7. Limit the number of parameters to seven
8. Never assume any parameter passing mechanism (i.e. calling conventions)
   

The author ends the chapter with comments on issues of using macros and how to solve the issues.

Find Top N : Solution 3

The problem is described here. Solution 1 is here. Solution 2 is here. In both the earlier solution, we used some in-built function offered by IBM Lotus Domino XPages Server side Javascript. In this solution, I will just try to find the optimal solution theoretically without using any in-built functions.

In my MTech thesis, I had worked on multi-pattern matching algorithm, Aho-Corasick. The algorithm basically creates a finite state machine from a list of patterns that are to be searched in a document. A sample FSM created for input strings {he, him, his, she, her} is shown in the image to the left. If we modify the state machine in such a manner that it also keeps the count for a particular string in the end state, the machine can actually work for finding top-N strings from a list of strings.

Now about the time and space complexity, you can clearly see here that the time to create the state machine is $O(|S|)$ where $|S|$ is nothing but the cumulative length of all the strings together. In the second pass, we can keep a list of Top $N$ strings with their occurrence count and then go through each end state and insert/replace the string represented by that end state in the Top N strings list if the occurrence count is higher than any of the string inside the list. This second pass can take $O(|S| \times N)$. This makes it the optimal algorithm in terms of time complexity but space required is quite huge, to the tune of $O(|S|)$.

I thought there might be already some work in this area and found burstsort. This is the fastest sorting algorithm found till 2007 and uses trie. It was discovered by Ranjan Sinha. I found that the space requirement reduces a lot by using the technique mentioned in this algorithm. This is the optimal algorithm in terms of both time and space complexity.

Code Complete by Steve McConnell : Chapter 4

This chapter focuses on the steps to build a routine from scratch, specifically it describes PDL (Program Design Language)-to-code process.

Author enlists many advantages of using PDL:

• When PDL is translated to code, PDL turns into programming-language comments which eliminates most commenting effort.
• PDL makes reviews easier since only detailed design written in PDL needs to be reviewed and not the actual source code.
• PDL supports the idea of iterative refinement.
• PDL makes changes easier.
• PDL is easier to maintain than other forms of design documentation since PDL remains along with the code and in sync with code-changes.

The author describes following steps in designing a routine:

• Prerequisites: Before doing any work on the routine, the job of the routine should be clearly defined and fits cleanly into the overall architecture.
• Problem definition: The problem the routine will solve should be stated in enough detail with regards to following:
  
  • Inputs to the routine
  • Outputs from the routine including the global variables affected
  • Information the routine will hide
  • How the routine will handle errors
• Name the routine: A routine should have a clear, unambiguous name. If there is problem in coming up with a good name, it usually indicates that the purpose of the routine is not clear.
• Decide on how to test the routine
• Think about efficiency: The author specifies two categories:
• If the system is not performance critical, the routine should be well modularized and is well readable. If it does not meet the performance criteria later, it can be replaced with a faster algorithm or more-efficient programming language. 
• If the system is performance critical, the architecture should clearly specify the space and time constraints and the routine should follow them.
• Research the algorithms and data structures:
• Write the PDL: This can be divided in several parts
• Write a concise statement of the purpose of the routine.
• Fill-in the high level PDL for the routine.
• Think about the data: If data manipulation is a prominent part of the routine, definitions of the key data structures are useful to have when you design the logic of the routine.
• Check the PDL: Review the PDL and think of how to explain it to someone else. Make sure it is easily understandable of what the routine does and how it does it.
• Iterate: Try different ideas in PDL before starting to code.
• Write the routine declaration:  Write the routine interface statement.
• Turn the PDL into high level comment and fill in the code below each comment: Each comment may translate into one or more lines of code.
• Check the code informally: Check each block of code and try to think of what it would take to break the block. 
• Clean up the leftovers:
• Check the routine interface and make sure that all input and output data is accounted for and all the parameters are used.
• Make sure routine does one thing and is loosely coupled with other routines.
• Check for unused data, undeclared variables and inaccurate variable names.
• Check for off-by one errors, improper nesting and infinite loops.
• Make sure proper indentation has been used to clarify the logical structure of the routine, the expressions and parameter lists.
• Make sure the PDL that was translated into comments is still accurate. Comments should provide algorithm descriptions, documentation on non-obvious dependencies and justification for unclear coding practices.
• Check the routine: Try to mentally execute the whole routine and see if there are any errors.
• Compile the routine: The author mentions about "Just One More Compile" syndrome where the programmer wants the routine to start working in just one more compilation effort. This leads to hasty, error-prone changes and takes more time in the long run.
• Debug the routine: Once the routine compiles, put it into a debugger and step through each line of code to make sure each line executes as you expect it to.
• Remove errors from the routine: If the routine is unusually buggy, don't patch it. Rewrite it. Creating an entirely new design for a buggy routine pays off.
  

Find Top N : Solution 2

The problem is described here. Solution 1 is here. Server-side Javascript in XPages in IBM Lotus Domino offers a function sort on an array.

Let S strings be stored in an Array names. Calling names.sort() returns sortedNames. Let topNames stores the top N strings with highest occurrence count found so far in descending order of occurrence and topCount keeps track of respective occurrence count. Following is the rest of the algorithm.

For each string s in sortedNames
Begin
   Let start,end store index of s in sortedNames
   Advance end till sortedNames[end] becomes different from s
   Set uniqueCount = end - start
   For each count c in topCount
      if uniqueCount is greater than c
         Begin
            move all the elements in topNames and topCount back by one
            insert uniqueCount in topCount and s in topNames
         End
   Advance sortedNames by uniqueCount
End

Since I don't have complexity numbers for Array.sort, I take the worst case and assume it to be of $O(S^2)$. After that the above algorithm is executed which, if all the strings are unique, take $O(S \times N)$ time. So the time complexity of this algorithm is $O(S^2)$. Space complexity is $O(S + N)$. Just remember that in both the solutions, the comparison of strings are counted. So the algorithms depend on not just the number of strings but on their length too.

Find Top N : Solution 1

The problem is described here. Server-side Javascript in XPages in IBM Lotus Domino offers a function @Unique.

Let S strings be stored in an Array names. Passing this to @Unique returns uniqueNames. Let topNames stores the top N strings with highest occurrence count found so far in descending order of occurrence and topCount keeps track of respective occurrence count. Following is the rest of the algorithm.

For each string u in uniqueNames
Begin
   Initialize uniqueCount to 0
   For each string n in names
      if n matches u, increase uniqueCount
   For each count c in topCount
      if uniqueCount is greater than c
      Begin
         move all the elements in topNames and topCount back by one
         insert uniqueCount in topCount and u in topNames
      End
End

Since I don't have complexity numbers for @Unique, I take the worst case and assume it to be of $ O(S^2) $. After that the above algorithm is executed which, if all the strings are unique, take $O(S \times (S+N))$ time. So the time complexity of this algorithm is $ O(S \times (S+N)) $. In most of the practical scenarios, $S >> N$, so the time complexity can be assumed to be $O(S^2)$. Space complexity is $O(S + N)$.