Algorithm Interview Questions - Set 1

1. A period of time where users login and logout, given a sets of login and logout time pairs, write a function that can show the number of users online at any given time.
2. Intersection of n sets without using a hash table.
3. Implement a LRU(Least Recently Used) cache
4. Implement a function to compute cubic root
   what is the time complexity?
5. Given a matrix with 1′s and 0′s, find the number of groups of 1′s. A group is defined by horiz/vertically adjacent 1′s.
6. Given a matrix of numbers in which some may be zero. If a cell contains a zero, set all the cells in the corresponding column and row to zero.
7. You are given a set of numbers 0 – n. Given a k, print all subsets of size k. Give the time complexity of the algorithm.
8. Given an unsorted array of integers, find a 3-element subset that sums to zero..Complexity…?
9. Multiply two big integers which don’t fit into an built-in integer type. How would you represent big numbers as a data structure? Write the function to multiply two big integers.
10. Implement atof function. eg., +3.5e-2, .03e1, 1e1, 0.0
11. How to implement Sqrt(double k) efficiently?   OR   Compute the square root of a number down to a certain precision.
    ie sqrt(num, precision) returns a number that is in-between sqrt(num) – precision and sqrt(num) + precision.
12. How to implement multiple inheritance in Java
13. Given set of coins and each coin has its unique probability to be head up, say double[] probs stores the probability values for all coins, print out all different cases and accordingly probability.
14. Find the min and max in an array. Now do it in less than 2n comparisons. (they were looking for the solution that finds both max and min in about 3/2 n comparisons).
15. FInd the maximum sum of a sub-sequence from an positive integer array where any two numbers of sub-sequence are not adjacent to each other in the original sequence. E.g 1 2 3 4 5 6 –> 2 4 6
16. Given an array of integers, now we want to erase all 0′s (can be other value), and we want the result array condensed, meaning no empty cell in the array.
17. given a list of words with a same size and a big string that contains one of the permutation of all the words combined(say p), find the startindex of the string p in the big string
18. Reverse a Linked list (Recursively/Non recursively)
19. Write the actual code to parse a regular expression including “*”, which stands for 0 or more characters, “+”, which stands for 1 or more characters, and “.”, which stands for 1 exact character.
20. print out all prime numbers in a given string. abc2134kd31 -> 2, 13, 3, 3
21. search needle in haystack problem. Make it more robust.
22. Implement a function rotateArray(vector arr, int r) which rotates the array by r places. Eg 1 2 3 4 5 on being rotated by 2 gives 4 5 1 2 3.
23. Implement a function string balanceParanthesis(string s); which given a string s consisting of some parenthesis returns a string s1 in which parenthesis are balanced and differences between s and s1 are minimum.
    Eg – “(ab(xy)u)2)” -> “(ab(xy)u)2″
    “)))(((” -> “”
24. All Possible balanced parenthesis problem
25. How will you design TinyUrl?
26. How will you design facebook newsfeed. Focus was on a design which could handle the huge number of status updates and display them on each of the user’s friend’s wall.
27. Implement a function
    char* readLine();
    which returns single lines from a buffer. To read the buffer, you can makes use of a function
    int read(char* buf, int len)
    which fills buf with upto len chars and returns the actual number of chars filled in. Function readLine can be called as many times as desired. If there is no valid data or newline terminated string available, it must block. In order to block, it can use read function which in turn will block when it doesn’t have anything to fill the buf.
28. Find Kth smallest element in a BST.
29. Implement a queue data structure given only stacks. What is the time complexity of enqueuing and dequeuing operations?
30. Given a Binary Search Tree, iterate over the elements without using recursion.
31. Given a set of non-overlapping integer ranges (1,3) (5,8), etc., and an input integer, what is the best way to organize the data and allow for quick search based on the input, etc.
32. Given a telephone number, find all the permutations of the letters assuming 1=abc, 2=def, etc.
33. Print a singly-linked list backwards, in constant space and linear time.
34. Convert a binary search tree to a sorted, circular, doubly-linked list, in place (using the tree nodes as the new list nodes).
35. Given a set of words, group them into sets of anagrams.
36. Given a string, remove all the duplicate characters (not necessarily consecutive)
37. Write a function to tell if two line segments intersect or not.
38. Find an algorithm to find the largest sum subarray in an array of integers. (Better than O(n^2) ).
39. Write a function that computes log2() using sqrt().
40. Given a list of n objects, write a function that outputs the minimum set of numbers that sum to at least K. FOLLOW UP: can you beat O(n ln n)?
41. Write a function to prettify Json objects
42. Given sorted arrays of length n and 2n with n elements each, merge first array into second array.
43. You are given intervals of contiguous integers, like [1, 10), [15, 25), [40, 50), which are non-overlapping and of a fixed size.
    Design a data structure to store these intervals and have the operations of insert, delete, and find functions
44. Design a system to detect typos and provide suggestions to users.  Design and implement an algorithm that would correct typos: for example, if an extra letter is added, what would you do?
45. Find the n-th smallest element in a binary tree.
46. Print a binary tree in infix order. Recursive and iterative.
47. Design the Facebook Credit system which is a application where users can buy/trade virtual currency and can use the virtual currency to purchase Facebook services, like paid apps.What's the advantage of the design?How would the total credit points of a user be calculated based on my design?
48. Write a code to convert an ASCII representation of a positive integer to it's numeric value.
49. Write a function to take two arbitrarily long numbers in the form of Strings and multiply them, returning another String with the product.
50. Given a binary tree, write a function to find the length of the longest path in the tree.
51. Write a function to take a BST and a value k as input and have it print the kth smallest element in the BST.
52. Find the minimum depth of binary search tree.. http://www.glassdoor.com/Interview/Find-the-minimum-depth-of-binary-search-tree-QTN_127018.htm
53. Print a binary search tree. Each level on a new line.
54. Implement the div operator without using / or %
55. You are trying to rob houses on a street. Each house has some +ve amount of cash. Your goal is to rob houses such that you maximize the total robbed amount. The constraint is once you rob a house you cannot rob a house adjascent to that house.
56. Given a matrix print it clockwise from the first element to the very inner element.
57. Given an array of integers and size find 3 integers that sum to zero.
58. You are going to take some numbers as an input from a file. You need to witer a program to find longest increasing sequence. You should process it as soon as you are taking an input. After finishing the last input immediately you should be able to tell the sequence.
    Input: 1 5 3 4 6 4
    Output: 3 4 6
59. A file contains 10 billions of Strings and need to find duplicate Strings. You have N number of systems available. How will you find duplicates?
60. Given a set of integers, print out all its subsets.
61. Code a program to check if a given string is matching a given regular expression
62. Each key on the telephone represents a list of letters. Given a telephone number, please write a program to output all the possible strings the telephone number represents.
63. write a function to check if a graph was bipartite.
64. Given two binary trees, return true if they have same elements (irrespective of tree structure)
65. Given a string, remove all chars from the string that are present in say another string called filter.
66. Given two events, each with a start and end time, implement a boolean check to see if they overlap.
67. Print out all combinations of k numbers out of 1...N
    e.g. when k = 2, n = 4
    Print out 12, 13, 14, 23, 24, 34
68. runtime complexity of binary search and the average num of guesses it takes to find a number between 1 to 1000.  Given the numbers 1 to 1000, what is the minimum numbers guesses needed to find a specific number if you are given the hint "higher" or "lower" for each guess you make.
69. Advantage of B Trees - Used in databases for indexing. Adv. Less number of memory lookups because of less hierarchy. Large fanout.
70. Given a set of inputs in a log file: log:
    example:
    1,2
    1,1
    2,1
    3,1
    1,2
    out:
    1,2
    2,1
    3,1
    The output should be all the unique numbers and the count associated with them.
71. Given an array, print the largest subarray that has elements in an increasing order
72. How do you find sequences of consequtive integers in a list that add to a particular number.
73. Given a score S, and individual points p1,p2,...,pn. give all combinations of p that add up to s.
74. Given a large string (haystack), find a substring (needle) on it.
75. Given a list of strings, for each string, find if it has an anagram in the list.
76. Function to compute the number of ways to climb a flight of n steps. Taking 1, 2, or 3 steps at a time. Do it in Linear time and constant space. n = 3.
    1 1 1
    1 2
    2 1
    3
    Ans = 4
77. Interweave a linked list. Do it in Linear time and constant space. Input: A->B->C->D->E
    Output: A->E->B->D->C
78. Given a dictionary based simple password, create all possible (special character) passwords based on a provided mapping. Input: face
    Map: {a -> @, 4, A}
    Output: f@ce, f4ce, fAce
79. Get numeric number out of a roman string, linear time
    Given: mapping I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000
    Input/Output:
    II = 2, III = 3, IV = 4
    VI, VII, VIII
    IX = 9
    XL = 40,
    XLIX = 49
80. Merge 'k' sorted arrays, each array may have max 'n' elements
81. how does hash map implementation looks like
82. Implement strstr in C
83. Write some pseudo code to raise a number to a power.
84. Given an array of integers, find the maximum number that can be reached by summing the best possible consecutive subsequence of the array.
85. Design a linked list operation that takes a singly-linked list (only forward ptrs, no backward ptrs) as input and reverses the list.
86. Given a 1TB file of serialized 4 byte integers, and 2GB of ram, sort the integers into a resulting 1TB file. My interviewer was very collaborative in entertaining various solution ideas until we came up with a combo that would work performantly and reduce the number of passes over the 1TB file and intermediate files.
87. Write a list class where the only data structure available is a stack
88. Determine the 10 most frequent words given a terabyte of strings.
89. Use basic arithmetic operations (+-*/) to implement sqrt function.
90. Print out all the permutations of a string
91. Write a function that prints out all subsets of a given set of numbers.
92. Write a function that takes in two binary strings and returns their sum (also a binary string).
93. Write a function that finds the minimum and maximum values within an unsorted array using divide-and-conquer.
94. Generate a new array from an array of numbers. Start from the beginning. Put the number of some number first, and then that number.
    For example, from array 1, 1, 2, 3, 3, 1
    You should get 2, 1, 1, 2, 2, 3, 1, 1
    Write a program to solve this problem.
95. given the utitlies getFriend(User u) and areFriends(User u1, User u2), write the function which takes as parameter the array of users and return a bool saying if you can divide the users in 2 groups s.t. if u1 and u2 both belong to a certain group, they are not friends.
96. remove duplicates in a string.
97. Given a file with 3-letter words, print all 3x3 with each row, column and diagonal being one of the words from given file.
98. Find the center of graph(vertex, that is connected with every other vertex, but edges are directed to the center of graph).
99. Given n+1 buckets with n of them with ball inside and move(a,b) function, that moves ball from bucket a to bucket b. Each ball has a different number from [1,n] on it. Move balls, so each bucket has a ball with matching number in it.
100. Implement a power function to raise a double to an int power, including negative powers.
101. Given a String containing java-script assets, write a parser which will output the String with proper indentation.
102. Given a certain state of an Othelo game board, location on the board, a certain piece to place on the given location, update the board and make the required validations
103. Given a collection of words, return a collection of anagrams found in the
     given collection
104. Output a single linked list in reverse, in linear time and constant space, and recursively
105. Pascal’s Triangle – print a row
106. Given a function for a fair coin, write a function for a biased coin that returns heads 1/n times (n is a param).

Read More

Design Questions - Set 1

1. Design a game of chess
2. Given an ebay site model., you have to deal with auctioning of a particular item. Design the billing & auctioning system of the same.
3. OOPs design of a file system
4. Class diagram of a system to implement Blackjack
5. Class diagram of a parking lot
6. design a furniture module, a furniture could be a couch,  chair, etc. each furniture could contain multiple materials, wood, steel, etc. http://www.careercup.com/question?id=12989661
7. Which Data structure is used in window search…??  http://www.careercup.com/question?id=12688668
8. Design elevator system    http://www.careercup.com/question?id=12598663
9. OOPs design of a file system     http://www.careercup.com/question?id=12598664
10. mplement LRU cache .  http://www.careercup.com/question?id=12674664
11. Design a Architecture of Online Movie Booking System . Find the possible issues and Idea to Resolve them. How do you optimize the Performance against all these issues.  http://www.careercup.com/question?id=12533687
12. Design an online movie booking system
13. Design and Implement Boggle game for n x n  http://www.careercup.com/question?id=12427668
14. A news paper agency wants an application through which customers can select the news paper & magzenes they need on daily basis (ex day1 -> he need paper1 ,paper2, magjene1, day2 -> none , day3 – paper4 ) etc.. how registration and billing will be done, Provide a high & low level diagrams for it. which are the classes needed for the same.
15. Two chess players want to play chess online with each other using facebook. Which are the classes you need for it and what are the APIs needed for the same. How one user will inform other once he made a move from his side .(Client server architecture .) . How a client will reduce the unwanted number of hits to server 2) once user1 has made a move how user2 will be informed quickly. 3) how the chess board position will be propagated from user1 to user2 with least amount of data . 4) Tell the security measures to make this game efficient (asked what is BUT and how to solve it) .
16. How will you implement file search facility in windows, so that you will save the search and indexes for future references. Provide the design & tell the classes needed for the same.  http://www.careercup.com/question?id=12419685
17. Give data structures for the following problems in making an employee management system:
    1) given a manager give all the employees he manages ( one to many relationship)
    2) represent organizational structure of the company  http://www.careercup.com/question?id=12375725
18. Consider a cloak room. It has 3 compartments, small, medium, large
    1 medium = 2 small
    1 large = 2 medium = 4 small Design such a system, ensuring maximum capacity optimization of the compartments. Also, make the required number of moves (in-btw compartments) as minimum as possible.
    Write class, functions. Wht functions will u expose. What token will you return back to the user.  http://www.careercup.com/question?id=12493669

Read More

Unix Interview Questions - Set 4

What is $*?
Its mainly used for showing up all params. This show all parameter values passed in shell script

What does $# stand for?
# will return the number of parameters that are passed as the command-line arguments.

What does $? Return? $?
It will return exit status of command .0 if command gets successfully executed ,non-zero if command failed.

What are Different types of shells?

sh :
the oldest shell
csh : C shell
ksh : Korn Shell
bash : bourne again shell

How do you read arguments in a shell program – $1, $2?
Shell script accepts parameters in following format…
$1 would be the first command line argument, $2 the second, and so on
$0 is the name of the script or function If your script has more than 9 params then accept in following way…
${12} : 12th param
${18} : 18th param

What are the different kinds of loops available in shell script?
for, if, while, case

What is the difference between a shell variable that is exported and the one that is not exported?
The Shell variable which is exported would available to all the programs outside the Shell also. And the shell variable which is not exported, would available for that shell or for the shell program only, in which the variable is declared. Export LANG=C
will make the variable LANG the global variable, put it into the global environment. All other processes can use it.

LANG=C
will change the value only in the current script.     If you have a string “one two three”, which shell command would you use to extract the strings? echo $string | cut -d” ” -f1
echo $string | cut -d” ” -f2
echo $string | cut -d” ” -f3

How will you list only the empty lines in a file (using grep)?
grep “^$” filename.txt

How would you get the character positions 10-20 from a text file?
cat filename.txt | cut -c 10-20 or cut -c10-20



How would you replace the n character in a file with some xyz?
sed ‘s/n/xyz/g’ filename > new_filename

We can replace n characters by using the following command:
1,$s/./xyz/g
where 1 shows that the search string will start searching patterns from first line of the file.
           ‘.’ for any character.
            g for global replacemet.

What is the difference between a ‘thread’ and a ‘process’?
A process is a collection of virtual memory space, code, data, and system resources. A thread is code that is to be serially executed within a process. A processor executes threads, not processes, so each application has at least one process, and a process always has at least one thread of execution, known as the primary thread. A process can have multiple threads in addition to the primary thread Thread – is stream of executable code within process. They are light weight process. All thread with in a process  share process instruction,code & data segment,open file descriptor,signal handler,userID and GroupID. Thread has its own set of register including program counter,stack pointer

What is this line in the shell script do ?#!/bin/ksh?
To invoke the shell indirectly this line is added as the first line in the file.This particular line invokes korn shell
What is use of “cut” command? Give some examples. Cut – Utility used to cut/Strip out the required data/text from the source. Cut can be used in three modes,   Stripping by Character      cut -c 1-3   Striping by Byte length      cut -b -1-72 Stripping by delimiter and fields.      cut -d “|” -f1 Where    -d “|” -> Delimiter used in input text to separate columns -f1 -> Field/Column number   While processing huge input files, Cut’s performance is far better than awk

References

• http://unixshellscript-india.blogspot.in/2012/06/unix-programming-basic.html

Read More

Amazon Questions - Set 1

1. Write code to find Nth last node in a linked list. Solution
2. Given a binary tree build a vertical sum array.    Solution
3. Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1? Solution
4. Given two lists of strings return a list of strings that is an intersection of both of the lists.
   Analyze running time and space complexity.
   Give Test Case scenarios.
5. There is n node graph, each node having only one root. All nodes are labeled in a random order from int 0 to n-1. The graph is represented in a array format such that the value in the array at index equal to child node label is root node label.
   For root assume the value is -1.
   Ex.

       3
   4   1     2
      0 5

   the array is
   value : 1, 3, 3, -1, 3, 1
   Index : 0, 1, 2, 3, 4, 5
   Find the height of graph. careercup
6. Given a node in a binary tree, how will you find out if left and right subtrees are mirror images of each other?  Solution
7. Given a binary tree and a number N, print all paths that start from root and add up to N.
8. Find the biggest BST in a given binary tree.   http://www.careercup.com/question?id=13000680
9. Given an array A, build another array B in which each element is the product of all elements in A other than the element at the same position. Write code that does this with and without division.
10. Find the position of first ’1′ in a sorted array that contains only 0-s and 1-s.
11. In a dial pad(similar to phone dial pad) where if 2 corresponds to ‘abc’ and 3 corresponds to ‘def’ etc. Write a program to form all possible and meaningful words for the given number.
    Example:
    if 2 is pressed possible words are a,b,c. But ‘a’ is only meaningful word. Hence print ‘a’ and
    if 23 is pressed. The possible words are going to be ad,ae,af,bd,be,bf,cd,ce,cf there is no meaningful word.So,dont print anything.
12. Given a binary tree which is huge and can not be placed in memory, how do you check if the tree is a mirror image.
13. Given a book containing 100′s of words., If a word is repeated, delete it. Process such that there are no repetitive words.
14.  Given coins of denomination 4, 5 and 7. How can you make up 13 ?   http://puddleofriddles.blogspot.com/2012/03/you-are-given-n-types-of-coin.html
15. Given a program on fork() system call.
    

    #include <stdio .h>
    #include <unistd .h>
    int main()
    {
       fork();
       fork() && fork() || fork();
       fork(); printf(“forked\n”);
       return 0;
    }
    

    
    How many processes will be spawned after executing the above program?
16. Do in-order traversal of tree without using recursion .  http://stackoverflow.com/questions/5502916/please-explain-morris-inorder-tree-traversal-without-using-stacks-or-recursion
17. 1. There is a web URL which contains %20 in place of space, how will your replace every %20 with space3. Let’s say, on the file there are only 5% URL which contains this %20, how will your replace with space in most efficient way?       http://www.careercup.com/question?id=13032664
18. Longest Palindrome in a input string
19. How do you find million smallest numbers from a file that contains billions of numbers ?
20. Given a binary tree, every node has a int value, return the root node of subtree with the largest sum up value. Java is more preferable. Caution: the return should be a node, not a integer!http://www.careercup.com/question?id=12868663
21. Let’s say you have a simple function (fibonacci/factorial) that you need to run constantly. The largest number that you will receive as input will be 1,000. How can you improve the performance of this function call?I said not use recursion and cache the results using a data structure (i.e. a Map)
    What else could you do to improve the performance?    http://www.careercup.com/question?id=12903663
22. Given an array of integers, find second largest element in an array.  http://www.careercup.com/question?id=12897677
23. Write a function convert a string to an integer. example convert String “1750″ to int 1750. Using Java, not allow use the default function ..http://www.careercup.com/question?id=12903687
24. Write a function convert a integer from 0 to 1000 to Roman numerals.
    1: I 5: V 10: X 50: L 100: C 500: D 1000: M
    Test Cases:
    XI 11, IX 9, XXX 30, DC 600, CM 900, XCVIII 98         http://www.careercup.com/question?id=12940668
25. Given an array. Find pairs of numbers that add up to a given value ‘x’. with time complexity less than O(n2) and use no additional space. http://www.careercup.com/question?id=12887674
26. Write Code: Find an integer array’s maximum value. Trace code. Use Try/catch instead of return.
27. Given a spreadhseet, what data structure you will use to store it. What will you use for dynamic updation of of Spreadsheet formulas.
28. Count number of set bits in an Integer
29. Find first unique character in an array.  http://www.careercup.com/question?id=12960668
30. Given 2 Arrays A and B, find the intersection of two arrays. Initially without using any other data structure. Later with using additional data structure.  http://www.careercup.com/question?id=12975663
31. Given a 2D array, all rows and all columns sorted. Find an integer x from the 2D array.  http://www.careercup.com/question?id=12977662
32. How do you find million smallest numbers from a file that contains billions of numbers ? http://www.careercup.com/question?id=13018675
33. Convert a sorted doubly linked list to a BST while trying to keep BST as balanced as possible   http://www.careercup.com/question?id=12778667
34. i got this as an interview question. i was given 2 linked lists of unequal lengths,containing a single digited number in each of their nodes. i was asked to build a 3rd linked list which contains the sum of the two linked lists, again in the form of 1 digit in a node. ex: linked list 1 is 4-7-9-6 linked list 2 is 5-7 then the 3rd linked list would be 4-8-5-3 can someone suggest me Java answer.   http://www.careercup.com/question?id=12743681
35. Given a string “This is an example” –> Output: “This is an example” There should be equal number of spaces between words.  http://www.careercup.com/question?id=12781696
36. each of 100 students in a school has a unique ranking 1-100. I will select 50 students randomly .
    Of the 50 randomly selected student i will select a boy, say ranking 40, and wish to know his relative ranking among the 50 students selected. How do you do this efficiently? http://www.careercup.com/question?id=12765663
37. What data structure you will use if you have to implement google map like utility, you will be able to search the city, you will be able to find shortest path between two nodes. And you have to implement one more feature of auto suggestion which means if user type “Na” then you should show all the cities starting with letter Na in a list. And algo should be very efficient because it should update things as soon as user changes the typed character.  http://www.careercup.com/question?id=12809665
38. Given two nodes of a tree, find the first common ancestor of these node.
39. How to store a binary tree in a file so that we can re construct the same tree with that file ..http://www.careercup.com/question?id=12805664
40. Algorithm to check a linked list is palindrome or not, each node contains a single character. http://www.careercup.com/question?id=12804667
41. Find the successor of a node in inorder traversal. http://www.careercup.com/question?id=1280566
42. print all possible combination of given n parentheses. Eg: if n=2 then all possible combinations are: (n stands for number of parentheses pair open-close)
    {}{}
    {{}}   http://www.careercup.com/question?id=12806664
43. Given an array of N integers with +ve & -ve numbers. Find the maxproduct of 3 numbers ? & Test Cases   http://www.careercup.com/question?id=12806693
44. Given an n-by-n matrix of 0′s and 1′s where all 1′s in each row come before all 0′s, find the most efficient way to return the row with the maximum number of 0′s.  http://www.careercup.com/question?id=12849666
45. Write Program to find longest common contiguous intersection from 2 lists provided to the function.
    Example: list1: abcrfghwetf
    list2: abrfghwwetxyab   http://www.careercup.com/question?id=12862670
46. Construct a Cartesian tree from in order traversal  ..http://www.careercup.com/question?id=12715683
47. Find if two rectangles overlap in cartesian space..http://www.careercup.com/question?id=12719693
48. Given an expression tree how do you evaluate it and also how do you evaluate for n-ary operators …http://www.careercup.com/question?id=12714690
49. The root node in the tree is equal to sum of its all descendants and the leafs are assigned value 0, so if your tree is something like 1020 30 40 50
    output will be
    140
    0 90
    0 0    http://www.careercup.com/question?id=12691679
50. Given n points in 2D space find k points nearest to origin..http://www.careercup.com/question?id=12691685
51. Print a binary tree in level by level in Zig-Zag manner …http://www.careercup.com/question?id=12688694
52. Given a binary tree return the new binary of given depth.
    Example:
    0 – 3 — Should return full binary tree from root to height 33 – 4 — Should return full binary tree from height 3 to 4   http://www.careercup.com/question?id=12642713
53. IMP—-Write a method to create new tree with same structure but the values of each node will be sum of their descendents (sub tree). The leaf nodes will become 0. So if the tree is 50 30 10 40 60 55 75 (PreOrder) then new tree should be 270 50 0 0 130 0 0(PreOrder)…http://www.careercup.com/question?id=12746661
54. write a function which takes a string S and a pattern string P and an integer i , and returns the i’th occurrence of P in S.
    example S = “abcabcefgabc ” , P = “abc” , i =3 , ..returns 10 …http://www.careercup.com/question?id=12782664
55. given an array A which has only 0′s and 1′s in sorted order , find the occurrence of first ’1′ in A.
    example : A [] = 00001111 , returns 5    http://www.careercup.com/question?id=12779666
56. Convert a BST to sorted doubly linked list.     http://www.careercup.com/question?id=12778666
57. implement “fill with paint” function which fill the screen(2d array) with respect to a given point and color,fill until border of screen or same color is met.   http://www.careercup.com/question?id=12572675
58. You are given a linked list. Apart from the normal “Next” pointer, there is one more pointer(random ptr) in each node which points to some random node of the list. How will you create a clone of such a list? (In less than O(n^2))   http://www.careercup.com/question?id=12590664
59. Write a function to convert an IPv4 Address in string format to an unsigned integer http://www.careercup.com/question?id=12651670
60. Given a set of unique numbers from 1 to 1000, propose a data structure that allows you to perform the following operations in constant time.
    1- Insertion,
    2- Deletion,
    3- Searching,
    4- Get any random numbe              http://www.careercup.com/question?id=12650665
61. Given a String – aaaabbbbcc, convert the given string in to a4b4c2 without using extra memory. ( Note that every character appears more than once in input string and the repeated characters are contiguous)    http://www.careercup.com/question?id=12663669
62. Search an element in a 3-D sorted array without modifying the given array.   http://www.careercup.com/question?id=12666670
63. Write a program to calculate the number of occurances of letters(chars) in a string. Eg:”Test”.  http://www.careercup.com/question?id=12666683
64. Print nodes at k distance from root..http://www.geeksforgeeks.org/archives/8615
65. Given references to roots of two binary trees, how do you short circuit determine whether the sequences of the leaf elements of both the trees are same ? The structure of two BTs may be different. Short circuit : for ex. If the very first leaf element of each tree is different, the algorithm should stop immediately returning false instead of checking all the leaf elements of both trees.  http://www.careercup.com/question?id=12698674
66. Given two nodes of a BST and all elements in BST are distinct, write code to determine the shortest distance between the two nodes. (unit distance between two adjacent nodes). Nodes dont have parent pointer.http://www.careercup.com/question?id=12696671
67. Given an array, subarray size k and a number ssum, find the number of subarrays of size k that sum up to ssum. http://www.careercup.com/question?id=12697675
68. one unsorted array is given.Find out the index i and j ,j> i for which a[j] – a[i] is maximum.perform in linear time complexity http://www.careercup.com/question?id=12705676
69. Why data members are private when we can access them through getter/setters?. Why can’t we just make them public.[ How will you convince the interviewer] http://www.careercup.com/question?id=12705691
70. Given two linked lists. Find their intersection point.
71. Given a binary search tree of n nodes, find two nodes whose sum is equal to a given number k in O(n) time and constant space ..http://www.careercup.com/question?id=12711674
72. Find the number of nodes in a singly link list, it can be both cyclic and acyclic..http://www.careercup.com/question?id=12631663
73. you have given 2n+1 numbers in which 2n numbers are repeated means every number is having duplicate value.find that non repeating number in constant space and o(n) time.i told him using XOR.
    then he gave me 2n+2 numbers in which 2n numbers are repeating like above now you have 2 different number.find both number in constant space and o(n) time.(f2f 4th round)   http://www.careercup.com/question?id=12570669
74. Write function compress(char* strSource)
    it should do the following .
    repeating chars in sequence should be replaced with char & count, in case count is 1 no need to add any integer.
    Example – AAAABBBCXYZEEEEPPPPPKKABC
    should be A4B3CXYZE4P5K2ABC.
    you are supposed to iterate the array only once, and modify the same input parameter, do not create any new string.   http://www.careercup.com/question?id=12514668
75. You have given two polynomials .. You have to choose a data structure which will be used for addition of both polynomials :-
    Condition :-
    polynomials are very huge ..(n is very big)
    a + bx +cx2 +…… +nxn ..
    c + dx +ex2+…… +nxn ..
    you have to store the polynomial after sum .  http://www.careercup.com/question?id=12514670
76. Get the top 3 frequently used words in a book. The book contents are given as a single text file.
    I used hashmap solution. The interviewer said its not optimal. Use a combination of two or three data struct.   http://www.careercup.com/question?id=12391700
77. You are given a function printKDistanceNodes which takes in a root node of a binary tree, a start node and an integer K. Complete the function to print the value of all the nodes (one-per-line) which are a K distance from the given start node in sorted order. Distance can be upwards or downwards.  http://www.careercup.com/question?id=12527666
78. Given a robot and a Maze in a game. Following our few of the primitives:
    bool IsMazeExit();
    bool Forward();
    void RightTurn();
    Constraints:
    Every room in the maze is a square. Each room has 2 doors. Robot can call IsExitMaze() when in a room and identify the exit. Forward moves the Robot forward few steps and if it finds a wall it returns to its position. Right turn turns the robot right 90 degrees.
    Write a method to find the exit  http://www.careercup.com/question?id=12549691
79. Given numbers 1 to 1000, suggest a data structure to store them such that following operations can be executed in constant time:
    1- insertion,
    2- deletion,
    3- searching,
    4- get_any_number (means return any number if present in the data-structure otherwise return -1).   http://www.careercup.com/question?id=12559669
80. Given a root and a node of a BST tree, write a function which print all the nodes which are a ‘k’ distance from the given nodes in sorted order. (distance can be upwards and downwards) [Hints -Recursion]  http://www.careercup.com/question?id=12533682
81. In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] Write a program to merge them like [a1,b1,c1,a2,b2,c2,...an,bn,cn]. We have to do it in O(1) extra space. [Hints- D&C or swapping]  http://www.careercup.com/question?id=12549702
82. You are given a linked list which has the following structureCode:

    linkedList {
    data
    *nextLink
    *randomLink

    }
    *nextLink will always point to next node in the linked list
    *randomLink will point to any random node node it the list (or NULL)Now given a list L write an algorithm to create replica of the list( say L’) in O(n) time and O(n) space. [Hints- Need Double Pass/Hashing]  http://www.careercup.com/question?id=12549703
83. How to build a heap from inoder traversal ?  http://www.careercup.com/question?id=9735293
84. Given a function getInorderSuccessor which takes a BST (Binary Search Tree) as it’s parameter. Every node has an extra pointer “next” , which is intialized to null, fill next with node pointers which represent Inorder Successor. [Hints -Recursion/Stack/DP]  http://www.careercup.com/question?id=12557684
85. An array contain +ve and -ve element, find the longest contiguous sub array whose sum is 0  http://www.careercup.com/question?id=12533685
86. Given a matrix pxq, You start from top left and have to reach the bottom right. Can only traverse right or bottom. How many ways are there to reach at the bottom right?. So If I allow all 4 way move is possible what will be the ans ? . What happened if i make some Restricted Move ?    http://www.careercup.com/question?id=12549705
87. Given A Binary Tree of size n , Find Out a Matrix M[n][n], where M[i][j]=1 if i is predecessor of j, else M[i][j]=0. [Hints DP]  http://www.careercup.com/question?id=12560677
88. How you implemnt a Priority Queue using Heap.  http://www.careercup.com/question?id=12549706
89. Given a Cache of n String Having length of k each, on Alphabet ALPHA where |ALPHA|=t, Find out number of 2k-length string constructable from the cache, where all sub-string of Resultant sub-string are also in cache ? What Data-structure should you use to Lookup cache? Design an Algorithm to find the count Efficiently? Calculate the Time/Space complexity of the technique. [Hints -Tries ]  http://www.careercup.com/question?id=12549707
90. Given a Cache of k-length Strings of size n,. Given a String X, We can to convert to another String Y using the following two Rules:
    R1:you can change only one character at a Time in stepwise Transformation
    R2: All intermediate String in the transformation must be also in cache.Cache has also an API : Called Is_Transformable(X,Y) return Ture if it is possible to transform X to Y, without violating the Above rule. Assume that Cache is fixed size and there is a sequence of Query of Checking the possibility of Transformation is coming to The API of Cache.
    the Question is : What Data-Structure U can use to implement Cache ? It might need some Initial Complexity to Organize the data , for efficient lookup, and provide service to APIs.
    How can u implement the API in O(1).
    Suppose we add one more API which calculate minimum number of Steps required to transform X to Y, How do u solve this problem in O(1).   http://www.careercup.com/question?id=12533686
91. Suppose, Amazon have a Logging system Like This:They Track all logs daily basis, stored in separate log file.Log contains a collection of tuples of Customer ID and Page ID. The length of Customer ID and Page ID is L1 and L2. Suppose We have a log of D-days , and size of each log fine can be Order of n , where n be the number of customer.
    In a most generalized situation, you can assume that a customer can visit the same page multiple times in a day or any number of days. We are interested to find out the number of Distinct customer visited at-least p distinct pages within exactly T days.
    Propose a Data Structure to be use to solve this problem efficiently . Design an Algorithm to solve this problem and Find out the complexity of the algorithm.
    {Hints:- Double Hashing/ {Hashing +Tries/BST }}  http://www.careercup.com/question?id=12560678
92. Find the character that has maximum frequency in an array of characters. If n is small and dealing with unicode char-space, extra space for hashtable is overhead, can you avoid?  http://www.careercup.com/question?id=12336749
93. placed two robots and a sensor on the line, write code that will be executed on both machines and make them meet. http://www.careercup.com/question?id=12337726
94. String represented as as singly Linked list with one letter on each Node. Need to check whether it is a paliandrome or not. Can use only one String variable other than the Linkedlist  http://www.careercup.com/question?id=12364061
95. Given the number, find the immediate next (larger) palindrome   http://www.careercup.com/question?id=12382912
96. Find the nth non-repeating number given a streams of characters in the range of A-Z  ..http://www.careercup.com/question?id=12381892
97. What is the complexity of an algorithm to check whether a binary tree is symetric or not. No need to check the data only the structure needs to be verified.  http://www.careercup.com/question?id=12374673
98. Given an array (length n), we need to find the subarray (length k) such that the sum of the first j elements of the subarray equals the sum of the remaining (k-j) elements of the subarray.
    For e.g.
    Array: 2,2,13,4,7,3,8,12,9,1,5
    Output: 4,7,3,8,12,9,1 [4+7+3+8=12+9+1]
    Could this be done with a complexity better than O(n^3)   http://www.careercup.com/question?id=12351270
99. given a linked list of objects.Print the objects in reverse order. I gave a recursive solution as well the normal one.
    But he wanted a solution where no recursion is used and no manipulation of any pointers in linked list.
    You can use any algorithm…any space and any time complexity…but remember linked list is dynamic.
    Could not answer this q     http://www.careercup.com/question?id=12381347
100. compare two strings arrays and return intersection elements in a string array without using 2 for loops?  http://www.careercup.com/question?id=12402663
101. GIven a binary tree, print the tree according to the level.
     eg
     01
     0203
     04050607
     0809101112131415
     proceed further to find the mirror image of alternate level
     01
     0203
     07060504
     0809101112131415    http://www.careercup.com/question?id=12419665
102. given a million integers find the largest k elements  http://www.careercup.com/question?id=12347483
103. find common ancestor of 2 nodes in
     1. binary tree
     2. binary search tree No parent pointer is given.   http://www.careercup.com/question?id=12374681
104. Given number n, return true if n is prime otherwise false.    http://www.careercup.com/question?id=12342686
105. write a function strRemove(char *source, char *remove )
     This function will delete all the chars that exist in string remove from array source, number of iteration should be only 1. Make the searching efficient.
     Example
     (“amazon development center”, “aenr”)
     “mzo dvlpmt ct”.
     Criteria – First parameter should be modified , no need to create an extra string.
     (Answer – Put the second array in a hash table, like array of 256 chars, to search which are the chars needed to be removed with complexity o(1) )   http://www.careercup.com/question?id=12518669
106. you have two BST , they contain the same amount of elements “N” but there structure is different. how will you cross check that the trees are identical with complexity O(N). Also how will you do the same in case its only Binary tree and not a Binary search tree.  http://www.careercup.com/question?id=12520661
107. Write code to traverse a binary tree and save all the elements found in a sorted order in double link list.  http://www.careercup.com/question?id=12514667
108. You have a table which contains huge data may be crores of records and a cache which can contain only 1000 records. Query is done on the basis of some unique ID. When any query happens data should be copied to the cache, but the records which are used least amount of time should be removed and should be occupied with newly added records from table.
     Cache should provide two mechanism , search for record(s) on the basis of a unique id & remove the records which used least amount of time. Cache can contain max 1000 records, and record should be available in cache even after your query is done. So records in cache is refreshed only when new query is done and new record arrives which do not exist in the cache.   http://www.careercup.com/question?id=12449679
109. You are given a paragraph , which contain n number of words, you are given m threads. What you need to do is , each thread should print one word and give the control to next thread … this way each thread will keep on printing one word , in case last thread come, it iwill invoke the first thread … procedure will repeat until all the words are printed in paragraph. Finally all the thread should exit gracefully. What kind of synchronization will use ? Answer only the logic to implement (not complete code)  http://www.careercup.com/question?id=12419684
110. you have 100 elements from 1 to 100 but my mistake one of those number overlapped another by repeating itself.
     Ex. in 1—-98,99,100 …. 99 overwrite 2 , so the array becomes … 1,99,3,4,—-99,100 .. Array is not in sorted format , how to find the repeating number ?  http://www.careercup.com/question?id=12515668
111. Right a program which will perform the following task ->
     In a binary tree , if a root is greater then the sum of two child nodes , then the new value of same root will be sum of child nodes , else the right // left child should reinit to such a value, so that the sum of the child nodes will be equal to the value of root node.
     (I asked him the answer , he told u need to do manipulation twice, 1) while parsing the nodes 2)while unwinding i.e. again recheck the values.   http://www.careercup.com/question?id=12426712
112. how would you design a rate limiter in a client to control the number of transactions it requests the server.  http://www.careercup.com/question?id=12322728
113. How do you check if an entered text in a textbox is a student email address (ends with edu). special case xyz@alumni.univ.edu should be rejected  http://www.careercup.com/question?id=12503676
114. Write code for the following problem:
     find the element in the array that appears consecutively in the array max number of times. Should be O(N)
     eg. 1113333244111 ans. 3  http://www.careercup.com/question?id=12375726
115. Given pre order traversal of a tree. It has only 2 type of nodes, N & L (non-leaf, leaf).. Also, every node either has zero or two children.
     Produce the tree. Eg: Pre-order NNLLL
     Tree;
     N
     / \
     N L
     / \
     L L  http://www.careercup.com/question?id=12477676
116. You have the post order traversal of a tree. produce the tree.
     Possible?
     If not, what other info you need?
     Ok you have that info, now produce the tree.
     Write code  http://www.careercup.com/question?id=12493668
117. Given a Singly Linked lists, write the function that takes as arguments the head of list and a number and then deletes all the nodes with that number.   http://www.careercup.com/question?id=12480668
118. Given a binary search tree, first find the least common ancestor of two numbers and then generalize it for m numbers.   http://www.careercup.com/question?id=12480667
119. Given a dynamic stream of integral numbers, write a function that returns its median. The numbers may arrive in bursts at any time   http://www.careercup.com/question?id=12343736
120. There are two integer arrays ,each in very large files (size of each is larger than RAM). How would you find the common elements in the arrays in linear time.  http://www.careercup.com/question?id=12469661
121. For an array of integers, find if there are 3 numbers that add up to zero. An algorithm of complexity O(n^2) was required.  http://www.careercup.com/question?id=12468661
122. How do you partition an array into 2 parts such that the two parts have equal average? Each partition may contain elements that are non-contiguous in the array..  http://www.careercup.com/question?id=1244666
123. Till Page 7 So far in careercup..Target—till page 20

Read More