Saturday, May 14, 2016

INTERVIEW - data structure problems that are hard to solve (answer from quora.com)

Links to interview questions or any practice problems.
17 Answers


Sai Teja Pratap
Sai Teja PratapTrying to master
36.7k Views
Less Time for preparation
If you just want to know the questions and answers for interview questions, the following are some good places to visit. These will be useful in a situation where there is not much time for preparation. 

  1. MyCareerStack 
    A sub domain of Hackerearth . The website looks clean and seems to have fairly good community.
  2. www.geeksforgeeks.org
  3. Stack overflow questions tagged with algorithms.
    http://stackoverflow.com/questio...
  4. www.careercup.com
    Read only the questions.People post shitty brute-force solutions in the comments. It would be a total waste of time to read the answers in the comments.
  5. http://www.dsalgo.com/
  6. Others

More than 2 months for preparation
If you have lot of time for the interview it is better to improve your coding skills, Here are a few  useful sites for practicing algorithmic programming.
  1. HackerRank (previously www.interviewstreet.com )
    • No-so-easy questions, most of them are challenging.
    • Solving one question requires multiple concepts.
    • Companies come for hiring via codesprints in interviewstreet
  2. Sphere Online Judge (SPOJ)
    • Use www.problemclassifier.appspot.com to search for problems of a concept and then solve the questions
    • Contains more than 10K questions
    • has questions of all levels.
  3. Codechef
    • Contains questions of all levels.
    • There will be monthly contests.
  4. http://algomuse.appspot.com/archive
    • They conduct non-programming contests once a while (may be around 3 months)
    • Moderate and difficult questions.
  5. http://community.topcoder.com/tc
    • Very good community.
    • High quality tutorials.
    • There will around 2 contests per month.
    • Contains questions of all levels(archives).
  6. http://www.codeforces.com 
    (similar to topcoder)
  7. projecteuler.net
    • Contains many easy questions in the beginning. But the questions after the 200th are challenging.
    • One can start with this (questions numbered <100) and move on to other sites once he/she gets confidence.

Feel free to suggest edits



Arun Prakash
Arun PrakashCS Grad Student
10.7k Views
1.Geeks for Geeks

This is one of the best computer science portal for geeks, mainly focus on Data structures and Algorithms. Analysis of algorithms,Searching and Sorting, Greedy Algorithms, Dynamic programming, Pattern searching, Backtracking, Divide and Conquer and Bit algorithms are explained clearly.

2.Top Coder

Top coder is one of the coding contest site mainly focus on algorithmic questions. Here is the good collection of algorithmic topics by various topcoder members.

3. OpenclassRoom- Stanford University 

Here is the collection of video tutorials by Prof.  Tim Roughgarden from Stanford univ. Topics discussed here are Introduction to fundamental techniques for designing and analyzing algorithms, including asymptotic analysis; divide-and-conquer algorithms and recurrences; greedy algorithms; data structures; dynamic programming; graph algorithms; and randomized algorithms

4. Introduction to Algorithms – Massachusetts Institute of Technology

Here is the collection of lecture slides,code on various algorithmic topics by Massachusetts institute of technology

5. Stanford CS Education Library

This online library collects education CS material from Stanford courses and distributes them for free.

Here are few more sites that might help you to learn data structures and algorithms:

1. CSE 214 - Lecture Notes
2.http://courses.csail.mit.edu/6.8...
3. CS 61B: Data Structures
4.https://www.coursera.org/course/...
5. Coursera
6. Algorithm Interview Questions
7.http://www.careercup.com/page?pi...
LeetCode
Newest 'data-structures' Questions - Stack Overflow
10. Newest 'algorithm' Questions - Stack Overflow
11 Introduction to Algorithms Course Online
12 Manish Kumar: September 2013

Quora questions:
1. What are some good resources for learning about data structures?
2. Data Structures: What is the best resource  to learn Data structure and algorithm (must contain practice assignments too)?
3  What are some of the best resources for learning advanced data structures like segment trees and binary indexed trees (Fenwick trees)?

Facebook group : https://www.facebook.com/groups/...


Yoshiya Miyata
Yoshiya MiyataLove solving algorithmic problems
44.4k Views
There are couple of websites that post interview questions along with its solutions:

http://www.leetcode.com
http://xorswap.com/

There are also websites that host algorithm problems used for programming competitions. These problems are not actual interview question but excellent problems to practice solving algorithm problems:

Peking University Online Judge:
http://poj.org/
Google Code Jam:
http://code.google.com/codejam/c...
TopCoder (Registration required to view the problems):
http://community.topcoder.com/tc...

The websites listed above are the ones I have used before, but there are a lot more websites that host programming competitions and most of them have archive of problems used on their previous matches. I will list some of them below but I cannot guarantee of their quality (since I have never used them):

Sphere Online Judge:
http://www.spoj.pl/problems/clas...
Codeforces:
http://codeforces.com/problemset


Cosmin Negruseri
Cosmin Negruseriproblem setter in Google Code Jam, trainer for the Romanian IOI team
16.4k Views • Cosmin has 60+ answers and 4 endorsements in Algorithms
This is a good set http://everything2.com/title/har...

And a few I like:

1) You are given a read only array of n integers from 1 to n. Each integer appears exactly once except A which appears twice and B which is missing. Find A and B using less than O(n) space in O(n) time.

A read-only array of length n, with address from 1 to n inclusive,

contains entries from the set {1, 2, ..., n-1}.
By Dirichlet's Pigeon-Hole Principle there are one or more duplicated
entries. Find a linear-time algorithm that prints a duplicated value,
using only "constant extra space". (This space restriction is important;
we have only a fixed number of usable read/write
memory locations, each capable of storing an integer between 1 and n.
The number of such locations is constant, independent of n.
The original array entries can not be altered.) The algorithm should
be easily implementable in any standard programming language.

via http://domino.research.ibm.com/C...

3) Given a stream of n integers between 1 and n find one number that repeats in linear time using less then O(n) space and traversing the stream sequentially O(1) times.

4) What's the hardest puzzle question asked at PayPal?

5) Given a tree where nodes have integer labels, find a path that goes down in the tree such that the sum of labels equals S. O(n) algorithm. source: Cracking the Coding Interview ( http://www.amazon.com/dp/098478280X ).

6) You're given a read only array of n integers. Find out if any integer occurs more then n/3 times in the array in linear time and constant additional space.

7) Do a stable merge of two arrays in place faster than O(n^2).

8) Build a sparse set datastructure that takes O(m) space to keep m integers in the range 1 .. n such that add-member(i) and is-member(i) take O(1) time. sourcehttp://research.swtch.com/sparse

9) http://gurmeet.net/puzzles/firin...

10) Test if two trees are isomorphic.

No comments: