Data Structures and Algorithms  I
Posted by Subash  8:27 AM
[1] Comments

links to this post
 Write a function and the node data structure to visit all of the nodes in a binary tree.
 You know what a queue is .... Implement a queue class with Java. What is the cost of enqueue and dequeue? Can you improve this? What if the queue is full (I was using an looping array)? What kind of mechanism would you use to increase its size?
 Give an algorithm that calculates the distance between two text strings (only operations you can have are: delete, add, and change, one by one).
 Given the definition of a sequence (5 4 7 6 is, but 1 2 4 5 is not), write an algorithm to check if an arbitrary array is a sequence or not. Once I figured out a solution, I was asked to do a space and time complexity analysis.
 Describe a situation where concurrent access would lead to inconsistency in your application. How would you solve this problem?
 You are given a list of n numbers from 1 to n1, with one of the numbers repeated. Devise a method to determine which number is repeated.
 Write an algorithm to detect loop in a linked list.
 Given the time, devise an algorithm to calculate the angle between the hour and minute hands of an analog clock.
 Devise an algorithm for detecting whether a given string is a palindrome (spelled the same way forwards and backwards). For example, "A man, a plan, a canal, Panama."
 Given an eightbit bitmap graphics file, devise an algorithm to convert the file into a twobit ASCII approximation.
 Reverse a linked list.
 Insert in a sorted list
 First some definitions for this problem: a) An ASCII character is one byte long and the most significant bit in the byte is always '0'. b) A Kanji character is two bytes long. The only characteristic of a Kanji character is that in its first byte the most significant bit is '1'. Now you are given an array of a characters (both ASCII and Kanji) and, an index into the array. The index points to the start of some character. Now you need to write a function to do a backspace (i.e. delete the character before the given index).
 Delete an element from a doubly linked list.
 Write a function to find the depth of a binary tree.
 Assuming that locks are the only reason due to which deadlocks can occur in a system. What would be a foolproof method of avoiding deadlocks in the system.
 Besides communication cost, what is the other source of inefficiency in RPC?
 Ways of optimizing symbol table storage in compilers.
 A walkthrough through the symbol table functions, lookup() implementation etc  The interv. was on the Microsoft C team.
 Given an array t[100] which contains numbers between 1..99. Return the duplicated value. Try both O(n) and O(nsquare).
 Given an array of characters. How would you reverse it. ? How would you reverse it without using indexing in the array.
 Given a sequence of characters. How will you convert the lower case characters to upper case characters. ( Try using bit vector  sol given in the C lib > typec.h)
 Give a good data structure for having n queues ( n not fixed) in a finite memory segment. You can have some datastructure separate for each queue. Try to use at least 90% of the memory space.
 Do a breadth first traversal of a tree.
 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).
 What is a balanced tree
 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.
 Implement an algorithm to reverse a doubly linked list.
 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.
 The Web can be modeled as a directed graph. Come up with a graph traversal algorithm. Make the algorithm nonrecursive and breadthfirst.
 How would you implement a hash table ? How do you deal with collisions?
 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.
 Given a history of URLs, how would you determine if a particular URL had been seen before?
 Since pages can have multiple URLs pointing to them, how can you make sure you've never seen the same CONTENT before?
 Write a function to print all of the permutations of a string.
 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.
 The Web can be modeled as a directed graph. Come up with a graph traversal algorithm. Make the algorithm nonrecursive and breadthfirst.
 Implement an algorithm to reverse a singly linked list. (with and without recursion)
 Implement an algorithm to reverse a doubly linked list.
 Implement an algorithm to insert in a sorted list.
 Delete an element from a doubly linked list.
 Write a function to copy two strings, A and B. The last few bytes of string A overlap the first few bytes of string B.
 Implement an algorithm to sort an array.
 Given a sequence of characters, how will you convert the lower case characters to upper case characters?
 Write a routine that prints out a 2D array in spiral order.
 Count the number of set bits in a number without using a loop.
 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.
 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.
 How would you print out the data in a binary tree, level by level, starting at the top?
 Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words in it.
 Write a function to find the depth of a binary tree.
 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).
 How would you implement a queue from a stack?
 Write a funtion that finds repeating characters in a string.
 Write a routine to reverse a series of numbers without using an array.
 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)
11:45 PM
could you please provide answers to these questions ???