## Saurabh Singhal

BAN USER- -1of 1 vote

AnswersSuppose a nxn chessboard has two diagonally opposite corners removed, leaving n^2-2 squares. Is it possible to place (n^2-2)/2 dominoes of size 2x1 so as to cover all of these squares?

- Saurabh Singhal in India| Report Duplicate | Flag | PURGE

Arista Networks Software Engineer - -1of 1 vote

AnswersDelete the repeated elements in a singly linked list in O(n) time complexity without using extra space. Linked list contains elements in unsorted order

- Saurabh Singhal in India

P.S. - Sorting is not allowed| Report Duplicate | Flag | PURGE

VMWare Inc Intern Coding Data Structures Linked Lists - 3of 3 votes

AnswersA standard chess knight (it moves in its standard way i.e. L shaped OR 2.5 moves) is sitting at the position a1 on an N x N chess board. What is the minimum number of moves it will take to reach the diagonally opposite corner?

- Saurabh Singhal in India

P.S. - If it were a 8 x 8 chess board, the final destination for the knight would be h8| Report Duplicate | Flag | PURGE

Goldman Sachs Intern Algorithm Coding Data Structures Trees and Graphs - 1of 1 vote

AnswersA young girl counted in the following way on the fingers of her left hand. She started calling the thumb 1, the index finger 2, the middle finger 3, the ring finger 4, the little finger 5, then reversed direction calling the ring finger 6, the middle finger 7, the index finger 8, the thumb 9 then back to the index finger for 10, the middle finger for 11, and so on. She counted up to n (to be input by the user). She ended on her which finger?

- Saurabh Singhal in India| Report Duplicate | Flag | PURGE

Goldman Sachs Intern Problem Solving

You got the question wrong. In an array of 7 elements, the order of removal of elements would be : 3,6,2,7,5,1

So, remaining element is 4

Size of the array is known

- Saurabh Singhal August 22, 2013The algorithm below finds 1 pair. However, it can be easily worked to find all possible pairs. Also it return 1 or -1 depending on whether any required pair exists or not. Users can work it to return indexes

hasArrayTwoCandidates (A[], ar_size, sum)

1) Sort the array in increasing order.

2) Initialize two index variables to find the candidate

elements in the sorted array.

(a) Initialize first to the leftmost index: l = 0

(b) Initialize second the rightmost index: r = ar_size-1

3) Loop while l < r.

(a) If (A[l] + A[r] == sum) then return 1

(b) Else if( A[l] + A[r] < sum ) then l++

(c) Else r--

4) No candidates in whole array - return -1

The operation of diff is based on solving the longest common subsequence problem.

In this problem, you have two sequences of items:

a b c d f g h j q z

a b c d e f g i j k r x y z

and you want to find a longest sequence of items that is present in both original sequences in the same order. That is, you want to find a new sequence which can be obtained from the first sequence by deleting some items, and from the second sequence by deleting other items. You also want this sequence to be as long as possible. In this case it is

a b c d f g j z

From a longest common subsequence it's only a small step to get diff-like output: if an item is absent in the subsequence but present in the original, it must have been deleted. (The '–' marks, below.) If it is absent in the subsequence but present in the second sequence, it must have been added in. (The '+' marks.)

e h i q k r x y

+ - + - + + + +

The answer to the above question would be to find the diameter of the given tree

Here's the code which works in O(n) :

int diameterOpt(struct node *root, int* height)

{

/* lh --> Height of left subtree

rh --> Height of right subtree */

int lh = 0, rh = 0;

/* ldiameter --> diameter of left subtree

rdiameter --> Diameter of right subtree */

int ldiameter = 0, rdiameter = 0;

if(root == NULL)

{

*height = 0;

return 0; /* diameter is also 0 */

}

/* Get the heights of left and right subtrees in lh and rh

And store the returned values in ldiameter and ldiameter */

ldiameter = diameterOpt(root->left, &lh);

rdiameter = diameterOpt(root->right, &rh);

/* Height of current node is max of heights of left and

right subtrees plus 1*/

*height = max(lh, rh) + 1;

return max(lh + rh + 1, max(ldiameter, rdiameter));

}

The .bss segment is an optimization. The entire .bss segment is described by a single number, probably 4 bytes or 8 bytes, that gives its size in the running process, whereas the .data section is as big as the sum of sizes of the initialized variables. Thus, the .bss makes the executables smaller and quicker to load. Otherwise, the variables could be in the .data segment with explicit initialization to zeroes; the program would be hard-pressed to tell the difference. (In detail, the address of the objects in .bss would probably be different from the address if it was in the .data segment.)

- Saurabh Singhal August 15, 2013Default value for a global variable is 0

- Saurabh Singhal August 15, 2013**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

X-Loader : Sets up the pin muxing, initializes clocks and memory, loads the U-boot into SDRAM and executes it.

- Saurabh Singhal September 19, 2013U-boot : Performs some additional platform initialization, sets the boot arguments, passes control to the kernel image.

Why are there two bootloaders? The first bootloader, x-loader, is a stripped-down version of the u-boot, designed to run in OMAP's small on-chip SRAM. It initializes the main off-chip memory of the system and other necessary device drivers, and then loads the larger bootloader for Linux, u-boot.

For further reference : Google the term 'bootloader project '