## softy

BAN USERGeek!

- 0of 0 votes

Answersdevise an algorithm to color the graph in such a way that no two adjacent vertices have same color.You have to color them with any of the two colors say red or green?what will the time and space complexity of the solution.

- softy in India| Report Duplicate | Flag | PURGE

Mentor Graphics MTS Algorithm Data Structures - 0of 0 votes

Answersfind the balance index of an array where balanced index i is defined as the one whose left sum is equal to the right sum of the index .

- softy in India for bing

i.e

summation (1 to i-1) = summation (i+1 to length of an array) firdt I gave o(n2) solution , but then before i could give O(n) solution it was time up for me,

O(n) solution will be we have to loop through i = 1 to N and find if ( sum of array - sum of array (1 to i-1 ) = ( sum of array - sum of array (1 to i+1 ) the return i.

Your thoughts?| Report Duplicate | Flag | PURGE

Microsoft Algorithm Arrays Coding Data Structures - -1of 1 vote

Answersthere are N people in a room one of them is a celebrity .At least one person knows other but all knows celebrity.Celebrity doesnt know any one.There is an api isKnown(a,b) which returns true if a knows b.y.

- softy in United States for bing

I gave the O(n2) answer.

But I think this can be done in O(n) .We have to compare call isKnown(a[i],a[i+1]) && iskNown(a[i+1],a[i]) returns true remove both frmo the array else remove that a[i] which return true, this will reduce the array to the celebrity. order will be O(n) then.Your thoughts ??| Report Duplicate | Flag | PURGE

Microsoft Algorithm

I think question is complete.Just like in 2 dimensional array there is spiral way of traversing the array , for cube also(which is a 3 D object) it is possible to go spiral traversal.

For representing the Spiral we will be taking a 3 D array liek this :

char arr[cube_face][rows][columns]

can it be done someting like this :

(1) Take an array of 16X4 , 4 edges of 16 squares

edges will be : left,right,top, bottom

fill the array with the 16 elements.

(2) Define a Data Structure which has not only left and right child but also top and bottom child as well , now define an function just like inserting node in linked list (but here you have to insert all the adjacent edges) and search for the adjacent square edge and build the data structure.Searching of adjacent square can be done by iterating over each square and comparing the edges,

e. char edges[16][4] = { {ab,bg,gf,fa},{bc,ch,hg,ga},{cd,di,ih,hc},....}

where the square is like this

a__b__c__d__e

|f__g__h___i__j

|k__l__m__n__o

|p__q__r__s__t

|u__v__w__x__y

different squares are - abgf,bchg,cdih,deji,

square abgf and bchg has left common that is bg , similarly every two adjacent square will have either left,right,top or bottom edge same.

does it makes some sense !!

cant it be char [2^64][8][8] array ?? we can create a character map for 8X8 elements like this

black (all odd numbers):

queen : 1

king : 3

pawns : 11

white (all even numbers):

queen ; 2

king : 4

pawns : 10

ideally it should be 2^64 - 1 positions if we are ignoring the nothing on chess board :) : ) !!

Question says : "data structure to capture long datatype" suppose the numbers are having some billion digits. How will you store them when you dont have a data type in c which can store large numbers.

so i am storing the digits from lsb till 32nd digit in row 1 of a 2 D array then in row 1 i am storing fomr 33 digit to 32 + 33rd digit and so on.I will be needing maximum (max_digits)/(sizeof(int)*8 = (max_digits)/32 rows, assuming intezer takes 32 bits.

so a'[m][n] represents the number and a[0][m][m] represents the first number.Does this make some sense?

But i think string would be the better way to store the large numbers.

kahar is correct.

We must free the child before freeing parent.A true Post order traversal .Just like deleting a file directory inside a directory doesnt allow us to delete the parent directory untill the inside directory is not empty int the linux filesystem,

I have read that Red Black tree is there in the implementation of Linux File system.

The memory layout canbe also like what you have pointed out.This will be for Big Endian machine where higher Byte value goes to lower byte position or address and Lower Byte Value to lower byte position or address.

Like

0x56677788 is the address of an int having the space for 8 bits

_ _ _ _ _ _ _ _

First four will be for the place for the lower byte value for little endina machine and for higher value like 0010 as you have pointed out !

By default the members in the struct are public while in class they are private.Class is used in data hiding and (using private keyword) and in implementing Polymorphism.

Structures can be used in creating a data packet having dissimilar set of elements(POD or user defined).

i = 300;

=> i = 100101100 //in binary in word format => B B Hb 0001 0010 1100 where B = Byte and Hb = Half Byte

(A)=> in memory (assuming it is Little endian))

0x12345678 - 0010- 1100

0x12345679 - 0000- 0001

0x1234567a - 0000 - 0000

0x1234567b - 0000 - 0000

0x1234567c - Location of next intezer(location of ptr++ or ptr + 1 where ptr is an intezer pointer as ptr is of type int => on doing ++ptr it will increment by 4 byte(**size of int**))

when

(B)we do char *ptr = &i;

ptr will become of type char => on doing ++ptr it will increment by 1 byte(**size of char**)

so on doing ++ptr it will jump to location -> 0x12345679 (which has 0000- 0001)

now we are doing

*++ptr = 2

=> 0x12345679 will be overwritten by 2 => 0x12345679 will have 00**10** - 0000 instead of 000**1** - 0000

so the new memory content will look like this :

(C)0x12345678 - 0010 - 1100

0x12345679 - 0000- 0010

0x1234567a - 0000 - 0000

0x1234567b - 0000 - 0000

which is equivalent to => B B Hb 0010 00101100 where B = Byte and Hb = Half Byte

=> 556

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

I dont know but interviewer asked me to tell first whether this is possible or not.

- softy July 17, 2012May be this is related to some well known Graph Theorem.I am all nill in that !