Total Experience: 10+ Years
Current Domain: Embedded (OS libraries)
Current Location: India
Tool used for virtual Interview: BlueJean, coderPad.
Interview Date: Last week of August 2020
Interview Time slot: 45 minutes

Phone Screening Round Questions:

1. Design a Hashmap with additional feature "Last". Code required for put, get, delete and last methods.

   Note:

   • last() is kind of undo operation which is maintaining the state of put and get and provide unique value if any otherwise null.
   • Delete() is remove the key from map and state maintained by last.

   Example:

   Input:

    [put({1, ‘a’}),  put({2, ‘b’}), put({3, ‘c’}), last(), last(), get(1), last(), last(), last(), last(), delete(1), last(), last(), last()]
    

   Output:

    [3, 2, 1, 3, 2, null, 3, 2, null]

   Explanation:

   • last() after put({3, ‘c’}) return key of operation just happened which is 3.
   • last() after last() should return key of operation (which done before operation returned by last())
   • last() after get(1) is resetting pointer to last operation. Therefore, return value is 1.
   • last() return 3 as put operation happened before get().
   • last() return 2.
   • last() return null as put() operation of key 1 is returned by last() method called eariler.
   • delete() delete key 1 from Hashmap and state chart maintain.
   • last() return 3 as last main operation of get for 1 key is deleted.
   • last() return 2.
   • last() return null as no previous state is present.

   Solution given:

   1. Create a double linked list to maintain the state.
   • If new operation is coming then add the key in front.
   • If old operation is coming like override by put operation and get value of previous key then moving the key in double linked list to front.

   To optimise the searching in double linked list, I saved iterator in the map.

   Time taken: around 15 min including dry run.

2. Write a program to resolve the path for unix platfrom. Function signature is like:

   string resolvePath(string currentDirectory, string expectedDirectory, int maxLength)
   
   currentDirectory: Path of directory where you are currently present
   expectedDirectory: Path of directory which we want to resolve. It may be absolute path or relative path. 
   maxLength: max length of return path allowed. 
   return: absolute path of directory under length given.

   Example:

   Input:

   currentDirectory: /root/abc/def/ghi
   expectedDirectory: ./../jkl/mno
   maxLength: 20

   Output:

   /root/abc/def/jkl/

   Explanation:

   1. Path after resolving currentDirectory and expectedDirectory is /root/abc/def/jkl/mno whose length is 21
   2. maxLength given is 20. So, check length of path upto last directory (/root/abc/def/jkl) which is 17. This path satisfy the condition. So, return it.

   Solution given:

   1. Identify the path is absolute or relative by first character (/ or not).

   2. If absolute path then call removePathBasedOnLength.

   3. If relative path then append both paths.

      a. Whenever there is pattern /./ then replace it with /
      b. Whenever there is pattern /../ then skip substring from “/” present before pattern till this last index of pattern.
      c. Call removePathBasedOnLength after removing all patterns of /./ and /../

   4. removePathBasedOnLength method check last directory within maxLength and return that path.

   Interviewer suggested me to improve it then I had given another solution based on stack as below

   1. Identify the path is absolute or relative by first character (/ or not).

   2. If absolute path then call removePathBasedOnLength.

   3. If relative path then

      a. Traverse left to right in the currentDirectory path and push all directories in stack. Stack will look like [“root”, “abc” , “def”, “ghi”]
      b. Traverse left to right in the expectedDirectory and if “.” then skip, else if “..” then pop one directory, else push in stack.
      c. Construct the path using stack entries and then call removePathBasedOnLength.

   4. removePathBasedOnLength method check last directory within maxLength and return it.

   Time taken: around 30 minutes, unabled to complete dry run.

I tried to test my code in IDE and found 2 mistakes after interview.

1. when currentDirectory length is more the maxLength then we should call removePathBasedOnLength directly.
2. the pattern matching code wrongly identifying ".." as ".".

Today, Got an email from recruiter that my feedback is on borderline. So, they can’t proceed further.