tag:blogger.com,1999:blog-64673043929573027052024-02-21T00:46:39.730-08:00Deepak Dhakal's BlogNothing new here .. Me and my view about new technology !!
I will put my view and wait for your comment.Unknownnoreply@blogger.comBlogger14125tag:blogger.com,1999:blog-6467304392957302705.post-58090913073543576602020-08-06T09:37:00.003-07:002020-08-06T09:37:36.029-07:00Algorithm you should know before system design.I collected the algorithm and example we may need during the system design on https://github.com/resumejob/system-design-algorithms
Frugal Streaming
Geohash / S2 Geometry
Leaky bucket / Token bucket
Loosy Counting
Operational transformation
Quadtree / Rtree
Ray casting
Reverse index
Rsync algorithm
Trie algorithm
Check out the examples on the repo.Unknownnoreply@blogger.com4tag:blogger.com,1999:blog-6467304392957302705.post-49831203079903485132010-04-04T22:25:00.000-07:002010-04-04T22:27:40.605-07:00MS interview<style type="text/css">
<br /><!--
<br />A:link {color: blue; text-decoration: none}
<br />A:visited {color: blue; text-decoration: none}
<br />A:hover{background: #66ff66; text-decoration: underline}
<br />-->
<br /></style>
<br /><small>
<br /><font color="black" face="verdana">
<br /><h3>Algorithm Collection</h3>
<br /><a href="#q1">Q1: How would you find a cycle in a linked list? Try to do it in O(n) time. Try it using constant amount of memory.<br></a>
<br /><a href="#q2">Q2: Given a history of URLs, how would you determine if a particular URL had been seen before?<br></a>
<br /><a href="#q3">Q3: Since pages can have multiple URLs pointing to them, how can you make sure you've never seen the same CONTENT before?<br></a>
<br /><a href="#q4">Q4: Come up with the plan on how to traverse a graph, as well as to quickly determine if a given URL is one of the million or so you've previously seen.<br></a>
<br /><a href="#q5">Q5: The Web can be modeled as a directed graph. Come up with a graph traversal algorithm. Make the algorithm non-recursive and breadth-first.<br></a>
<br /><a href="#q6">Q6: Write a function to print the Fibonacci numbers<br></a>
<br /><a href="#q7">Q7: Write a function to print all of the permutations of a string.<br></a>
<br /><a href="#q8">Q8: Design a memory management scheme.<br></a>
<br /><a href="#q9">Q9: Give a one-line C expression to test whether a number is a power of 2. Now implement it without using loops.<br></a>
<br /><a href="#q10">Q10: How can I swap two integers in a single line statement?<br></a>
<br /><a href="#q11">Q11: Implement an algorithm to sort a linked list.<br></a>
<br /><a href="#q12">Q12: Implement strstr(), strcat(), strtok(), strrchr, and strcmp<br></a>
<br /><a href="#q13">Q13: Given a linked list which is sorted, how will you insert in sorted way.<br></a>
<br /><a href="#q14">Q14: Give me an algorithm and C code to find the subarray with the largest sum given an array containing both positive and negative integers.<br></a>
<br /><a href="#q15">Q15: Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it.<br></a>
<br /><a href="#q16">Q16: A square picture is cut into 16 squares and they are shuffled. Write a program to rearrange the 16 squares to get the original big square.<br></a>
<br /><a href="#q17">Q17: Implement an algorithm to reverse a singly linked list. (with and without recursion)<br></a>
<br /><a href="#q18">Q18: Implement an algorithm to reverse a doubly linked list.<br></a>
<br /><a href="#q19">Q19: Delete an element from a doubly linked list.<br></a>
<br /><a href="#q20">Q20: Implement an algorithm to sort an array.<br></a>
<br /><a href="#q21">Q21: Given a sequence of characters, how will you convert the lower case characters to upper case characters?<br></a>
<br /><a href="#q22">Q22: Count the number of set bits in a number without using a loop.<br></a>
<br /><a href="#q23">Q23: Give me an algorithm and C code to shuffle a deck of cards, given that the cards are stored in an array of ints. Try to come up with a solution that does not require any extra space.<br></a>
<br /><a href="#q24">Q24: How would you print out the data in a binary tree, level by level, starting at the top?<br></a>
<br /><a href="#q25">Q25: Do a breadth first traversal of a tree.<br></a>
<br /><a href="#q26">Q26: Write a routine to draw a circle given a center coordiante (x,y) and a radius (r) without making use of any floating point computations.<br></a>
<br /><a href="#q27">Q27: Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words in it.<br></a>
<br /><a href="#q28">Q28: Implement a TIC-TAC-TOE game assuming Computer as one of the player. Optimize it for fast computer play time and space. Do some analysis on memory and processing requirements.<br></a>
<br /><a href="#q29">Q29: Write a function to find the depth of a binary tree.<br>
<br /><a href="#q30">Q30: You are given two strings: S1 and S2. Delete from S2 all those characters which occur in S1 also and create a clean S2 with the relevant characters deleted.<br></a>
<br /><a href="#q31">Q31: Write a small lexical analyzer for expressions like "a*b" etc.<br></a>
<br /><a href="#q32">Q32: Given an array t[100] which contains numbers between 1 and 99. Return the duplicated value. Try both O(n) and O(n-square).<br></a>
<br /><a href="#q33">Q33: Write efficient code for extracting unique elements from a sorted list of array.<br></a>
<br /><a href="#q34">Q34: Given a list of numbers (fixed list) Now given any other list, how can you efficiently find out if there is any element in the second list that is an element of the first list (fixed list).<br></a>
<br /><a href="#q35">Q35: Print an integer using only putchar. Try doing it without using extra storage.<br></a>
<br /><a href="#q36">Q36: Write a function that allocates memory for a two-dimensional array of given size(parameter x & y).<br></a>
<br /><a href="#q37">Q37: Write source code for printHex(int i) in C/C++<br></a>
<br /><a href="#q38">Q38: What sort of technique you would use to update a set of files over a network, where a server contains the master copy.<br></a>
<br /><a href="#q39">Q39: How do you handle deadlock on a table that is fed with a live serial feed?<br></a>
<br /><a href="#q40">Q40: Do the class/structure description for a Hash table, and write the source code for the insert function.<br></a>
<br /><a href="#q41">Q41: How would you implement a hash table? How do you deal with collisions.?<br></a>
<br /><a href="#q42">Q42: What would you suspect if users report they are seeing someone else's data on their customized pages?<br></a>
<br /><a href="#q43">Q43: How would you do conditional compilation?<br></a>
<br /><a href="#q44">Q44: Write an algorithm to draw a 3D pie chart?<br></a>
<br /><a href="#q45">Q45: Prove that Dijkstra's MST algorithm indeed finds the overall MST.<br></a>
<br /><a href="#q46">Q46: How would you implement a queue from a stack?<br></a>
<br /><a href="#q47">Q47: Write a funtion that finds repeating characters in a string.<br></a>
<br /><a href="#q48">Q48: Write a routine to reverse a series of numbers without using an array.<br></a>
<br /><a href="#q49">Q49: Write a function to find the nth item from the end of a linked list in a single pass.<br></a>
<br /><a href="#q50">Q50: Give me an algorithm for telling me the number I didn't give you in a given range of numbers (Numbers are given at random).<br></a>
<br /><a href="#q51">Q51: Write a random number generator in a specified range.<br></a>
<br /><a href="#q52">Q52: Delete a node from a single linked list.<br></a>
<br /><a href="#q53">Q53: Say you have three integers between 0 - 9. You have the equation: A! + B! + C! = ABC. Find A, B, and C that satisfies this equation.<br></a>
<br /><a href="#q54">Q54: Give 2 nodes in a tree, how do you find the common root of the nodes?<br></a>
<br /><a href="#q99">Q99: Write a small lexical analyzer for expressions like a(b|c)d*e+.<br></a>
<br /><br>
<br /><hr>
<br /><a name=q1></a>
<br />Q1: How would you find a cycle in a linked list? Try to do it in O(n) time. Try it using constant amount of memory.<br>
<br />A1: p2 is guaranteed to reach the end of the list before p1 and every link will be tested by the while condition so no chance of access violation. Also, incrementing p2 by 2 and p1 by 1 is the fastest way of finding the cycle. In general if p1 is incremented by 'n' and p2 by 'm', ('n' not == 'm'), then if we number the nodes in the cycle from 0 to k-1 (k is the number of nodes in the cycle), then p1 will take values given by i*n (mod k) and p2 will take values i*m (mod k). These will collide every n*m iterations. Clearly, n*m is smallest for n==1 and m==2.<br>
<br /><pre><font color="Navy" size=2>
<br />bool HasCycle(Node *pHeadNode)
<br />{
<br /> Node *p1, *p2;
<br /> p1 = p2 = pHeadNode;
<br /> while (p2 && p2->Next) {
<br /> p1 = p1->Next;
<br /> p2 = p2->Next->Next;
<br /> if (p1 == p2)
<br /> return true;
<br /> }
<br /> return false;
<br />}
<br /></font></pre>
<br /><a name=q2></a>
<br />Q2: Given a history of URLs, how would you determine if a particular URL had been seen before?<br>
<br />A2: Hash Table is the most efficient way to do this. You can use several hashing algorithms. For example, checksum of a link can be used as a key for hashing. This will ensure o(1) order provided good checksum algorithm is used which is always unique. Whenever page loads we can parse all URL's from the page and take their checksum and compare them w/ the hashtable. Whichever links matches are displayed in some different color.<br>
<br /><br>
<br />Hashtable is the correct answer, but a constant order algo. sounds too fantastic. URLs are by themselves unique and so hash function should not add to the redundancy by being unique. O/w it becomes nothing but a linear sort of search, while binary can do better.<br>
<br /><br>
<br />Though URLs are not inherently alphabetically ordered, one might think of ordering them that way, or making the hash function that utilizes this. This will entail a combined binary + linear search which sounds optimal and is open to complexity calculations. A good data structure can be a hash table pointing to a binary tree (an array pointing to a binary tree).<br>
<br /><br>
<br /><a name=q3></a>
<br />Q3: Since pages can have multiple URLs pointing to them, how can you make sure you've never seen the same CONTENT before?<br>
<br />A3: Keep a list (or a binary tree) of hashes (using MD5, SHA1 or similar hash/digest algorithm) of pages you've visited. Then just compare digest of current page to the hashes in the tree.<br>
<br /><br>
<br /><a name=q4></a>
<br />Q4: Come up with the plan on how to traverse a graph, as well as to quickly determine if a given URL is one of the million or so you've previously seen.<br>
<br />A4: Use prim's algorithm; Kruskal's algorithm is faster than Prim's. For checking for an already seen url, use dictionary search tree. It is the most efficient i.e. O(1) for whatever number of urls you have in the database.<br>
<br /><br>
<br /><a name=q5></a>
<br />Q5: The Web can be modeled as a directed graph. Come up with a graph traversal algorithm. Make the algorithm non-recursive and breadth-first.<br>
<br /><br>
<br /><a name=q6></a>
<br />Q6: Write a function to print the Fibonacci numbers<br>
<br /><pre><font color="Navy" size=2>
<br />int fib (int n)
<br />{
<br /> assert(n>=1);
<br /> return (n<=2 ? 1: (fib(n-1) + fib(n-2)));
<br />}
<br />
<br />int fibonacci (int n)
<br />{
<br /> if (n <= 2) return 1;
<br /> int current, one_back 1, two_back = 1;
<br /> for (int i = 3; i <= n; i++) {
<br /> current = one_back + two_back;
<br /> one_back = two_back;
<br /> two_back = current;
<br /> } /* the end of for loop */
<br /> return current;
<br />}
<br /></font></pre>
<br /><a name=q7></a>
<br />Q7: Write a function to print all of the permutations of a string.<br>
<br /><pre><font color="Navy" size=2>
<br />map<string, int> map_StrInt;
<br />void PermuteString(char* str, int n)
<br />{
<br /> char ch = str[n-1];
<br /> for(int i = 0; i < n; i++)
<br /> {
<br /> swap (str[i], str[n-1]);
<br /> PermuteString(str, n-1);
<br /> swap (str[i], str[n-1]);
<br /> }
<br />
<br /> if (n == 1)
<br /> </font><small><font color="Navy" size=2>map_StrInt</font></small><font color="Navy" size=2>[string(str)]++;
<br />}
<br /></font></pre>
<br /><a name=q8></a>
<br />Q8: Design a memory management scheme.<br>
<br /><br>
<br /><a name=q9></a>
<br />Q9: Give a one-line C expression to test whether a number is a power of 2. Now implement it without using loops.<br>
<br />A9: x = ((x > 0) & !(x & x - 1));<br>
<br /><br>
<br /><a name=q10></a>
<br />Q10: How can I swap two integers in a single line statement?<br>
<br />A10: Use xor operator to accomplish this: a ^= b ^= a ^= b;<br>
<br /><br>
<br /><a name=q11></a>
<br />Q11: Implement an algorithm to sort a linked list.<br>
<br />A11: The merge sort algorithm:<br>
<br /><pre><font color="Navy" size=2>
<br />#include <cassert>
<br />
<br />typedef struct MNode *PNODE;
<br />struct MNode
<br />{
<br /> int Key;
<br /> struct MNode *Next;
<br />};
<br />
<br />PNODE Merge(PNODE p, PNODE q)
<br />{
<br /> assert(p);
<br /> assert(q);
<br />
<br /> PNODE pHead;
<br /> if (p->Key < q->Key)
<br /> {
<br /> pHead = p, p = p->Next;
<br /> }
<br /> else
<br /> {
<br /> pHead = q, q = q->Next;
<br /> }
<br />
<br /> PNODE r = pHead;
<br /> while (p && q)
<br /> {
<br /> if(p->Key < q->Key)
<br /> {
<br /> r->Next = p, r = r->Next, p = p->Next;
<br /> }
<br /> else
<br /> {
<br /> r->Next = q, r = r->Next, q = q->Next;
<br /> }
<br /> }
<br /> if(!p) r->Next = q;
<br /> if(!q) r->Next = p;
<br /> return pHead;
<br />}
<br />
<br />PNODE Partition(PNODE pNode)
<br />{
<br /> PNODE p1 = pNode;
<br /> PNODE p2 = pNode->Next->Next;
<br /> while (p2 && p2->Next)
<br /> {
<br /> p2 = p2->Next->Next;
<br /> p1 = p1->Next;
<br /> }
<br /> PNODE pSav = p1->Next;
<br /> p1->Next = NULL;
<br /> return pSav;
<br />}
<br />
<br />PNODE Merge_Sort(PNODE p)
<br />{
<br /> if (!p || !p->Next) return p;
<br /> PNODE q = Partition(p);
<br /> p = Merge_Sort(p);
<br /> q = Merge_Sort(q);
<br /> p = Merge(p, q);
<br /> return p;
<br />}
<br /></font></pre>
<br /><a name=q12></a>
<br />Q12: Implement strstr(), strcat(), strtok(), strrchr, and strcmp<br>
<br /><pre><font color="Navy" size=2>
<br />char * strstr (const char *str1, const char *str2)
<br />{
<br /> char *cp = (char *)str1;
<br /> char *endp = cp + (strlen(cp) - strlen(str2));
<br />
<br /> while (*cp & (cp <= endp))
<br /> {
<br /> char *s1 = cp;
<br /> char *s2 = (char *)str2;
<br /> while ( *s1 & *s2 && (*s1 == *s2) )
<br /> s1++, s2++;
<br /> if (!(*s2)) return(cp); // success!
<br /> cp++; // bump pointer to next char
<br /> }
<br /> return(NULL);
<br />}
<br />
<br />char *strcat (char * dst, const char * src)
<br />{
<br /> char *cp = dst;
<br /> while (*cp) cp++; // find end of dst
<br /> while (*cp++ = *src++); // Copy src to end of dst
<br /> return (dst); // return dst
<br />}
<br />
<br />char *strcpy (char * dst, const char * src)
<br />{
<br /> char* cp = dst;
<br /> while (*cp++ = *src++); // Copy src over dst
<br /> return(dst);
<br />}
<br />
<br />char *strtok (char *string, const char *control)
<br />{
<br /> char *str;
<br /> const char *ctrl = control;
<br />
<br /> char map[32];
<br /> int count;
<br />
<br /> static char *nextoken;
<br />
<br /> /* Clear control map */
<br /> for (count = 0; count < 32; count++)
<br /> map[count] = 0;
<br />
<br /> // Set bits in delimiter table
<br /> do {
<br /> map[*ctrl >> 3] |= (1 << (*ctrl & 7));
<br /> } while (*ctrl++);
<br />
<br /> // Initialize str. If string is NULL, set str to the saved pointer
<br /> // (i.e., continue breaking tokens out of the string from the last strtok call)
<br /> if (string)
<br /> str = string;
<br /> else
<br /> str = nextoken;
<br />
<br /> // Find beginning of token (skip over leading delimiters). Note that there is
<br /> // no token iff this loop sets str to point to the terminal null (*str == '\0')
<br /> while (</font><small><font color="Navy" size=2>*str && </font></small><font color="Navy" size=2>(map[*str >> 3] & (1 << (*str & 7))))
<br /> str++;
<br />
<br /> string = str;
<br />
<br /> // Find the end of the token. If it is not the end of the string, put a null there.
<br /> for ( ; *str ; str++)
<br /> if (map[*str >> 3] & (1 << (*str & 7))) {
<br /> *str++ = '\0';
<br /> break;
<br /> }
<br />
<br /> // Update nextoken
<br /> nextoken = str;
<br />
<br /> // Determine if a token has been found.
<br /> if (string == str)
<br /> return NULL;
<br /> else
<br /> return string;
<br />}
<br />
<br />int strcmp(const char *src, const char* dst)
<br />{
<br /> int ret = 0;
<br /> while (!(ret = (*src - *dst)) & *dst);
<br /> ++src, ++dst;
<br /> if (ret < 0)
<br /> ret = -1;
<br /> else
<br /> ret = 1;
<br /> return ret;
<br />}
<br />
<br />char *strrev (char *string)
<br />{
<br /> char *start = (char *)string;
<br /> char *left = (char *)string;
<br /> while (*string++); // find end of string
<br /> string -= 2;
<br /> while (left < string)
<br /> {
<br /> char ch = *left;
<br /> *left++ = *string;
<br /> *string-- = ch;
<br /> }
<br /> return start;
<br />}
<br />
<br />char *strrchr (const char *string, int ch)
<br />{
<br /> char *start = (char *)string;
<br /> while (*string--); // find end of string
<br /> while (--string != start && *string != (char)ch); // search forward front
<br /> if (*string == (char)ch) // char found ?
<br /> return (char *)string;
<br /> return (NULL);
<br />}
<br /></font></pre>
<br /><a name=q13></a>
<br />Q13: Given a linked list which is sorted, how will you insert in sorted way.<br>
<br /><pre><font color="Navy" size=2>
<br />void Insert(PNODE &pHead, PNODE pThing)
<br />{
<br /> if (pHead == 0)
<br /> pHead = pThing;
<br /> else
<br /> {
<br /> bool fComesFirst = true;
<br /> PNODE pCurrent = pHead;
<br /> PNODE pPrevious;
<br /> while (pCurrent)
<br /> {
<br /> if (pThing->Key < pCurrent->Key)
<br /> break;
<br /> pPrevious = pCurrent;
<br /> pCurrent = pCurrent->Next;
<br /> fComesFirst = false;
<br /> }
<br />
<br /> if (fComesFirst)
<br /> pHead = pThing;
<br /> else
<br /> pPrevious->Next = pThing;
<br /> pThing->Next = pCurrent;
<br /> }
<br />}
<br /></font></pre>
<br /><a name=q14></a>
<br />Q14: Give me an algorithm and C code to find the subarray with the largest sum given an array containing both positive and negative integers.<br>
<br />/* Give me an algorithm and C code to find the subarray with the largest sum given an array containing both positive and negative integers.<br>
<br /><br>
<br />For each position i in the array we can find out the sub array ending exactly at that position and having the largest sum. At the beginning for the first element the only possible sub array it that one containing the first element so initially the largest amount is a[1]. (For algorithm sake let assume that the array is 1-indexed). Following the principle of dynamic programming it will be proved that the best sub array( with the largest sum) ending in position i+1 is somehow related to best sub array ending in position i.<br>
<br />Let be k the starting index of the best sub array ending in position i and S the sum of this sub array. Let be t an index strictly less than k. The sum from the index t to i+1 is T + S + a[i+1] where T is the sum of elements from t to k-1 indexes. Because of the properties of index k T+S <= S otherwise k will not point to best sub array ending in i so each sub array starting in t<k and ending in i+1 will be worst than the sub array starting exactly in k and ending in i+1.<br>
<br />Similarly , let choose an index t between k+1 and i. The sum from index t to i+1 is T+a[i+1], where is the sum of elements between t and i positions. Again T < S according to the optimality of k index so the best sub array ending in i+1 is that one starting from k and that has S+a[i+1] as sum of array elements. But there is one more situation to analyse. If S is less then zero is obvious that S+a[i+1] < a[i+1] so in this case the best sub array ending in i+1 position is exactly the sub array containing only that element. In fact this situation direct you to start a new sub array that will be candidate for the best sub array of the entire array.<br>
<br />In conclusion the information to be kept while going through the array only once (O(n)) is the best sub array ending in the current position and best sub array found for the entire array until the current step.(if it necessary also the starting and ending position for these sub array can be kept). After the processing of the last element the algorithm will have determined the sub array having the largest sum.<br>
<br /><br>
<br />Note: The algorithm works fine even there is no negative number in the array and it will produce of course as the largest sum the sum of all array elements.<br>
<br /><br>
<br />Algorithm: arr is the array of n integer; the function will return the largest sum and the limits of the sub array producing that value */
<br /><pre><font color="Navy" size=2>
<br />#include <iostream>
<br />using namespace std;
<br />
<br />int GetLargestSubArray(int* arr, int n, int &iBeginRet, int &iEndRet)
<br />{
<br /> int iBeginSaved=0, iEndSaved=0; // the start/end positions of the saved sub array
<br /> int iBegin, iEnd; // the start/end positions of the current sub array
<br /> int nSumSaved=0, nSum=0; // the sums of whole saved largest and current sub arrays
<br /> int i = 0; // index to loop in the array
<br />
<br /> if (0 == n) // Nothing to analyze, return invalid array indexes
<br /> {
<br /> iEndRet = iBeginRet = -1;
<br /> return 0;
<br /> }
<br />
<br /> nSumSaved = nSum = arr[i];
<br /> for(i = 2; i < n; i++)
<br /> {
<br /> /* Compute the current largest sum */
<br /> if (nSum<0)
<br /> {
<br /> nSum = arr[i];
<br /> iBegin = iEnd = i;
<br /> }
<br /> else
<br /> {
<br /> nSum += arr[i];
<br /> iEnd = i;
<br /> }
<br /> if (nSum > nSumSaved)
<br /> {
<br /> nSumSaved = nSum;
<br /> iBeginSaved = iBegin;
<br /> iEndSaved = iEnd;
<br /> }
<br /> }
<br /> iBeginRet = iBeginSaved;
<br /> iEndRet = iEndSaved;
<br /> return nSumSaved;
<br />}
<br /></font></pre>
<br /><a name=q15></a>
<br />Q15: Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it.<br>
<br />A15: I'll try to do it in O(N) w/o using any additional memory. The key is to use content of the array as index into array, checking in O(1) if that number has been seen already.
<br /><pre><font color="Navy" size=2>
<br />bool HasDups(int * a, int N)
<br />{
<br /> bool fHasDup = false;
<br /> for (int i = 0; i < N; i++) {
<br /> int index = a[i] % N;
<br /> if (a[index] > N) {
<br /> fHasDup = true;
<br /> break;
<br /> }
<br /> a[index] += N;
<br /> }
<br />
<br /> //restore the array
<br /> for (int j = 0; j < i; j++)
<br /> if (a[j] > N) a[j] </font><small><font color="Navy" size=2>%=</font></small><font color="Navy" size=2> N;
<br />
<br /> return fHasDup;
<br />}
<br /></font></pre>
<br /><a name=q16></a>
<br />Q16: A square picture is cut into 16 squares and they are shuffled. Write a program to rearrange the 16 squares to get the original big square.<br>
<br /><br>
<br /><a name=q17></a>
<br />Q17: Implement an algorithm to reverse a singly linked list. (with and without recursion)<br>
<br /><pre><font color="Navy" size=2>
<br />Node *RevSList(Node *pCur, Node *pRev) {
<br /> if (!pCur) return pRev;
<br /> Node *pNext = pCur->Next;
<br /> pCur->Next = pRev;
<br /> pRev = pCur;
<br /> return (RevSList(pNext, pRev));
<br />}
<br />
<br />Node * RevSList(Node *pCur) {
<br /> Node *pRev = NULL;
<br /> while (pCur)
<br /> {
<br /> Node *pNext = pCur->Next;
<br /> pCur->Next = pRev;
<br /> pRev = pCur;
<br /> pCur = pNext;
<br /> }
<br /> return pRev;
<br />}
<br /></font></pre>
<br /><a name=q18></a>
<br />Q18: Implement an algorithm to reverse a doubly linked list.
<br /><pre><font color="Navy" size=2>
<br />Node *RevDList(Node *pCur)
<br />{
<br /> if (!pCur) return pCur;
<br /> pSav = pCur->Next;
<br /> pCur->Next = pCur->Prev;
<br /> pCur->Prev = pSav;
<br /> if (!pSav) return pCur;
<br /> return RevDList(pSav);
<br />}
<br />
<br />Node *RevDList(Node *pCur)
<br />{
<br /> while (pCur)
<br /> {
<br /> Node *pSav = pCur->Next;
<br /> pCur->Next = pCur->Prev;
<br /> pCur->Prev = pSav;
<br /> if (!pSav) return pCur;
<br /> pCur = pSav;
<br /> }
<br /> return pCur;
<br />}
<br /></font></pre>
<br /><a name=q19></a>
<br />Q19: Delete an element from a doubly linked list.
<br /><pre><font color="Navy" size=2>
<br />Node *DelDLLNode(Node *pNode)
<br />{
<br /> if (!pNode) return pNode;
<br /> if (pNode->Next) pNode->Prev->Next = pNode->Next;
<br /> if (pNode->Prev) pNode->Next->Prev = pNode->Prev;
<br /> return pNode; // delete it if it's heap-based.
<br />}
<br /></font></pre>
<br /><a name=q20></a>
<br />Q20: Implement an algorithm to sort an array.<br>
<br /><br>
<br /><a name=q21></a>
<br />Q21: Given a sequence of characters, how will you convert the lower case characters to upper case characters?<br>
<br /><br>
<br /><a name=q22></a>
<br />Q22: Count the number of set bits in a number without using a loop.
<br /><pre><font color="Navy" size=2>
<br />#define reverse(x) \
<br /> (x=x>>16 | (0x0000ffff&x)<<16, \
<br /> x=(0xff00ff00&x)>>8|(0x00ff00ff&x)<<8, \
<br /> x=(0xf0f0f0f0&x)>>4|(0x0f0f0f0f&x)<<4, \
<br /> x=(0xcccccccc&x)>>2|(0x33333333&x)<<2, \
<br /> x=(0xaaaaaaaa&x)>>1|(0x55555555&x)<<1)
<br />
<br />#define count_ones(x) \
<br /> (x=((0xaaaaaaaa&x)>>1)+(0x55555555&x), \
<br /> x=((0xcccccccc&x)>>2)+(0x33333333&x), \
<br /> x=((0xf0f0f0f0&x)>>4)+(0x0f0f0f0f&x), \
<br /> x=((0xff00ff00&x)>>8)+(0x00ff00ff&x), \
<br /> x=(x>>16) + (0x0000ffff&x))
<br /></font></pre>
<br /><a name=q23></a>
<br />Q23: Give me an algorithm and C code to shuffle a deck of cards, given that the cards are stored in an array of ints. Try to come up with a solution that does not require any extra space.<br>
<br /><pre><font color="Navy" size=2>
<br />for (Src = 0; Src < N; Src++)
<br />{
<br /> Dest = rand() % N; // All N positions equally likely
<br /> Swap (X[Src], X[Dest]);
<br />}
<br /></font></pre>
<br />At first glance, it would appear that this algorithm generates all permutations with equal probability. On examination, though, one can see that this will generate N<sup>N</sup> arrangements of elements---each of the N iterations of the loop positions a value among the N available positions. It is known, though, that there are only N! possible permutations of N elements: for each permutation there are multiple ways to generate that permutation---on average, N<sup>N</sup>/N! ways.
<br /><pre><font color="Navy" size=2>
<br />for (Src = 0; Src < N; Src++)
<br />{
<br /> Dest = rand() % N; // All N positions equally likely
<br /> Swap (X[Src], X[Dest]);
<br />}
<br /></font></pre>
<br />Examination of the structure of this loop shows that it will generate N! arrangements of elements. All permutations are equally likely, aside from the very minor deviation from uniform distribution by selecting a random value between 0 and Dest as (rand() % (Dest+1)).<br>
<br /><br>
<br /><a name=q24></a>
<br />Q24: How would you print out the data in a binary tree, level by level, starting at the top?<br>
<br /><br>
<br /><a name=q25></a>
<br />Q25: Do a breadth first traversal of a tree.<br>
<br /><pre><font color="Navy" size=2>
<br />typedef int VertexType;
<br />typedef class Vertex *LPVertex;
<br />
<br />class Vertex
<br />{
<br /> int index;
<br /> int weight;
<br /> LPVertex next;
<br />public:
<br /> int GetIndex();
<br /> bool Visited();
<br /> Vertex &Visit();
<br /> Vertex &Mark();
<br /> Vertex *GetNext();
<br />};
<br />
<br />enum { kMaxVertices = 7 };
<br />typedef LPVertex HeaderArray[kMaxVertices];
<br />HeaderArray adjacencyList;
<br />
<br />void BreathFirstSearch (HeaderArray adjacencyList, LPVertex pv)
<br />{
<br /> queue<LPVertex> Q;
<br /> pv->Visit().Mark();
<br /> Q.push(pv);
<br /> while (!Q.empty())
<br /> {
<br /> pv = Q.front(); Q.pop();
<br /> pv = adjacencyList[pv->GetIndex()];
<br /> for (; pv; pv = pv->GetNext())
<br /> if (!pv->Visited())
<br /> {
<br /> pv->Visit().Mark();
<br /> Q.push (pv);
<br /> }
<br /> }
<br />}
<br />
<br />void DepthFirstSearch (HeaderArray adjacencyList, LPVertex pv)
<br />{
<br /> stack<LPVertex> S;
<br /> pv->Visit().Mark();
<br /> S.push(pv);
<br /> while (!S.empty())
<br /> {
<br /> pv = S.top();
<br /> pv = adjacencyList[pv->GetIndex()];
<br /> for (; pv; pv = pv->GetNext())
<br /> if (!pv->Visited())
<br /> {
<br /> pv->Visit().Mark();
<br /> S.push(pv);
<br /> }
<br /> S.pop();
<br /> }
<br />}
<br /></font></pre>
<br /><a name=q26></a>
<br />Q26: Write a routine to draw a circle given a center coordiante (x,y) and a radius (r) without making use of any floating point computations.<br>
<br /><br>
<br /><a name=q27></a>
<br />Q27: Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words in it.<br>
<br /><pre><font color="Navy" size=2>
<br />char *ReverseWords (char *string)
<br />{
<br /> char *start = strrev(string);
<br /> char *left;
<br /> char *right;
<br /> char ch;
<br />
<br /> while (*string)
<br /> {
<br /> while (*string == ' ' & *string)
<br /> string++;
<br /> left = string;
<br />
<br /> while (*string != ' ' & *string)
<br /> string++;
<br /> right = string-1;
<br />
<br /> while (left < right)
<br /> {
<br /> ch = *left;
<br /> *left++ = *right;
<br /> *right-- = ch;
<br /> }
<br /> }
<br /> return start;
<br />}
<br /></font></pre>
<br /><a name=q28></a>
<br />Q28: Implement a TIC-TAC-TOE game assuming Computer as one of the player. Optimize it for fast computer play time and space. Do some analysis on memory and processing requirements.<br>
<br /><br>
<br /><a name=q29></a>
<br />Q29: Write a function to find the depth of a binary tree.<br>
<br /><pre><font color="Navy" size=2>
<br />long findDepth(Node *pNode)
<br />{
<br /> if (</font><small><font color="Navy" size=2>!pNode</font></small><font color="Navy" size=2>) return 0;
<br /> long depthLeft = findDepth(</font><small><font color="Navy" size=2>pNode</font></small><font color="Navy" size=2>->Left);
<br /> long depthRight = findDepth(</font><small><font color="Navy" size=2>pNode</font></small><font color="Navy" size=2>->Right);
<br /> return (depthLeft>depthRight ? ++depthLeft: ++depthRight);
<br />}
<br /></font></pre>
<br /><a name=q30></a>
<br />Q30: You are given two strings: S1 and S2. Delete from S2 all those characters which occur in S1 also and create a clean S2 with the relevant characters deleted.<br>
<br /><pre><font color="Navy" size=2>
<br />char *strtokrem (char *string, const char *control)
<br />{
<br /> char *start = string;
<br /> char *str = string;
<br /> const char *ctrl = control;
<br />
<br /> char map[32];
<br /> int count;
<br />
<br /> /* Clear control map */
<br /> for (count = 0; count < 32; count++)
<br /> map[count] = 0;
<br />
<br /> // Set bits in delimiter table
<br /> do {
<br /> map[*ctrl >> 3] |= (1 << (*ctrl & 7));
<br /> } while (*ctrl++);
<br />
<br /> // Remove each token whenever it matches
<br /> while (*str)
<br /> if (map[*str >> 3] & (1 << (*str & 7))) {
<br /> for (char *pch = str; *pch; pch++)
<br /> *pch = *(pch+1);
<br /> }
<br /> else
<br /> str++;
<br /> return start;
<br />}
<br /></font></pre>
<br /><a name=q31></a>
<br />Q31: Write a small lexical analyzer for expressions like "a*b" etc.<br>
<br /><pre><font color="Navy" size=2>
<br />bool is_astarb(char* string)
<br />{
<br /> // expressions: b, ab, aab, aaab, ...
<br /> bool bRet = false;
<br /> while (*string == 'a')
<br /> ++string;
<br />
<br /> if (*string == 'b')
<br /> bRet = (*++string == '\0');
<br />
<br /> return bRet;
<br />}
<br /></font></pre>
<br /><a name=q32></a>
<br />Q32: Given an array t[100] which contains numbers between 1 and 99. Return the duplicated value. Try both O(n) and O(n-square).<br>
<br /><br>
<br /><a name=q33></a>
<br />Q33: Write efficient code for extracting unique elements from a sorted list of array.
<br /><pre><font color="Navy" size=2>
<br />void PrintUniqueElements(int rgNumb[], int cNumb)
<br />{
<br /> assert(cNumb>0);
<br /> int iSav;
<br /> cout << (iSav = rgNumb[0]) << "\t";
<br /> for (int i = 1; i < cNumb; i++)
<br /> if (iSav != rgNumb[i])
<br /> cout << (iSav = rgNumb[i]) << "\t";
<br />}
<br /></font></pre>
<br /><a name=q34></a>
<br />Q34: Given a list of numbers (fixed list) Now given any other list, how can you efficiently find out if there is any element in the second list that is an element of the first list (fixed list).<br>
<br /><br>
<br /><a name=q35></a>
<br />Q35: Print an integer using only putchar. Try doing it without using extra storage.<br>
<br /><pre><font color="Navy" size=2>
<br />void putDigits(int val)
<br />{
<br /> if (val < 0) { cout << "-"; val = -val; }
<br /> stack<int> S;
<br /> S.push(val);
<br /> while (!S.empty())
<br /> {
<br /> val = S.top(); S.pop();
<br /> if (val >= 10)
<br /> {
<br /> S.push(val%10);
<br /> S.push(val/10);
<br /> }
<br /> else
<br /> cout.put(val+'0');
<br /> }
<br />}
<br /></font></pre>
<br /><a name=q36></a>
<br />Q36: Write a function that allocates memory for a two-dimensional array of given size(parameter x & y).<br>
<br /><br>
<br /><a name=q37></a>
<br />Q37: Write source code for printHex(int i) in C/C++
<br /><pre><font color="Navy" size=2>
<br />void putHex(int val)
<br />{
<br /> if (val < 0) {
<br /> printf("-");
<br /> val = -val;
<br /> }
<br /> if (val >= 0 & val < 16) {
<br /> printf("%c", val > 9 ? (val-10)+'A' : val+'0');
<br /> return;
<br /> }
<br /> putHex(val/16);
<br /> printf("%c", val%16 > 9 ? (val%16-10)+'A' : val%16+'0');
<br />}
<br /></font></pre>
<br /><a name=q38></a>
<br />Q38: What sort of technique you would use to update a set of files over a network, where a server contains the master copy.<br>
<br /><br>
<br /><a name=q39></a>
<br />Q39: How do you handle deadlock on a table that is fed with a live serial feed?<br>
<br /><br>
<br /><a name=q40></a>
<br />Q40: Do the class/structure description for a Hash table, and write the source code for the insert function.<br>
<br /><br>
<br /><a name=q41></a>
<br />Q41: How would you implement a hash table? How do you deal with collisions.?<br>
<br /><br>
<br /><a name=q42></a>
<br />Q42: What would you suspect if users report they are seeing someone else's data on their customized pages?<br>
<br />A42: Overflow; If we're talking about ASP, JSP, CFML that sort of thing, I would suspect unsynchronized access to session data in a multi-threaded Servlet, JavaBean or COM object -- i.e., a non-threadsafe bug in the server application.<br>
<br /><br>
<br /><a name=q43></a>
<br />Q43: How would you do conditional compilation?<br>
<br />A43: The #if directive, with the #elif, #else, and #endif directives, controls compilation of portions of a source file. If the expression you write (after the #if) has a nonzero value, the line group immediately following the #if directive is retained in the translation unit. Plus, #ifdef and #ifndef identifier.<br>
<br /><br>
<br /><a name=q44></a>
<br />Q44: Write an algorithm to draw a 3D pie chart?<br>
<br /><br>
<br /><a name=q45></a>
<br />Q45: Prove that Dijkstra's MST algorithm indeed finds the overall MST.<br>
<br />A45: The two common MST algorithms are by Kruskal and Prim. Djikstra gave us an algorithm for shortest path, not MST.<br>
<br /><br>
<br /><a name=q46></a>
<br />Q46: How would you implement a queue from a stack?<br>
<br /><pre><font color="Navy" size=2>
<br />stack stk1, stk2;
<br />void push(element e)
<br />{
<br /> push.stk1(e);
<br />}
<br />
<br />element pop()
<br />{
<br /> if(stk2.empty())
<br /> while(!stk1.empty())
<br /> stk2.push(stk1.pop());
<br /> return stk2.pop();
<br />}
<br /></font></pre>
<br /><a name=q47></a>
<br />Q47: Write a funtion that finds repeating characters in a string.<br>
<br /><br>
<br /><a name=q48></a>
<br />Q48: Write a routine to reverse a series of numbers without using an array.
<br /><pre><font color="Navy" size=2>
<br />int iReverse (int iNum)
<br />{
<br /> int iRev =0;
<br /> while(iNum !=0)
<br /> {
<br /> iRev = iRev * 10 + iNum % 10;
<br /> iNum /= 10;
<br /> }
<br /> return iRev;
<br />}
<br /></font></pre>
<br /><a name=q49></a>
<br />Q49: Write a function to find the nth item from the end of a linked list in a single pass.<br>
<br />A49: I would think keeping a gap of "n" between fptr and sptr would do. Then, advance both together till fptr->next (fptr is the one in front) = NULL.<br>
<br /><br>
<br />Aren't you traversing the list twice - once with fptr and the second time with sptr. I think you should maintain an queue of pointers. Keep pushing a pointer into the queue and whenever the size of the queue becomes greater than n, remove a pointer at the head of the queue. When you reach the end of the list. The element at the head of the queue gives a pointer to the nth element from the end.<br>
<br /><pre><font color="Navy" size=2>
<br />#include <queue>
<br />PNODE GetNthLastElement (PNODE pCur, unsigned nOffset)
<br />{
<br /> queue<PNODE> Q;
<br />
<br /> for (; pCur && Q.size() < nOffset; Q.push(pCur), pCur = pCur->Next) ;
<br /> if (Q.size() < nOffset) return NULL;
<br />
<br /> while (pCur)
<br /> {
<br /> Q.pop();
<br /> Q.push(pCur);
<br /> pCur = pCur->Next;
<br /> }
<br /> return (Q.front());
<br />}
<br /></font></pre>
<br /><a name=q50></a>
<br />Q50: Give me an algorithm for telling me the number I didn't give you in a given range of numbers (Numbers are given at random).<br>
<br /><br>
<br /><a name=q51></a>
<br />Q51: Write a random number generator in a specified range.
<br /><pre><font color="Navy" size=2>
<br />#include <algorithm>
<br />
<br />int random_range(int lowest_number, int highest_number)
<br />{
<br />¡¡¡¡if (lowest_number > highest_number)
<br />¡¡¡¡{
<br />¡¡¡¡¡¡¡¡swap(lowest_number, highest_number);
<br />¡¡¡¡}
<br />
<br />¡¡¡¡int range = highest_number - lowest_number + 1;
<br />¡¡¡¡return lowest_number + int(range * rand()/(RAND_MAX + 1.0));
<br />}
<br /></font></pre>
<br /><br>
<br /><a name=q52></a>
<br />Q52: Delete a node from a single linked list.
<br /><pre><font color="Navy" size=2>
<br />Node *DelSLLNode(Node *pDelete, Node *pHead)
<br />{
<br /> if (pHead == pDelete)
<br /> return (pHead = pHead->Next);
<br />
<br /> Node *pPrev = pHead;
<br /> for ( ; pPrev->Next; pPrev = pPrev->Next)
<br /> {
<br /> if (pPrev->Next == pDelete)
<br /> {
<br /> pPrev->Next = pPrev->Next->Next;
<br /> break;
<br /> }
<br /> }
<br /> return pHead;
<br />}
<br /></font></pre>
<br /><br>
<br /><a name=q53></a>
<br />Q53: Say you have three integers between 0 - 9. You have the equation: A! + B! + C! = ABC (where ABS is a three digit numbers, not A * B * C). Find A, B, and C that satisfies this equation.
<br /><pre><font color="Navy" size=2>
<br />1! + 4! + 5! = 145
<br /></font></pre>
<br /><br>
<br /><a name=q54></a>
<br />Q54: Give 2 nodes in a tree, how do you find the common root of the nodes?<br>
<br /><br>
<br /><a name=q99></a>
<br />Q99: Write a small lexical analyzer for expressions like a(b|c)d*e+.
<br /><pre><font color="Navy" size=2>
<br />enum State {
<br /> s0 = 0, s1, s2, s3, // states
<br /> m0 = 0, m1, m2, m3, acc, err // actions: matches, accept or error
<br />};
<br />
<br />State DecisionTable[4][6] = {
<br />// a b c d e other // input
<br /> m1,err,err,err,err,err, // s0
<br /> err, m2, m2,err,err,err, // s1
<br /> err,err,err, m2, m3,err, // s2
<br /> acc,acc,acc,acc, m3,acc // s3
<br />};
<br />
<br />State IsAcceptable (char *&theIStream)
<br />{
<br /> State stateCur = s0, State theDecision = err;
<br /> do
<br /> {
<br /> char theChar = *theIStream++;
<br /> int theInput = (theChar - 'a') % 6;
<br /> theDecision = DecisionTable[stateCur][theInput];
<br />
<br /> switch (theDecision)
<br /> {
<br /> default:
<br /> stateCur = theDecision;
<br /> break;
<br /> case err:
<br /> case acc:
<br /> ; // do nothing
<br /> }
<br /> } while (theDecision != err & theDecision != acc);
<br /> return theDecision;
<br />}
<br /></font></pre>
<br /><hr>
<br /><h4>The Six Phases of a Compiler</h4>
<br /><ul>
<br /><li>Front End<ul>
<br /><li>Lexical Analysis - Token Stream
<br /><li>Syntactic Analysis - Parse Tree
<br /><li>Semantic Analysis - Parse Tree
<br /><li>Intermediate Code Generation - IR</ul>
<br /><li>Back End<ul>
<br /><li>Code Optimization - IR
<br /><li>Code Generation - Target Program</ul>
<br /><li>Error Handling and Symbol Table
<br /></ul>
<br /></ol>
<br /><br>
<br /><h4>Two Parts - Analysis and Synthesis</h4>
<br /><br>
<br /><h5>The Six Components of a Compiler</h5>
<br /><ul>
<br /><li>Scanner, Lexer, or Lexical Analyzer<ul>
<br /> <li>Groups characters into tokens - basic unit of syntax<br>
<br /> (character string forming a token is a lexeme)<br>
<br /><li>Eliminates white space (blanks, tabs and returns)</ul>
<br /><li>Parser, Syntactic Analyzer<ul>
<br /> <li>Groups tokens into grammatical phrases
<br /> <li>Represent the grammatical phrases into a parse tree
<br /> <li>The syntac of a language is specified by context-free grammar</ul>
<br /><li>semantic Analyzer<ul>
<br /> <li>Variables redefined, Procedures called w/ the right number of types of args.
<br /> <li>Type checking with permitted coercions, e.g. Operator called w/ incompatible types</ul>
<br /><li>Intermediate Code Generator
<br /><li>Code Optimizer - The VC++ can perform copy propagation and dead store elimination, common subexpression elimination, register allocation, function inlining, loop optimizations, flow graph optimizations, peephole optimizations, scheduling, and stack packing.
<br /><li>Code Generator
<br /></ul>
<br /><br>
<br /><h4>Lexers - Finite State Automata (FSA)</h4>
<br />LEX implements this by creating a C program that consists of a general algorithm and a decision table specific to the DFSA:
<br /><pre><font color="Navy" size=2>
<br /> state= 0; get next input character
<br /> while (not end of input) {
<br /> depending on current state and input character
<br /> match: /* input expected */
<br /> calculate new state; get next input character
<br /> accept: /* current pattern completely matched */
<br /> perform action corresponding to pattern; state= 0
<br /> error: / input unexpected /
<br /> reset input; report error; state= 0
<br /> }
<br /></font></pre>
<br /><br>
<br /><h4>Parsers - Push Down Automata (PDA)</h4>
<br />There are two important classes of parsers, known as top-down parsers and bottom-up parsers. They are important because they provide a good trade-off between speed (they read the input exactly once, from left-to-right) and power (they can deal w/ most computer languages, but are confused by some grammars).<br>
<br /><br>
<br /><h5>Top-Down Parsers</h5>
<br />Here, the stack of the PDA is used to hold what we are expecting to see in the input. Assuming the input is correct, we repeatedly match the top-of-stack to the next input symbol and then discard them, or else replace the top-of-stack by an expansion from the grammar rules.
<br /><pre><font color="Navy" size=2>
<br /> initialise stack to be the start symbol followed by end-of-input
<br /> repeat
<br /> if top-of-stack == next input
<br /> match -- pop stack, get next input symbol
<br /> else if top-of-stack is non-terminal and lookahead (e.g. next input) is as expected
<br /> expand -- pop stack (= LHS of grammar rule)
<br /> and push expansion for it (= RHS of grammar rule) in reverse order
<br /> else
<br /> error -- expected (top-of-stack) but saw (next input)
<br /> until stack empty or end-of-input
<br />
<br />e.g. recognising a , b , c using:
<br />list : id tail;
<br />tail : ',' id tail | ;
<br />
<br />stack next input rest of input action ($ represents end-of-input)
<br />$ list a , b , c $ expand list to id tail
<br />$ tail id a , b , c $ match id a
<br />$ tail , b , c $ expand tail to ',' id tail
<br />$ tail id , , b , c $ match ,
<br />$ tail id b , c $ match id b
<br />$ tail , c $ expand tail to ',' id tail
<br />$ tail id , , c $ match ,
<br />$ tail id c $ match id c
<br />$ tail $ expand tail to (nothing)
<br />$ $ accept
<br /></font></pre>
<br /><br>
<br /><h5>Bottom-Up Parsers</h5>
<br />Here, the stack of the PDA is used to hold what we have already seen in the input. Assuming the input is correct, we repeatedly shift input symbols onto the stack until what we have matches a grammar rule, and then we reduce the grammar rule to its left-hand-side.<br>
<br /><pre><font color="Navy" size=2>
<br /> initialise stack (to end-of-input marker)
<br /> repeat
<br /> if complete grammar rule on stack and lookahead (e.g. next input) is as expected
<br /> reduce -- pop grammar rule and push LHS
<br /> else if lookahead (e.g. next input) is as expected
<br /> shift -- push next input, get next input symbol
<br /> else
<br /> error
<br /> until stack==start symbol and at end-of-input
<br />
<br />e.g. recognising a , b , c using:
<br />list : id | list ',' id;
<br />
<br />stack next input rest of input action
<br />$ a , b , c $ shift id a
<br />$ id , b , c $ reduce id to list
<br />$ list , b , c $ shift ,
<br />$ list , b , c $ shift id b
<br />$ list , id , c $ reduce list ',' id to list
<br />$ list , c $ shift ,
<br />$ list , c $ shift id c
<br />$ list , id $ reduce list ',' id to list
<br />$ list $ accept
<br />
<br />e.g. here is the y.output and corresponding decision table for list : id | list ',' id ;
<br />
<br />state 0 $accept : _list $end
<br /> id shift 1 . error list goto 2
<br />state 1 list : id_ (1)
<br /> . reduce 1
<br />state 2 $accept : list_$end
<br /> list : list_, id
<br /> $end accept , shift 3 . error
<br />state 3 list : list ,_id
<br /> id shift 4 . error
<br />state 4 list : list , id_ (2)
<br /> . reduce 2
<br /></font></pre>
<br /><table border=1 cellspacing=0 cellpadding=0>
<br /><tr bgcolor="skyblue">
<br /> <th rowspan=2 width=80 bgcolor="DodgerBlue"><small>state</small></th>
<br /> <th colspan=3><small>terminal symbols</small></th>
<br /> <th colspan=1a><small>non-terminals</small></th>
<br /></tr>
<br /><tr bgcolor="yellowgreen">
<br /> <td width=170><p align=center><small>id</small></p></td>
<br /> <td width=70><p align=center><small>','</small></p></td>
<br /> <td width=70><p align=center><small>$end</small></p></td>
<br /> <td width=140><p align=center><small>list</small></p></td>
<br /></tr>
<br /><tr>
<br /> <td bgcolor="DodgerBlue"><p align=center><small>0</small></p></td>
<br /> <td><small>shift 1</small></td>
<br /> <td>.</td>
<br /> <td>.</td>
<br /> <td><small>goto 2</small></td>
<br /></tr>
<br /><tr>
<br /> <td bgcolor="DodgerBlue"><p align=center><small>1</small></p></td>
<br /> <td><small>reduce (list:id)</small></td>
<br /> <td>.</td>
<br /> <td>.</td>
<br /> <td>.</td>
<br /></tr>
<br /><tr>
<br /> <td bgcolor="DodgerBlue"><p align=center><small>2</small></p></td>
<br /> <td>.</td>
<br /> <td><small>shift 3</small></td>
<br /> <td><small>accept</small></td>
<br /> <td>.</td>
<br /></tr>
<br /><tr>
<br /> <td bgcolor="DodgerBlue"><p align=center><small>3</small></p></td>
<br /> <td><small>shift 4</small></td>
<br /> <td>.</td>
<br /> <td>.</td>
<br /> <td>.</td>
<br /></tr>
<br /><tr>
<br /> <td bgcolor="DodgerBlue"><p align=center><small>4</small></p></td>
<br /> <td><small>reduce (list : list ',' id)</small></td>
<br /> <td>.</td>
<br /> <td>.</td>
<br /> <td>.</td>
<br /></tr>
<br /></table>
<br /><br>
<br /><li>References: <a href="http://www.cs.man.ac.uk/~pjj/cs2121/ho/node7.html" target="blank">How LEX and YACC work</a> and <a href="http://www.cs.man.ac.uk/~pjj/cs2111/ho/node6.html" target="blank">Inside Lex and Yacc</a>
<br /></small>
<br /></font>
<br /></body>Unknownnoreply@blogger.com111tag:blogger.com,1999:blog-6467304392957302705.post-67508024019621903502009-09-28T11:21:00.000-07:002009-09-28T11:22:02.628-07:00Amazon interview question CollectionGeneral Questions and Comments [more]<br />generic questions on software development<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What is the complexity of this algorithm<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What is your stronger language (Java or C#)<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Lot of design questions and OOAD stuff 2<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Programming questions asked were more or less same as the ones listed at this site<br /><br /><br />--------------------------------------------------------------------------------<br /><br />more architectural view about solve problem capability. I think the intervier was more realistic than the other two . Not just because he recommend to 2nd interview, since I also have the experience with recuriting other employees in the past. I felt the potenial is more than anything in work. Coding is just one thing , maybe the one who can solve the tricky algorithms is good in some way, but how about the one who has been out of school for several years and I cant remeber anything about mergesort or quicksort or how to find the shortest path blah blah. But I do have the confidence I am very good at work. No matter where I go, I found most people are not that smart and if you are willing to learn, you can be the best. Of course, you must have the potenial first. Like you are willing to learn and you like your job... 5<br /><br /><br />--------------------------------------------------------------------------------<br /><br />3rd phone interview<br /><br /><br />--------------------------------------------------------------------------------<br /><br />what do you like in a job 2<br /><br /><br />--------------------------------------------------------------------------------<br /><br />gave some description about the job and then it is done<br /><br /><br />--------------------------------------------------------------------------------<br /><br />I took around 2 hours to do a good job for this becoz he wanted propper OO concepts. Created the util class as a singleton with synchronization for the add and edit methods with exceptions being thrown when employee's arent found etc. He seemed to like it from the reply mail i received<br /><br /><br />--------------------------------------------------------------------------------<br /><br />The standard stuff had to be added to the api like synchronization, singleton etc.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />its coming up soon, hopefully ill do good :D<br /><br /><br />--------------------------------------------------------------------------------<br /><br />How do you resolve a collision in a hash table<br /><br /><br />Algorithm [more]<br />Coding: How would you find the nth to last element in a linked list? 27<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Algorithm: Explain algorithm to shuffle cards 8<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Coding: Jig saw puzzle. What are the data structures? Assume you have some method which can tell you if two pieces fit together. How would you solve the puzzle, minimizing the number of times you have to call that function? 9<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Algorithm: You have 50,000 html files, some of which contain phone numbers. How would you create a list of all the files which contain phone numbers? 14<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Coding: How would you reverse the words in a string? (ie, "the quick brown fox" --> "fox brown quick the" 41<br /><br /><br />--------------------------------------------------------------------------------<br /><br />How would you detect a repeated element in an integer array. Discuss various solutions and the order of the algorithm. 37<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Write a function to smooth out stock fluctuations. Asked me to layout the mathematical idea for curve smoothing before writing code. 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Given two sets, Write a function to provide the union of them. STL not allowed to be used.<br />Optimise for Time and space. 24<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design an algorithm to calculate the most user viewed pages 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Find missing element in an array of 100 elements. 16<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design an algorithm to find duplicates in an array. Discuss different approaches. 16<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design an algorithm and write code to find nth node from the end in a linked list 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design an algorithm and write code to shuffle a standard deck of cards 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design an algorithm and write code to serialize a binary tree. Discuss various solutions 18<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design an algorithm and write code to find two numbers in an array whose sum equals a given value 19<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Given 2 files, each with names of thousands of customers who bought something from Amazon.com on that particular day. Find the common customers (i.e. common names in file1 and file2) 9<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Given 3 files, each with names of thousands of customers who bought something from Amazon.com on that particular day. Find the common customers (i.e. common names in file1 and file2 and file3) 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />count bits in an integer. Solved using mask, did not attempt -1 approach. 6<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Given two binary trees, find whether or not they are similar. 12<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Determine is a graph is circular. 6<br /><br /><br />--------------------------------------------------------------------------------<br /><br />assume your computer is reading characters one by one from a stream (you don't know the length of the stream before ending). Note that you have only one character of storage space (so you cann't save the characters you've read to a something like a strong). When you've finished reading you should return a character out of the stream with equal probability. 11<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Algorithm: You have a tree (not Binary) and you want to print the values of all the nodes in this tree level by level. Discussed on phone and asked me to email Java code for my algorithm. 4<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Unix: You have 50,000 html files in a UNIX directory structure, some of which contain phone numbers in the format ***-***-****. How would you create a list of all the files which contain phone numbers? (Assume that you already have the regular expression) 5<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Given two log files, each with a billion usernames (each username appended to the log file), find the usernames existing in both documents in the most efficient manner? Use pseudo-code or code. If your code calls pre-existing library functions, create each library function from scratch. 8<br /><br /><br />--------------------------------------------------------------------------------<br /><br />How could a linked list and a hash table be combined to allow someone to run through the list from item to item while still maintaining the ability to access an individual element in O(1) time? 4<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Here is a tree. It's a binary tree but in no particular order. How do you write this tree to a file so that it can be reread in an reconstructed exactly as shown? 33<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Here is a graph of distribution centers and the weight to go from one to another. How would you represent this using a data structure? Code an alogrithm that allows me to check if there is a path from one node to another and what the weight of this path is. 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Given two dates, Design an algorithm to return whether the dates are exactly a month apart, less than a month apart or more than a month apart. 2<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Discussed the proof and solution to my card shuffle problem 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Write a method to shufle the deck. The constraint is it has to be a perfect shuffle - in other words, every 52! permutations of the deck has to be equally like (given a completely random function which is theoretical of course).<br /><br />I managed to do this with a simple for loop in O(n) time<br /><br /><br />int[] deck = new int[52];<br />for(int i=0; i<52; i++)<br />deck[i] = i;<br /><br />Random r = new Random();<br />for(int i=0; i<br />int ran = r.nextInt(deck.length-i) + i;<br />int temp = deck[i];<br />deck[i] = deck[ran];<br />deck[ran] = temp;<br />}<br /><br /><br />--------------------------------------------------------------------------------<br /><br />int[1000], numbers from 1 to 1000, but one is missed - find it 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />reverse linked list. Why don't you use recursion? 5<br /><br /><br />--------------------------------------------------------------------------------<br /><br />If there are two structs, TreeNode and Tree. TreeNode contains 3 elements, data, lChild and rChile. Tree contains 2 elements, int size and TreeNode *root. The tree is a complete tree. So how to find a O(logN) approach to insert a new node. 2<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Algorithm and code to detect occurence of a string(patterns) in another string ex: aab, aababa 5<br /><br /><br />--------------------------------------------------------------------------------<br /><br />If you are given a set of 1000 integers in a set A , and 10,000,000 integers in a set B, how would you create a set C that would only contain numbers that are both in A and B? 2<br /><br /><br />--------------------------------------------------------------------------------<br /><br />In a general tree, how would you find the lowest common ancestor of two nodes that are given to you as parameters? 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />How do you merge n sorted lists with average length K in O(n*log(K)) time? 12<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design an algorithm to find the 100 shortest distances to stars in the universe 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />If you have a draft ransom note and a book, how would you determine if said ransom note can be composed from the book on its own? What if the ransom note is not necessarily in ascii (can be in chinese and such). What if you have no storage save for a few counters?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What is a scripting language? Write a code to output the dot product of two files.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Suggest an algorithm to find the first non-repeating character in a given string. 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />How to find the two numbers whose difference is minimum among the set of numbers 7<br /><br /><br />--------------------------------------------------------------------------------<br /><br />a. Findodd - given ana array of numbers return a number which appear odd number of times.<br />b. isPrime<br />c. Garbage Collector.<br />d. OO model for Elevator, grilled a bit but successfully answered.<br />e. Find if high bit is set in the integer.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Describe the data structures you will use for implementing snake & ladder game 3<br /><br /><br />Application / UI Design [more]<br />How would you design a parking garage?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Given an outline for an architectural plan, automate the loading of the design into a computer<br /><br /><br />Behavioral [more]<br />Why do you want to work at Amazon? 2<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Talk about your favourite project? What part of a Software Project do you enjoy most?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Lunch - QA manager.<br /><br />1. tell me a situation when u had to face problems and the requirements were not clear. how did u handle the situation?<br /><br />2. which is the best error you have caught?<br /><br />3. which is the worst error u've ever caught?<br /><br />4. asked about a project on my resume<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Why do you want to work here?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Favorite feature on Amazon personalization site<br /><br /><br />--------------------------------------------------------------------------------<br /><br />How did you hear about Amazon?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />what you don't like in a job<br /><br /><br />--------------------------------------------------------------------------------<br /><br />what kind og job do you prefer<br /><br /><br />--------------------------------------------------------------------------------<br /><br />why amazon<br /><br /><br />--------------------------------------------------------------------------------<br /><br />why cs<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What is Polymorphism?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />If you are already working why are you still looking?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What's the latest book you've read?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />If there's a glitch in the system and for some reason, for a very brief moment, the website is inaccessible from your browser. You got back to it a few minutes later and the glitch is gone. Would you report this problem?<br /><br /><br />Brain Teasers [more]<br />You have eight balls: seven are the same weight, and one is heavier than the rest. Given a scale that only tells you which side is heavier, how do you find the heavy ball? 9<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Given an array of integers where every int has exactly one duplicate except one,<br />find the number with odd occuring number. 27<br /><br /><br />--------------------------------------------------------------------------------<br /><br />assume your computer is reading characters one by one from a stream (you don't know the length of the stream before ending). Note that you have only one character of storage space (so you cann't save the characters you've read to a something like a strong). When you've finished reading you should return a character out of the stream with equal probability. 11<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Brainteaser: there is a bar with 25 seats in a line. The people there are anti-social so when they walk in the bar, they always try to find a seat farthest away from others. If one person walks in and find there is no seat are adjecent to nobody, that person will walk away. The bar owner wants as many people as possible. The owner can tell the first customer where to sit. all the other customers will pick the farthest possible seat from others. So where should the first customer sit. 9<br /><br /><br />--------------------------------------------------------------------------------<br /><br />If there are a huge array of positive integers, all the integers show up twice except one. Find out that integer. 1<br /><br /><br />Coding [more]<br />Coding: Write code to tokenize a string (had to explain code out loud and then follow-up with the actual code in an email 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Coding: How would you find the nth to last element in a linked list? 27<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Coding: You have an array of ints. How would you find the two elements that sum to a particular value? 18<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Coding: Implement a binary search in a sorted array 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Coding: How would you reverse the words in a string? (ie, "the quick brown fox" --> "fox brown quick the" 41<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design a graph class. Write the C++ interface for it. 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Write a function to smooth out stock fluctuations. Asked me to layout the mathematical idea for curve smoothing before writing code. 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Write a function to find the no of set bits of an integer. Optimise. Ended up giving two solutions . Could not implement the third one. 10<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Given two sets, Write a function to provide the union of them. STL not allowed to be used.<br />Optimise for Time and space. 24<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Given a binary tree, write code to check whether it is a binary search tree or not 9<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Do you have unix experience? Have you heard of WC (word count). Code it in c/c++. You can use STL.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Find missing element in an array of 100 elements. 16<br /><br /><br />--------------------------------------------------------------------------------<br /><br />write push and pop for stack 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design an algorithm and write code to find nth node from the end in a linked list 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design an algorithm and write code to shuffle a standard deck of cards 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design an algorithm and write code to serialize a binary tree. Discuss various solutions 18<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design an algorithm and write code to find two numbers in an array whose sum equals a given value 19<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Print BST level by level 7<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Find Nth last element in a linked list 4<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Given 2 files, each with names of thousands of customers who bought something from Amazon.com on that particular day. Find the common customers (i.e. common names in file1 and file2) 9<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Check if binary representation of an int is a palindrome or not. 21<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Write in java a method to parse an integer from a string 2<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Count characters in a string, wanted to see a hashtable used. 5<br /><br /><br />--------------------------------------------------------------------------------<br /><br />count bits in an integer. Solved using mask, did not attempt -1 approach. 6<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Reverse a linked list 10<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Given two binary trees, find whether or not they are similar. 12<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Determine is a graph is circular. 6<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Algorithm: You have a tree (not Binary) and you want to print the values of all the nodes in this tree level by level. Discussed on phone and asked me to email Java code for my algorithm. 4<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Given two log files, each with a billion usernames (each username appended to the log file), find the usernames existing in both documents in the most efficient manner? Use pseudo-code or code. If your code calls pre-existing library functions, create each library function from scratch. 8<br /><br /><br />--------------------------------------------------------------------------------<br /><br />2nd phone interview: reverse linklist(so stupid, I was too focus on the rule using the exist library much better than build something new(Effctive Java) and when the intervier insisted on asking me to give the non extra memory consuming answer, I was stucked for a while then I told her to move on the next topic. Find the duplicate number from an array. I gave the hash solving method.but I also gave her other answers.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Write code to reverse vowels of string 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Here is a tree. It's a binary tree but in no particular order. How do you write this tree to a file so that it can be reread in an reconstructed exactly as shown? 33<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Multiply a number by 7 without the * operator. 7<br /><br /><br />--------------------------------------------------------------------------------<br /><br />I want to see if all the ones in a number appear on the right side of the number and all zeros appear on the left, how can I do this most efficiently? (i.e. 00000111 is true but 100010 is false) 7<br /><br /><br />--------------------------------------------------------------------------------<br /><br />no.of 1 bits in a number ---program 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />find dup number for n+1 numbers from 1...n 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Phone Screen 2: Check whether the bit representation of integer is a palindrome<br />Multithreading and operating system stuff 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Given two dates, Design an algorithm to return whether the dates are exactly a month apart, less than a month apart or more than a month apart. 2<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Print out a multiplication table, i wasnt told what kind of data structure it is, just that it has 1*1=1, 1*2=2, ...... 200*200=40000, ..... values. 2<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Given a deck of nCards unique cards, cut the deck iCut cards from top and perform a perfect shuffle. A perfect shuffle begins by putting down the bottom card from the top portion of the deck followed by the bottom card from the bottom portion of the deck followed by the next card from the top portion, etc., alternating cards until one portion is used up. The remaining cards go on top. The problem is to find the number of perfect shuffles required to return the deck to its original order. Your function should be declared as:<br /><br />static long shuffles(int nCards,int iCut); 4<br /><br /><br />--------------------------------------------------------------------------------<br /><br />The hardest question to date on a phone interview. he asked me to take 2 hours and write the following API.<br /><br />Create an LRU Cache that caches some key/value pair and kicks out the Least Recently Used when you run out of space. Wanted run times and asked me to comment on how good my implementation is and whether its good for industry level usage.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Asked me to reverse a Linked list without re-creating a new one. I did it recursively going all the way to end and linking it backwards after the recursive call. Had to pass in two nodes though, one previous and one current. He said he likes iteration better becoz its more resource friendly :)<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Write a method to shufle the deck. The constraint is it has to be a perfect shuffle - in other words, every 52! permutations of the deck has to be equally like (given a completely random function which is theoretical of course).<br /><br />I managed to do this with a simple for loop in O(n) time<br /><br /><br />int[] deck = new int[52];<br />for(int i=0; i<52; i++)<br />deck[i] = i;<br /><br />Random r = new Random();<br />for(int i=0; i<br />int ran = r.nextInt(deck.length-i) + i;<br />int temp = deck[i];<br />deck[i] = deck[ran];<br />deck[ran] = temp;<br />}<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design a data structure for storing sparse arrays. Implement multiplications of such arrays. 2<br /><br /><br />--------------------------------------------------------------------------------<br /><br />reverse linked list. Why don't you use recursion? 5<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Homework: Reverse all the words in a string.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Algorithm and code to detect occurence of a string(patterns) in another string ex: aab, aababa 5<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Asked to code the 'floodFill' method used by graphic products like Paint. 2<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design the classes for Tic Tac Toe. Implement make next move method for the computer player and make sure that the computer wouldn't lose.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design the game Othello. Write the code to check whether someone has won the game.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Implement class Stack using a linked list.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />void removeChars(char *str, char *delete). Remove characters in str that is in delete. 2<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Find nth to the last node in a single linked list.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Write a function that would find the one value that occurs an odd number of times in an array. ie; function would return "r" if "ttttjjrll" is passed in. 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />If you are given a number as a parameter, write a function that would put commas after every third digit from the right.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Discuss the code of pre-order traversal of a tree.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Write code to find n-th to last node in a linked list<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Write code to delete a node in circular linked list<br /><br /><br />--------------------------------------------------------------------------------<br /><br />A phone screen. Write a atoi function for decimal. Expected me to "tell" the code right<br />from "declare a variable i of type int" to the actual logic. Once this was done generalize it do the atoi for any radix.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />How do you determine the size of an object in Java?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Implement the unix command WordCount (wc) using lenguage of your choice. The method takes a string and returns the number of words in the string, number of chars and the number of lines.<br /><br /><br />Computer Architecture & Low Level [more]<br />When would a program crash in a buffer overrun case. Gave me,<br />buff[50];<br />for( int i=0; i <100; i++ )<br />buff[i] = 0;<br /><br />What will happen to first 50 bytes assigned, when would the program crash 5<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What is buffer overflow and how do you exploit it? 1<br /><br /><br />Data structure [more]<br />What is the difference between arrays and linked lists? What is the advantage of contiguous memory over linked lists?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Given a file containing approx 10 million words, Design a data structure for finding all the anagrams in that set<br /><br /><br />Database [more]<br />database question like self joint with tables given by him<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Explain how to write a stored procedure in SQL 1<br /><br /><br />Experience [more]<br />What sort of commenting standards do you use 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />From 1 - 10, rate c++, c, java, unix, sql skills<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Most challenging project 2<br /><br /><br />--------------------------------------------------------------------------------<br /><br />How much experience do you have with unix<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Talk about your favourite project? What part of a Software Project do you enjoy most?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Tell me about your work experiences in the past?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />asked some questions based on my previous job<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Lunch - QA manager.<br /><br />1. tell me a situation when u had to face problems and the requirements were not clear. how did u handle the situation?<br /><br />2. which is the best error you have caught?<br /><br />3. which is the worst error u've ever caught?<br /><br />4. asked about a project on my resume<br /><br /><br />--------------------------------------------------------------------------------<br /><br />XML: How have you used XML in your previous projects?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />focus on my last project<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What was your hardest techincal project?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What was the most interesting thing you have ever done (technical or non technical) ?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Mailed me this code and asked to find the mistakes in the code<br /><br />class Base {<br />public:<br />Base(int numElements) {<br />m_baseArray = new int[numElements];<br />}<br />~Base { //non-virtual<br />delete [] m_baseArray;<br />}<br />private:<br />int* m_baseArray;<br />}<br />class Derived : public Base {<br />public:<br />Derived(int numElements) : Base(numElements) {<br />m_derivedArray = new int[numElements];<br />}<br />~Derived() {<br />delete[] m_derivedArray;<br />}<br />private:<br />int* m_derivedArray;<br />}<br />int main(int argc, char** argv) {<br />Base* base = new Derived(3);<br />delete base;<br />return 0;<br />}<br /><br />What is wrong with the code ? 5<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Projects<br /><br /><br />Ideas [more]<br />If you had the entire text to 65 million books in a database, what would you do with it? 9<br /><br /><br />Java [more]<br />What is the difference between Inheritance and Interfaces? Under what conditions would you prefer one over the other? 2<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What is Garbage Collection in Java. How is it implemented? What kind of algorithms does the garbage collector use? How does it know that references can be collected? What are advantages and disadvantages of garbage collection?<br /><br /><br />Math & Computation [more]<br />You have a basket ball hoop and someone says that you can play 1 of 2 games. You get $1000 and one shot to get the hoop. Or, you get three shots and you have to make 2 of 3 shots. Which one do you choose? If p is the probability of making a particular shot, what value of p makes you switch games? 16<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Some question about random sampling and buffer read. Don't remember exactly. Had to do with calculating the probabilty and stuff.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />When i wasn't certain whether my random function generated with equal probability all permutations, the interviewer asked me to write a formal proof that it works or not and send it to him (really strange).<br /><br />Proved it with the following and he bought it:<br />Probabilisticly<br />card 1 has 52 positions it can fit in<br />card 2 has 51<br />card 3 has 50<br />so on and so forth<br />card 52 has 1 position to fit in<br /><br />hence its 52 x 51 x 50 x ... x 1 = 52! can be generated using this shuffle.<br /><br />Oblivious to me, aparantly this kind of shuffle is used a lot in online card games. Silly me :P<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Brainteaser: there is a bar with 25 seats in a line. The people there are anti-social so when they walk in the bar, they always try to find a seat farthest away from others. If one person walks in and find there is no seat are adjecent to nobody, that person will walk away. The bar owner wants as many people as possible. The owner can tell the first customer where to sit. all the other customers will pick the farthest possible seat from others. So where should the first customer sit. 9<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Write a program which makes the probablity of getting the even number when a dice is thrown in 72%( some number other than 50%).<br /><br /><br />Multiple Questions in One [more]<br />Phone Screen 1: Serialize and deserialize a binary tree/graph<br />General Unix questions<br />C++ questions<br />Design classes to represent a deck of cards<br /><br /><br />Object Oriented Design [more]<br />Design the classes and objects for a generic deck of cards that would be used in a poker game 4<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Describe the classes and data structures you would use for a file system 23<br /><br /><br />--------------------------------------------------------------------------------<br /><br />How would you implement a map (not a map of like a city... just a set of keys which "map" to values")<br />- Give two data structures you could use<br />- What is average and worst case insert time, delete time, look up time<br />- What are pros/cons of each 7<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design a graph class. Write the C++ interface for it. 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />QA engineer -<br /><br />1. say you have a calculator service running on a server. Automate the process of testing it. i.e. by one click of a buttonu should be able to test it.<br /><br />2. how would you do the same if you did not have access to the input and expected output. for example. no excel sheet that has the expected values. generate the 2 inputs on the fly. now how would you automate the testing.<br /><br />3. discuss data structures for NOTEPAD. discuss with reference to bufferer write.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Given two log files, each with a billion usernames (each username appended to the log file), find the usernames existing in both documents in the most efficient manner? Use pseudo-code or code. If your code calls pre-existing library functions, create each library function from scratch. 8<br /><br /><br />--------------------------------------------------------------------------------<br /><br />The bigger the ratio between the size of the hash table and the number of data elements, the less chance there is for collision. What is a drawback to making the hash table big enough so the chances of collision is ignorable? 2<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Here is a graph of distribution centers and the weight to go from one to another. How would you represent this using a data structure? Code an alogrithm that allows me to check if there is a path from one node to another and what the weight of this path is. 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Imagine you're implementing the game of chess. Design the classes, objects and heirachies behind it.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design a deck of cards<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design the data structures and algorithms for a LRU (Least Recently Used) Cache 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design a Deck of Cards 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Asked me to take some time around 1 hour and create an API that could read names,emp ID's,phone numbers, office names in that order from a file and stores them and has the following functionality:<br /><br />1) getEmployeeById<br />2) getEmployeeByName<br />3) getEmployeesByName<br />4) editEmployeeInfoById<br />5) editEmployeeInfoByName<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design a data structure for storing sparse arrays. Implement multiplications of such arrays. 2<br /><br /><br />--------------------------------------------------------------------------------<br /><br />reverse linked list. Why don't you use recursion? 5<br /><br /><br />--------------------------------------------------------------------------------<br /><br />OO design related question? How would you design a class structure for animals in a zoo<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design the classes for Tic Tac Toe. Implement make next move method for the computer player and make sure that the computer wouldn't lose.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design the game Othello. Write the code to check whether someone has won the game.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Design the classes and data structures for a parking lot<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Look within the book. Each person can look at 20% of the book at a time. Only 70% of the book can be served to all users. Design the data structures for this. 4<br /><br /><br />--------------------------------------------------------------------------------<br /><br />How would you do a design of a monopoly game (later changed to a chess game)?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />How would you design a file system using class diagrams and what data structure would you use?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Discuss the important features of Object Oriented Programming<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Model a chess game<br /><br /><br />System Design [more]<br />Imagine that there are 7 servers running in parallel. What happens when you need to expand to 20 live? What are issues? What could you do to fix this issue in the future? 6<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Algorithm: You have 50,000 html files, some of which contain phone numbers. How would you create a list of all the files which contain phone numbers? 14<br /><br /><br />--------------------------------------------------------------------------------<br /><br />You have a website which has 5 reads on a database when it is loaded. Each read takes 7 seconds for a total of 35 seconds, discuss how you could improve the performance? 5<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Say you have a system. The design is good. But performance is not good. How would you find where the problem is? went on for about half an hour about it. 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />the "logging in" feature of amazon.com has a problem. isolate the problem.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />App server+DB server, solve the querying delay problem...<br /><br /><br />--------------------------------------------------------------------------------<br /><br />How would you design the software that runs on an ATM machine? The software should support operations such as checking balance, transfer funds from one account to another, deposits and withdrawals.<br /><br /><br />Terminology & Trivia [more]<br />Difference between class and object 16<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What's the max look up time for a binary tree 21<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What's the point of inheritance? 4<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What's the max insertion time for a hash table 8<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Why would you use an array vs linked-list 14<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What is a Pure Function? 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What is a linked list? What are its advantages over arrays? 7<br /><br /><br />--------------------------------------------------------------------------------<br /><br />exception handling, C++ basics, bitwise operations<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What is an array? What is a Linked List, Map.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Complexity of insertion and deletion for linked list.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Unix: You want to kill a process that has been running for a long time, how to do that? 2<br /><br /><br />--------------------------------------------------------------------------------<br /><br />XML: Differentiate between SAX and DOM. 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Data Structures: Time complexities for HashTable, Linked List, Binary Search, Array. 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Java: Differentiate between final, finally and finalize<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Java: How does the synchronized keyword work? What happens when you use it on a static method?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Java: Talk to me about the Java Collections API<br /><br /><br />--------------------------------------------------------------------------------<br /><br />MultiThread, Garbage Collection. Tomcat distribute request(Java Spaces), http protocal. Socket programming...<br /><br /><br />--------------------------------------------------------------------------------<br /><br />to find a telephone number in dir and subdir (find command is the answer)<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What is Polymorphism, how do virtual functions work<br /><br /><br />--------------------------------------------------------------------------------<br /><br />When would a program crash in a buffer overrun case. Gave me,<br />buff[50];<br />for( int i=0; i <100; i++ )<br />buff[i] = 0;<br /><br />What will happen to first 50 bytes assigned, when would the program crash 5<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Asked me to describe the difference between final, finally and finalize in java. (The last one is tricky coz we rarely use it) 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Define "class" and "object."<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What does the keyword "final" do when put in front of a Collection in Java? 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Asked me the differnce between using Abstract class vs interface on a real world problem im working on (at one point he settled for an answer where is said "it's just intuitively wrong" - however, he tried to trick me into justifying using the wrong thing, I had to say that there is no justification for using this technique here, took a little bit of guts but he liked it)<br /><br /><br />--------------------------------------------------------------------------------<br /><br />array vs list<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Java. final, finalize, finally<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What are thread, why are they used in programming?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Difference between polmorphism and inheritance?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Difference between class and object?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Questions about C++/Java and Design Patterns.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />When would you create an interface class. 2<br /><br /><br />--------------------------------------------------------------------------------<br /><br />How would a copy constructor behave if the class had an Object as a member Variable?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Explain the relationship between Equals and Hashcode in Java. 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What is a tree? How do you traverse a tree? 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What's the difference between virtual methods in C++ and Java? 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What's the difference between == and Equals()?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What is Perfect/Universal hashing?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What are the advantages and disadvantages of function lining?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />How do you determine the size of an object in Java?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />What is Context Free Grammar? What is it used for?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />When does the Operating Systems do a Context Switch? 1<br /><br /><br />Testing [more]<br />3. What is black box testing?<br />4. What do you include in a test plan? 1<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Say you have a system. The design is good. But performance is not good. How would you find where the problem is? went on for about half an hour about it. 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Suppose there is a problem with the address change feature on Amazon.com. How would you test it? What data sets would you test it against? How would you decide on such a data set?<br /><br /><br />--------------------------------------------------------------------------------<br /><br />say u are in charge of the "login" fature of amazon.com. TEST IT.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />the "logging in" feature of amazon.com has a problem. isolate the problem.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />QA engineer -<br /><br />1. say you have a calculator service running on a server. Automate the process of testing it. i.e. by one click of a buttonu should be able to test it.<br /><br />2. how would you do the same if you did not have access to the input and expected output. for example. no excel sheet that has the expected values. generate the 2 inputs on the fly. now how would you automate the testing.<br /><br />3. discuss data structures for NOTEPAD. discuss with reference to bufferer write.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />say i give you a universal vegetable cutter which claims that it can cut any kind of vegetable. TEST IT.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />How would you test an ATM in a distributed banking system.<br /><br /><br />--------------------------------------------------------------------------------<br /><br />How would you load test a web page without using any test tools 3<br /><br /><br />--------------------------------------------------------------------------------<br /><br />Suppose there is a problem with calculation of taxes on the amazon.com website. How would you isolate the problem. Once isolated and fixed, how would you go ahead and test it?Unknownnoreply@blogger.com184tag:blogger.com,1999:blog-6467304392957302705.post-84532087715866166952009-04-20T22:51:00.000-07:002009-04-20T22:51:13.418-07:00Deepak Dhakal's Blog: Parameter Sniffing and Reporting service through Visual studio<a href="http://ddhakal.blogspot.com/2009/04/parameter-sniffing-and-reporting.html#links">Deepak Dhakal's Blog: Parameter Sniffing and Reporting service through Visual studio</a>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-6467304392957302705.post-38524321792448898852009-04-20T22:34:00.001-07:002009-04-20T22:47:31.715-07:00Parameter Sniffing and Reporting service through Visual studioToday I had a very bad day. My friend left me a job that he estimated for 2 hours and Now I need to finish that ..There is no chance that i can write multiple pages sql Stored procedures /query and create report in 2 hours .. It is going to take me at least 15 hours for everything .. <br /><br />Ok that is not the point .. the point .. I spent 5 hours to write all the query .. tested in Sql query manager and ran great ... Thought I was really good .. created a report layout .. added few dataset and ran the report using VS 2005 IDE .. Now the drama begins .. It took 5-10 mins to render report by VS 2005.<br /><br />I went to sql server machine.. checked for task manager .. CPU uses was more than 50% for that 10 mins time .WOW .. When I ran the same query in query manager .. it took less than 5 seconds .. <br /><br />I was upset .. restarted VS .. restarted computer .. nothing happened .. recompiled code .. redeployed .. Nothing ..Nothing at all..<br /><br /><br /><br />I googled about it .. I am not only one..<br /><br />If u have same problem .. Google about "Parameter Sniffing " ..U will see many article about it .. <br /><br />In short the solution was:<br /><br />Suppose I have :<br /><br />create proc newProc<br />{<br />@name varchar(200)<br />}<br /><br />as<br /><br />select name from nametable where name=@name .. <br /><br />go<br /><br />everytime u call it from outside with even NULL value or some value not equal to varchar(200) SQl server tried to create a brand new execution plan ..and it takes forever to run the script if u have pretty complex sql..<br /><br /><br />Sol<br /><br />Very simple .<br /><br />create proc newProc<br />{<br />@name varchar(200)<br />}<br /><br /><span style="font-weight:bold;">@declare @newName varchar(200)<br />set @newname=@name</span><br />as<br /><br /><br />select name from nametable where name=<span style="font-weight:bold;">@newname .. <br /></span><br />go<br /><br />done !!<br /><br />SQL just ignores to create execution plan and runs the last used plan .. <br /><br /><br />Ok ..so lesson of today: There are lot of thing u dont know about which is realy importantUnknownnoreply@blogger.com1tag:blogger.com,1999:blog-6467304392957302705.post-28068017187485907382008-11-14T08:50:00.001-08:002008-11-16T09:27:00.696-08:00Inheritance in CSSCSS Inheritance<br /><br />An explanation of how inheritance works in CSS and why CSS doesn't need Object Oriented style inheritance.<br />Introduction<br /><br />Many newcomers to CSS are confused by inheritance; this is often because they come from a background in object oriented (OOP) programming and expect CSS to work in a similar way.<br /><br />This document attempts to explain CSS inheritance and present alternatives to OO-style inheritance to demonstrate why it is not necessary.<br />CSS Inheritance<br /><br />CSS inheritance works on a property by property basis. When applied to an element in a document, a property with the value 'inherit' will use the same value as the parent element has for that property.<br /><br />For example, given this style sheet:<br /><br />`.foo {<br /> background-color: white;<br /> color: black;<br />}<br /><br />`.bar {<br /> background-color: inherit;<br /> color: inherit;<br /> font-weight: normal;<br />}<br /><br />And this HTML fragment:<br /><br />div class="foo"><br /> <p class="bar"><br /> Hello, world. This is a very short<br /> paragraph!<br /> </p><br />`div><br /><br />The background colour of the div element is white, because the background-color property is set to white. The background colour of the paragraph is also white, because the background colour property is set to inherit, and the background colour of the parent element (the div) is set to white.<br /><br />The inherit value does not require that the parent element have the same property set explicitly; it works from the computed value. In the above example, the color property of the paragraph has a value of "inherit", but the computed value is "black" because it inherits.<br /><br />This might seem like a lot of typing, but the default value for many properties is already inherit, and for most others (border for instance) you wouldn't usually want to inherit the parent element's value.<br /><br />While on that line of thought, I'll point out that not all properties can be inherited.<br />Object Oriented inheritance<br /><br />Many people ask on mailing lists and in newsgroups about CSS if it is possible to do something such as:<br /><br />`.foo {<br /> background-color: white;<br /> color: black;<br />}<br /><br />`.bar {<br /> Some reference to the above style for .foo<br /> font-weight: normal;<br />}<br /><br />It isn't. A selector is just a selector, there is nothing special about classes. Things would get rather complex if you had .foo > .bar as the selector for a style you wanted to import, or multiple identical selectors.<br /><br />I won't go into how CSS could be changed to allow such functionality, not only would there be a lack of support among today's generation of browsers (which are likely to be with us for a long time to come), but it isn't needed. CSS already gives us the tools we need.<br /><br />There are several approaches we could take.<br />Multiple Classes<br /><br />Making good use of classes will solve most problems. Take the example of having boxes of data floating on alternating sides of the canvas.<br /><br />`.oddBoxOut {<br /> width: 12em;<br /> float: left;<br /> padding: 0.5em;<br /> margin: 0.5em;<br /> border: solid 1px black;<br />}<br /><br />`.evenBoxOut {<br /> width: 12em;<br /> float: right;<br /> padding: 0.5em;<br /> margin: 0.5em;<br /> border: solid 1px black;<br />}<br /><br />As you can see, many properties are duplicated in each definition, so it is obvious why somebody might want OO-style inheritance.<br /><br />There is another solution though. Lets take a quick look back at the HTML specification:<br /><br /> ` class = cdata-list[CS]<br /> This attribute assigns a class name or set of class names to an element. Any number of elements may be assigned the same class name or names. Multiple class names must be separated by white space characters. <br /><br />So we can assign multiple class names to a single element? That means we can change the style sheet so it looks like this:<br /><br />`.boxOut {<br /> width: 12em;<br /> padding: 0.5em;<br /> margin: 0.5em;<br /> border: solid 1px black;<br />}<br /><br />`.oddBoxOut {<br /> float: left;<br />}<br /><br />`.evenBoxOut {<br /> float: right;<br />}<br /><br />And then the HTML will look like:<br /><br />`div class="boxOut oddBoxOut">div><br /><br />Grouping Selectors<br /><br />A single style may have multiple selectors assigned to it through the use of grouping.<br /><br />To revisit the previous example, we first simplify the HTML so we only mention the one class:<br /><br />div class="oddBoxOut">div><br /><br />Then we assign the CSS we want to it, but we group the common property/value pairs.<br /><br />`.oddBoxOut, <br />`.evenBoxOut {<br /> width: 12em;<br /> padding: 0.5em;<br /> margin: 0.5em;<br /> border: solid 1px black;<br />}<br /><br />`.oddBoxOut {<br /> float: left;<br />}<br /><br />`.evenBoxOut {<br /> float: right;<br />}<br /><br />These two techniques should solve most problems which people think can be solved with OO-style inheritanceUnknownnoreply@blogger.com0tag:blogger.com,1999:blog-6467304392957302705.post-55004484328160164842008-07-18T12:21:00.000-07:002008-07-18T12:23:21.962-07:00Algorithm Interview questions Answers ( Microsoft, Google and Amazon )<span style="font-weight:bold;">1. Reverse a singly linked list</span><br /><br /><br />//<br />// iterative version<br />//<br />Node* ReverseList( Node ** List ) <br />{<br /><br /> Node *temp1 = *List;<br /> Node * temp2 = NULL;<br /> Node * temp3 = NULL;<br /><br /> while ( temp1 )<br /> {<br /> *List = temp1; //set the head to last node <br />temp2= temp1->pNext; // save the next ptr in temp2<br /> temp1->pNext = temp3; // change next to privous<br /> temp3 = temp1;<br /> temp1 = temp2;<br /> }<br /> <br /> return *List;<br />}<br /><br /><br /><span style="font-weight:bold;">2. Delete a node in double linked list</span><br /><br /><br />void deleteNode(node *n)<br />{<br />node *np = n->prev;<br />node *nn = n->next;<br />np->next = n->next;<br />nn->prev = n->prev;<br />delete n;<br />}<br /> <br /><span style="font-weight:bold;"><br />3. Sort a linked list</span><br /><br />//sorting in descending order<br />struct node<br />{<br />int value;<br />node* NEXT;<br />}<br />//Assume HEAD pointer denotes the first element in the //linked list<br />// only change the values…don’t have to change the //pointers<br /><br />Sort( Node *Head)<br />{<br />node* first,second,temp;<br />first= Head;<br />while(first!=null)<br />{<br />second=first->NEXT;<br />while(second!=null)<br />{<br />if(first->value < second->value)<br />{<br />temp = new node();<br />temp->value=first->value;<br />first->value=second->value;<br />second->value=temp->value;<br />delete temp;<br />}<br />second=second->NEXT;<br />}<br /><br />first=first->NEXT;<br />}<br />}<br /> <br /><br /><span style="font-weight:bold;">4. Reverse a string</span><br /><br />void ReverseString (char *String)<br />{<br />char *Begin = String;<br />char *End = String + strlen(String) - 1;<br />char TempChar = '\0';<br /><br />while (Begin < End) <br />{<br />TempChar = *Begin;<br />*Begin = *End;<br />*End = TempChar;<br />Begin++;<br />End--;<br />}<br />}<br /> <br /><br /><span style="font-weight:bold;">5. Insert a node a sorted linked list</span><br /><br />void sortedInsert(Node * head, Node* newNode)<br />{<br />Node *current = head;<br /> <br />// traverse the list until you find item bigger the // new node value<br /> // <br />while (current!= NULL && current->data < newNode->data)<br />{<br />current = current->next);<br />}<br />//<br />// insert the new node before the big item<br />//<br />newNode->next = current->next;<br />current = newNode;<br />} <br /><br /><br /><br /><span style="font-weight:bold;">6. Covert a string to upper case</span><br /><br />void ToUpper(char * S)<br />{<br />while (*S!=0)<br />{<br />*S=(*S >= 'a' && *S <= 'z')?(*S-'a'+'A'):*S;<br />S++;<br />}<br />} <br /><br /><br /><span style="font-weight:bold;">7. Multiple a number by 7 without using * and + operator.</span><br /><br /> NewNum = Num << 3; // mulitplied by 2 ^ 3 = 8<br /><br /> NewNum = NewNum - Num; // 8 – 1 = 7<br /> <br /><span style="font-weight:bold;"><br />8. Write a function that takes in a string parameter and checks to see whether or not it is an integer, and if it is then return the integer value.</span><br /><br />#include <stdio.h><br /><br />int strtoint(char *s)<br />{<br />int index = 0, flag = 0;<br /><br />while( *(s+index) != '\0')<br />{<br />if( (*(s + index) >= '0') && <br />*(s + index) <= '9')<br />{<br />flag = 1;<br />index++;<br />}<br />else<br />{<br />flag = 0;<br />break;<br />}<br />}<br /><br />if( flag == 1 )<br />return atoi(s);<br />else<br />return 0;<br />}<br /><br />main() <br />{ <br />printf("%d",strtoint("0123")); <br />printf("\n%d",strtoint("0123ii")); <br />}<br /><br /> <br /><br /><span style="font-weight:bold;">9. Print a data from a binary tree – In-order(ascending)</span><br /><br />//<br />// recursive version<br />//<br /><br />Void PrintTree ( struct * node node )<br />{<br /> if ( node == NULL )<br /> return;<br /><br /> PrintTree(node->left );<br /> Printf(“%d”, node->data);<br /> PrintTree(node->right );<br />}<br /> <br /><span style="font-weight:bold;">10. print integer using only putchar</span><br /><br />//<br />// recursive version<br />//<br />void PrintNum ( int Num )<br />{<br /> if ( Num == 0 )<br /> return;<br /> PrintNum ( Num / 10 );<br /> Puthcar ( ‘0’+ Num % 10 );<br />} <br /><br /><span style="font-weight:bold;">11. Find the factorial of number</span><br /><br /> //<br /> // recursive version<br /> //<br /><br /> int Factorial( int Num )<br /> {<br /><br /> If ( num > 0 )<br /> return Num * Factorial ( Num –1 ); <br />else<br /> return 1;<br />}<br /><br /><br />//<br />// iterative version<br />//<br /><br /> int Factorial( int Num )<br /> {<br /> int I<br /> int result = 1;<br /> <br />for ( I= Num; I > 0; I-- )<br />{<br /> result = result * I;<br />}<br /><br />return result;<br />}<br /> <br /><br /><span style="font-weight:bold;">12. Generate Fib numbers:</span><br /><br />int fib( n ) // recursive version<br />{<br /> <br /> if ( n < 2 )<br /> return 1;<br /> else<br /> return fib ( n –1 ) + fib ( n –2 );<br /><br />}<br /><br />int fib( n ) //iterative version<br />{<br /> int f1 =1, f2 = 1;<br /><br /> if ( n < 2 )<br /> return 1; <br /> for ( i = 1; i < N; i++)<br /> {<br /> f = f1 + f2;<br /> f1= f2;<br /> f = f1;<br /> }<br /><br /> return f;<br />}<br /><br /><br /><br /><br /><br /><br /><br /><span style="font-weight:bold;">13. Write a function that finds the last instance of a character in a string</span><br /><br />char *lastchar(char *String, char ch)<br />{<br />char *pStr = NULL;<br /><br /> // traverse the entire string<br /> <br />while( * String ++ != NULL ) <br />{<br />if( *String == ch ) <br />pStr = String;<br />}<br /> <br />return pStr;<br />} <br /><br /><span style="font-weight:bold;">14. Return Nth the node from the end of the linked list in one pass.</span><br /><br />Node * GetNthNode ( Node* Head , int NthNode )<br />{<br /> Node * pNthNode = NULL;<br /> Node * pTempNode = NULL;<br /> int nCurrentElement = 0;<br /> <br />for ( pTempNode = Head; pTempNode != NULL; pTempNode = pTempNode->pNext )<br /> {<br /> nCurrentElement++; <br /> if ( nCurrentElement - NthNode == 0 )<br /> {<br /> pNthNode = Head;<br /> }<br /> else<br /> if ( nCurrentElement - NthNode > 0)<br /> {<br /> pNthNode = pNthNode ->pNext;<br /> } <br /> }<br /> if (pNthNode )<br /> {<br /> return pNthNode;<br /> }<br /> else<br /> return NULL;<br />}<br /><br /><br /><br /><span style="font-weight:bold;">15. Counting set bits in a number.</span><br /><br />First version:<br /><br />int CoutSetBits(int Num)<br />{<br /><br />for(int count=0; Num; Num >>= 1)<br />{<br /> if (Num & 1) <br />count++;<br />}<br />return count;<br /> }<br /><br /><br />Optimized version:<br /><br />int CoutSetBits(int Num)<br />{<br /><br />for(int count =0; Num; count++)<br />{<br /> Num &= Num -1;<br /> }<br />}Unknownnoreply@blogger.com76tag:blogger.com,1999:blog-6467304392957302705.post-27866228435295909262008-07-18T08:45:00.000-07:002008-07-18T08:46:38.620-07:00C++ Microsoft and Amazon interview Questions<div class="post-header-line-1"></div><br /><div class="post-body entry-content"><br /><p><span style="font-weight: bold;">What is encapsulation??</span><br>Containing and hiding information about an object, such as internal data structures and code. Encapsulation isolates the internal complexity of an object's operation from the rest of the application. For example, a client component asking for net revenue from a business object need not know the data's origin.<br><br><span style="font-weight: bold;">What is inheritance?</span><br>Inheritance allows one class to reuse the state and behavior of another class. The derived class inherits the properties and method implementations of the base class and extends it by overriding methods and adding additional properties and methods.<br><span style="font-weight: bold;">What is Polymorphism??<br><br></span>Polymorphism allows a client to treat different objects in the same way even if they were created from different classes and exhibit different behaviors.<br>You can use implementation inheritance to achieve polymorphism in languages such as C++ and Java.<br>Base class object's pointer can invoke methods in derived class objects.<br>You can also achieve polymorphism in C++ by function overloading and operator overloading.<br><br><span style="font-weight: bold;">What is constructor or ctor?<br></span>Constructor creates an object and initializes it. It also creates vtable for virtual functions. It is different from other methods in a class.<br><br><span style="font-weight: bold;">What is destructor?</span><br>Destructor usually deletes any extra resources allocated by the object.<br><br><span style="font-weight: bold;">What is default constructor?</span><br>Constructor with no arguments or all the arguments has default values.<br><br><span style="font-weight: bold;">What is copy constructor?</span><br>Constructor which initializes the it's object member variables ( by shallow copying) with another object of the same class. If you don't implement one in your class then compiler implements one for you.<br>for example:<br>Boo Obj1(10); // calling Boo constructor<br>Boo Obj2(Obj1); // calling boo copy constructor<br>Boo Obj2 = Obj1;// calling boo copy constructor<br><br><span style="font-weight: bold;">When are copy constructors called? </span><br>Copy constructors are called in following cases:<br>a) when a function returns an object of that class by value<br>b) when the object of that class is passed by value as an argument to a function<br>c) when you construct an object based on another object of the same class<br>d) When compiler generates a temporary object<br><br><span style="font-weight: bold;">What is assignment operator? </span><br>Default assignment operator handles assigning one object to another of the same class. Member to member copy (shallow copy)<br>What are all the implicit member functions of the class? Or what are all the functions which compiler implements for us if we don't define one.??<br>default ctor<br>copy ctor<br>assignment operator<br>default destructor<br>address operator<br><br><span style="font-weight: bold;">What is conversion constructor?</span><br>constructor with a single argument makes that constructor as conversion ctor and it can be used for type conversion.<br>for example:<br>class Boo<br>{<br>public:<br>Boo( int i );<br>};<br>Boo BooObject = 10 ; // assigning int 10 Boo object<br>What is conversion operator??<br>class can have a public method for specific data type conversions.<br>for example:<br>class Boo<br>{<br>double value;<br>public:<br>Boo(int i )<br>operator double()<br>{<br>return value;<br>}<br>};<br>Boo BooObject;<br>double i = BooObject; // assigning object to variable i of type double. now conversion operator gets called to assign the value.<br><br></p><p><span style="font-size: 100%;"><b>What is diff between malloc()/free() and new/delete?</b></span></p> <p>malloc allocates memory for object in heap but doesn't invoke object's constructor to initiallize the object.</p> <p>new allocates memory and also invokes constructor to initialize the object.</p> <p>malloc() and free() do not support object semantics<br>Does not construct and destruct objects<br>string * ptr = (string *)(malloc (sizeof(string)))<br>Are not safe<br>Does not calculate the size of the objects that it construct<br>Returns a pointer to void<br>int *p = (int *) (malloc(sizeof(int)));<br>int *p = new int;<br>Are not extensible<br>new and delete can be overloaded in a class </p> <p>"delete" first calls the object's termination routine (i.e. its destructor) and then releases the space the object occupied on the heap memory. If an array of objects was created using new, then delete must be told that it is dealing with an array by preceding the name with an empty []:- </p> <p>Int_t *my_ints = new Int_t[10];</p> <p>...</p> <p>delete []my_ints;</p> <p><b>what is the diff between "new" and "operator new" ?</b> </p> <p style="margin-bottom: 12pt;"><br>"operator new" works like malloc.</p> <p><b>What is difference between template and macro??</b></p> <p>There is no way for the compiler to verify that the macro parameters are of compatible types. The macro is expanded without any special type checking.</p> <p>If macro parameter has a postincremented variable ( like c++ ), the increment is performed two times.</p> <p>Because macros are expanded by the preprocessor, compiler error messages will refer to the expanded macro, rather than the macro definition itself. Also, the macro will show up in expanded form during debugging. </p> <p>for example:</p> <p>Macro:</p> <p>#define min(i, j) (i <> </p><p style="margin-bottom: 12pt;">template:<br>template<class><br>T min (T i, T j)<br>{<br>return i <><br><!--[endif]--></class></p> <p><b>What are C++ storage classes?</b></p> <p>auto<br>register<br>static<br>extern</p> <p><b>auto:</b> the default. Variables are automatically created and initialized when they are defined and are destroyed at the end of the block containing their definition. They are not visible outside that block</p> <p><b>register:</b> a type of auto variable. a suggestion to the compiler to use a CPU register for performance</p> <p><b>static:</b> a variable that is known only in the function that contains its definition but is never destroyed and retains its value between calls to that function. It exists from the time the program begins execution</p> <p style="margin-bottom: 12pt;"><b>extern:</b> a static variable whose definition and placement is determined when all object and library modules are combined (linked) to form the executable code file. It can be visible outside the file where it is defined.</p><br><p><b>What are storage qualifiers in C++ ?</b></p> <p>They are..</p> <p>const<br>volatile<br>mutable</p> <p><b>Const </b>keyword indicates that memory once initialized, should not be altered by a program.</p> <p><b>volatile </b>keyword indicates that the value in the memory location can be altered even though nothing in the program<br>code modifies the contents. for example if you have a pointer to hardware location that contains the time, where hardware changes the value of this pointer variable and not the program. The intent of this keyword to improve the optimization ability of the compiler. </p> <p><b>mutable</b> keyword indicates that particular member of a structure or class can be altered even if a particular structure variable, class, or class member function is constant.</p> <p>struct data<br>{<br>char name[80];<br>mutable double salary;<br>}</p> <p>const data MyStruct = { "Satish Shetty", 1000 }; //initlized by complier</p> <p style="margin-bottom: 12pt;">strcpy ( MyStruct.name, "Shilpa Shetty"); // compiler error<br>MyStruct.salaray = 2000 ; // complier is happy allowed</p> <p><b>What is reference ??</b></p> <p>reference is a name that acts as an alias, or alternative name, for a previously defined variable or an object.</p> <p>prepending variable with "&" symbol makes it as reference.</p> <p>for example: </p> <p>int a;<br>int &b = a;<br></p> <p><b>What is passing by reference?</b></p> <p>Method of passing arguments to a function which takes parameter of type reference.</p> <p>for example:</p> <p>void swap( int & x, int &amp;amp;amp;amp; y )<br>{<br>int temp = x;<br>x = y;<br>y = temp;<br>}</p> <p>int a=2, b=3;</p> <p>swap( a, b );</p> <p style="margin-bottom: 12pt;">Basically, inside the function there won't be any copy of the arguments "x" and "y" instead they refer to original variables a and b. so no extra memory needed to pass arguments and it is more efficient.<br></p> <p><b>When do use "const" reference arguments in function?</b></p> <p style="margin-bottom: 12pt;">a) Using const protects you against programming errors that inadvertently alter data.<br>b) Using const allows function to process both const and non-const actual arguments, while a function without const in the prototype can only accept non constant arguments.<br>c) Using a const reference allows the function to generate and use a temporary variable appropriately.<br></p> <p><b>When are temporary variables created by C++ compiler?</b></p> <p>Provided that function parameter is a "const reference", compiler generates temporary variable in following 2 ways. </p> <p>a) The actual argument is the correct type, but it isn't Lvalue</p> <p>double Cube(const double & num)<br>{<br>num = num * num * num;<br>return num;</p> <p>}</p> <p>double temp = 2.0;<br>double value = cube(3.0 + temp); // argument is a expression and not a Lvalue;</p> <p>b) The actual argument is of the wrong type, but of a type that can be converted to the correct type</p> <span style="">long temp = 3L;<br>double value = cuberoot ( temp); // long to double conversion<br><br></span><p><b>What is virtual function?</b></p> <p>When derived class overrides the base class method by redefining the same function, then if client wants to access redefined the method from derived class through a pointer from base class object, then you must define this function in base class as virtual function.</p> <p>class parent<br>{<br> void Show()<br>{<br>cout << "i'm parent" << endl;<br>}<br>};</p> <p>class child: public parent<br>{<br> void Show()<br>{<br>cout << "i'm child" << endl;<br>}</p> <p>};</p> <p>parent * parent_object_ptr = new child;</p> <p>parent_object_ptr->show() // calls parent->show() i </p> <p>now we goto virtual world...</p> <p>class parent<br>{<br> virtual void Show()<br>{<br>cout << "i'm parent" << endl;<br>}<br>};</p> <p>class child: public parent<br>{<br> void Show()<br>{<br>cout << "i'm child" << endl;<br>}</p> <p>};</p> <p>parent * parent_object_ptr = new child;</p> <p style="margin-bottom: 12pt;">parent_object_ptr->show() // calls child->show() <br><!--[if !supportLineBreakNewLine]--><br><!--[endif]--></p> <p><b>What is pure virtual function? or what is abstract class?</b></p> <p>When you define only function prototype in a base class without implementation and do the complete implementation in derived class. This base class is called abstract class and client won't able to instantiate an object using this base class.</p> <p>You can make a pure virtual function or abstract class this way.. </p> <p>class Boo<br>{<br>void foo() = 0;<br>}</p> <p>Boo MyBoo; // compilation error</p> <p><br><b>What is Memory alignment??</b></p> <p style="margin-bottom: 12pt;">The term alignment primarily means the tendency of an address pointer value to be a multiple of some power of two. So a pointer with two byte alignment has a zero in the least significant bit. And a pointer with four byte alignment has a zero in both the two least significant bits. And so on. More alignment means a longer sequence of zero bits in the lowest bits of a pointer.</p> <p><b>What problem does the namespace feature solve? </b></p> <p>Multiple providers of libraries might use common global identifiers causing a name collision when an application tries to link with two or more such libraries. The namespace feature surrounds a library's external declarations with a unique namespace that eliminates the potential for those collisions. </p> <p>namespace [identifier] { namespace-body }</p> <p>A namespace declaration identifies and assigns a name to a declarative region.<br>The identifier in a namespace declaration must be unique in the declarative region in which it is used. The identifier is the name of the namespace and is used to reference its members.</p> <p><b>What is the use of 'using' declaration?</b></p> <p>A using declaration makes it possible to use a name from a namespace without the scope operator. </p> <p><b>What is an Iterator class? </b></p> <p>A class that is used to traverse through the objects maintained by a container class. There are five categories of iterators: input iterators, output iterators, forward iterators, bidirectional iterators, random access. An iterator is an entity that gives access to the contents of a container object without violating encapsulation constraints. Access to the contents is granted on a one-at-a-time basis in order. The order can be storage order (as in lists and queues) or some arbitrary order (as in array indices) or according to some ordering relation (as in an ordered binary tree). The iterator is a construct, which provides an interface that, when called, yields either the next element in the container, or some value denoting the fact that there are no more elements to examine. Iterators hide the details of access to and update of the elements of a container class. Something like a pointer.<br></p><br><p><b>What is a dangling pointer? </b></p> <p>A dangling pointer arises when you use the address of an object after its lifetime is over. This may occur in situations like returning addresses of the automatic variables from a function or using the address of the memory block after it is freed.</p> <p><b>What do you mean by Stack unwinding? </b></p> <p>It is a process during exception handling when the destructor is called for all local objects in the stack between the place where the exception was thrown and where it is caught.</p> <p><b>Name the operators that cannot be overloaded??</b></p> <p style="margin-bottom: 12pt;">sizeof, ., .*, .->, ::, ?: </p> <p><b>What is a container class? What are the types of container classes? </b></p> <p>A container class is a class that is used to hold objects in memory or external storage. A container class acts as a generic holder. A container class has a predefined behavior and a well-known interface. A container class is a supporting class whose purpose is to hide the topology used for maintaining the list of objects in memory. When a container class contains a group of mixed objects, the container is called a heterogeneous container; when the container is holding a group of objects that are all the same, the container is called a homogeneous container. </p> <p><b>What is inline function??</b></p> <p>The __inline keyword tells the compiler to substitute the code within the function definition for every instance of a function call. However, substitution occurs only at the compiler's discretion. For example, the compiler does not inline a function if its address is taken or if it is too large to inline.<br> </p> <p><b>What is overloading??</b></p> <p>With the C++ language, you can overload functions and operators. Overloading is the practice of supplying more than one definition for a given function name in the same scope.</p> <p style="margin-bottom: 12pt;">- Any two functions in a set of overloaded functions must have different argument lists.<br>- Overloading functions with argument lists of the same types, based on return type alone, is an error. </p> <p><b>What is Overriding?</b></p> <p>To override a method, a subclass of the class that originally declared the method must declare a method with the same name, return type (or a subclass of that return type), and same parameter list.<br>The definition of the method overriding is:<br>· Must have same method name.<br>· Must have same data type.<br>· Must have same argument list.<br>Overriding a method means that replacing a method functionality in child class. To imply overriding functionality we need parent and child classes. In the child class you define the same method signature as one defined in the parent class.</p> <p><b>What is "this" pointer?</b></p> <p>The this pointer is a pointer accessible only within the member functions of a class, struct, or union type. It points to the object for which the member function is called. Static member functions do not have a this pointer.</p> <p>When a nonstatic member function is called for an object, the address of the object is passed as a hidden argument to the function. For example, the following function call</p> <p>myDate.setMonth( 3 );</p> <p>can be interpreted this way:</p> <p>setMonth( &myDate, 3 );</p> <p>The object's address is available from within the member function as the this pointer. It is legal, though unnecessary, to use the this pointer when referring to members of the class.</p> <p><b>What happens when you make call "delete this;" ??</b></p> <p>The code has two built-in pitfalls. First, if it executes in a member function for an extern, static, or automatic object, the program will probably crash as soon as the delete statement executes. There is no portable way for an object to tell that it was instantiated on the heap, so the class cannot assert that its object is properly instantiated. Second, when an object commits suicide this way, the using program might not know about its demise. As far as the instantiating program is concerned, the object remains in scope and continues to exist even though the object did itself in. Subsequent dereferencing of the pointer can and usually does lead to disaster.</p> <p>You should never do this. Since compiler does not know whether the object was allocated on the stack or on the heap, "delete this" could cause a disaster.</p> <p><b>How virtual functions are implemented C++?</b></p> <p>Virtual functions are implemented using a table of function pointers, called the vtable. There is one entry in the table per virtual function in the class. This table is created by the constructor of the class. When a derived class is constructed, its base class is constructed first which creates the vtable. If the derived class overrides any of the base classes virtual functions, those entries in the vtable are overwritten by the derived class constructor. This is why you should never call virtual functions from a constructor: because the vtable entries for the object may not have been set up by the derived class constructor yet, so you might end up calling base class implementations of those virtual functions</p> <p><b>What is name mangling in C++??</b></p> <p>The process of encoding the parameter types with the function/method name into a unique name is called name mangling. The inverse process is called demangling.</p> <p>For example Foo::bar(int, long) const is mangled as `bar__C3Fooil'.<br>For a constructor, the method name is left out. That is Foo::Foo(int, long) const is mangled as `__C3Fooil'.</p><p><b>What is the difference between a pointer and a reference? </b></p> <p>A reference must always refer to some object and, therefore, must always be initialized; pointers do not have such restrictions. A pointer can be reassigned to point to different objects while a reference always refers to an object with which it was initialized.</p> <p><b>How are prefix and postfix versions of operator++() differentiated?</b> </p> <p>The postfix version of operator++() has a dummy parameter of type int. The prefix version does not have dummy parameter.</p> <p><b>What is the difference between const char *myPointer and char *const myPointer? </b></p> <p>Const char *myPointer is a non constant pointer to constant data; while char *const myPointer is a constant pointer to non constant data. </p> <p><b>How can I handle a constructor that fails?</b></p> <p>throw an exception. Constructors don't have a return type, so it's not possible to use return codes. The best way to signal constructor failure is therefore to throw an exception. </p> <p><b>How can I handle a destructor that fails?</b></p> <p style="margin-bottom: 12pt;">Write a message to a log-file. But do not throw an exception.<br>The C++ rule is that you must never throw an exception from a destructor that is being called during the "stack unwinding" process of another exception. For example, if someone says throw Foo(), the stack will be unwound so all the stack frames between the throw Foo() and the } catch (Foo e) { will get popped. This is called stack unwinding.<br>During stack unwinding, all the local objects in all those stack frames are destructed. If one of those destructors throws an exception (say it throws a Bar object), the C++ runtime system is in a no-win situation: should it ignore the Bar and end up in the } catch (Foo e) { where it was originally headed? Should it ignore the Foo and look for a } catch (Bar e) { handler? There is no good answer -- either choice loses information.<br>So the C++ language guarantees that it will call terminate() at this point, and terminate() kills the process. Bang you're dead. </p> <p><b>What is Virtual Destructor?</b></p> <p>Using virtual destructors, you can destroy objects without knowing their type - the correct destructor for the object is invoked using the virtual function mechanism. Note that destructors can also be declared as pure virtual functions for abstract classes. </p> <p>if someone will derive from your class, and if someone will say "new Derived", where "Derived" is derived from your class, and if someone will say delete p, where the actual object's type is "Derived" but the pointer p's type is your class.</p> <p><br><b>Can you think of a situation where your program would crash without reaching the breakpoint which you set at the beginning of main()?</b></p> <p>C++ allows for dynamic initialization of global variables before main() is invoked. It is possible that initialization of global will invoke some function. If this function crashes the crash will occur before main() is entered. </p> <p><b>Name two cases where you MUST use initialization list as opposed to assignment in constructors.</b></p> <p>Both non-static const data members and reference data members cannot be assigned values; instead, you should use initialization list to initialize them. </p> <p><b>Can you overload a function based only on whether a parameter is a value or a reference?</b></p> <p>No. Passing by value and by reference looks identical to the caller. </p> <p><b>What are the differences between a C++ struct and C++ class?</b></p> <p>The default member and base class access specifiers are different. </p> <p>The C++ struct has all the features of the class. The only differences are that a struct defaults to public member access and public base class inheritance, and a class defaults to the private access specifier and private base class inheritance. </p> <p><b>What does extern "C" int func(int *, Foo) accomplish?</b></p> <p>It will turn off "name mangling" for func so that one can link to code compiled by a C compiler. </p> <p><b>How do you access the static member of a class?</b></p> <p><classname>::<staticmembername></staticmembername></classname></p> <p><b>What is multiple inheritance(virtual inheritance)? What are its advantages and disadvantages?</b></p> <p>Multiple Inheritance is the process whereby a child can be derived from more than one parent class. The advantage of multiple inheritance is that it allows a class to inherit the functionality of more than one base class thus allowing for modeling of complex relationships. The disadvantage of multiple inheritance is that it can lead to a lot of confusion(ambiguity) when two base classes implement a method with the same name.<br></p><p><b>What are the access privileges in C++? What is the default access level?</b></p> <p>The access privileges in C++ are private, public and protected. The default access level assigned to members of a class is private. Private members of a class are accessible only within the class and by friends of the class. Protected members are accessible by the class itself and it's sub-classes. Public members of a class can be accessed by anyone.</p> <p><b>What is a nested class? Why can it be useful?</b></p> <p>A nested class is a class enclosed within the scope of another class. For example:</p> <p> // Example 1: Nested class<br> //<br> class OuterClass<br> {<br> class NestedClass<br> {<br> // ...<br> };<br> // ...<br> };<br>Nested classes are useful for organizing code and controlling access and dependencies. Nested classes obey access rules just like other parts of a class do; so, in Example 1, if NestedClass is public then any code can name it as OuterClass::NestedClass. Often nested classes contain private implementation details, and are therefore made private; in Example 1, if NestedClass is private, then only OuterClass's members and friends can use NestedClass.</p> <p style="margin-bottom: 12pt;">When you instantiate as outer class, it won't instantiate inside class.</p> <p><b>What is a local class? Why can it be useful?</b></p> <p>local class is a class defined within the scope of a function -- any function, whether a member function or a free function. For example:</p> <p style="margin-bottom: 12pt;"> // Example 2: Local class<br> //<br> int f()<br> {<br> class LocalClass<br> {<br> // ...<br> };<br> // ...<br> };<br>Like nested classes, local classes can be a useful tool for managing code dependencies.<br><!--[if !supportLineBreakNewLine]--><br><!--[endif]--></p> <p><b>Can a copy constructor accept an object of the same class as parameter, instead of reference of the object?<br></b> </p> <p>No. It is specified in the definition of the copy constructor itself. It should generate an error if a programmer specifies a copy constructor with a first argument that is an object and not a reference.</p> <p><b>What is encapsulation??</b><o:p></o:p></p> <p>Containing and hiding information about an object, such as internal data structures and code. Encapsulation isolates the internal complexity of an object's operation from the rest of the application. For example, a client component asking for net revenue from a business object need not know the data's origin.<o:p></o:p></p> <p><b>What is inheritance?</b><o:p></o:p></p> <p>Inheritance allows one class to reuse the state and behavior of another class. The derived class inherits the properties and method implementations of the base class and extends it by overriding methods and adding additional properties and methods.<o:p></o:p></p> <p><b>What is Polymorphism??</b><o:p></o:p></p> <p>Polymorphism allows a client to treat different objects in the same way even if they were created from different classes and exhibit different behaviors.<o:p></o:p></p> <p>You can use implementation inheritance to achieve polymorphism in languages such as C++ and Java. <o:p></o:p></p> <p>Base class object's pointer can invoke methods in derived class objects.<o:p></o:p></p> <p>You can also achieve polymorphism in C++ by function overloading and operator overloading.<o:p></o:p></p> <p><b>What is constructor or ctor?</b><o:p></o:p></p> <p>Constructor creates an object and initializes it. It also creates vtable for virtual functions. It is different from other methods in a class.<o:p></o:p></p> <p><b>What is destructor?</b><o:p></o:p></p> <p>Destructor usually deletes any extra resources allocated by the object. <o:p></o:p></p> <p><b>What is default constructor?</b><o:p></o:p></p> Constructor with no arguments or all the arguments has default values.<br /><br /><div style="clear: both;"></div><br /></div>Unknownnoreply@blogger.com9tag:blogger.com,1999:blog-6467304392957302705.post-53619335559325022952008-07-17T20:20:00.000-07:002008-07-18T07:18:13.066-07:00Few Programming Interview Tips and Tricks ( Amazon and MicroSoft )<font><b>Area Number One: Coding</b></font> <br /><br /><p> The candidate has to write some code. Give them a coding problem that requires writing a short, straightforward function. They can write it in whatever language they like, as long as they don't just call a library function that does it for them. </p><br /><p> It should be a trivial problem, one that even a slow candidate can answer in 5 minutes or less. </p><br /><p> (If the candidate seems insulted by the thought of having to get their hands dirty with a trivial coding question, after all their years of experience, patents, etc., tell them it's required procedure and ask them to humor you. If they refuse, tell them we only interview people who can demonstrate coding skills over the phone, thank them for their time, and end the call.) </p><br /><p> Give them a few minutes to write and hand-simulate the code. Tell them they need to make it syntactically correct and complete. Make them read the code to you over the phone. Copy down what they read back. Put it into your writeup. If they're sloppy, or don't want to give you exact details, give them one more chance to correct it, and then go with Not Inclined. </p> <br /><p> <font color="firebrick"><em>(Note added 10/6/04)</em></font> -- another good approach being used by many teams is to give the candidate "homework". E.g. you can give them an hour to solve some coding problem (harder than the ones below) and email the solution to you. Works like a charm. Definitely preferable to reading code over the phone. </p> <br /><p> Anyway, here are some examples. I've given solutions in Java, mostly. I've gone back and forth on accepting solutions in other languages (e.g. Ruby, Perl, Python), and I've decided that candidates need to be able to code their answers in C, C++ or Java. It's wonderful if they know other languages, and in fact those who do tend to do a <em>lot</em> better overall. But to be an Amazon SDE, you need to<br />prove you can do C++ or Java first. </p> <br /><p> <b>Example 1: </b> <i>Write a function to reverse a string.</i> </p> <br /><p> Example <font color="#8a2be2">Java</font> code: </p> <br /><p> <font size="+1" face="courier, lucida, fixed"><pre><font size="2"> public static String reverse ( String s ) {<br> int length = s.length(), last = length - 1;<br> char[] chars = s.toCharArray();<br> for ( int i = 0; i < length/2; i++ ) {<br> char c = chars[i];<br> chars[i] = chars[last - i];<br> chars[last - i] = c;<br> }<br> return new String(chars);<br> }</font><br></pre></font> </p><br /><br /><p> Example output for "Madam, I'm Adam": <font color="#555555">madA m'I ,madaM</font> </p> <br /><br /><p> <b>Example 2: </b> <i>Write function to compute Nth fibonacci number:</i> </p> <br /><br /><p> <font color="#8a2be2">Java</font> and <font color="#1874cd">C/C++:</font><br /><br /><font size="+1" face="courier, lucida, fixed"><pre><font size="2"> static long fib(int n) {<br> return n <= 1 ? n : fib(n-1) + fib(n-2);<br> }</font><br></pre></font></p><br /><br /><p><font color="#8a2be2"><i>(Java Test harness)</i></font><br /><font size="+1" face="courier, lucida, fixed"><pre><font size="2"> public static void main ( String[] args ) {<br> for ( int i = 0; i < 10; i++ ) {<br> System.out.print ( fib(i) + ", " );<br> }<br> System.out.println ( fib(10) );<br> }</font><br></pre></font> </p><br /><br /><p> <font color="#1874cd"><i>(C/C++ Test Harness)</i></font><br /><font size="+1" face="courier, lucida, fixed"><pre><font size="2"> main () {<br> for ( int i = 0; i < 10; i++ ) {<br> printf ( "%d, ", fib(i) );<br> }<br> printf ( "%d\n", fib(10) );<br> }</font><br></pre></font> </p><br /><br /><p> Test harness output: </p><br /><br /><p> <font color="#555555">0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55</font> </p> <br /><br /><p> <b>Example 3: </b> <i>Print out the grade-school multiplication table up to 12x12</i> </p> <br /><br /><p> <font color="#8a2be2">Java:</font> <em>(similar for <font color="#1874cd">C/C++</font>)</em><br /><br /><font size="+1" face="courier, lucida, fixed"><pre><font size="2"> public static void multTables ( int max )<br> {<br> for ( int i = 1; i <= max; i++ ) {<br> for ( int j = 1; j <= max; j++ ) {<br> System.out.print ( String.format ( "%4d", j * i ));<br> }<br> System.out.println();<br> }<br> }</font><br></pre></font> </p><br /><br /><p> Example output: </p><br /><br /><font color="#555555"><pre> 1 2 3 4 5 6 7 8 9 10 11 12<br> 2 4 6 8 10 12 14 16 18 20 22 24<br> 3 6 9 12 15 18 21 24 27 30 33 36<br> 4 8 12 16 20 24 28 32 36 40 44 48<br> 5 10 15 20 25 30 35 40 45 50 55 60<br> 6 12 18 24 30 36 42 48 54 60 66 72<br> 7 14 21 28 35 42 49 56 63 70 77 84<br> 8 16 24 32 40 48 56 64 72 80 88 96<br> 9 18 27 36 45 54 63 72 81 90 99 108<br> 10 20 30 40 50 60 70 80 90 100 110 120<br> 11 22 33 44 55 66 77 88 99 110 121 132<br> 12 24 36 48 60 72 84 96 108 120 132 144<br></pre></font><br /><br /><p> <b>Example 4: </b> <i>Write a function that sums up integers from<br />a text file, one int per line.</i> </p><br /><br /><p> <font color="#8a2be2">Java:</font><br /><font size="+1" face="courier, lucida, fixed"><pre><font size="2"> public static void sumFile ( String name ) {<br> try {<br> int total = 0;<br> BufferedReader in = new BufferedReader ( new FileReader ( name ));<br> for ( String s = in.readLine(); s != null; s = in.readLine() ) {<br> total += Integer.parseInt ( s );<br> }<br> System.out.println ( total );<br> in.close();<br> }<br> catch ( Exception xc ) {<br> xc.printStackTrace();<br> }<br> }</font><br></pre></font> </p><br /><br /><p> <b>Example 5: </b> <i>Write function to print the odd numbers from 1 to 99.</i> </p> <br /><br /><p> <font color="#1874cd">C/C++:</font><br /><font size="+1" face="courier, lucida, fixed"><pre><font size="2"> void printOdds() {<br> for (int i = 1; i < 100; i += 2) {<br> printf ("%d\n", i); // or cout << i << endl;<br> }<br> }</font><br></pre></font> </p><br /><br /><p> <font color="#8a2be2">Java:</font> </p><br /><br /><p> <font size="+1" face="courier, lucida, fixed"><pre><font size="2"> public static void printOdds() {<br> for (int i = 1; i < 100; i += 2) {<br> System.out.println ( i );<br> }<br> }</font><br></pre></font> </p><br /><br /><p> <b>Example 6: </b> <i>Find the largest int value in an int array.</i> </p> <br /><br /><p> <font color="#8a2be2">Java:</font><br /><font size="+1" face="courier, lucida, fixed"><pre><font size="2"> public static int largest ( int[] input ) {<br> int max = Integer.MIN_VALUE;<br> for ( int i = 0; i < input.length; i++ ) {<br> if ( input[i] > max ) max = input[i];<br> }<br> return max;<br> }</font><br></pre></font> </p><br /><br /><p> <b>Example 7: </b> <i>Format an RGB value (three 1-byte<br />numbers) as a 6-digit hexadecimal string.</i> </p><br /><br /><p> <font color="#8a2be2">Java:</font><br /><font size="+1" face="courier, lucida, fixed"><pre><font size="2"> public String formatRGB ( int r, int g, int b ) {<br> return (toHex(r) + toHex(g) + toHex(b)).toUpperCase();<br> }<br><br> public String toHex ( int c ) {<br> String s = Integer.toHexString ( c );<br> return ( s.length() == 1 ) ? "0" + s : s;<br> }</font><br></pre></font> </p><br /><br /><p> Or in <font color="#8a2be2">Java 1.5:</font><br /><font size="+1" face="courier, lucida, fixed"><pre><font size="2"> public String formatRGB ( int r, int g, int b ) {<br> return String.format ( "%02X%02X%02X", r, g, b );<br> }</font><br></pre></font> </p><br /><br /><p> Example output for (255, 0, 128): </p>Unknownnoreply@blogger.com38tag:blogger.com,1999:blog-6467304392957302705.post-3957914991364480762008-06-25T17:03:00.000-07:002008-06-25T17:08:17.970-07:00Few Software Development Knowledge <span style="font-weight:bold;">What are the benefits of OOD?</span><br />o <span style="font-style:italic;">Object oriented design facilitates “Reusability”, “Extensibility” and “Modularity” of the software. We can divide the software into many components/classes so that “Abstraction” can be done on the changing part and non changing part to support the “changeability”. Plus Inheritance, Composition and polymorphism will always help in implementation.</span><br /><br /><br /> <span style="font-weight:bold;">Explain how the Garbage Collector works in C#</span><br />o The GC of the C# (.Net rather) is a cool component in .NET framework. Being a C++ programmer, I truly understand the importance of it. I don’t need to worry about allocating /freeing the memory once I use it in .net. <br />In c#, all the object memory management is done in “Managed heap. GC collects the unused memory based on metadata information which gives the memory layout of the created object. It performs the collection in two phases.<br /><br />Mark -> GC first finds the root of each object and traverse to the bottom of it adding each object and make a graph of it. It does not add the object already in the graph. The object not in a graph considered as a garbage.<br /><br /><br /> Compact -> in this step, GC pushes the entire live object down to the heap re-arranging the pointers and making the free space on the top of the heap. It corrects the pointers in moving the object here and there.<br /><br /><span style="font-weight:bold;">What's the difference between Dispose and Finalize?</span><br />o Dispose and Finalize are both to remove the unmanaged memory allocated by the object. Dispose is an explicit way and programmers need to implement Idisposable interface where as finalize is the implicit way to free the memory and called by GC. Developer is not supposed to call the finalize method on an object but he/she can call dispose method. Microsoft recommends that we implement both Dispose and Finalize when working with unmanaged resources. The correct sequence then would be for a developer to call Dispose. The Finalize implementation would run and the resources would still be released when the object is garbage collected even if a developer neglected to call the Dispose method explicitly.<br /><br /> <span style="font-weight:bold;">What are the drawbacks in using the String class in C#?</span><br />o String class in C# is immutable and new memory is created whenever value of it is changed. If we do some operations of String object, a new memory is created and value is copied over there. This is a major problem if we use the long/huge string and manipulate it in C# Program.<br /><br /><br /><span style="font-weight:bold;"> How does StringBuilder improve on that?</span><br />o StringBuilder is a Mutable class and new memory is not referenced when it value gets changed.<br /><br /><br /> <span style="font-weight:bold;">What is an abstract class and when would you use it.</span><br />o Abstact class is a class having at least one abstract method/property on it. Abstract class cannot be instantiated and is a base class for other classes. We cannot use “sealed” keyword on it to prevent other classes to inherit from it. It is used when Common methods are implemented in a base class but other methods/properties will be changed in child classes.<br /><br /><br /> <span style="font-weight:bold;">Test a stapler, provide all the test cases</span><br />Requirement test: <br />Size (length, breadth and height) of it.<br />Color of it.<br />Weight of it.<br />Size of Pin in it.<br />Does it have stapler indicator?<br />What type of metal used to make it?<br />It is magnetic?<br />Functional test:<br />what happens if you put bigger stapler pin?<br />What happens when it is jammed?<br />How does it work when there is no pin? Does it produce sound? or indicator blinks?<br />Does it have a base? <br />Does it have a body? <br />Does it have a rear pivot?<br />What is the max depth it can be used.<br />What happens if the size of the pin is smaller or bigger?<br />Does it have a staple exit?<br />What happens if I staple materials other then paper?<br />Usability Test:<br />can blind person use it?<br />Can a person with one only one hand use it?<br />What is the age limit to use it?<br />Does it contain harmful materials?<br />How much different size of Staplers it can use?<br />Do you need manual to use it?<br />Mass testing <br />All the staplers are of the same size and same functionality?<br />Do they have same materials?<br /> Stress Testing <br /> What max temp it can bear?<br /> What is the min temp its spring can bear or work?<br /> How much pressure needed to break it ?<br /> Does it break if it falls from my desk or from the running vehicle?<br />Performance Test:<br />. How many staples can be stapled in the stapler's use-full life?<br /> How many staples can be stapled in a sec or a minute?<br /><br />Rule Test:<br />Do you need license to use it?<br />Does it harmful to the minor?<br />Do you need to tell which country is it made?<br />Does it expiration date? (Note: this is funny)<br /><br /><br /><br /> <span style="font-weight:bold;">Test an API called FormatURL which takes as an input a http URL string and replaces all special characters eg: space with %20 etc.,</span><br />o Test cases:<br />FormatURL(http://www.yahoo.com?name=deepak%20dhakal) <br />FormatURL(http://www.yahoo.com?name=%20%7Bdeepakdhakal) <br />FormatURL(http://www.yahoo.com?name=%20%7Bdeepakdhakal%20%5D)<br />FormatURL(http://www.yahoo.com?name=%21%7Bdeepakdhakal%20%5D) //non existence code<br />FormatURL(http://www.yahoo.com?name=%20)<br />FormatURL(“”)<br />FormatURL(“%7D”)<br />FormatURL(“%AAAA”)<br />FormatURL(%%%)<br />FormatURL(http://www.yahoo.com? %%%)<br />FormatURL(http://www.yahoo.com)Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-6467304392957302705.post-48848724974167600132007-10-29T11:26:00.001-07:002008-06-25T17:09:44.060-07:00About MeDEEPAK DHAKAL<br />285 Robins Rd Apt E7, Hiawatha, IA, 52233, (319) 210-7070<br />therisingdeepak@yahoo.com<br /><br />Key qualification<br />• Over 3 years of experience in programming, testing, deploying and maintaining web /windows based applications; has contributed to full software development life-cycle.<br />• Strong technical background, interpersonal communication and project management skills, with ability to adapt to new technologies, environment and applications proficiently.<br /><br />Professional Summary <br />• 3+ years of designing, developing and testing software using .NET 1.1/2.0/3.5(C#, VB.NET), NUnit, ASP.NET, ADO.NET, COM, WINAPI, MFC, C, C++, AJAX, XML, Web Services, Adobe Flash, VSTO, WCF, Mobile Web Development.<br />• 3+ years strong experience with Object Oriented Systems Analysis/Design, Test driven development, Multi-tier design, Design patterns and UML Diagrams with excellent knowledge of the software development life-cycle.<br />• 3+ years of hands on experience in Relational Database schema design using MS-SQL 2000/2005, Oracle 9i with Strong familiarity of relational database modeling principles/techniques and great experience in integrating views, triggers, cursors, indexes and stored procedures with development environment<br />• 6+ months of experience using Test Stand (LABVIEW) for testing test fixtures.<br />• 5+ years of engineering and software development experience using Microsoft Technologies <br />• 1+ years of experience in Java swing programming, PHP, JDBC and JUnit testing.<br /><br />Professional Experiences<br /><br />Fastek Intl, Cedar Rapids, Iowa March 2007-Present<br />Software Engineer<br />• Worked as a Software Engineer/team leader for Fastek International and its clients. Performed tasks including day-to-day development and maintenance of the web/windows applications, including web component creation and leading a team of programmers. <br />• Contributed as a team leader during the development of different web/windows based company management systems software as well as trained entry level programmers.<br />• Quality assurance testing of all the development prior to launch to ensure proper functionality, logics, coding conventions, and consistency with user interface.<br /><br />Major Projects Summary <br /><br />iPrsim Global (http://www.iprismglobal.com)<br />A Secure Virtual Office (SVO); real time collaborative Web Conferencing with a suite of high performance workflow tools, data integration applications.<br /><br />Summary:<br />• Developed dynamic web pages using ASP.NET 2.0, ADO.NET, AJAX and Web Services with MSSQL 2005.<br />• Designed/developed Mobile web pages for www.iprismglobal.com for handheld mobile devices using MS Mobile Emulators.<br />• Implemented Dundas Chart, Gauge, and Digital Dashboard using Dundas 6.0 using ASP.NET.<br />• Designed/Developed Windows Prism Jabber Chat Application ( like Google Talk ) that supports link post, chat history, adding/deleting users, managing groups and offline messages using .NET web services, XMPP protocol and .NET Interop services.<br />• Developed Prism Outlook toolbar that facilitates to sync the MS Outlook Calendar Appointments to prism Web calendar using .Net add-on Projects (VSTO) for Outlook 2003 and 2007.<br />• Wrote testing cases and test procedures to test the above applications in NUnit and created documentations.<br />Development Tools: C# 2.0, ASP.NET 2.0 (AJAX), Dundas 6.0, VS 2005, SQL Server 2005 and Reporting Services, VSS, Windows forms, Office 2003/2007<br />ViconNet 4.0 Intregation for CCTV (www.vicon-cctv.com/viconnet-intro.html )<br />A Fully scalable networked video surveillance solution based upon ViconNet software that Allows for complete interoperability between all devices connected to the network.<br />Summary:<br />• Developed/Managed MFC layer application to connect to the Win32 C library that connects to the CCTV devices connected to the network.<br />• Integrate the .NET/CLR layer to the MFC layer that facilitates easy interface to the windows based application using .NET API calls.<br />• Developed and tested the Upper windows form layer that manages the Zooming, Rotating and storing the video frames to the database.<br />• Documented and managed the proposal estimation for the application.<br />Development Tools: C#, MFC, C++, WIN32 API, VS 2005/2003, VSS, Computer Workstation.<br /> AIRport (University of IOWA, MBA)<br />AIRport is university of Iowa’s Admission, Information, and Registration portal to the MBA.<br /><br />Summary:<br />• Developing N tier AIRport Web application and implementing UML classes and interfaces in ASP.NET 2.0 with full AJAX support.<br />• Writing DTS Packages, triggers, cursors and stored procedures in MSSQL 2000 and integrating them with the application.<br />• Documenting test cases/test suits and testing them in NUnit.<br />• Writing reusing components (SSH FTP client, .CSV Creator, Nightly processes using multithread, Reporting tool using Crystal Report) to support the main application.<br />• Communicating with the clients about the changes they desired as the project developed, including follow-up documentation.<br />• Provided Training to few entry level programmers.<br />Development Tools: C# 2.0, ASP.NET 2.0(AJAX), Visual Studio.Net 2005, ADO.NET, XML Web Service, SQL Server 2000, HTML, CSS.<br />J&P Cycles – E-commerce website & Internal Portal <br />“J&P cycles” is company that sells motorcycles part of various brands since 1979. J&P Cycles consulted Fastek for solution for the issues which they had with their E-commerce system. I was a member of the consulting team in upgrading and maintain their E-commerce system. http://www.jpcycles.com <br /> <br />Summary:<br />• Web Development using ASP.Net, ADO.Net & SQL 2000.<br />• Development in ASP, JavaScript, AJAX, XHTML, VBScript, XML.<br />• Integrating the e-commerce system to Controller+ using TCP/IP Socket Programming.<br />• Implementation and consumption of Web Services using SOAP, WSDL.<br />Development Tools: VB.NET 2.0, ASP.NET 2.0(AJAX), NUnit, XML Web Service, MSSQL 2000<br /><br /><br />FASePay Autobilling (PSO Canada)<br />An auto billing system for different restaurants in Canada to handle credit/debit card process, it manages payment history and billing processing with its own payment gateway.<br /><br />Summary:<br />• Developing N tier Merchant Manager Web application with ASP.Net 3.0, Silverlight.<br />• Writing views, triggers, cursors and stored procedures in MSSQL 2005 and integrating them with Merchant Manager Web application.<br />• Designing and Implementing WCF (Windows Communication Foundation) services and testing them with service host and service clients.<br />• Documenting test cases for the services and testing them in NUnit.<br />Development Tools: C# 3.0(WCF), ASP.NET 3.0 (AJAX), SilverLight 1.0, Visual Studio.Net 2005 SP1, SQL Server 2005 and Reporting Services, Visual SourceSafe.<br /><br />B787-Model 0877B1 Software verification<br />A Model 877B1 is the icing conditions Detector (ICD) for the BoeingB78. The software was from Goodrich and verification was done by Fastek Team. TestStand was the testing tool<br /><br />Summary:<br />• Configure TestStand Enjoinment with hardware and other software Components.<br />• Assisted writing test sequences to test the hardware using TestStand.<br />• Tested and modified the basic C code for the hardware.<br />• Run and generated the reports for each Test case and documented it using VSS.<br /><br />HRT (University of IOWA)<br />A Health risk tracking application with few flash animations to find the risk of dying within coming 10 year by heart attack.<br /><br />Summary:<br />• Developing/ testing a flash animation using Adobe Flash CS3 (Action script 3.0) to track the 10 year risk to heart attack...<br />• Developing/ testing the main application in ASP 3.0 with SQL server 2000 backend.<br />• Writing DTS Packages, triggers, cursors and stored procedures in MSSQL 2000 and integrating them with the application.<br />• Documenting test cases/test suits and testing them in NUnit.<br />Development Tools: ASP 3.0, SQL Server 2000, Adobe Flash CS3, AS 3.0, CSS, VSS.<br /><br />HitechValley iNet Pvt Ltd, Kathmandu Nepal Sept 2004- Aug 2006<br />ASP.NET Web Developer in C#<br /><br />Major Projects Summary <br /><br />Online Jewelry for Car<br />An E-commerce project, sells various parts of automobiles of different types. It has to handle millions of data and the project was from USA. <br /><br />Summary:<br />• Converting existing VB.NET code to C# code and writing test cases.<br />• Implementing the UML classes and interfaces to the C# in VS 2003 and integrating them within the subsystem.<br />• Writing views, triggers, cursors and stored procedures in MSSQL 2000 and integrating them with .NET environment.<br />• Communicating with the clients about the changes they desired as the project developed, including follow-up documentation.<br />• Configuring and maintaining the source control CVS.<br />• Reusing components like Data access layer with XML.<br />• Documenting daily TODO tasks and submitting to the project manager.<br />• Finishing the project within time limit specified by client.<br />Development Tools: C#/ASP.NET 1.1, VS.Net 2003, ADO.NET, SQL Server 2000<br /><br />Online used car management application:<br />An E-commerce project to sell and buy used cars. The client is UK-based and requires special handling and manipulation of postal code data<br /><br />Summary:<br />• Communicating with the client to define the requirements for the application, including full documentation between the parties.<br />• Designing the use cases, class diagrams, and subsystem diagrams with full documentation using Rational Rose using RUP.<br />• Implementing the UML diagram to the code in C# and writing test cases using N unit.<br />• Communicating and coordinating with two new developers and assigning daily tasks to them.<br />• Integrating payment gateway PAYPAL to the application.<br />Development Tools: : C# 1.1, ASP.NET 1.1, Visual Studio.Net 2003, ADO.NET, XML, XSLT, SQL Server 2000, XHTML/DHTML, CSS, JavaScript and CVS.<br /><br />Online DVD management system<br />An E-commerce project that helps to sell and rent various types of DVDs using web services and RSS Fee, the project was based on Nepal<br />Development Tools: C# 2.0, ASP.NET 2.0, VS 2005, ADO.NET, SQL Server 2005, CSS.<br /><br />Maharishi University of Management, Fairfield, Iowa Nov 2006- Jan 2007<br />Teaching Assistant<br />(Software Engineering, Distributed computing, advanced software development)<br /><br />Everest Engineering College, Kathmandu, Nepal Sept 2004 – July 2006<br />Project Instructor <br /><br />Education<br />• Master of Computer Science, Maharishi University of Management, Fairfield, Iowa, GPA: 3.82 (Computer Science) currently enrolled ( one course remaining for the graduation)<br />• Bachelor of Engineering in Computer, Pokhara University, Pokhara, Nepal (2005) CGPA: 3.68 <br /><br />Certification<br />ASP.NET: Brainbench Certification, Score: 3.71, ID: 6663541<br />C#: Brainbench Certification, Score: 3.79<br /><br />Technical Skill<br />Languages C# 1.1/2.0/3.0, J2SE, VB.NET, VB 6.0, C/C++, MFC.<br />Development Environments VisualStudio.Net 2003/2005, Eclipse 3.1/3.2 for Java, VS 6.0<br />Web-Development Technologies ASP.NET 1.1/2.0/3.0 (C#), ASP, ADO.NET, XML WebServices, SOAP, WSDL, XML, Servlets, Flash CS3, Action script<br />Scripting and Markup JavaScript, PHP, HTML,XHML, XML, XSL, XSLT.<br />Databases SQL Server 2005/2000, MS Access , MYSQL,Oracle<br />Operating Systems Windows 98/NT/2000/XP, Windows Server 2000/2003, Linux<br />OO Tools & Languages Rational Unified Process (RUP), Rational Rose 2000, Omondo.<br />Testing Frameworks NUnit, JUnit., NAnt, NDoc<br />Web/App Server Apache Tomcat, IIS 6.0.<br />Methodologies Rational Unified Process (RUP), Design Patterns.<br />Source Control CVS, Visual Source Safe.Unknownnoreply@blogger.com20tag:blogger.com,1999:blog-6467304392957302705.post-4919152243041640562007-10-16T08:22:00.000-07:002007-10-16T14:24:00.256-07:00Microsoft Silverlight : An Introduction<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXp5Rf2qWU-m5STUnjCG2OlvSYQ_xX_YL71j5kSJNPky_OkOURpglBjs5Yh6JcirgRZcOESIRVcF0To740Xi4jlXwRjUOYftaN0Fb_hPRJ_ejMT5-bBKgouxmvLI4JidpVAPRoyjH7CiM/s1600-h/Silverlight.png"><img style="margin: 0pt 10px 10px 0pt; float: left; cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgXp5Rf2qWU-m5STUnjCG2OlvSYQ_xX_YL71j5kSJNPky_OkOURpglBjs5Yh6JcirgRZcOESIRVcF0To740Xi4jlXwRjUOYftaN0Fb_hPRJ_ejMT5-bBKgouxmvLI4JidpVAPRoyjH7CiM/s320/Silverlight.png" alt="" id="BLOGGER_PHOTO_ID_5121956703038438754" border="0" /></a><br /><span style="color: rgb(0, 153, 0);font-size:180%;" ><span style="font-weight: bold;"><blockquote>WHY ?<br /></blockquote></span></span><ol><li>It supports playback of WMV files on both PC and Macintosh, with many options for interactivity during playback; with just a couple of lines of code, you can provide a platform-neutral way to handle all your movie files. Silverlight supports full-screen 720p video and offers seamless transitions between full-screen and windowed mode without losing your position in the video (something that media sites are crying out for today). </li><li>By separating markup (XAML) from code, Silverlight provides a familiar web metaphor for designers and developers. You can embed XAML directly within an HTML file if you want a simple, monolithic solution, or you can keep the two separate to enforce a delineation between different web development roles.</li><li>Silverlight and HTML integrate seamlessly together. Every XAML element can be accessed or manipulated from the same client-side JavaScript that would be used to interact with any DHTML element: there are no artificial boundaries or barriers, and you can even overlay HTML elements on top of Silverlight content (simply by creating a windowless frame). We'll also make it very easy for an ASP.NET AJAX developer to add Silverlight content.</li><li>You can embed XAML directly into your HTML pages; there's nothing binary or opaque about the format. There are only three steps necessary to add animation or media to your RIA application: (i) include a standard JavaScript file in your HTML header; (ii) call a function to create the Silverlight object anywhere on the screen; (iii) add some XAML content (an animation, some media) for runtime delivery.</li><li>You have full runtime interactivity with Silverlight content. The contents of the XAML file can be completely server-generated, to contain information populated from a database. From JavaScript, it's just a matter of calling the createFromXaml method to add or remove elements dynamically at runtime. There's nothing that you can only create or manipulate at design-time.</li><li>Silverlight is just a 1MB download on a PC (slightly more on a Macintosh because the universal package contains both Intel and PowerPC versions); it supports Windows XP and above, with Windows 2000 support to come.</li><li>Silverlight is blindingly fast - for example, you can play many videos simultaneously without stuttering or dropping frames (subject to network bandwidth, of course). We're introducing a new video brush in Silverlight that allows you to use video as a texture for any 2D object (a rectangle, an ellipse or a path). This is going to allow designers incredible power to use media in new ways that have never been accessible through other existing technologies.</li><li>Silverlight is both client- and server-agnostic. There's no difference between the Macintosh and PC runtimes; you don't need any Microsoft software on the server if you don't want to - you can deliver a great Silverlight experience from an Apache / Linux server to a Mac OS 10.4 client. </li><li>Silverlight is almost 100% upward compatible with WPF. Animation, 2D vector graphics, media, text - they're all present in Silverlight and the concepts you've learnt in WPF carry forward (although Silverlight is a subset - it doesn't support WPF features such as 3D, data binding or templates). You can use the same tools (e.g. Expression Design) to generate content for Silverlight; you can take XAML from Silverlight and use it in a WPF application when you want to scale up and take full advantage of your local machine.</li></ol>Src: http://blogs.msdn.com/tims/archive/2007/04/15/introducing-microsoft-silverlight.aspx1Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-6467304392957302705.post-78998429672210245012007-10-15T19:57:00.000-07:002007-10-15T19:58:07.481-07:00database<h1>: The Relational Model</h1> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal"><b>Purpose</b>: Concepts, terminology. Express queries in relational algebra and relational calculus. Translate between relational algebra and SQL (Lesson 6).</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">e.g. Student, Courses, Grades relations (tables)</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">An attribute in an entity-relationship diagram has a <b>domain</b>, that is, a datatype and a range of valid values. For example, zip code is a five-digit positive number.</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">A <b>Cartesian product</b> of domains is a set containing all possible combinations of elements, one from each domain. For example, a chessboard presents the Cartesian product of the rows (a-h) with the columns (1-8), with one square for each combination b5, h2, etc.</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">A <b>tuple</b> is an element of a Cartesian product.</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">A <b>relation</b> is a subset of a Cartesian product. For example, the set of valid values for (city, state, zip code) form a relation. Note that this relation contains information, whereas the Cartesian product City x State x Zip contains no information.</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">In a relation, there are</p> <p class="MsoNormal"><span style=""> </span>no duplicate attribute names</p> <p class="MsoNormal" style="text-indent: 0.5in;">no duplicate tuples</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">In a relation</p> <p class="MsoNormal"><span style=""> </span>degree = number of attributes</p> <p class="MsoNormal"><span style=""> </span>cardinality = number of tuples</p> <p class="MsoNormal"><span style=""> </span>order of attributes has no significance</p> <p class="MsoNormal"><span style=""> </span>order of tuples has no sigificance</p> <p class="MsoNormal"><span style=""> </span></p> <p class="MsoNormal">Note: it is because the columns of a relation are named with distinct names that the order of the columns has no significance.</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">Note: a <b>result set</b> is a relation in which the both the columns and the tuples are ordered.</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">Note: a <b>table</b> is a physical representation of a relation. In a table, whether it is in a document on a hard drive, some sequence of columns and tuples will generally be evident.</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">A <b>relational schema</b> is the set of attributes (with their domains) in a relation.</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal"><b>Relational variables</b>: when we write “a relation R”, we are using R as a variable which represents a specific relational schema and could take as its values or instances any table that is consistent with the relational schema.</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal"><b>Relational Algebra</b>: five fundamental operations, two standard derived operations</p> <p class="Bullet1"><!--[if !supportLists]--><span style="font-family: Symbol;"><span style="">·<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal;"> </span></span></span><!--[endif]-->select(R, proposition)<span style=""> </span>S(R, p)</p> <p class="Bullet1"><!--[if !supportLists]--><span style="font-family: Symbol;"><span style="">·<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal;"> </span></span></span><!--[endif]-->project(R, attribute set)<span style=""> </span>P(R, A)</p> <p class="Bullet1"><!--[if !supportLists]--><span style="font-family: Symbol;"><span style="">·<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal;"> </span></span></span><!--[endif]-->union(R1, R2)<span style=""> </span>R1+R2</p> <p class="Bullet1"><!--[if !supportLists]--><span style="font-family: Symbol;"><span style="">·<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal;"> </span></span></span><!--[endif]-->difference(R1, R2)<span style=""> </span>R1-R2</p> <p class="Bullet1"><!--[if !supportLists]--><span style="font-family: Symbol;"><span style="">·<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal;"> </span></span></span><!--[endif]-->product(R1, R2)<span style=""> </span>R1*R2</p> <p class="Bullet1"><!--[if !supportLists]--><span style="font-family: Symbol;"><span style="">·<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal;"> </span></span></span><!--[endif]-->join(R1, R2, comparison)<span style=""> </span>J(R1, R2, p)</p> <p class="MsoNormal" style="text-indent: 0.5in;"><span style=""> </span><span style=""> </span>= S(R1*R2, p)</p> <p class="Bullet1"><!--[if !supportLists]--><span style="font-family: Symbol;"><span style="">·<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal;"> </span></span></span><!--[endif]-->divide(R1, R2)<span style=""> </span>R1 / R2</p> <p class="MsoNormal" style="text-indent: 0.5in;"><span style=""> </span><span style=""> </span>= P(R1- (P(R1, att(R1) \ att(R2))*R2) - R1), att(R1) \ att(R2))</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">Aggregate functions in SQL can be represented in relational algebra by allowing the projection operator to project onto aggregate functions on attributes which are themselves projected out.</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">A <b>proposition</b> is a Boolean expression which evaluates to True or False for each tuple without requiring any data except that provided by the tuple. For example, on Grades relation, “grade > B” is a proposition. A proposition does not contain any “for all” or “there exists” quantifiers.</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">Joins come in various flavors:</p> <p class="Bullet1"><!--[if !supportLists]--><span style="font-family: Symbol;"><span style="">·<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal;"> </span></span></span><!--[endif]-->Theta join, equi-join (a particular type of theta join)</p> <p class="Bullet1"><!--[if !supportLists]--><span style="font-family: Symbol;"><span style="">·<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal;"> </span></span></span><!--[endif]-->Natural join, outer join, inner join</p> <p class="Bullet1"><!--[if !supportLists]--><span style="font-family: Symbol;"><span style="">·<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal;"> </span></span></span><!--[endif]-->Semi-join</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">Division—for example, identify all students who have taken all courses.</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal"><b>Relational Calculus (tuple oriented)</b>:</p> <p class="MsoNormal"><span style=""> </span>R = { FQAttSet | predicate }</p> <p class="MsoNormal">where “FQAttSet” stands for a set of fully-qualified attribute names.</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal"><b>Relational Calculus (domain oriented)</b>:</p> <p class="MsoNormal"><span style=""> </span>R = { AttributeSet | predicate }</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">A <b>predicate</b> is a Boolean expression which may contain attributes not in the set “FQAttSet”. All such attributes will be quantified by a “for all” or “there exists”. For example, to get a list of names of student with at least one “A”, we take</p> <p class="MsoNormal" style="text-indent: 0.5in;">FQAttSet = Student.name</p> <p class="MsoNormal" style="text-indent: 0.5in;">predicate = “there exists Grade.courseID such that</p> <p class="MsoNormal" style="margin-left: 1in; text-indent: 0.5in;">Student.courseID = Grade.courseID and</p> <p class="MsoNormal" style="margin-left: 1in; text-indent: 0.5in;">Grade.grade = A”</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">Note <b>closure</b>: every operation in relational algebra or relational calculus produces a relation.</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal"><b>Fundamental Theorem</b>: Given a set of relations RSet = {R1, ..., Rn}, a relation R can be derived from RSet by relational algebra if and only if R can be derived from RSet by relational calculus.</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal"><b>Keys</b> in a Relation R</p> <p class="Bullet1"><!--[if !supportLists]--><span style="font-family: Symbol;"><span style="">·<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal;"> </span></span></span><!--[endif]-->A superkey is a set of attributes whose values uniquely identifies each tuple in any instance of R</p> <p class="Bullet1"><!--[if !supportLists]--><span style="font-family: Symbol;"><span style="">·<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal;"> </span></span></span><!--[endif]-->A candidate key is a superkey which does not contain another superkey</p> <p class="Bullet1"><!--[if !supportLists]--><span style="font-family: Symbol;"><span style="">·<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal;"> </span></span></span><!--[endif]-->A primary key is a specific candidate key</p> <p class="Bullet1"><!--[if !supportLists]--><span style="font-family: Symbol;"><span style="">·<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal;"> </span></span></span><!--[endif]-->An alternate key is a candidate key other than the primary key</p> <p class="Bullet1"><!--[if !supportLists]--><span style="font-family: Symbol;"><span style="">·<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal;"> </span></span></span><!--[endif]-->A foreign key is a set of attributes in R which matches a candidate key in a relation S, where S could be R</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">Note that a key is defined with respect to a relational variable, not an instance of the variable. Identification of a key must be supported by business rules.</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">No instance of R can establish that a set of attributes is a superkey for R. For example, it may happen that student names in a specific course are all different, but this would not imply that the student-name attribute is a superkey for a classlist relation. On the other hand, a single class in which two students have identical names is sufficient to establish that the student-name attribute is not a superkey.</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">A <b>view</b> is a derived relation. A view can always be defined by a query on base relations. The purpose of a view is to give restricted access to the database for both user convenience and data security.</p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">The principle issue with a view is whether or not it permits updating the base relations from which it is derived. <span style="font-family: Times;">Updates are allowed if the defining query involves a single base relation and contains a candidate key of base relation.</span></p> <p class="MsoNormal"><o:p> </o:p></p> <p class="MsoNormal">A <b>relational database</b> is a set of normalized relations (Lesson 4).</p> <p class="MsoNormal"><o:p> </o:p></p> <h3>Integrity <span style="font-weight: normal;">in a relational database</span></h3> <p class="Bullet1"><!--[if !supportLists]--><span style="font-family: Symbol;"><span style="">·<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal;"> </span></span></span><!--[endif]-->Entity Integrity—no attribute of a primary key can be Null</p> <p class="Bullet1"><!--[if !supportLists]--><span style="font-family: Symbol;"><span style="">·<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal;"> </span></span></span><!--[endif]-->Referential Integrity—a foreign key is either wholly Null or has a match</p> <p class="MsoNormal"><o:p> </o:p></p> <b><span style="font-size: 12pt; font-family: "Times New Roman";"><br /> </span></b> <p class="MsoNormal"><b>Nulls</b> may be used to indicate incomplete data. The Interim Report 75-02-08 to the ANSI X3 (SPARC Study Group 1975) lists 14 different kinds of incomplete data that could appear as the result of queries or as attribute values. These types include overflows, underflows, errors and other problems trying to represent the real world within the limits of a computer.</p> <ol style="margin-top: 0in;" start="1" type="1"><li class="MsoNormal" style="">not valid for this individual (e.g., maiden name of male employee)</li><li class="MsoNormal" style="">valid, but does not yet exist for this individual (e.g., married name of female, unmarried employee).</li><li class="MsoNormal" style="">exists, but not permitted to be logically stored (e.g. religion of this employee).</li><li class="MsoNormal" style="">exists, but not knowable for this individual (e.g., last efficiency rating of an employee who worked for another company).</li><li class="MsoNormal" style="">exists, but not yet logically stored for this individual (e.g. medical history of newly hired employee)</li></ol> <p class="Bullet1" style=""><!--[if !supportLists]--><span style=""><span style="">6.<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-size-adjust: none; font-stretch: normal;"> </span></span></span><!--[endif]--><span style="">logically stored but subsequently logically deleted<o:p></o:p></span></p> <ol style="margin-top: 0in;" start="7" type="1"><li class="MsoNormal" style="">logically stored, but not yet available.</li><li class="MsoNormal" style="">available, but undergoing change (may be no longer valid).</li><ol style="margin-top: 0in;" start="1" type="a"><li class="MsoNormal" style="">change begun, but new values not yet computed</li><li class="MsoNormal" style="">change incomplete, committed values are part new, part old, may be inconsistent</li><li class="MsoNormal" style="">change incomplete, but part new values not yet committed</li><li class="MsoNormal" style="">change complete but new values not yet committed.</li></ol><li class="MsoNormal" style="">available, but of suspect validity (unreliable)</li><ol style="margin-top: 0in;" start="1" type="a"><li class="MsoNormal" style="">possible failure in conceptual data acquisition</li><li class="MsoNormal" style="">possible failure in internal data maintenance</li></ol><li class="MsoNormal" style="">available, but invalid</li><ol style="margin-top: 0in;" start="1" type="a"><li class="MsoNormal" style="">not too bad</li><li class="MsoNormal" style="">too bad</li></ol><li class="MsoNormal" style="">secured for this class of conceptual data</li><li class="MsoNormal" style="">secured for this individual object</li><li class="MsoNormal" style="">secured at this time</li><li class="MsoNormal" style="">derived from null conceptual data (any of the above).</li></ol> <h3><o:p> </o:p></h3>Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-6467304392957302705.post-29188293317025863472007-10-15T18:39:00.000-07:002007-10-15T18:40:10.162-07:00My First English BlogHi this is DeepakUnknownnoreply@blogger.com1