TECHNICAL QUESTIONS

Write a C function to print the link list in reverse order Posted: A: void Display_List_Reverse(struct node* current) { if (current==NULL) return ; Display_List_Reverse(current->next); printf(”

Implement a breadth first traversal of a binary tree Posted: The breadth first traversal of a binary tree can be accomplished by making use of a queue to store the elements from the tree that need to be printed next. Assuming a node in the binary tree is defined as follows: struct Node { int value; Node* left; Node* right; }; Here is an [...]

Given an N x M two dimensional array of integers where all rows and columns are sorted in ascending order, write a function that can determine if a certain value exists in the array. Posted: A: The obvious brute force solution would involve checking each item in the array to see if matches the desired value. This does not take advantage of the fact that the rows and columns in the array are sorted. The trick is to find a way to eliminate rows and columns from the array and [...]

What is the effective way of Device Independent Bitmap files management? Posted: A: Memory-mapped file is the best choice for device-independent bitmaps. MMF allows to map the file to RAM/SWAP addresses and to let Windows handle all load/unload operations for the file.

Set the highest significant bit of an unsigned integer to zero. Posted: (from Denis Zabavchik) Set the highest significant bit of an unsigned integer to zero #define zero_most_significant(h) (h&=(h>>1)|(h>>2), h|=(h>>2), h|=(h>>4), h|=(h>>8), h|=(h>>16))

How do we test most simply if an unsigned integer is a power of two? Posted: A: #define power_of_two(x) ((x)&&(~(x&(x-1))))

Compute the discrete log of an unsigned integer. Posted: A: #define discrete_log(h) (h=(h>>1)|(h>>2), h|=(h>>2), h|=(h>>4), h|=(h>>8), h|=(h>>16), h=(0xaaaaaaaa&h)>>1+(0×55555555&h), h=(0xcccccccc&h)>>2+(0×33333333&h), h=(0xf0f0f0f0&h)>>4+(0×0f0f0f0f&h), h=(0xff00ff00&h)>>8+(0×00ff00ff&h), h=(h>>16)+(0×0000ffff&h)) If I understand it right, log2(2) =1, log2(3)=1, log2(4)=2….. But this macro does not work out log2(0) which does not exist! How do you think it should be handled?

Compute the number of ones in an unsigned integer. Posted: A: #define count_ones(x) (x=(0xaaaaaaaa&x)>>1+(0×55555555&x), x=(0xcccccccc&x)>>2+(0×33333333&x), x=(0xf0f0f0f0&x)>>4+(0×0f0f0f0f&x), x=(0xff00ff00&x)>>8+(0×00ff00ff&x), x=x>>16+(0×0000ffff&x))

Reverse the bits of an unsigned integer. Posted: A: #define reverse(x) (x=x>>16|(0×0000ffff&x)8|(0×00ff00ff&x)4|(0×0f0f0f0f&x)2|(0×33333333&x)1|(0×55555555&x)

Reverse a singly linked list recursively. The function prototype is node * reverse (node *) ; Posted: node * reverse (node * n) { node * m ; if (! (n && n -> next)) return n ; m = reverse (n -> next) ; n -> next -> next = n ; n -> next = NULL ; return m ; }

Given a singly linked list, print out its contents in reverse order. Can you do it without using any extra space? Posted: Start reversing the list. Do this again, printing the contents. tags: microsoft sw programming

Write an efficient C code for tr program. tr has two command line arguments. They both are strings of same length. tr reads an input file, replaces each character in the first string with the corresponding character in the second string. eg. tr abc xyz replaces all a by x, b by y and so on. Posted: A: a) have an array of length 26. put x in array element corr to a put y in array element corr to b put z in array element corr to c put d in array element corr to d put e in array element corr to e and so on. the code while (!eof) [...]

Given a linked list with the following property node2 is left child of node1, if node2 <> Posted: O P | | O A | | O B | | O C How do you convert the above linked list to the form without disturbing the property. Write C code for that. O P | | O B / / / O ? O ? determine where do A and C go

Make the pointer aligned to a 4 byte boundary in a efficient manner Posted: Assign the pointer to a long number and the number with 11…1100 add 4 to the number

Write a program to remove duplicates from a sorted array. Posted: int remove_duplicates(int * p, int size) { int current, insert = 1; for (current=1; current <>

An array of pointers to (very long) strings. Find pointers to the (lexicographically) smallest and largest strings. Posted: Scan array in pairs. Remember largest-so-far and smallest-so-far. Compare the larger of the two strings in the current pair with largest-so-far to update it. And the smaller of the current pair with the smallest-so-far to update it. For a total of

An array of integers. The sum of the array is known not to overflow an integer. Compute the sum. What if we know that integers are in 2s complement form? Posted: If numbers are in 2s complement, an ordinary looking loop like for(i=total=0;i<>

Given an array of length N containing integers between 1 and N, determine if it contains any duplicates. Posted: [Is there an O(n) time solution that uses only O(1) extra space and does not destroy the original array?]

Given an array of integers, find the contiguous sub-array with the largest sum. Posted: Can be done in O(n) time and O(1) extra space. Scan array from 1 to n. Remember the best sub-array seen so far and the best sub-array ending in i

Besides communication cost, what is the other source of inefficiency in RPC? How can you optimize the communication? Posted: Context switches, excessive buffer copying. Optimize by communicating through shared memory on same machine, bypassing the kernel.