First page
Q64: Implement an algorithm to do string matching with wildcards.
tags: microsoft sw programming algorithms
Q66: Given an array t[100] which contains numbers between 1..99. Return the duplicated value. Try both O(n) and O(n-square).
tags: microsoft sw programming algorithms
Q73: Do a breadth first traversal of a tree.
tags: microsoft sw programming algorithms
Q75: Write, efficient code for extracting unique elements from a sorted list of array. e.g. (1, 1, 3, 3, 3, 5, 5, 5, 9, 9, 9, 9) -> (1, 3, 5, 9).
tags: microsoft sw programming algorithms
Q76: Given an array of integers, find the contiguous sub-array with the largest sum.
tags: microsoft sw programming algorithms
Q77: Given an array of length N containing integers between 1 and N, determine if it contains any duplicates.
tags: microsoft sw programming algorithms
Q78: Sort an array of size n containing integers between 1 and K, given a temporary scratch integer array of size K.
tags: microsoft sw programming algorithms
Q81: An array of pointers to (very long) strings. Find pointers to the (lexicographically) smallest and largest strings.
tags: microsoft sw programming algorithms
Q84: 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).
tags: microsoft sw programming algorithms
Q93: What is a balanced tree
tags: microsoft sw programming algorithms
Q103: A real life problem - 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.
tags: microsoft sw programming puzzle algorithms
Q115: Given a binary tree with nodes, print out the values in pre-order/in-order/post-order without using any extra space.
tags: microsoft sw programming algorithms
Q123: Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) = 3 and so on. Given k >= 0, compute f(k).
tags: microsoft sw programming algorithms
Q126: How do you represent an n-ary tree? Write a program to print the nodes of such a tree in breadth first order.
tags: microsoft sw programming algorithms
Q127: Write the tr program of UNIX. Invoked as tr -str1 -str2. It reads stdin and prints it out to stdout, replacing every occurance of str1[i] with str2[i]. e.g. tr -abc -xyz to be and not to be <- input to ye xnd not to ye <- output
tags: microsoft sw programming algorithms
Q200: Design and describe a system/application that will most efficiently produce a report of the top 1 million Google search requests.These are the particulars. * You are given 12 servers to work with. They are all dual-processor machines with 4Gb of RAM, 4x400GB hard drives and networked together.(Basically, nothing more than high-end PC's) * The log data has already been cleaned for you. It consists of 100 Billion log lines, broken down into 12 320 GB files of 40-byte search terms per line. * You can use only custom written applications or available free open-source software.
tags: google sw software programming design algorithms
Q197: The Dutch National Flag Problem (The following problem was proposed by W.H.J. Feijen and made famous by Edsger W.Dijkstra, both of Dutch origin.) You are given a row of n buckets, each containing one ball, which may be either red, white, or blue. Your goal is to rearrange the balls in the buckets such that they appear in the order of the colors on the Dutch national flag: red balls should be grouped on the left, the order of the colors on the Dutch national flag: red balls should be grouped on the left, move balls is swap(i,j), which swaps the contents of the i and j buckets. Give pseudocode for a linear-time algorithm for sorting an array B[1..n] of balls in the Dutch national flag order. Your algorithm should use only constant space in addition to the given array.
tags: microsoft ebay hp yahoo programming algorithms sw
Q64: Implement an algorithm to do string matching with wildcards.
tags: microsoft sw programming algorithms
Q66: Given an array t[100] which contains numbers between 1..99. Return the duplicated value. Try both O(n) and O(n-square).
tags: microsoft sw programming algorithms
Q73: Do a breadth first traversal of a tree.
tags: microsoft sw programming algorithms
Q75: Write, efficient code for extracting unique elements from a sorted list of array. e.g. (1, 1, 3, 3, 3, 5, 5, 5, 9, 9, 9, 9) -> (1, 3, 5, 9).
tags: microsoft sw programming algorithms
Q76: Given an array of integers, find the contiguous sub-array with the largest sum.
tags: microsoft sw programming algorithms
Q77: Given an array of length N containing integers between 1 and N, determine if it contains any duplicates.
tags: microsoft sw programming algorithms
Q78: Sort an array of size n containing integers between 1 and K, given a temporary scratch integer array of size K.
tags: microsoft sw programming algorithms
Q81: An array of pointers to (very long) strings. Find pointers to the (lexicographically) smallest and largest strings.
tags: microsoft sw programming algorithms
Q84: 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).
tags: microsoft sw programming algorithms
Q93: What is a balanced tree
tags: microsoft sw programming algorithms
Q103: A real life problem - 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.
tags: microsoft sw programming puzzle algorithms
Q115: Given a binary tree with nodes, print out the values in pre-order/in-order/post-order without using any extra space.
tags: microsoft sw programming algorithms
Q123: Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) = 3 and so on. Given k >= 0, compute f(k).
tags: microsoft sw programming algorithms
Q126: How do you represent an n-ary tree? Write a program to print the nodes of such a tree in breadth first order.
tags: microsoft sw programming algorithms
Q127: Write the tr program of UNIX. Invoked as tr -str1 -str2. It reads stdin and prints it out to stdout, replacing every occurance of str1[i] with str2[i]. e.g. tr -abc -xyz to be and not to be <- input to ye xnd not to ye <- output
tags: microsoft sw programming algorithms
Q200: Design and describe a system/application that will most efficiently produce a report of the top 1 million Google search requests.These are the particulars. * You are given 12 servers to work with. They are all dual-processor machines with 4Gb of RAM, 4x400GB hard drives and networked together.(Basically, nothing more than high-end PC's) * The log data has already been cleaned for you. It consists of 100 Billion log lines, broken down into 12 320 GB files of 40-byte search terms per line. * You can use only custom written applications or available free open-source software.
tags: google sw software programming design algorithms
Q197: The Dutch National Flag Problem (The following problem was proposed by W.H.J. Feijen and made famous by Edsger W.Dijkstra, both of Dutch origin.) You are given a row of n buckets, each containing one ball, which may be either red, white, or blue. Your goal is to rearrange the balls in the buckets such that they appear in the order of the colors on the Dutch national flag: red balls should be grouped on the left, the order of the colors on the Dutch national flag: red balls should be grouped on the left, move balls is swap(i,j), which swaps the contents of the i and j buckets. Give pseudocode for a linear-time algorithm for sorting an array B[1..n] of balls in the Dutch national flag order. Your algorithm should use only constant space in addition to the given array.
tags: microsoft ebay hp yahoo programming algorithms sw
