## Directi Interview Question for SDE1s

• 1
of 1 vote

Country: India

Comment hidden because of low score. Click to expand.
3
of 3 vote

instead of posting just code it would have been better if you write the DS / algo / logic in plain english

Comment hidden because of low score. Click to expand.
2

I really don't know why people think that code is more important than logic. Write the damn logic as no one is going to go through your damn code.

Comment hidden because of low score. Click to expand.
2
of 2 vote

O(2 * k) per character where k is the size of your stream's horizon (e.g. 10 here). I used k = 3 for demonstration purposes; change k's assignment to whatever you need otherwise.

To those demanding logic:

1) This build a prefix tree; each k-character instance encountered is added to the tree (if not already contained within it).

2) Adding to a prefix tree is linear in the length of the insertion (e.g. k).

3) Seeing if the string is contained in the tree is linear in the length of the String being checked (e.g. k).

``````import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Main{

static public void main(String[] args){
//I set k to 3, but you can easily up it to 10 if you want the full solution.
//It's easier to produce verifiable test cases for k = 3.

int k = 3;
Set<String> testStreams = new HashSet<String>();

for(String testStream : testStreams){
analyzeStream(testStream, k);
}
}

private static void analyzeStream(String stream, int k){
System.out.println("Analyzing stream: " + stream);
Node root = new Node(true);
for(int i = 0; i < stream.length() - k + 1; i++){
String substr = stream.substring(i, i + k);
if(root.contains(substr)){
System.out.println(substr + " found in stream.");
}
}
System.out.println();
}

private static class Node{
Map<Character, Node> children;
boolean root;

public Node(){
this(false);
}

public Node(boolean root){
this.root = root;
this.children = new HashMap<Character, Node>();
}

public boolean contains(String str){
//This tree is uniform height; 0 children => depth = 10
if(children.size() == 0 && !root){
return true;
}
Node child = children.get(str.charAt(0));
return child == null ? false : child.contains(str.substring(1));
}

Node cur = children.get(in.charAt(0));
if(cur == null){
cur = new Node();
children.put(in.charAt(0), cur);
}
if(in.length() > 1){
}
}
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class RepeatedSequenceFinder
{

public static void main(String[] args) throws IOException
{
String sequence = "abcdefghijklmabcdefghijklm";
int sequenceLength = 10;
}

{
List<Node> forming = new ArrayList<Node>();
List<Node> tracing = new ArrayList<Node>();

Map<Character, Node> parsed = new HashMap<Character, Node>();
{
List<Node> newForming = new ArrayList<Node>();

for(Node node : forming)
{
Node newNode = new Node(c, node.depth+1, node);
node.children.put(c, newNode);
if(newNode.depth!=sequenceLength)
{
}
}

forming = newForming;

List<Node> newTracing = new ArrayList<Node>();

for(Node node : tracing)
{
if(node.children.containsKey(c))
{
Node newNode = node.children.get(c);
if(newNode.depth==sequenceLength)
{
printSequence(newNode);
System.out.println();
}
else
{
}
}
else
{
Node newNode = new Node(c, node.depth+1, node);
node.children.put(c, newNode);
if(newNode.depth!=sequenceLength)
{
}
}
}

tracing = newTracing;

if(parsed.containsKey(c))
{
}
else
{
Node newNode = new Node(c, 1, null);
parsed.put(c, newNode);
}
}
}

private void printSequence(Node newNode)
{
if(newNode==null)
{
return;
}
printSequence(newNode.parent);
System.out.print(newNode.character);
}
}

class Node
{

public char character;

int depth;

Map<Character, Node> children = new HashMap<Character, Node>();

Node parent;

public Node(char character, int depth, Node parent)
{
this.character = character;
this.depth = depth;
this.parent = parent;
}
}

Comment hidden because of low score. Click to expand.
0

Just Posting it with formatting

``````import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class RepeatedSequenceFinder
{

public static void main(String[] args) throws IOException
{
String sequence = "abcdefghijklmabcdefghijklm";
int sequenceLength = 10;
}

{
List<Node> forming = new ArrayList<Node>();
List<Node> tracing = new ArrayList<Node>();

Map<Character, Node> parsed = new HashMap<Character, Node>();
{
List<Node> newForming = new ArrayList<Node>();

for(Node node : forming)
{
Node newNode = new Node(c, node.depth+1, node);
node.children.put(c, newNode);
if(newNode.depth!=sequenceLength)
{
}
}

forming = newForming;

List<Node> newTracing = new ArrayList<Node>();

for(Node node : tracing)
{
if(node.children.containsKey(c))
{
Node newNode = node.children.get(c);
if(newNode.depth==sequenceLength)
{
printSequence(newNode);
System.out.println();
}
else
{
}
}
else
{
Node newNode = new Node(c, node.depth+1, node);
node.children.put(c, newNode);
if(newNode.depth!=sequenceLength)
{
}
}
}

tracing = newTracing;

if(parsed.containsKey(c))
{
}
else
{
Node newNode = new Node(c, 1, null);
parsed.put(c, newNode);
}
}
}

private void printSequence(Node newNode)
{
if(newNode==null)
{
return;
}
printSequence(newNode.parent);
System.out.print(newNode.character);
}
}

class Node
{

public char	character;

int depth;

Map<Character, Node> children = new HashMap<Character, Node>();

Node parent;

public Node(char character, int depth, Node parent)
{
this.character = character;
this.depth = depth;
this.parent = parent;
}``````

}

Comment hidden because of low score. Click to expand.
0

instead of posting just code it would have been better if you write the DS / algo / logic in plain english

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.