Showing posts with label Adobe Interview. Show all posts
Showing posts with label Adobe Interview. Show all posts

Friday, May 23, 2008

Adobe - Reverse the order of words in a char seq



Question: Write an efficient algorithm to Reverse the order of words in a given array of character which form a sequence of words.


Note: Memory-based question, suppodely a part of 'Engineering' section of the written test for a Dev position at Adobe.



Solution: Find below one possible algorithm to solve this problem:-

  • Allocate memory for another array of same size
  • Iterate through the array and find words (by finding white spaces)
  • Put the word reversed (order of characters reversed) in the new array
  • Put the white spaces as well (you won't reverse them as they are same either way)
  • Continue and complete the iteration for all the words in the array
  • Copy the new array reversed into the original array and you're done!


Example: Suppose you have one array "int char float" in the beginning. The expected result should be "float char int" in this case. Let's dry run the above algorithm for this test array and see if it gets us the expected result.


NewArray = " " (a array of 14 characters, currently all blank)

Iteration starts here

First word found: "int", so NewArray = "tni "

Second word found: "char", so NewArray = "tni rahc "

Third word found: "float", so NewArray = "tni rahc taolf"

Iteration ends here


Now reverse of the NewArray = "float char int"



Share/Save/Bookmark


Adobe - C code for allocating a 2D (or 3D) array


Question: Write C code to dynamically allocate and free memory for a 2D (or 3D) array.

Note: Memory-based question, suppodely a part of 'C Programming' section of the written test for a Dev position at Adobe.


Solution: Here, I'm taking the case of a 2D array only. Allocation of a 3D array will also be quite similar. Let number of rows be ROW and number of columns be COL. There are at least three ways of doing the allocation, which are:-

Method #1: Store the elements of the array as a set of ROW, each of which holds COL integers. An array of ROW integer pointers, each of which will point to the corresponding row having COL integers each. Array is accessed as arr[i][j]. The allocation may be Non-Contiguous in this case.


Find above the C-code for allocating and freeing a 2D array following this method. Click the image to enlarge it.

Method #2: Store the elements of the array as a 1D array of ROW*COL integers with an array of ROW integer pointers which refer to the appropriate places in the previously allocated 1D array for the arr[i][j] type of access. In this case the allocation will always be Contiguous.


Find above the C-code for allocating and freeing a 2D array following this method. Click the image to enlarge it.

Method #3: This method is just a variant of the second method. In this case we allocate memory for 1D of ROW*COL integers and access the elements as arr[COL * i + j], instead of arr[i][j]. The allocation is always Contiguous in this case as well.


Find above the C-code for allocating and freeing a 2D array following this method. Click the image to enlarge it.



Share/Save/Bookmark


Thursday, May 22, 2008

Adobe - Larger of two int without Logical or Relational ops


Question: Find the larger of two integers without using logical or relational operators.

Note: This question was supposedly asked sometime back in the 'C Programming' section of the written test for a Dev position at Adobe. The question is purely based on memory and collected either from friends, colleagues, or Web. No guarantee whether the same question actually appeared in their test. However, you may use it to your advantage by having a feel of the type of questions Adobe asks.


Solution: In C, UINT_MAX represents the maximum value an unsigned integer can have and INT_MAX represents the maximum value of an integer variable.

So, (UINT_MAX >> 1) will have the same value as INT_MAX and consequently ~(UINT_MAX >> 1) = ~(INT_MAX) with all the bits as '0' and only the sign bit set as '1'.

If the given two integers are 'a' and 'b' then (a - b) will be negative for the case where 'a' < 'b' and hence the sign bit will be '1' for (a - b) in that case. Right? Now (a - b) & ~(UINT_MAX >> 1) will be 'true (1)' in this case as for both the operands of the operator '&', the leftmost bit is '1'. Other bits will become '0' as the second operand has all other bits set as '0'.

That means (a - b) & ~(UINT_MAX >> 1) will be true in case 'a' < 'b'. We can easily understand that (a - b) will be true (some positive number) in case of 'a' > 'b'. Otherwise, both the operands will be equal i.e., 'a' == 'b' in which case both the above conditions will return 'false (0)'.


Code Snippet in C:

if ((a - b) & ~(UINT_MAX >> 1)) /*... OR, (a - b) & ~INT_MAX ...*/
/*... a is less than b ...*/
else if (a - b)
/*... a is greater than b ...*/
else
/*... a is equal to b ...*/



Share/Save/Bookmark


Adobe Interview - C Function to Reverse a String


Question: Write a C Function to Reverse a String

Note: This question was supposedly asked sometime back in the 'C Programming' section of the written test for a Dev position at Adobe. The question is purely based on memory and collected either from friends, colleagues, or Web. No guarantee whether the same question actually appeared in their test. However, you may use it to your advantage by having a feel of the type of questions Adobe asks.


Solution: Fairly easy one, I guess. The steps are as follows:

  • Compute the length and store in a variable
  • Declare one temporary variable to iterate through the string
  • Iterate through the string array (only half length) from both the ends
  • Keep swapping the characters during the iteration
  • Exit from the loop. The string is reversed now :-)



Find above the Code Snippet in C (as it was supposedly asked in the C Programming section :-)). Click the image to enlarge it.



Share/Save/Bookmark