ALGORITHMS & CODING

1) You are developing a web browser (something like e.g. Netscape, etc.) and need to display all
visited links on a page. The visited links need to use a different color then that used to display
scheme than the unvisited links. Now, given a history of links you have visited before, how
would you go about writing the piece of code that makes the determination if you have seen this
link before? Answer or not? The answer could be a simple string comparison, but then think
about the time it will take for the client to render any HTML page. Alternatively, so, given a
history of URLs, come-up with an elegant way (algorithm, data structures, etc.) to make the
determination if a given link already exists in the history list? (Answer)
2) Since web pages can have multiple URLs pointing to them, as a web browser developer how can
you make sure you have never seen the same content before? (Answer)
3) Write a function to print all the possible permutations of a string. Now, modify the algorithm to
discard duplicates. (Answer)
4) Design a memory management scheme.
5) Implement strstr(), strcpy(), strtok() etc. (Answer)
6) Write an algorithm and C code to find the sub array with the largest sum given an array that
contains both positive and negative integers (Answer)
7) A square picture is cut into 16 squares and then shuffled. Write a program to rearrange the 16
squares to get the original big square. (Answer)
8) Implement an algorithm to reverse a singly linked list (with and without recursion). (Answer)
9) Count the total number of set bits in a number without using a loop. (Answer)
10) Given an array of characters which form a sentence of words, give an efficient algorithm to
reverse the order of the words in it. (Answer)
11) Do the class/structure description for a Hash table, and write the source code for the insert
function. (Answer)
12) What sort of technique you would use to update a set of files over a network, where a server
contains the master copy.
13) How do you handle deadlock on a table that is fed with a live serial feed?
14) Say you have three integers between 0-9. You have the equation: A! +B! +C! = ABC (where
ABC is a three digit number, not A*B*C). Find A, B, and C that satisfies this equation.
(Answer)
15) Is it possible to keep 2 stacks in a single array if one grows from position one of the array, and
the other grows from the last position? Write a procedure PUSH (x, s) that pushes element x
onto stack S, where S is one or the other of these two stacks. Include all necessary error checks.
16) How would you find a cycle in a linked list? Try to do it in O(n) time. Try it using a constant
amount of memory. (Answer)
17) Implement an algorithm to reverse a doubly linked list. (Answer)
18) The web can be modeled as a directed graph. Come up with a graph traversal algorithm. Make
the algorithm non-recursive and breadth-first. (Answer)
19) How would you implement a queue from a stack? (Answer)
20) Write source code for printHex (int i) in C/C++. (Answer)
21) Given an array of size N in which every number is between 1 and N, determine if there are any
duplicates in it. (Answer)
22) You are given one fixed list of numbers (let’s call it the first list) and one other list (second list).
How can you efficiently find out if there is any element in the second list that is an element of
the first list? (Answer)
23) 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. (Answer)
24) Do a breadth first traversal of a tree. (Answer)
25) Write a function to find the depth of a binary tree. (Answer)
26) Given 2 nodes in a tree, how do you find the common root of the nodes? (Answer)
27) Write atoi().