Uncategorized – Page 5

Tree Quesitons

How would you print out the data in a binary tree, level by level, starting at the top?

Linked List Questions

How would you find a cycle in a linked list?

Implement an algorithm to insert a node into a circular linked list without traversing it.

Sorting Questions

– Describe advantages and disadvantages of the various stock sorting algorithms.

– How would you write qsort?

Implement an algorithm to sort an array. Why did you pick the method you did?
Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?
Count the number of set bits in a number. Now optimize for speed. Now optimize for size.
Multiple by 8 without using multiplication or addition. Now do the same with 7.
Add numbers in base n (not any of the popular ones like 10, 16, 8 or 2 — I hear that Charles Simonyi, the inventor of Hungarian Notation, favors -2 when asking this question).
Write routines to read and write a bounded buffer.
Write routines to manage a heap using an existing array.
Implement an algorithm to take an array and return one with only unique elements in it.
Implement an algorithm to print out all files below a given root node.
Given that you are receiving samples from an instrument at a constant rate, and you have constant storage space, how would you design a storage algorithm that would allow me to get a representative readout of data, no matter when I looked at it? In other words, representative of the behavior of the system to date.

Give me an algorithm to shuffle a deck of cards, given that the cards are stored in an array of ints.
The following asm block performs a common math function, what is it?
```
cwd xor ax, dx
sub ax, dx
```
Imagine this scenario:
I/O completion ports are communictaions ports which take handles to files, sockets, or any other I/O. When a Read or Write is submitted to them, they cache the data (if necessary), and attempt to take the request to completion. Upon error or completion, they call a user-supplied function to let the users application know that that particular request has completed. They work asynchronously, and can process an unlimited number of simultaneous requests.
Design the implementation and thread models for I/O completion ports. Remember to take into account multi-processor machines.
Implement malloc.
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.
Imagine you are standing in front of a mirror, facing it. Raise your left hand. Raise your right hand. Look at your reflection. When you raise your left hand your reflection raises what appears to be his right hand. But when you tilt your head up, your reflection does too, and does not appear to tilt his/her head down. Why is it that the mirror appears to reverse left and right, but not up and down?
You have 4 jars of pills. Each pill is a certain weight, except for contaminated pills contained in one jar, where each pill is weight + 1. How could you tell which jar had the contaminated pills in just one measurement?
The SF Chronicle has a word game where all the letters are scrambled up and you have to figure out what the word is. Imagine that a scrambled word is 5 characters long:
1. How many possible solutions are there?
2. What if we know which 5 letters are being used?
3. Develop an algorithm to solve the word.

You’re given an array containing both positive and negative integers and required to find the subarray with the largest sum (O(N) a la KBL). Write a routine in C for the above.

Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it. You are allowed to destroy the array if you like.

Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it.

—————————————— from a guys google interview ——————————————————-

http://blog.madhukar4e.com/2008/06/google-interview-questions-algorithms.html

Below are some of the questions that I can remember from my Google interview …

1. Anagram (GOD <-> DOG) : algorithm to identify if two given strings are anagrams

2. Given a source array of integers with possible duplicates and a target integer, write algorithm to find out 2 numbers in source array whose sum is equal to target integer.

3. If pre-processing of source in the above is allowed, what pre-processing will you do to reduce the complexity of algorithm written above ?

4. If you are given a random number generator which gives float value between 0 and 1 & if an array is given, write algorithm to randomize the array values.

5. Given an array of strings, write algorithm to find out if there are duplicates and also print the duplicate strings once.

6. For all the above questions, they will ask you to determine big o complexity and check for ways to optimize.

—————————————— done from a guys google interview ——————————————————-